Thursday, December 3, 2015

How to Design 12306 - 建设一个靠谱的火车票网上订购系统



http://massivetechinterview.blogspot.com/2016/01/blog-post_2.html
http://www.cnblogs.com/netfocus/p/5187241.html
http://blog.sina.com.cn/s/blog_46d0a3930100yc6x.html

讨论如何改进 12306 网上购票系统 [3]。其中比较有代表性的,有两篇 [4,5]。
网友的评论中,有观点认为,[4] 利用“虚拟排队”的手段,将过程拉长负载降低,是网游的设计思路。而 [5] 利用缓存技术,一层层地降低系统负荷, 是互联网的设计思路。

个人认为,[4] 和 [5] 并不是相互排斥的两种路线,两者着重解决的问题不同,不妨结合起来使用,取长补短


三类请求的业务处理过程,被分为两个阶段,

1. 运行于缓存中的任务队列。设置队列的目的,是防止处理过程耗时太长,导致大量用户请求拥塞于门户服务器,导致系统瘫痪。

查询任务可以进一步细化,大致分成三种。

1. 查询车次和时间表,这是静态内容,很少与数据库交互,数据量也不大,可以缓存在内存中。

车次和时间表的数据结构,不妨采用 Key-Value 的方式,开发简单,使用效率高。Key-Value 的具体实现有很多产品,[5] 建议使用 Redis。

2. 查询某一班次的剩余车票,这需要调用数据库中不断更新的数据。

[5] 建议把剩余车票只分为两种,“有”或“无”,这样减少调用访问数据库的次数,降低数据库的压力。但是这样做,不一定能够满足用户的需求,说不定会招致网友的批评讥讽。

[4] 建议在订票队列中,增加测算订票队列长度的功能,根据订票队列长度以及队列中每个请求的购票数量,可以计算出每个车次的剩余座位。如果 12306.cn 网站只有一个后台系统,这个办法行之有效。

但是假如 12306.cn 网站采用分布式结构,每个铁路分局设有子系统,分别管理各个铁路分局辖区内的各个车次。在分布式系统下,这个办法面临任务转发的麻烦。不仅开发工作量大,而且会延长查询流程处理时间,导致用户长久等待。

3. 已经下单的用户,查询是否已经成功地订上票。

每个用户通常只关心自己订的票。如果把每个用户订购的车票的所有内容,都缓存在内存里,不仅非常耗用内存空间,内存空间使用效率低下,更严重的问题是,访问数据库过于频繁,数据量大,增大数据库的压力。

解决上述分布式同步,以及数据库压力的两个问题,不妨从订票的流程设计和数据结构设计入手。

假如有个北京用户在网上订购了一套联票,途经北京铁路局和郑州铁路局辖区的两个车次。用户从北京上网,由北京铁路局的子系统,处理他的请求。北京铁路局的订票服务器把他的请求一分为二,北京铁路局的车次的订票,在北京子系统完成,郑州铁路局的车次在郑州子系统完成。

每个子系统处理四种 Key-Value 数据组。

1. 用户ID:多个 (订单ID)s。
2. 订单ID:多个 (订票结果ID)s。
3. 订票结果ID: 一个 (用户ID,车次ID)。
4. 车次ID:一个(日期),多个 (座位,用户ID)。

北京订票服务器完成订票后,把上述四个数据组,写入北京子系统的数据库,同时缓存进北京的查询服务器,参见图二下半部第6步和第7步。

郑州订票服务器完成订票后,把上述四个数据组,写入郑州子系统的数据库,同时缓存进北京的查询服务器,而不是郑州的服务器。

让订票服务器把订票数据,同时写入数据库和查询服务器的缓存,目的是让数据库永久保留订票记录,而让大多数查询,只访问缓存,降低数据库的压力。

北京用户的订票数据,只缓存在北京的查询服务器,不跨域缓存,从而降低缓存空间的占用,和同步的麻烦。这样做,有个前提假设,查询用户与订票用户,基本上是同一个人,而且从同一个城市上网。

http://blog.sina.com.cn/s/blog_46d0a3930100yiap.html

 “最难的两关是登陆和支付,这也是用户体验最糟糕的两步。登陆是最难闯的一关,验证码验证码验证码...,每次尝试等待若干时间,然后总是一个系统繁忙。这是令人着急和上火的一步。支付则是悲催的一步,订单到手,接着在 45 分钟内超时自动取消”[4]。
流程。

拙文 [3] 讨论了把 12306 系统,按登录、查询、订票三类业务,切割成三种流程。其中查询业务,又可以再切割成三种,查询车次时间表、查询某车次余票、查询某用户订购了哪些车票。

