论文部分内容阅读
摘 要：随着电子商务的爆炸式发展，使得现实应用越来越体现出大数据、高并发。但使用者对系统实时响应的要求却没有降低。这就要求系统应用要向分布式、云技术化发展，随之而来的就是业务为适应分布式而做的改变，算法也要适应性变化。
关键词：大数据、算法、位图
解决大数据并发业务，现在通常采用分布式系统，就是将业务尽可能的平均分配到多台服务器处理。业务处理时尽量减少服务器间的交互，在一个服务器内部也要尽量减少数据的关联性、耦合性。这实际提出了一个关键性要求：分布式业务算法必须不同于传统的解决办法。
这里我们假定要开发一个开源的订票系统，业务只是简单模拟12306的部分订票功能，来说明分布式业务算法的不同。对比一个常见的电子商务网站，12306的库存复杂性要高很多倍，运算量也大很多倍。传统的分布式数据库、缓存、负载均衡技术并不能恰好满足12306的需求。
在平时，12306也就是个正常的电商网站。但一到特殊节日，12306就是一个全站所有商品都秒杀，所有SKU都是动态库存的变态。本文重点针对订票算法的讨论，所以不会涉及动画验证码、分时段抢票，后端去小型机、虚拟化、内存数据库等运用。
一、首先，解释一下，为什么采用普通设计方法库存秒杀压力大，以及为什么12306的动态库存很复杂。
以北京西到深圳北的G71次高铁为例，它有17个站。我从中选取16个站进行演绎，只是为了方便进行位图演示。因为我打算用 unsigned short 对应这16站，unsigned short刚好2字节16位。实际应用可以选择 unsigned int、unsigned long，甚至是long long。它还有3种座位（商务、一等、二等）。所以G71有120*3=360种商品。
如果卖北京西始发的，有15种卖法，北京西到：保定、石家庄、郑州、武汉、长沙、广州、虎门、深圳……都是一个独立的商品。同理，石家庄上车的，有14种下车的可能，以此类推，单以上下车的站来计算，有120种票：15+14+…+2+1=120。每种票都有3种座位，一共是360个商品。
再看出票时怎么减库存，由于商务、一等、二等三种座位数是独立的，库存操作也是一样的，下文我就不再提座位的差别的，只讨论出发与到达站。另外，下文说的是理论世界的模型，不是说12306的数据库就是这么设计的。
旅客A买了一张北京西（01号站）到保定东（02号站）的，那【北京西到保定东】这个商品的库存就要减一，同时，北京西到石家庄、郑州、武汉、长沙、广州、虎门、深圳等14个站台的商品库存也要减一，也就是说，出一张北京到保定东的票，实际上要减14个商品的库存！
这还不是最复杂的，如果旅客B买了一张北京西（01号站）到深圳北（16号站）的票，除了【北京西到深圳北】这个商品的库存要减一，北京西到保定东、石家庄、郑州、武汉、长沙、广州、虎门等14个站台的商品库存也要减1，保定东到石家庄、郑州、武汉、长沙、广州、虎门、深圳北等13个站台的商品库存要减1……总计要减库存的商品数是15+14+……+1=120个。
当然，也不是每一张票都的库存都完全这样实时计算，可以根据往年的运营情况，在黄金周这样的高峰时段，预先对票做一些分配，比如北京到武汉的长途多一点，保定到石家庄的短途少一点。我没有证据证实铁道部这样做了，但我相信，在还没有12306网站的时候，铁道部就有这种人工预分配的策略了。
以上讨论不考虑它后面的票池，还有电话售票、火车站售票、代售点售票等多个传统渠道要服务。
小结：车票这个东西具有极强的关联性。一张车票不像淘宝亚马逊这种卖商品的，商品具有相对独立性，车票的话，每卖一张就要更新遍历整个数据库相关其他车票数量。
由此可见，这种传统电子商务的商品设计方法，操作表、记录数太多，效率极差。新算法就是要避免这些关联性。同时尽可能的满足大并发对分布式的要求。
二、下面提出一个新的数据结构和算法。核心思想就是引入一个简单的位图bit-dmp，用来描述一个座位的全景状态，同时和16个车站建立关联。
首先将全线16个车站，用16个二进制数描述，取值必须符合特定规则，不同位的取值将和bit-dmp对应。
每一个座位都有自己的位图bit-dmp，位图中的每一位代表一站也可以说有自己的全景状态。bit-dmp和车站的对应关系如下：
采用这种方式后，车票出票数/剩余数（商品）的库存如下：
三、模拟一下业务流程
假设G71列车是从C→A→B→D，还有G79是从E→A→F→B→G……，我要订从A→B的车票，不管是什么车次，怎么操作？其中A=郑州东，B=武汉。
第一步：查从A到B的有那些车。同时生成从A到B的bit-dmp。这个bit-dmp包含了我订票的信息。简单说，针对G71列车，郑州东的位图编码是0000 1000 0000 0000，武汉的位图编码是0000 0001 0000 0000，则从郑州到武汉的位图编码v=0000 1111 0000 0000。实际使用中采用16进制。G79列车的逻辑相同。
第二步：查询每列车有空余座位数，不考虑商务、一等、二等区别。t_seat_reservation保存了G71列车所有座位的库存信息，并且按不同全景信息进行了分类。比如，座位bit-dmp值s=1111 0000 0000 0000的座位表示：北京西-邯郸东已卖出，邯郸东-深圳北尚处空闲。判断座位符合要求的逻辑是（s&v）%2==0，也就是（座位bit-dmp & 郑州到武汉的bit-dmp）%2==0。
第三步：买票。t_seat_dmp保存G71所有座位的全景信息。先不考虑率哪种座位被优先出售。假定seq=2，1车2号的座位被选中出售，s0表示座位当前bit-dmp，s1表示买票后bit-dmp。
买票操作就是：s1=s0|v ，操作t_set_dmp 中1条记录。s0库存-1，s1库存+1，操作t_seat_reservation 中2条记录。整个买票操作只涉及3条记录，不是120 条（采用传统方式）。可以大幅降低锁的可能性，提高处理效率。
总结：大数据并发业务的算法，必须根据实际业务特性定制。否则事倍功半。
参考文献
[1]人大经济论坛，传统分析与大数据分析的对比[DB/OL]. （2012） http：//bbs.pinggu.org/forum.php？mod=viewthread&tid=2140833&page=1
[2]CT论坛. 华为SmartVision大数据解决方案[Z]. 2012 http：//ec.ctiforum.com
关键词：大数据、算法、位图
解决大数据并发业务，现在通常采用分布式系统，就是将业务尽可能的平均分配到多台服务器处理。业务处理时尽量减少服务器间的交互，在一个服务器内部也要尽量减少数据的关联性、耦合性。这实际提出了一个关键性要求：分布式业务算法必须不同于传统的解决办法。
这里我们假定要开发一个开源的订票系统，业务只是简单模拟12306的部分订票功能，来说明分布式业务算法的不同。对比一个常见的电子商务网站，12306的库存复杂性要高很多倍，运算量也大很多倍。传统的分布式数据库、缓存、负载均衡技术并不能恰好满足12306的需求。
在平时，12306也就是个正常的电商网站。但一到特殊节日，12306就是一个全站所有商品都秒杀，所有SKU都是动态库存的变态。本文重点针对订票算法的讨论，所以不会涉及动画验证码、分时段抢票，后端去小型机、虚拟化、内存数据库等运用。
一、首先，解释一下，为什么采用普通设计方法库存秒杀压力大，以及为什么12306的动态库存很复杂。
以北京西到深圳北的G71次高铁为例，它有17个站。我从中选取16个站进行演绎，只是为了方便进行位图演示。因为我打算用 unsigned short 对应这16站，unsigned short刚好2字节16位。实际应用可以选择 unsigned int、unsigned long，甚至是long long。它还有3种座位（商务、一等、二等）。所以G71有120*3=360种商品。
如果卖北京西始发的，有15种卖法，北京西到：保定、石家庄、郑州、武汉、长沙、广州、虎门、深圳……都是一个独立的商品。同理，石家庄上车的，有14种下车的可能，以此类推，单以上下车的站来计算，有120种票：15+14+…+2+1=120。每种票都有3种座位，一共是360个商品。
再看出票时怎么减库存，由于商务、一等、二等三种座位数是独立的，库存操作也是一样的，下文我就不再提座位的差别的，只讨论出发与到达站。另外，下文说的是理论世界的模型，不是说12306的数据库就是这么设计的。
旅客A买了一张北京西（01号站）到保定东（02号站）的，那【北京西到保定东】这个商品的库存就要减一，同时，北京西到石家庄、郑州、武汉、长沙、广州、虎门、深圳等14个站台的商品库存也要减一，也就是说，出一张北京到保定东的票，实际上要减14个商品的库存！
这还不是最复杂的，如果旅客B买了一张北京西（01号站）到深圳北（16号站）的票，除了【北京西到深圳北】这个商品的库存要减一，北京西到保定东、石家庄、郑州、武汉、长沙、广州、虎门等14个站台的商品库存也要减1，保定东到石家庄、郑州、武汉、长沙、广州、虎门、深圳北等13个站台的商品库存要减1……总计要减库存的商品数是15+14+……+1=120个。
当然，也不是每一张票都的库存都完全这样实时计算，可以根据往年的运营情况，在黄金周这样的高峰时段，预先对票做一些分配，比如北京到武汉的长途多一点，保定到石家庄的短途少一点。我没有证据证实铁道部这样做了，但我相信，在还没有12306网站的时候，铁道部就有这种人工预分配的策略了。
以上讨论不考虑它后面的票池，还有电话售票、火车站售票、代售点售票等多个传统渠道要服务。
小结：车票这个东西具有极强的关联性。一张车票不像淘宝亚马逊这种卖商品的，商品具有相对独立性，车票的话，每卖一张就要更新遍历整个数据库相关其他车票数量。
由此可见，这种传统电子商务的商品设计方法，操作表、记录数太多，效率极差。新算法就是要避免这些关联性。同时尽可能的满足大并发对分布式的要求。
二、下面提出一个新的数据结构和算法。核心思想就是引入一个简单的位图bit-dmp，用来描述一个座位的全景状态，同时和16个车站建立关联。
首先将全线16个车站，用16个二进制数描述，取值必须符合特定规则，不同位的取值将和bit-dmp对应。
每一个座位都有自己的位图bit-dmp，位图中的每一位代表一站也可以说有自己的全景状态。bit-dmp和车站的对应关系如下：
采用这种方式后，车票出票数/剩余数（商品）的库存如下：
三、模拟一下业务流程
假设G71列车是从C→A→B→D，还有G79是从E→A→F→B→G……，我要订从A→B的车票，不管是什么车次，怎么操作？其中A=郑州东，B=武汉。
第一步：查从A到B的有那些车。同时生成从A到B的bit-dmp。这个bit-dmp包含了我订票的信息。简单说，针对G71列车，郑州东的位图编码是0000 1000 0000 0000，武汉的位图编码是0000 0001 0000 0000，则从郑州到武汉的位图编码v=0000 1111 0000 0000。实际使用中采用16进制。G79列车的逻辑相同。
第二步：查询每列车有空余座位数，不考虑商务、一等、二等区别。t_seat_reservation保存了G71列车所有座位的库存信息，并且按不同全景信息进行了分类。比如，座位bit-dmp值s=1111 0000 0000 0000的座位表示：北京西-邯郸东已卖出，邯郸东-深圳北尚处空闲。判断座位符合要求的逻辑是（s&v）%2==0，也就是（座位bit-dmp & 郑州到武汉的bit-dmp）%2==0。
第三步：买票。t_seat_dmp保存G71所有座位的全景信息。先不考虑率哪种座位被优先出售。假定seq=2，1车2号的座位被选中出售，s0表示座位当前bit-dmp，s1表示买票后bit-dmp。
买票操作就是：s1=s0|v ，操作t_set_dmp 中1条记录。s0库存-1，s1库存+1，操作t_seat_reservation 中2条记录。整个买票操作只涉及3条记录，不是120 条（采用传统方式）。可以大幅降低锁的可能性，提高处理效率。
总结：大数据并发业务的算法，必须根据实际业务特性定制。否则事倍功半。
参考文献
[1]人大经济论坛，传统分析与大数据分析的对比[DB/OL]. （2012） http：//bbs.pinggu.org/forum.php？mod=viewthread&tid=2140833&page=1
[2]CT论坛. 华为SmartVision大数据解决方案[Z]. 2012 http：//ec.ctiforum.com