也说12306

需求分解

  • 对于查询余票:从从库查询,并且允许延迟,保证查询系统基本可用即可。
  • 对于支付:本文不做分析,但是需要明确:下单和支付不是耦合的,而是完全分离的两个系统
  • 对于退票:视为购票数量为-1的下单。
  • 对于下单:以下重点说明

下单系统分析

  • 高并发:由分布式的部署进行缓解,使用高强度验证码、限流等方式过滤异常请求,分时段放票,必要时放弃部分有效请求等。
  • CAP三角形中的CP:C由事务型数据库保证,P从架构设计上消灭。

算法说明

  • 把每次列车的每个席别都看成一个单独的车次,比如G381有商务座、特等座、一等座、二等座,那么对应的车次编号可以是:G381-1、G381-2、G381-3、G381-4。
  • 将每次列车的任意两站看成一个子车次子车次之间是互相依赖的。比如对于C2205-1次列车,它是由北京南(1)始发,经由武清(2),终到天津(3)的商务座,这次列车有3个子车次分别是:(1,2)、(1,3),(2,3),并且(1,3)依赖(1,2)和(2,3),也就是说当北京到武清的票售罄了,那么北京到天津的票也无法购买了。
  • 所有的子车次放在一个数据结构中,统一管理,当卖出一张从A到B之间的票的时候,A到B之间的所有子车次的票数都减少1。比如上条中的C2205-1次列车卖出了一张北京到天津的票,那么北京到武清和武清到天津这两个子车次的票数也要减1。
上面的算法是实际的出票方案,可在其上引入“配额”的概念。
比如,车次9527-1,有三站A,B,C。通过分析得到 分段B-C 的需求更强烈,也就是说整趟列车各个分段的“热度”是不均匀的。

设车次9527-1有5个座位,想优先卖A-B和B-C,那么可以把A-B和B-C的“配额”设置为4,而A-C设置为1。在售票的时候,卖出哪段的1张票,哪段的“配额”减1。比如卖出了A-C的一张票,那么A-C的配额减少1,A-B和B-C的配额不变,之后是按照上面的算法出票。并且当某分段的配额不足时,直接提示失败。

配额是可以调整的。比A-C卖出了1张,A-B卖出了1张,B-C卖出了3张,那么可以重新设置配额为:A-C 1张、A-B 3张、B-C 1张。

引入“配额”的概念,是为了人工干预各个分段的售票情况。当然也可以将实际票数当作配额,也就是直接使用出票算法出票。

架构

  • 整个下单系统由N个节点组成,每个节点是一个集群,节点与节点之间是无感知的,孤立的。
  • 采用智能DNS,与运营商合作等方式,解决DNS轮询所带来的弊端。比如北京的用户发起的请求,只会解析到为北京及周边用户所部署的节点。
  • 因为算法的纬度是车次,所以可以按照车次进行分布式部署,比如G2496从吉林省出发,经过辽宁省、河北省,最终在凌晨2点30左右抵达北京,故该车的意图主要是给吉林省的旅客返京准备的,因此,G2496-1、G2496-2、G2496-3、G2496-4这四个车次部署在东北的节点上。
  • 因为售票这种行为是要优先保证一致性的,并且已经在车次上做了分布式,所以不使用支持事务的分布式数据库,选择Oracle等支持ACID的关系数据库。假定在北京有节点,那么北京的节点上的下单服务使用的是部署在北京的节点上的数据库集群,这样就可以把网络分区避免掉。
  • 按照车次和车出发的日期等进行分表,减轻单个库的压力。
  • 在同城、异地各做若干份服务以及数据库集群的热备,并保持数据的同步。在出现挖断网线等故障时,人工切服务。

表设计

  • 车次:作为唯一索引,比如G2496-1
  • 车站列表:逗号分隔的车站ID,比如11000,11001,11002
  • 子车次信息:采用json序列化,比如{(11000, 11001): 4, (11001, 11002): 3, (11000, 11002): 4},其中key是子车次,value是余票,例子中的11000、11001、11002是车站ID

粗略的实现

#coding: utf8

class Train:  
    def __init__(self, stations, station2ticket_num):
        assert all(isinstance(s, int) for s in stations) \
            and len(stations) == len(set(stations))
        self._stations = stations

        if isinstance(station2ticket_num, int):
            self._station2ticket_num = \ 
                dict.fromkeys(self.generate_substations(stations), 
                    station2ticket_num)
        elif isinstance(station2ticket_num, dict):
            self._station2ticket_num = station2ticket_num
        else:
            raise TypeError('expected int or dict')

    def generate_substations(self, stations):
        substations = []
        for i in range(len(stations)-1):
            for j in range(i+1, len(stations)):
                substations.append((stations[i], stations[j]))
        return substations

    def find_middle_stations(self, start, end):
        start = self._stations.index(start)
        end = self._stations.index(end)
        assert 0 <= start < end 
        return self.generate_substations(self._stations[start:end+1])

    def is_satisfy(self, middle_stations, ticket_num, sell=False):
        for station in self._station2ticket_num:
            if not station in middle_stations:
                continue
            if sell:
                self._station2ticket_num[station] -= ticket_num
            elif self._station2ticket_num[station] - ticket_num  < 0:
                return False
        return True

    def sell(self, start, end, ticket_num=1):
        middle_stations = self.find_middle_stations(start, end)
        if not self.is_satisfy(middle_stations, ticket_num):
            return False
        return self.is_satisfy(middle_stations, ticket_num, True)

    def query_not_sold(self, start=None, end=None):
        if (start, end) not in self._station2ticket_num:
            return self._station2ticket_num
        return self._station2ticket_num[(start, end)]

if __name__ == "__main__":  
    #Transaction start
    #按照车次,从数据库获取子车次余票信息和车站列表

    # + 下面是一个例子
    stations = [11000, 11001, 11002]
    not_sold = {(11000, 11001): 4, (11001, 11002): 3, (11000, 11002): 4}
    train = Train(stations, not_sold)
    print train.sell(11000, 11001)
    print train.sell(11000, 11002)
    print train.sell(11001, 11002)
    print train.sell(11001, 11002)
    not_sold = train.query_not_sold()
    print not_sold

    #将余票not_sold更新回数据库
    #Transaction end


每卖成功一张票需要读一次数据库,写一次数据库;没有足够的余票则读一次数据库。上例的输出是:

True  
True  
True  
True  
{(11000, 11001): 2, (11001, 11002): 0, (11000, 11002): 3}

感谢浏览tim chow的作品!

如果您喜欢,可以分享到: 更多

如果您有任何疑问或想要与tim chow进行交流

可点此给tim chow发信

如有问题,也可在下面留言: