火车售票算法和数据库性能测试
博客专区 > iBoxDB 的博客 > 博客详情
火车售票算法和数据库性能测试
iBoxDB 发表于4年前
火车售票算法和数据库性能测试
  • 发表于 4年前
  • 阅读 10128
  • 收藏 165
  • 点赞 9
  • 评论 28

标题:腾讯云 新注册用户域名抢购1元起>>>   

摘要: 对一个具体算法实例进行说明,并用来进行数据库性能测试, 选用的算法为火车售票算法.

我们都看过关于数据库的性能测试,但大部分都只是测试一两个基本操作,本文将会就一个实际算法进行数据库性能测试, 选用的数据库是iBoxDB, 在进行测试前,先介绍一下火车售票算法.

一个快速的售票算法是先进行配票,这里的配票是指对各站点预先分配一些计划的电子票,如果乘客想购买武汉-长沙票,就到武汉-长沙票的箱子里把计划的电子票移到已售的箱子里。销售一段时间后或某个箱子的票供不应求时,把全部未售出的计划电子票收回,按第一次销售的情况调整分配方式,再进行第二次配票。

这算法的第一次配票,可以根据各车站的规模,也可以平均分配,也可以人工输入到电子表格中,再读入到计算机中。第二次及以后的配票可以直接根据上一次销售中各个箱子的出票速度调整。

下面使用操作系统自带的文件系统实现此算法,进行具体说明.

假设有一列火车经北京-武汉-长沙 三站, 共有4个座位.  哪么它的首次配票可以是

1号座 北京-至-长沙

2号座 北京-至-长沙

3号座 北京-至-武汉

4号座 北京-至-武汉

3号座 武汉-至-长沙

4号座 武汉-至-长沙

所以在操作系统中创建三个文件夹   北京至长沙, 北京至武汉 , 武汉至长沙 , 然后在文件夹中创建对应的电子票。结果如下图:


如果有一个乘客需要购买武汉至长沙 的票, 就从 武汉至长沙 目录把两张票移入已售 目录


此时首次配票余下


1号座 北京-至-长沙


2号座 北京-至-长沙


3号座 北京-至-武汉


4号座 北京-至-武汉


武汉至长沙已经无票,根据首次配票的销售情况,收回首次未售出的电子票,然后进行第二次配票计算, 此例子中可以把 1号座 北京-至-长沙 分拆为两张,所以第二次配票的结果如下


1号座 北京-至-武汉


2号座 北京-至-长沙


3号座 北京-至-武汉


4号座 北京-至-武汉


1号座 武汉-至-长沙



这种火车票售票算法主要是配票方程式选择,对数据库毫无压力,本文需要的是一个能对数据库的性能进行测试的算法,所以上面的算法不合适。为了测试数据库,我们需要设计一种最差的算法,让它进行大量的数据库运算。


这种最差算法的基本思路是每个座号经过的每一站路为一个区间,也就是一个4座3站的班次有4x2=8个区间,3个车站中间是2段路. 当要购买北京至长沙 票时,从1号座开始扫描,如果有连续的区间到长沙,就出票,并且删除已经出票的区间,没有时就开始扫描2号座,然后3号座,直到最后一个座位,每个购票请求都是如此重复从1号座开始. 下面将会使用这个算法对iBoxDB数据库的性能进行测试,iBoxDB有Java和.NET双版本,这篇文章使用的是java版本。先从代码开始说明算法结合数据库的实现. 


1.首先定义基本类型

public static class Region {
	public int SeatNumber;
	public short Stop;
}

public static class Ticket {
	public long TicketID;
	public int SeatNumber;
	public short FirstStop;
	public short LastStop;
}
Region代表区间,它由座位号 SeatNumber和路段编号 Stop组成. Ticket 是车票,与区间相似,但它路段编号有开始( FirstStop)与结束( LastStop)两段.