为什么要不厌其烦地切割流程?因为不同流程的环节构成不同,不同流程用到的数据也不一样,有些是静态数据,例如车次时间表,有些是动态数据,例如余票和乘客订购的车次座位。分而治之,有利于优化效率,也有利于让系统更皮实,更容易维护。

静态数据,更新少,尽可能存放在缓存(Cache)里,读起来快,而且不给数据库添麻烦。例如车次路线和时间表查询,就应该这样处理。

只有动态数据,才必须存放在数据库中。动态数据在数据库中,存放的方式是表。例如,查询余票与订票,就必须这样处理。

四。切割数据。
我们的办法是纵向切,根据不同车次,以及同一个车次的不同日期,切成若干表,放进多个数据库中去。这样,每张表只有(座位,经停站1,...经停站N)几列。假如每趟火车的载客人数不超过 5000 人,那么每张表的行数也不会超过 5000 行。

同一个车次,不同日期,分别有一张表。这样做的好处是,可以方便地实现分时出票。假如提前十天出票,今天是1月16日,那么在G19车次的数据库中,存放着 1月16日到1月26日的 10 张表,今晚打烊期间,数据库清除今天的表,并转移到备份数据库中,作为历史记录。同时增添1月27日的表。明天一早开门营业时,乘客就可以预定1月27日的车票了。

把不同车次的表,分别存放在不同的数据库中去,可以有效降低在每个数据库外面,用户排队等待的时间,同时也避免了同步和上锁的麻烦。

另外,假如每趟火车的座位不超过 5000 个,每趟火车沿线停靠的车站不超过 50 个,那么每个车次数据库外面,排队订票的队列长度,不必超过 50 x 5000 = 250,000。理由是,火车上每个座位,最多被 50 位乘客轮流坐,这种极端情况,出现在每位乘客只坐一站。

七。登录流程。

除了支付是短板以外,登录也是突出问题,尤其是大量用户不断刷屏,导致登录请求虚高。

应对登录洪峰的办法,说来简单,可以放置一大排 Web Servers。每个 Web Server 只做非常简单的工作,读用户请求的前几个 Bytes,根据请求的业务类型,迅速把用户请求扔给下家,例如查询队列。

Web Server 不甄别用户是否在刷屏,它来者不拒,把用户请求(也许是刷屏的重复请求),扔给业务排队队列。队列先查询用户ID是否已经出现在队列中,如果是,那么就是刷屏,不予理睬。只有当用户ID是新鲜的,队列才把用户请求,插入队尾。

有观点质疑,“Twitter 业务没有交易, 2 Phase Commit, Rollback 等概念”,所以 Twitter 的做法,未必能沿用到 12306 网站中来 [6]。

这个问题问得好,但是交易、二次确认、回放等等环节,都出现在 12306 系统的后续业务流程中,尤其是订票流程中,而登录发生在前端。

我们设计的出发点,是前端迅速接纳,但是后端推迟服务,一言以蔽之,通过增加前端 Web Servers 机器数量来蓄洪。

又有观点质疑,通过蓄洪的办法,Twitter 每秒能处理 42,000 条短信,但是 12306 面对的洪峰流量远远高过这个数量。增加更多前端 Web Servers 机器,是否能如愿地抵抗更大的洪峰呢?

每逢“超级碗 SuperBowl”橄榄球赛,Twitter 的流量就大涨。根据统计,在 SuperBowl 比赛时段内,每分钟 Twitter 的流量,与当日平均流量相比,平均高出40%。在比赛最激烈时,更高达150%以上。

面对排山倒海的洪峰流量,Twitter 还是以不变应万变,通过增加服务器的办法来蓄洪抗洪。更确切地说,Twitter 临时借用第三方的服务器来蓄洪,而且根据实时流量,动态地调整借用服务器的数量 [10]。

值得注意的是,Twitter 把借来的服务器,主要用于前端,增加 Apache Web Servers 的数量。而不是扩充后端,以便加快推送等等业务的处理速度。

这一细节,进一步证实 Twitter 的抗洪措施,与我们的相似。强化蓄洪能力,而不必过份担心泄洪能力。



