| 100行代码搞定12306库存问题：谈12306系统设计思路 | 您所在的位置：网站首页 › 12306订票系统中数据库的作用 › 100行代码搞定12306库存问题：谈12306系统设计思路 |
100行代码搞定12306库存问题：谈12306系统设计思路
|
2016年春运刚过，12306购票系统又一次被推到风头浪尖，这次春运12306系统表现还是不错的，除了神一样的验证码以外，基本上没有出现过大面积长时间的故障。12306系统复杂程度、系统如何设计，作为技术人员值得深入思考一下。 ##12306数据分析 预售期：60天车站：3000＋车次：7000／天日期车次：7000 X 60＝42万站站：21万／天日期站站：21万x 60=1260万商品（站站、车次、日期、座位类型）：1.5亿左右商品间存在关联，当售出一张票后，两站间的库存都要减少. 2015年春节访问量峰值当天：共有297亿pv次访问，536.9万张票访问量平均值；51万 qps访问量峰值（平均值2倍计算）；51万 x 2 = 102万 qps虽然访问量很高，但主要集中在搜索查询上，搜索的压力体现在库存管理上. ##架构设计思路
##基础数据设计思路
##库存管理设计思路 购票占座其实就是找到符合条件的座位，假设有一列经过A到F ，6个车站的火车，车上共有10个座位，大体需要有以下几种场景需要满足： 场景1:当卖掉了一张A到F的车票，则AF之间所有站站库存要减1，若果经过100个站，则需要C(100，2)＝4950次操作；场景2:列车中途需要增加减少车厢，或者有一节车厢不对外出售；场景3:为了降低空座率,需要特定站站最多卖票数量，特定出发站的最多卖票数量；场景4:由于座位的唯一性，需要标示特定座位某站站已被卖出，并且找到满足特定条件的座位，如果1列火车有2000个座位，这个运算就是一个挑战；场景5:某特定车厢或座位只能卖给特定始发站的人群，即某特定车厢是给某个车站预留的；###数据结构和算法设计 由于车站A,B,C,D,E,F顺序固定，可以用用数字表示为(1,2,3,4,5,6)，相邻车站站 (AB,BC,CD,DE,EF)顺序号可表示为(0,1,2,3,4);
购票流程： 1、输入车次、站站(AE)、坐席类型信息； 2、根据站站找到A和E的位置信息,即1和5; 3、根据车次站站库存判断索引，判断该车次站站是否有余票，若果有继续； 4、根据购买限制索引，判断站站余票数量限制，如果可以购买继续； 5、遍历座位站站库存判断索引数组，找到该站站有余票的座位索引编号； 6、更新座位站站库存判断索引值，相关位置置1，说明该站站座位票已卖出； 7、相邻站库存数组，AE间相邻站库存减1; 8、更新车次站站库存判断索引，如果AE间相邻站库存为0,则对应标示位置1，表示该邻近站站已无库存; 9、更新购买限制索引，如果存在限制索引则减1； 10、返回座位索引编号； 取消票流程： 1、输入车次、站站(AE)、座位编号； 2、根据座位编号找到座位站站库存判断索引，相关索引位置置0，说明该站站座位票未卖出； 3、更新相邻站库存，AE间相邻站库存加1; 4、更新车次站站库存判断索引，AE间相邻站站位置置0，说明AE间所有站站还有库存； 5、更新购买限制索引，如果存在限制索引则加1； 余票查询流程 1、输入车次、站站(AE)、坐席类型信息； 2、根据车次站站库存判断索引，判断该车次站站是否有余票，若有记录限制值并，若无返回0； 3、遍历AE间相邻站(AB,BC,CD,DE)间余票，记录相邻站站余票最小值min(AB,BC,CD,DE)； 4、返回min(限制值，相邻站站余票最小值)； 以100车站2000座位车次为例，存储空间应不超过3K，其实大多数车次不超过10个车站1000个座位，基本上1.5K能搞定，理想情况下42W的日期车次库存数据不超过1G的存储空间。当然这个不包括存储数据本身需要的数据结构维护的空间，这也与实现方式和存储方案有关； 整个实时计算过程中采用位运算和数组操作，模拟一个100车站2000坐席的车次，在出票情况最多的场景下，即每次都购买相邻站并且每次都需要遍历，不存在被可购买索引挡出的情况下，订票19.8万张票用时17秒，即每个日期车次每秒钟可订票11000张。理想情况下最多每秒钟可出47万(日期车次数量)x1.1万张票，即47亿张，如果每个日期车次最多只售卖1万张票，则所有票可在1秒内出完。###算法代码 import java.util.BitSet; import java.util.HashMap; import java.util.Map; /** * Created by jerrysun on 16/2/23. */ public class TrainStock { public Map stationMap = new HashMap(); public BitSet canBookIndex; public Map s2sMaxCountMap = new HashMap(); public Integer[] s2sTickets; public BitSet[] seatCanBookIndex; @Override public String toString() { String temp = "stationMap:" + stationMap.toString() + "\r\n"; temp = temp + "s2sTickets:"; for (int i = 0; i temp = temp + "," + seatCanBookIndex[i].toString(); } temp = temp + "\r\n"; return temp; } public Integer bookTicket(Integer fromStation, Integer toStation) { Integer fIdx = stationMap.get(fromStation); Integer tIdx = stationMap.get(toStation); BitSet bookIndex = this.canBookIndex.get(fIdx, tIdx); if (bookIndex.isEmpty()) { Integer maxCount = s2sMaxCountMap.get(fromStation * 10000 + toStation); if (maxCount != null && maxCount > 0 || maxCount == null) { for (int i = 0; i for (int j = fIdx; j return -100; } } public Integer cancleTicket(Integer fromStation, Integer toStation, int seatIndex) { Integer fIdx = stationMap.get(fromStation); Integer tIdx = stationMap.get(toStation); for (int j = fIdx; j Integer fIdx = this.stationMap.get(fromStation); Integer tIdx = this.stationMap.get(toStation); int temp1 = 10000; for (int j = fIdx; j @Test public void testData() throws Exception { Integer stationCount = 6; Integer seatCount = 10; TrainStock trainStock = buildTrainStock(stationCount, seatCount); System.out.println(trainStock.toString()); //已出票索引,这么设计存储有性能问题,其实可以优化为List,数据按位存储,实际应用中应该是和订单相关信息 Map bookedSeatMap = new HashMap(); //订票测试,并计入已出票 long start = System.currentTimeMillis(); for (int i = 1; i TrainSeatMsg trainSeatMsg = new TrainSeatMsg(); trainSeatMsg.setFromStation(i); trainSeatMsg.setToStation(i + 1); trainSeatMsg.setSeatIndex(num); bookedSeatMap.put(i + "_" + (i + 1) + "_" + num, trainSeatMsg); } System.out.println((System.currentTimeMillis() - start) + "ms"); System.out.println("Book s2s=" + i + "_" + (i + 1) + ":" + num); System.out.println(trainStock.toString()); } //取消订票测试 long start1 = System.currentTimeMillis(); for (TrainSeatMsg value : bookedSeatMap.values()) { int num = trainStock.cancleTicket(value.fromStation, value.toStation, value.seatIndex); System.out.println((System.currentTimeMillis() - start1) + "ms"); System.out.println("Cancle s2s=" + value.fromStation + "_" + value.toStation + "_" + value.seatIndex); System.out.println(trainStock.toString()); } //余票查询 long start2 = System.currentTimeMillis(); for (int i = 1; i Integer stationCount = 100; Integer seatCount = 2000; TrainStock trainStock = buildTrainStock(stationCount, seatCount); System.out.println(trainStock.toString()); //订票测试,模拟stationCount*seatCount次,模拟出票情况最多的情况,即每次都购买相邻站并且每次都需要遍历,不存在被可购买索引挡出的情况 Integer bookcount=0; System.out.println("Book Ticket"); long start = System.currentTimeMillis(); for (int i = 1; i int num = trainStock.bookTicket(i, i + 1); bookcount++; } } long bookTotalTime= System.currentTimeMillis() - start; System.out.println(bookTotalTime + "ms"); System.out.println(bookcount + "times"); System.out.println((float)bookTotalTime/(float)bookcount + "ms"); System.out.println(bookcount/bookTotalTime*1000+"/s"); //System.out.println(trainStock.toString()); System.out.println("=========================="); //余票查询,模拟stationCount*seatCount次,模拟最耗时的始发站到终点站的查询 Integer getcount=0; System.out.println("Get " + "Stock"); long start1 = System.currentTimeMillis(); for (int i = 1; i int num = trainStock.getStock(1,stationCount); getcount++; } } long getTotalTime= System.currentTimeMillis() - start; System.out.println(getTotalTime + "ms"); System.out.println(getcount + "times"); System.out.println((float)getTotalTime/(float)getcount + "ms"); System.out.println(getcount/getTotalTime*1000+"/s"); //System.out.println(trainStock.toString()); } /** * 构建车次库存数据实体 * * @param stationCount 车站数量 * @param seatCount 座位数量 * @return */ private TrainStock buildTrainStock(Integer stationCount, Integer seatCount) { TrainStock trainStock = new TrainStock(); //构建车站map,车站索引从1开始构建 Integer[] stations = new Integer[stationCount]; for (int i = 0; i stationMap.put(stations[i], i); } //构建可预定判断索引 BitSet canBookIndex = new BitSet(stationCount - 1); //构建车次购买限制Map,构建相邻车站最大可购买数量 Map s2sMaxCountMap = new HashMap(); for (int i = 0; i s2stickets[i] = seatCount; } //构建座位可预定判断索引Map BitSet[] seatCanBookIndexs = new BitSet[seatCount]; for (int i = 0; i public Map stationMap = new HashMap(); public BitSet canBookIndex; public Map s2sMaxCountMap = new HashMap(); public Integer[] s2sTickets; public BitSet[] seatCanBookIndex; @Override public String toString() { String temp = "stationMap:" + stationMap.toString() + "\r\n"; temp = temp + "s2sTickets:"; for (int i = 0; i temp = temp + "," + seatCanBookIndex[i].toString(); } temp = temp + "\r\n"; return temp; } public Integer bookTicket(Integer fromStation, Integer toStation) { Integer fIdx = stationMap.get(fromStation); Integer tIdx = stationMap.get(toStation); BitSet bookIndex = this.canBookIndex.get(fIdx, tIdx); if (bookIndex.isEmpty()) { Integer maxCount = s2sMaxCountMap.get(fromStation * 10000 + toStation); if (maxCount != null && maxCount > 0 || maxCount == null) { for (int i = 0; i for (int j = fIdx; j return -100; } } public Integer cancleTicket(Integer fromStation, Integer toStation, int seatIndex) { Integer fIdx = stationMap.get(fromStation); Integer tIdx = stationMap.get(toStation); for (int j = fIdx; j Integer fIdx = this.stationMap.get(fromStation); Integer tIdx = this.stationMap.get(toStation); int temp1 = 10000; for (int j = fIdx; j Integer fromStation; Integer toStation; Integer seatIndex; public Integer getSeatIndex() { return seatIndex; } public void setSeatIndex(Integer seatIndex) { this.seatIndex = seatIndex; } public Integer getFromStation() { return fromStation; } public void setFromStation(Integer fromStation) { this.fromStation = fromStation; } public Integer getToStation() { return toStation; } public void setToStation(Integer toStation) { this.toStation = toStation; } } } |
【本文地址】
公司简介
联系我们