文档章节

火车售票算法和数据库性能测试

iBoxDB
 iBoxDB
发布于 2014/01/03 14:42
字数 2086
阅读 10217
收藏 165
点赞 9
评论 28

我们都看过关于数据库的性能测试,但大部分都只是测试一两个基本操作,本文将会就一个实际算法进行数据库性能测试, 选用的数据库是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

iBoxDB

粉丝 46
博文 17
码字总数 7207
作品 3
拉萨
加载中

评论(28)

红白机
红白机
有一次我坐车,还碰到一个一座多卖的现象,结果那两个人都在那里掐,最后叫列车长来了。我想知道,是不是其中一人买的是黄牛假票?
Qiujuer
Qiujuer
相当精辟!
很经典!
支持了!
天天天
天天天
1万个人来,只放100个进来,其他的直接等下次刷选
GIFCOOL
GIFCOOL
管你什么算法,你让我买到票就可以了。
铂金小哥
铂金小哥
仍然不明觉历...
iBoxDB
iBoxDB

引用来自“blackdante”的评论

这是在推iBoxDB吗?

0推荐,连接上有与MongoDB的性能对比, 前一篇博客有各平台运行截图
中山野鬼
中山野鬼

引用来自“iBoxDB”的评论

给自己回个帖子1月4日的最新新闻(【春运K696次网络售票现场直播瞬间抢光】央视直播上海-成都K696次网络售票现场,记者现场展示票量随时间变化的过程:仅开始抢票40秒,就只剩下300多张票,2分钟后票基本全部售出。记者表示在车票开卖的一小时内都会有车票重回票库,所以坚持还是有一定机会的。)
这个新闻的结果与昨天发博客时的数据测试结果一致.13

哈,楼主,你的上面算法的每步骤都是个坑啊。不是说你,而是说,这种系统,一旦到了分布式大规模的处理,任何一个中间环节,都存在逻辑同步的问题。系统越复杂这种同步要求和应对手段就越复杂。哈。继续加油。
iBoxDB
iBoxDB
给自己回个帖子1月4日的最新新闻(【春运K696次网络售票现场直播瞬间抢光】央视直播上海-成都K696次网络售票现场,记者现场展示票量随时间变化的过程:仅开始抢票40秒,就只剩下300多张票,2分钟后票基本全部售出。记者表示在车票开卖的一小时内都会有车票重回票库,所以坚持还是有一定机会的。)
这个新闻的结果与昨天发博客时的数据测试结果一致.13
blackdante
blackdante
这是在推iBoxDB吗?
not3
not3

引用来自“微宇”的评论

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

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

1、假設票已被搶到,加了讀鎖,沒有任何意義
2、假設票未被搶,爲什麽要加讀鎖,讓某些人看不到
3、同時搶-未付款。當然看最終付款成功的那個人啦,就跟天貓的那啥啥啥活動的機制一樣的
调度思想-现实中的事物与技术里面其实存在类似道理

以前看有人解决铁道部订票方案的时候,提供的思路。网友评价是:陷入了纯技术思维路子。 仔细想想非常有道理。 这里还是一种调度的思想原则。现实中很多事情像公交车,列车,拥堵的时候进行调...

wangtaotao
2013/12/01
0
0
再再续:一张图搞定 12306

本文是前三篇文章的续篇,针对网友提出的各种问题,详细介绍一下基于微仓储概念的12306网站总体架构设计。前文中,我们从仓储结构的设计逐步完善到仓储引擎的设计,这次我们画张图,详细介绍...

八风不动
2014/01/28
2.1K
17
评论:火车票网售为何总是“逢节必瘫”

新京报 社论   建12306网站花了一大笔钱,每年维持网站运营又是一大笔钱,好评不多,差评不少。既然,其经济效益和社会效益都不是很好,何必继续将火车网络售票权垄断在自家怀里呢? 又是一...

oschina
2013/12/30
7.5K
126
再续:12306 火车售票系统的仓储引擎设计

本文是前两篇文章的续篇,继续研讨12306网站特殊仓储结构的售票引擎设计。 前文请看:12306 售票仓储结构的设计 续篇:续篇:12306 火车售票系统的仓储结构设计 关于大并发时系统处理能力的问...

八风不动
2014/01/27
1K
7
铁道部:已开始设计新一代客票系统

12306网站的工作人员在处理用户身份核对申请 今年春运以来,旅客在www.12306.cn网站购买火车票过程中,遭遇了“网络运行缓慢”“票没订上,但钱被扣走了”等问题。针对这些问题,中国铁路客 ...