http://blog.chedushi.com/archives/2824
也就是说,很多时候通过加机器就能解决大多数问题。只要规模在一定量级下(通常的在线系统规模都不会特别大),我们可以先不考虑硬件故障以及自动运维。
但为什么很多时候系统还是崩溃呢?罪魁祸首就是请求的尖峰,10倍于平常的压力是很正常的。普通模型到达性能瓶颈后,开始堆积请求(可能在web server,也可能在请求队列,不过通常不会在CDN),吞吐急剧下降,延迟急剧上升,而随着堆积请求越多,情况越糟,引起雪崩效应。而这样的压力通常不会持续很久,如果性能不急剧下降的话,一段时间后其实也就能把请求都响应了。
为10倍压力而准备机器是不合适的,我们需要有办法能扛住瞬间压力。这时候架构设计主要考虑的问题,也就是我上个weibo所说的,如何保证极限情况下的稳定吞吐。有很多种办法,分级队列、请求调度、延迟截断、主动拒绝等等,这些都有助于帮系统度过艰难时刻。具体的做法,就不在这里讨论了。

在线系统应以保证极限情况下的稳定输出(sustained throughput)为首要设计目标,而这是不容易实现的

对于一个理想的在线服务系统,应该包括几方面的能力。1) 单机高性能,也就是所谓的c10k能力。2) 良好的scalability。简单来说,就是加机器可以提升系统性能。3) 稳定输出,特别在极限情况下。4) 良好的自管理自运维能力,在故障、升级或扩容时尽量减少人工介入。

c) 最重要的是sustained throughput。在峰值压力情况下,平滑过渡,可以有效避免雪崩效应,大幅提升用户体验。我提了一些做法,很多朋友说这在通信系统中也是常用的。有兴趣的朋友也可以去研究一下queueing theory,看看latency和throughput是怎样的关系。
d) 在小规模时可以先不考虑自管理自运维能力。随着机群的扩展,故障处理、扩容减容以及服务调度等等逐渐成为最头疼的问题,而这正是分布式系统所要解决的最难的问题。对于大互联网公司来说,应该深有体会。

c) 增加flow control机制,上游根据下游的负载做throttling,反馈可以有ack/poll等多种做法,有时需要由最下游一路反馈到最前端。可能有人会问,反正请求都在队列中,在上游或下游不都一样吗?这里的问题在于资源使用,在请求响应的不同阶段占用的资源是不同的。我们需要根据反馈,让任务在占用最少资源的阶段挂起。
d) 延迟截断,对于太老的请求,直接给出拒绝响应,让它在应用层重试。
e) 分级队列,某些高优先级任务优先响应。
可能很多人也听说过SEDA结构,这是一种方案,还有很多种做法。上面ppt中的kylin框架也是一种,以后找机会介绍。但最关键的是思维的转变,由同步思维换成异步思维。而当你习惯了异步思维后,其实慢慢也会发现单机系统和多机系统并没有太大差别,从而也将跨入分布式系统的阶段
http://www.cnblogs.com/afarmer/archive/2012/09/21/2697494.html
相对靠谱的
1、云风:铁路订票系统的简单设计 http://blog.codingnow.com/2012/01/ticket_queue.html
文中提出:取得ticket id进行排队,排到后获得session id去完成购票过程。排队过程中还可以定时获得排队人数等。只要排到了,购票过程就会很顺利。
点评:需考虑黄牛取得一票ticket id进行排队的情形,毕竟这个排队跟网游魔兽世界登录排队、zol下载排队并不太一致。当然,可以借鉴网游中反外挂的处理,对同一个IP发出的排队请求,每隔一定时间就弹出要求输入验证码,目的是提高黄牛DDOS的成本。
不靠谱的
1、批判下最近关于12306架构方案的“排队思路” http://www.iteye.com/topic/1119803
文中提出:(1)事先选择车次票次,等排到了,票没了,再重新开始排,用户不认可;(2)排到后再选择车次票次,用户不熟练等操作时间过长,排队等待时间长。
点评:完全可以让用户事先选择可接受的车票车次,再排队,等排到后,网站列出用户事先选择的车票车次,并显示是否有票,用户一个单击操作即可购买,这样会大大减少用户购票操作时间。
二、预约
相对靠谱的
不靠谱的
1、我认为现阶段最可行的春运售票模式:公平买票,可解决买票难、买票苦,并且可彻底断绝黄牛后路 http://blog.sina.com.cn/s/blog_6a64bd150100zp23.html
文中提出:提前预约,系统分组,根据沪深指数确定哪一组获得购票权
点评:使得暗箱操作变得容易,不应考虑此种方式。
三、订票与支付分离
相对靠谱的
不靠谱的
1、火车票网售又是无反应和扣款没买到票 http://blog.csdn.net/sz_haitao/article/details/7174037
文中提出:用户先在银行支付,并指定车次、车票,银行后台再跟12306交互,有票出票并扣款,无票退款。
点评:试想一下,如果用户先在支付宝充值,并告诉支付宝买什么,然后支付宝后台完成交易过程。这样的过程是与用户体验相悖的。这不是炒股。这种做法是把简单业务复杂化,也是银行等不愿意做的。
四、缓存
相对靠谱的
1、曹政:铁路订票网站个人的设计浅见 http://hi.baidu.com/caoz/blog/item/f4f1d7caee09b558f21fe780.html
文中提出:车次、车票等信息查询都可静态缓存。车票可以简化为有票、无票两种状态。只有状态变化的时候才更新静态缓存。使用Redis等key-value数据库。
点评:其实12306目前每隔10分钟更新数据,也是完全可以的。只要采用key-value数据库进行缓存,而不是去查sql,查询速度就会快很多很多。
五、综合
相对靠谱的
1、邓侃:建设一个靠谱的火车票网上订购系统 http://blog.sina.com.cn/s/blog_46d0a3930100yc6x.html
邓侃:建设一个靠谱的火车票网上订购系统 (续) http://blog.sina.com.cn/s/blog_46d0a3930100yiap.html
文中提出:根据业务横向切割,根据流程纵向切割。与用户交互的前端使用云计算,靠堆机器来实现蓄水池的功能。
点评:跟云风、曹政提出的不谋而合。
2、陈皓:由12306.cn谈谈网站性能技术 http://coolshell.cn/articles/6470.html
文中对系统涉及到的业务细节和技术细节进行了分析,提出抢票的业务设计的变态以致不能很好解决,各地建分站等措施。
点评:本文中除了几个技术细节方面有待商榷,比如队列一致性等,具有一定的参考意义。
3、林仕鼎:简单讨论火车票系统后面的架构设计 http://qing.weibo.com/2244218960/85c41050330009xm.html
林仕鼎:再谈谈火车票系统 http://qing.weibo.com/2244218960/85c4105033000a3v.html
林仕鼎:三谈火车票系统 http://qing.weibo.com/2244218960/85c4105033000ab2.html
林仕鼎是百度的架构师,在为海量用户提供在线服务方面拥有大量的经验,具有很强的权威性。在这三篇文档中,林仕鼎提出了在解决类似业务场景是需要遵循的原则(系统稳定,不雪崩),在技术架构上需要采取的措施(业务与锁解耦,请求调度,多线程同步模式改为事件驱动的异步模式等等)。具有极高的参考价值。
六、12306现状
1、铁路客票系统建设“复杂”?业内吐槽排队功能 http://www.nbd.com.cn/articles/2012-09-21/683750.html
文中写到:“客票系统采取了集中与分布相结合的方案,即设立一个中央数据库和若干个地区数据库,在地区数据库中存储本地区始发列车的座席数据。

