算法：12306的余票算法。

一时失言乱红尘 2023-02-20 08:18 16阅读 0赞

我看过网上称某宝工程师写的12306文章，觉得狗屁不通。他们将每个站点独立成一件商品，每次购、退票都需要查询删改库存，造成巨大的数据库操作开销。其实这是个简单到不能再简单的算法。我以8个站点的班次举例，票面现值pm每位代表一个站点，客户乘坐需求gp也一样每位代表他需要乘坐的站点：

票面现值（初始值）pm=（00000000），客户购票需求=gp（01111111），（01110000），（00001111），（01101100），（00110110）。。。等等等

（这里需要注意的是gp赋值的原则，始发站（或任意上游站）该位都为0，这样就能衔接上该位为1的下车乘客。例如，乘坐一站就是01，两站011。。。前边的0代表你在第几个站始发，1代表你要乘坐经达的下游站，例如第二站上车001，第三站0001。。。乘类推）

算法原则：用二进制同位加法，原则为同位加不能产生溢出（不能产生进位，否则为错误）。

第一步：pm&gp=0 （and运算，根据位运算法则结果为0则不溢出）。

第二步：余票现值pm=pm|gp （由于有pm&gp=0屏蔽，这步直接or即可写入pm值，这步即为二进制同位加法）

第二步的结果：票面现值pm=01111111,01110000,00001111,01101100，00110110

pm值（后七位）带有0的票恒为余票

再有新客户购票时，pm（后七位）带有0的继续做算法。

例如有一个客户他的购买需求gp=01111111，与余票值pm运算，他将无法购买那些pm（后七位）值任意一位带有1的余票，因为算法不准溢出（pm&gp必须=0才能购买）。

这样一列火车2000个座位或者3000个座位，或者更多都没有问题。所有票面值（后七位）或初始值带有0的组成pm()数组，数组长度10万以下都是简单运算而已，一下就能匹配完成。

退票：退票时pm直接减去该客户需求即可立即得出余票现值。（即：pm=pm^gp，二进制xor运算）

查询优化：所有余票全部做同位and运算则立即得出查询伪码wm，查询伪码任意一位为1则表示全部余票在该站点余票面值为1。这样一条伪码可以完成先导查询wm&gp=0，结果不为0的查询将无法进入pm()内进一步操作。大大降低了系统负担（例如pm()长度为2000，理想情况下查询压力下降2000倍）。

以8个站点的班列为例。以票为单位存储，数据库的记录长度，将比以站点为单位的数据库，下降8倍，读写操作也将分别下降n倍。

某宝的工程师算法逻辑是直接操作库的逻辑，那么将数据库映射成为bmp处理，但这又带来新的问题，比如锁定机制，数据同步机制，写入仲裁机制，这些在本算法中由天然的cpu硬件机制来实施。与硬件有一致性，机制成熟算法健壮性有保证。如果人为的另立机制想拓展bmp算法的性能会导致很多问题，

比如你买一个站点，只想改写bmp中的1bit，但是硬件机制是写8bit一次。那么后七位一样要锁定（不然会发生后七位有退票的线程改写了那些商品位，而本线程又因硬件机制复原了内容的现象发生）。要使写冲突保护与硬件高度一致，那就只能化为变量来处理。那本算法已经是最优解。因为本算法也将数据库映射成为bmp，但算法逻辑并不是直接操作库的逻辑而是数组变量，确定性发生完后再更新入库。

将每站点全部商品位化，是为了营造高并发的假象而已，白白浪费了计算资源。以每趟车2000张票为例子。由于每张票的独立性，pm()在一开始能最大维持2000个线程写入的锁定，但是会迅速下降，因为随着购票确定性的发生，pm()是越来越短的。现代处理器16核能在本端维持32线程，看起来似乎并发少，但是本端处理能将各类延迟最小化，各种机制效率最大化，况且处理一个2000长度且越来越短的位运算数组，算力已经远远超过需求，来1000个数组都没问题，按需分布服务器即可。比起集群带来的2000线程假象更有效益。集群应该用在那些“胸大无脑”的响应上，而不是来处理核心任务。