2.定义存取上面类型的数据表, iBoxDB是 NoSQL 数据库,定义表不需要写SQL, 调用方法就可以了.
private static class TrainConfig extends BoxFileStreamConfig {
	public TrainConfig(long trainId) {

		this.EnsureTable(Ticket.class, "Ticket", "TicketID");

		this.EnsureTable(Region.class, "Region", "SeatNumber", "Stop");
		this.EnsureIndex(Region.class, "Region", true, "Stop",
				"SeatNumber");
	}
}
上面的定义是 Ticket 表使用 TicketID 作为主键. Region 表使用一个复合主键 [ "SeatNumber", "Stop"], 同时 Region表再加一个与主键顺序相反的复合索引,这样可以方便 Region表从不同的维度开始查找数据.   EnsureIndex 中的 true参数是指这是一个数值不可重复的唯一索引.


3.定义操作的API
public static interface WebAPI {

	public Ticket orderTickets(int beginSeatNumber, int endSeatNumber,
			short firstStop, short lastStop);

	public boolean cancelTickets(long ticketID);

	public Iterable<Ticket> readAll();

	public int last();

	public void init();

	public void close();
}
orderTickets() 是购票,它可以指定只从哪个座号段中选票。 cancelTickets()是退票。 readAll() 是读取全部已经售出的票. last() 是还回当前还余下有多少个区间. init()进行数据初始化.


4.测试开始前首 要生成所有准备销售的区间,这里采用多线程方式增加CPU利用率 , 测试程序使用的是5000座位 50个路段的参数,下面的初始化代码会插入25万条带索引的记录。
ExecutorService pool = Executors.newFixedThreadPool(16);
for (int x = 1; x <= MaxSeat; x++) {
	final int seatNumber = x;
	pool.execute(new Runnable() {
		@Override
		public void run() {
			try (Box box = db.cube()) {
				for (short y = 1; y <= MaxStop; y++) {
					Region region = new Region();
					region.SeatNumber = seatNumber;
					region.Stop = y;
					box.insert("Region", region);
					keyCount.incrementAndGet();
				}
				box.commit().Assert();
			}
		}
	});
}

 


5.开始使用本文中的第二个购票算法对数据库进行性能测试 
public Ticket orderTickets(int beginSeatNumber, int endSeatNumber,
		short firstStop, short lastStop) {
	if (firstStop > lastStop) {
		return null;
	}
	try (Box box = db.cube()) {
		Ticket ticket = null;
		for (Region key : box
				.select(Region.class,
						"from Region where Stop==? & SeatNumber>=? & SeatNumber<=? ",
						firstStop, beginSeatNumber, endSeatNumber)) {
			if (box.selectCount(
					"from Region where SeatNumber==? & Stop>=? & Stop<=? ",
					key.SeatNumber, firstStop, lastStop) == (lastStop
					- firstStop + 1)) {
				ticket = new Ticket();
				ticket.TicketID = box.newId(0, 1);
				ticket.SeatNumber = key.SeatNumber;
				ticket.FirstStop = firstStop;
				ticket.LastStop = lastStop;
				break;
			}
			if (ticket != null) {
				break;
			}
		}
		if (ticket != null) {
			int kCount = 0;
			for (short s = ticket.FirstStop; s <= ticket.LastStop; s++) {
				box.bind("Region", ticket.SeatNumber, s).delete();
				kCount--;
			}
			box.bind("Ticket").insert(ticket);
			CommitResult r = box.commit();
			if (r.equals(CommitResult.OK)) {
				keyCount.addAndGet(kCount);
				return ticket;
			}
		}
		return null;
	}
}

先使用 "from Region where Stop==? & SeatNumber>=? & SeatNumber<=? " 查找在当前站点是空座的座位号,带有座位范围控制"SeatNumber>=? & SeatNumber<=?". 然后检测到达目标站点前,这个座位是不是一直空着,通过对"from Region where SeatNumber==? & Stop>=? & Stop<=? "的计数(Count)判断,因为已经售出的区间会被移走,没移走的代表是空座. 

购票后删除此票对应的区间,最后插入票据记录.退票操作刚好与购票操作最后两步相反,是插入区间,删除票据记录. 上面有一比较特别的代码

if (r.equals(CommitResult.OK)) {
   keyCount.addAndGet(kCount);
   return ticket;
}