http://www.ifanr.com/68019
网友的评论中,有观点认为,[4] 利用“虚拟排队”的手段,将过程拉长负载降低,是网游的设计思路。而 [5] 利用缓存技术,一层层地降低系统负荷, 是互联网的设计思路。

12306 处理的用户请求,大致分为三类,
1. 查询。用户订票前,查询车次以及余票。用户下订单后,查询是否已经订上票。
2. 订票,包括确定车次和票数,然后付款。用户付款时,需要在网银等网站上操作。
3. 第一次访问的用户,需要登记,包括姓名和信用卡等信息。
三类请求的业务处理过程,被分为两个阶段,
1. 运行于缓存中的任务队列。设置队列的目的,是防止处理过程耗时太长,导致大量用户请求拥塞于门户服务器,导致系统瘫痪。
查询的业务流程,参见图二上半部,分五步。这里有两个问题需要注意,
1. 用户发出请求后,经过短暂的等待时间,能够迅速看到结果。平均等待时间不能超过 1 秒。
2. 影响整个查询速度的关键,是“查询服务器”的设计。
查询任务可以进一步细化,大致分成三种。
1. 查询车次和时间表,这是静态内容,很少与数据库交互,数据量也不大,可以缓存在内存中。
车次和时间表的数据结构,不妨采用 Key-Value 的方式,开发简单,使用效率高。Key-Value 的具体实现有很多产品,[5] 建议使用 Redis。
这些是技术细节,不妨通过对比实验,针对火车票订票系统的实际流量,以及峰值波动,确定哪一个产品最合适。
2. 查询某一班次的剩余车票,这需要调用数据库中不断更新的数据。
[5] 建议把剩余车票只分为两种,“有”或“无”,这样减少调用访问数据库的次数,降低数据库的压力。但是这样做,不一定能够满足用户的需求,说不定会招致网友的批评讥讽。
[4] 建议在订票队列中,增加测算订票队列长度的功能,根据订票队列长度以及队列中每个请求的购票数量,可以计算出每个车次的剩余座位。如果 12306.cn 网站只有一个后台系统,这个办法行之有效。
但是假如 12306.cn 网站采用分布式结构,每个铁路分局设有子系统,分别管理各个铁路分局辖区内的各个车次。在分布式系统下,这个办法面临任务转发的麻烦。不仅开发工作量大,而且会延长查询流程处理时间,导致用户长久等待。
3. 已经下单的用户,查询是否已经成功地订上票。
每个用户通常只关心自己订的票。如果把每个用户订购的车票的所有内容,都缓存在内存里,不仅非常耗用内存空间,内存空间使用效率低下,更严重的问题是,访问数据库过于频繁,数据量大,增大数据库的压力。
解决上述分布式同步,以及数据库压力的两个问题,不妨从订票的流程设计和数据结构设计入手。
TODO: http://www.cnblogs.com/netfocus/p/5187241.html
越是复杂的业务,就越要重视业务分析,重视领域模型的抽象和设计。如果不假思索,凭以往经验行事,则很可能会被以往的设计经验先入为主,陷入死胡同。我发现技术人员往往更注重技术层面的解决方案,比如一上来就分析如何集群、如何负载均衡、如何排队、如何分库分表、如何用锁,如何用缓存等技术问题,而忽略了最根本的业务层面的思考,如分析业务、领域建模。我认为越是复杂的业务系统,则越要设计一个健壮的领域模型。如果一个系统的架构我们设计错了,还有补救的余地,因为架构最终沉淀的只是代码,调整架构即可(一个系统的架构本身就是不断演进的);而如果领域模型设计错了,那要补救的代价是非常大的,因为领域模型沉淀的是数据结构及其对应的大量数据,对任何一个大型系统,要改核心领域模型都是成本非常高的。

