先前讀過有人分析 12306 後台設計的文章,其中一個觀點讓我印象很深:火車票的銷售邏輯,和一般電商的下單完全不是一回事。
最麻煩的地方在於,一張票並不是不可分割的整體。以北京到上海為例,沿途停靠許多站,旅客可以買北京到濟南、濟南到南京、徐州到南京……種種區段。也就是說,同一個座位在不同區段上可以重複賣給不同的人。想用「庫存數量加一減一」這種最直白的做法,是行不通的。
網路上看過一個相當漂亮的思路:把一張票表示成一段二進位字串,每一位對應一個行車區段。假如北京到上海一共 10 站,那麼這張票的初始狀態就是:
'1111111111'
1 代表該區段還可賣,0 代表已被佔用。接著看幾個操作:
'0000000000'。'0011111111'。'0011100011'。退票時,從票池裡找出第一張「沒辦法賣出這個區段」的票,把它還原回去就好。例如要退徐州到南京,找到上面那張 '0011100011',退票後它又變回 '0011111111'。買票用的是 AND,退票用的是 OR,兩者互為反操作。
12306 面臨的是多入口並行、資料必須強一致的環境,查票、買票、退票都得有極致的效率。據說高峰期每秒有二十萬量級的請求,因此票的資料結構是放在記憶體中運算的,而不是每次都回到資料庫。在這種前提下,一個小而精悍的資料結構就顯得格外關鍵——位元運算正好符合這個要求。
function Server(){
var self = this;
self.ticketsPool = [];
self._init = function(number){
if(typeof(number) != 'number')
throw ('type error');
for(i=0; i<number; i++){
self.ticketsPool.push(new Ticket());
}
};
// 判斷一張票是否可以賣出,透過位元運算完成。
// 訂單 o 為北京-濟南(0011111111),某張票為(0000000011)(已賣出北京-南京),回傳 false
// 訂單 o 為北京-濟南(0011111111),某張票為(1111100011)(已賣出徐州-南京),回傳 true
self.canBuy = function(o, t){
var _o = '';
for(j=0; j<o.length; j++){
_o += o[j]=='0' ? 1 : 0;
}
var r1 = (parseInt(t.tic,2) | parseInt(o,2)) & parseInt(_o,2);
var r2 = parseInt(_o,2);
return r1 == r2;
};
// 賣出一張票
self.pop1Ticket = function(o){
for(i=0; i < self.ticketsPool.length; i++){
if(self.canBuy(o, self.ticketsPool[i])){
self.buy(self.ticketsPool[i], o);
return i;
}
};
return -1;
};
// 賣出票的實作:以 AND 改寫位元字串,例如 '1111111111' -> '0011111111'
self.buy = function(t, o){
t.tic = (parseInt(t.tic,2) & parseInt(o,2)).toString(2);
};
// 查詢餘票
self.remainTics = function(o){
var count = 0;
for(i=0; i < self.ticketsPool.length; i++){
count += self.canBuy(o, self.ticketsPool[i]) ? 1 : 0;
};
return count;
};
// 退票:以 OR 還原區段
self.refund = function(o){
for(i=0; i < self.ticketsPool.length; i++){
if(!self.canBuy(o, self.ticketsPool[i])){
var _o = '';
for(j=0; j<o.length; j++){
_o += o[j]=='0' ? 1 : 0;
}
self.ticketsPool[i].tic =
(parseInt(self.ticketsPool[i].tic,2) | parseInt(_o,2)).toString(2);
return i;
}
};
return -1;
};
}
// 資料模型:票
function Ticket(){
var self = this;
self.tic = '1111111111'; // 初始為全程票
}
// 資料模型:訂單
function Order(from, to){
var s = '';
for(i=0; i<10; i++){
s += (i>=from && i<to) ? 0 : 1;
}
return s;
}
Server = new Server();
Server._init(400); // 初始票池:400 張全程票
這段程式碼的重點不在語法,而在於思維方式:當業務的複雜度來自「區段可重疊」時,把狀態壓縮成位元,再靠位元運算完成比對,往往比直覺的計數器方案乾淨得多。當然,這只是教學用的簡化模型,真正的售票系統還要處理座位選擇、連線併發、異步一致性等一大堆問題。