红薯
2012/01/14
3.4K
43
续篇:12306 火车售票系统的仓储结构设计

本文是前一篇文章的续篇:http://www.oschina.net/question/124158_141925 前文概述了火车售票系统仓储结构的设计思路,关键点就是用64bit的long类型数据表示一条线路。这次继续展开,进一步...

八风不动
2014/01/26
1K
10
火车售票的数据库该如何设计?

模拟火车售票系统,有登陆注册查询购票功能,用户不存在权限,仅仅是乘客进行购票。 模拟火车票数据库需要的数据进行设计,以票面信息为中心,考虑旅客、火车等的信息。 站点就模拟:济南-泰...

走夜路的coder
2015/05/12
497
2
分支预测:为什么有序数组比无序数组快?

最近几天在搜集一些关于 JavaScript 函数式编程的性能测试用例,还有内存占用情况分析。 我在一年前(2017年1月) 曾写过一篇文章《JavaScript 函数式编程存在性能问题么?》,在文中我对数组高...

justjavac
07/10
0
0
关于Struts的Action一点说明(线程安全性)

今天看到有人发帖子问Action的问题,我想来说明一下。 虽然我也不能算精通,但是希望把我知道的和大家分享一下; 我没有用过Struts2,一直在用Struts。不知道是不是一样的。 对Struts,我可以...

人型电脑天使心
2012/09/03
0
0
java多线程模拟程序(售票、消费者生产者)

(火车售票)http://www.oschina.net/code/snippet73380635772 (消费者生产者)http://www.oschina.net/code/snippet73380635764...

去哪儿了
2014/05/14
276
1

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Mybatis收集配置

一、Mybatis取Clob数据 1、Mapper.xml配置 <resultMap type="com.test.User" id="user"> <result column="id" property="id"/> <result column="json_data" property="jsonData" ......

星痕2018
28分钟前
0
0
centos7设置以多用户模式启动

1、旧版本linux系统修改inittab文件,在新版本执行vi /etc/inittab 会有以下提示 # inittab is no longer used when using systemd. # # ADDING CONFIGURATION HERE WILL HAVE NO EFFECT ON......

haha360
今天
0
0
OSChina 周日乱弹 —— 局长:怕你不爱我

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @ andonny :分享周二珂的单曲《孤独她呀》 《孤独她呀》- 周二珂 手机党少年们想听歌,请使劲儿戳(这里) @孤星闵月 :没事干,看一遍红楼梦...

小小编辑
今天
158
9
Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式 Factory工厂模式 Singleton单例模式 Delegate委派模式 Strategy策略模式 Prototype原型模式 Template模板模式 Spring5 beans 接口实例化 代理Bean操作 ...

小致dad
今天
0
0
SpringBoot | 第十章:Swagger2的集成和使用

前言 前一章节介绍了mybatisPlus的集成和简单使用,本章节开始接着上一章节的用户表,进行Swagger2的集成。现在都奉行前后端分离开发和微服务大行其道,分微服务及前后端分离后,前后端开发的...

oKong
今天
10
0
Python 最小二乘法 拟合 二次曲线

Python 二次拟合 随机生成数据,并且加上噪声干扰 构造需要拟合的函数形式,使用最小二乘法进行拟合 输出拟合后的参数 将拟合后的函数与原始数据绘图后进行对比 import numpy as npimport...

阿豪boy
今天
17
0
云拿 无人便利店

附近(上海市-航南路)开了家无人便利店.特意进去体验了一下.下面把自己看到的跟大家分享下. 经得现场工作人员同意后拍了几张照片.从外面看是这样.店门口的指导里强调:不要一次扫码多个人进入....

周翔
昨天
1
0
Java设计模式学习之工厂模式

在Java(或者叫做面向对象语言)的世界中,工厂模式被广泛应用于项目中,也许你并没有听说过,不过也许你已经在使用了。 简单来说,工厂模式的出现源于增加程序序的可扩展性,降低耦合度。之...

路小磊
昨天
248
1
npm profile 新功能介绍

转载地址 npm profile 新功能介绍 npm新版本新推来一个功能,npm profile,这个可以更改自己简介信息的命令,以后可以不用去登录网站来修改自己的简介了 具体的这个功能的支持大概是在6这个版...

durban
昨天
1
0
Serial2Ethernet Bi-redirection

Serial Tool Serial Tool is a utility for developing serial communications, custom protocols or device testing. You can set up bytes to send accordingly to your protocol and save......

zungyiu
昨天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部