越是复杂的业务,就越要重视业务分析,重视领域模型的抽象和设计。如果不假思索,凭以往经验行事,则很可能会被以往的设计经验先入为主,陷入死胡同。我发现技术人员往往更注重技术层面的解决方案,比如一上来就分析如何集群、如何负载均衡、如何排队、如何分库分表、如何用锁,如何用缓存等技术问题,而忽略了最根本的业务层面的思考,如分析业务、领域建模。我认为越是复杂的业务系统,则越要设计一个健壮的领域模型。如果一个系统的架构我们设计错了,还有补救的余地,因为架构最终沉淀的只是代码,调整架构即可(一个系统的架构本身就是不断演进的);而如果领域模型设计错了,那要补救的代价是非常大的,因为领域模型沉淀的是数据结构及其对应的大量数据,对任何一个大型系统,要改核心领域模型都是成本非常高的。
http://m.guancha.cn/Science/2014_01_11_199046

TODO: http://gfzeng.github.io/#!/posts/yet-another-12306-design-way.org

Labels

Review (572) System Design (334) System Design - Review (198) Java (189) Coding (75) Interview-System Design (65) Interview (63) Book Notes (59) Coding - Review (59) to-do (45) Linux (43) Knowledge (39) Interview-Java (35) Knowledge - Review (32) Database (31) Design Patterns (31) Big Data (29) Product Architecture (28) MultiThread (27) Soft Skills (27) Concurrency (26) Cracking Code Interview (26) Miscs (25) Distributed (24) OOD Design (24) Google (23) Career (22) Interview - Review (21) Java - Code (21) Operating System (21) Interview Q&A (20) System Design - Practice (20) Tips (19) Algorithm (17) Company - Facebook (17) Security (17) How to Ace Interview (16) Brain Teaser (14) Linux - Shell (14) Redis (14) Testing (14) Tools (14) Code Quality (13) Search (13) Spark (13) Spring (13) Company - LinkedIn (12) How to (12) Interview-Database (12) Interview-Operating System (12) Solr (12) Architecture Principles (11) Resource (10) Amazon (9) Cache (9) Git (9) Interview - MultiThread (9) Scalability (9) Trouble Shooting (9) Web Dev (9) Architecture Model (8) Better Programmer (8) Cassandra (8) Company - Uber (8) Java67 (8) Math (8) OO Design principles (8) SOLID (8) Design (7) Interview Corner (7) JVM (7) Java Basics (7) Kafka (7) Mac (7) Machine Learning (7) NoSQL (7) C++ (6) Chrome (6) File System (6) Highscalability (6) How to Better (6) Network (6) Restful (6) CareerCup (5) Code Review (5) Hash (5) How to Interview (5) JDK Source Code (5) JavaScript (5) Leetcode (5) Must Known (5) Python (5)

Popular Posts