这个功能是提交成功后更新余下区间的总数量,后面的随机票生成代码中会检测区间数量, 如果区间用完了,就会停止生成随机票.


6.基本数据库操作实现后,就正式开始进行数据库性能测试了,使用10条线程对10个座位段进行随机票订购,再使用1条线程进行退票操作. 程序两次运行结果如下

Begin
对 5000座 *50站, 合计 250000 个区间进行了随机售票
一共进行了 1650093 张随机票生成并下单的操作
其中符合条件售出的票数是 59669 张,还执行了 160 个随机退票操作
共消耗时间为51秒
END.

Begin
对 5000座 *50站, 合计 250000 个区间进行了随机售票
一共进行了 2862039 张随机票生成并下单的操作
其中符合条件售出的票数是 59671 张,还执行了 159 个随机退票操作
共消耗时间为55秒
END.


整个测试一般需要1-2分钟,这个结果除了说明数据库很快之外,同时也说明了在现今计算机技术的帮助下,无论多不合理的设计都能在3分钟内把票售空. 测试代码已经上传到 git.oschina.net . 感兴趣可以重写WebAPI接口, 测试在其它数据库下的性能。 更多关于 iBoxDB 


共有 人打赏支持
iBoxDB
粉丝 47
博文 17
码字总数 7207
作品 3
评论 (28)
osos
沙发
edgeman03
不觉明厉
komelio
问题的重点不是票卖不出去,是票不够卖
mopdzz
不明觉厉
cat_l_fish
反正2014,我买到票了
limengwei
觉厉
王振威
铁道部的售票逻辑没这么简单。。
刘建业
恩.是啊.重点是买不到票,一直买,一直买.就给买崩溃了.
汤医森
1. 铁道部售票逻辑还要考虑政策规定,没这么简单
2. 售票和查询的速度已经合格了,崩溃的原因是网络流量过大没有分流,这是架构设计问题,不在算法
ChenNicq

引用来自“王振威”的评论

铁道部的售票逻辑没这么简单。。

还有铁道部呢。
xpsair
还是不明觉厉
hentai
好像很牛逼的样子
not3
根據商業上的邏輯,應該是全程票優先的吧。中間缺票不是虧死了?
BoXuan

引用来自“Stondet”的评论

根據商業上的邏輯,應該是全程票優先的吧。中間缺票不是虧死了?

完全按照商业逻辑,那将出现很多不公平的现象,况且中途票到站还可能有中途乘客的
mikiyonney
不明觉厉!
微宇
前不久12306还发生账户和姓名不对,不知道是故意不搞好,还是真的搞不好……

售票这个问题记得csdn当初有个帖子讨论了很长,最后也没有个结论,我想知道真实场景查票的时候会有读锁吗?
微宇
今年算是用上队列机制了……
not3

引用来自“BoXuan”的评论

引用来自“Stondet”的评论

根據商業上的邏輯,應該是全程票優先的吧。中間缺票不是虧死了?

完全按照商业逻辑,那将出现很多不公平的现象,况且中途票到站还可能有中途乘客的

所以根據歷史的一些數據,會開闢很多新的單獨的鐵路班次,以保證這種需求。當然會留一些額度給中途站的,但是不可能會這麽多。要考慮總體的各個站點的旅客滯留總數,不可能采取普通的加權重就可以解決的。隻考慮中途票,可以會引發更多的總體的旅客滯留數。
not3

引用来自“微宇”的评论

前不久12306还发生账户和姓名不对,不知道是故意不搞好,还是真的搞不好……

售票这个问题记得csdn当初有个帖子讨论了很长,最后也没有个结论,我想知道真实场景查票的时候会有读锁吗?

1、假設票已被搶到,加了讀鎖,沒有任何意義
2、假設票未被搶,爲什麽要加讀鎖,讓某些人看不到
3、同時搶-未付款。當然看最終付款成功的那個人啦,就跟天貓的那啥啥啥活動的機制一樣的
blackdante
这是在推iBoxDB吗?
×
iBoxDB
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: