内存数据库内核开发(转载)

转载：http://www.cnblogs.com/konyel/articles/1511133.html

1 初衷

许多人听到内存数据库第一印象就是大型的电信企业，银行的解决方案，但其实内存数据的应用相当广泛，从中型网站并发到批量文件处理都可以有很有效的应用。 在商业领域的内存数据库主要ALTIBASE,与Oracle，TimeSen，但其昂贵的授权费（数十万$）令许多普通用户望而却步。

在这里希望能整合在自身对数据处理业务的，开发并商业化一款面向普通用户的内存数据库，整合文件数据处理，和数据库数据处理，并发高效率处理的内存数据库解决方案。

而开发我们数据库的方向，当然不在于与有十多年根基的TimeSen们竞争，在于开发一款拥有基本功能，具备二次开发的价值 的内存数据处理软件，并提供在批量数据处理，与并发数据处理的解决方案，应该能满足大部分客户的数据处理需求。

以下是内存数据库的简介作者为:智雨青

由于把大多数数据都放在内存中进行操作，使得内存数据库有着比磁盘数据库高得多的性能表现，这一特点非常契合电信企业运营支撑系统对实时性的要求。

电信业的竞争正在全方位地展开，这种竞争必然带来新的价值链模式以及新的计费方式，这些变化对目前的电信运营支撑 系统是一个挑战。比如，多种业务的计费环节将不再是单一的按照时长或通信距离收取费用，而可能是根据时长、内容、使用量等多种参数的组合计费。为了应对这 些挑战，电信企业先后引入了内存数据库，以提高后台数据管理的实时性、精确性和灵活性。

内存数据库

内存数据库，顾名思义就是将数据放在内存中直接操作的数据库。相对于磁盘，内存的数据读写速度要高出几个数量级， 将数据保存在内存中相比从磁盘上访问能够极大地提高应用的性能。同时，内存数据库抛弃了磁盘数据管理的传统方式，基于全部数据都在内存中重新设计了体系结 构，并且在数据缓存、快速算法、并行操作方面也进行了相应的改进，所以数据处理速度比传统数据库的数据处理速度要快很多，一般都在10倍以上。内存数据库 的最大特点是其“主拷贝”或“工作版本”常驻内存，即活动事务只与实时内存数据库的内存拷贝打交道。显然，它要求较大的内存量，但并非任何时刻整个数据库 都存放在内存，即内存数据库系统还是要处理I/O。

尽管内存数据库已不是传统磁盘数据库的概念，但是内存数据库本质上还是数据库，它也具有一般数据库的基本功能:

■ 永久数据的管理，包括数据库的定义、存储、维护等;

■ 完成各种数据操作，如查询处理、存取、完整性检查;

■ 事务管理，包括调度与并发控制等;

■ 对存取的控制和安全性检验;

■ 具有数据库的可靠性恢复机制。

相对于利用程序开发手段调用内存处理来说，内存数据库自有其优势。首先，内存数据库是产品化的数据库管理软件，极 大缩短了开发周期; 其次，内存数据库有着开放的平台和接口，程序开发和移植更加灵活便捷，也便于维护和二次开发; 第三，可以通过使用统一的SQL语言方便地查询内存中的数据; 最后，能在数据库中保障数据的安全性和完整性。这些优势，对于快速部署和简化维护都是有利的。

但内存数据库也有其不可避免的缺点，比如: 不容易恢复，内存数据库中的数据不总是永久的，为了保证实时，也不一定是一致和绝对正确的，有的是短暂的，有的是暂时不一致或非绝对正确的。

电信企业一直是内存数据库的主要用户，近几年来，随着计算机硬件技术的飞速发展、内存容量的提高、价格下跌以及计 算机进入64位时代操作系统后可以支持更大的地址，为内存数据库的实现提供了可能。目前内存数据库在电信行业的应用也日趋成熟，已有超过90G的电信系统 案例，能自动扩展内存空间，不需要重启数据库，提供ESOL自定义存储过程，支持多线程，开发效率高，程序移植容易等等。下面以两个例子来介绍内存数据库 的应用。

电信计费数据的加载

电信的二次批价和实时累账是计费系统中的两个必备功能。所谓二次批价是相对于一次批价来说的。一次批价是按照国家 标准资费来进行价格计算，比如: 全球通每分钟本地通话为0.4元，在一次批价完成后，会根据这个用户的套餐进行再一次的计算。以北京全球通用户接听4分钟的电话为例，一次批价完成后，这 条话单的价格是1.6元，如果这个用户参加了10元包月接听套餐，那么在二次批价后，这次通话的费用就为0元。一次批价是用于各大运营商之间结算的，而二 次批价是针对用户个人的。

实时累账是将用户从每月1号到目前为止的所有费用累加起来，也就是用户目前可以通过10086查到截止到前一天的实时话费。累账值可以帮助用户控制高额话费或是供用户即时查询消费信息。

二次批价和实时累账过程涉及用户资料、用户套餐等与用户相关的信息，电信支撑系统在开始批价时必须加载这些数据。 稍大一点的省级运营商的这些数据就会超过1000万条，计费处理模型也由于套餐的组合、产品的组合以及不同的优惠规则变得相当复杂，加载这部分数据对系统 而言是一笔不小的开销，这就使得现在的计费处理速度比较慢，而且很难做到对数据的实时更新。内存数据库的引入在一定程度上解决了这个问题。

在计费二次批价过程中数据量最大的是详单数据，这部分数据不用放在内存数据库中，每处理完一个话单文件或达到设 定的提交记录数时直接操作磁盘数据库，不会影响系统性能。最急切的是将用户资料、套餐、营业套餐和计费套餐对应关系数据、计费套餐模型数据及用户累计数据 放到内存数据库中，这部分数据查询操作远比数据新增和更新操作要频繁。除了这些数据外，当然还有应用需要的其他数据也都可以加载到内存数据库。

在采用内存数据库后，用户通过营业部或客户查询实时话费的时候完全可以做到实时，比目前只能提供查询到前一天的 实时话费在业务上有了质的飞跃。因为系统在处理这部分数据时查询流程和以前的完全一样，但系统省去了以往内存中的数据和磁盘数据库数据同步的环节，所以就 能做到了实时查询。对于信控来说也同样，以往系统在累完账后要按照一定周期刷新信控数据，这就存在一个时间差，不能够完全做到实时。

而采用内存数据库后，信控可以直接取得内存数据库中的实时话费累计表中的数据，完全实现实时预警、停机。二次批价和累账中采用内存数据库后，对防欺诈、收入保障系统也有相当大的好处，这样能够充分保证运营商的切身利益。

另外，在采用内存数据库后，整体提高了系统批价、累账的处理速度，大大缓解访问磁盘数据库的压力，提高数据查询、修改、删除的效率，也为后付费和预付费的融合提供了可能。

电信计费数据的同步

电信营业数据和计费系统中的数据总是在不断的变化中，这就涉及内存数据库中的数据和磁盘数据库数据的同步问题（为 了描述清楚，这里的磁盘数据库以Oracle DB为例来说明）。数据同步包括两部分: 从内存数据库到Oracle DB数据同步和从Oracle DB到内存数据库的同步。

1. Oracle DB到内存数据库同步

这部分数据同步采用增量表的方式，营业系统或CRM新增或更新的数据将生成到Oracle的增量表中，计费后台程 序先到这些增量表中查询数据。如果能在这些增量表中查到数据就把这些数据更新到内存数据库对应表中，如果查不到，就直接从内存数据库中直接查询，从而保证 了数据的完整性和实时性。由于增量表的数据量一般会很小，所以这部分操作不会影响系统的性能。

2. 内存数据库到Oracle DB同步

由于Oracle的计费后台批价、累账数据几乎都加载到了内存数据库中，所以Oracle数据库对应的数据表将主要用于对内存数据库的数据备份。

用户最新的实时话费等信息都保存在内存数据库中，实时话费查询将直接连接到内存数据库中查询，保证用户得到最新的 费用信息。信控也直接从内存数据库查询数据，因此对Oracle中的这部分数据已经没有实时性的要求。这时内存数据库到Oracle的同步可以由应用程序 生成文件，定时地往Oracle数据库中同步备份，或者采用Oracle 存储过程在系统相对空闲时间段进行数据导入就可以了。

总体而言，由于市场与技术的快速发展，电信业务在不断扩充，其运营和管理不断优化，传统的一些支撑系统的架构已 经逐渐不能满足日益增长的业务要求和客户需求，引入一些新的技术来解决我们生产中遇到的问题是必然的。比如采用内存数据库来代替以前的共享内存技术，使得 原来在内存中不标准的东西，包括接口、格式和管理都标准化了。

内存数据库只是多种新技术中有代表性的一种而已，只要解放思想、选用得当，完全可以在投入不大的情况下克服系统中的瓶颈，以最小的代价获得最大回报。

二次批价内存数据操作流程图

链接一:内存数据库与传统数据库的异同

传统的数据库系统是关系型数据库，开发这种数据库的目的，是处理永久、稳定的数据。关系数据库强调维护数据的完整性、一致性，但很难顾及有关数据及其处理的定时限制，不能满足工业生产管理实时应用的需要，因为实时事务要求系统能较准确地预报事务的运行时间。

对磁盘数据库而言，由于磁盘存取、内外存的数据传递、缓冲区管理、排队等待及锁的延迟等使得事务实际平均执行时间 与估算的最坏情况执行时间相差很大，如果将整个数据库或其主要的“工作”部分放入内存，使每个事务在执行过程中没有I/O，则为系统较准确估算和安排事务 的运行时间，使之具有较好的动态可预报性提供了有力的支持，同时也为实现事务的定时限制打下了基础。这就是内存数据库出现的主要原因。

内存数据库所处理的数据通常是“短暂”的，即有一定的有效时间，过时则有新的数据产生，而当前的决策推导变成无 效。所以，实际应用中采用内存数据库来处理实时性强的业务逻辑处理数据。而传统数据库旨在处理永久、稳定的数据，其性能目标是高的系统吞吐量和低的代价， 处理数据的实时性就要考虑的相对少一些。实际应用中利用传统数据库这一特性存放相对实时性要求不高的数据。

在实际应用中这两种数据库常常结合使用，而不是以内存数据库替代传统数据库。

链接二:几款内存数据库产品

■ Oracle TimesTen

Oracle TimesTen是Oracle从TimesTen公司收购的一个内存优化的关系数据库，它为应用程序提供了实时企业和行业（例如电信、资本市场和国防） 所需的即时响应性和非常高的吞吐量。Oracle TimesTen可作为高速缓存或嵌入式数据库被部署在应用程序层中，它利用标准的 SQL 接口对完全位于物理内存中的数据存储区进行操作。

■ Altibase

Altibase是一个在事务优先的环境中提供高性能和高可用性的软件解决方案。它提供高性能、容错能力和事务管 理能力，特别适合通信、网上银行、证券交易、实时应用和嵌入式系统领域。Altibase能够最大限度地发挥数据库服务系统的潜力，增强数据服务器的处理 能力。Altibase支持客户端/服务器架构或嵌入式架构。其中客户端/服务器架构非常适合一般的应用。而嵌入式架构将应用程序嵌入到数据库服务器，适 合于有高时效要求的实时系统。

■ eXtremeDB

eXtremeDB实时数据库是McObject公司的一款特别为实时与嵌入式系统数据管理而设计的数据库，只有 50K到130K的开销，速度达到微秒级。eXtremeDB完全驻留在主内存中，不使用文件系统（包括内存盘）。eXtremeDB采用了新的磁盘融合 技术，将内存拓展到磁盘，将磁盘当做虚拟内存来用，实时性能保持微秒级的同时，数据管理量在32BIT下能达到20G。

2，由开源软件入手

由于我们当然得不到有关内存数据库处理数据的核心技术，所以我们只能出开源内存数据库入手，研究内存数据的开发，

市面上有两款著名的开源内存数据库 Oracle Berkeley DB 与 SQLite

但使用过的人会发现以上两款数据库有以上的缺点和优点

Oracle Berkeley DB 功能相当成熟，支持高并发，多种读写锁，局部锁，且具有数据原子的完整性保护。

但缺点的不支持sql解析，Oracle 将其定位为强大的不具有DBMS的文件数据处理软件。原因理所当然（不能与自己的Timesen打对台）

SQLite 有较成熟DBMS,当然支持SQL解析 ，但不支持局部锁,读写锁为整个数据库锁定，当然不支持高并发操作等特点,（根据对SQLite的最新文档，SQLite 3.6版本可以支撑数据页级的(page)数据锁，在以后文档中会添加改机制的详细剖析）

那么我们会想到，如果将两款开源软件的优缺点结合，那么我们可以整合出我们的内存数据库的初步形态。

这两个内存数据库都有强大完善的文档，帮助我们了解出其中的机制和接口，进一步加大的整合的可能性。

3,数据库核心 VDBE （Virtual Database Engine）

在此先感谢开源社区的伙计们为我提供非常优秀的理论文档，但在此深表感谢，
正是有你们的无私和博学，人类才能在科学美丽的道路上不断前进。
Eric Niebler， Kevlin Henney，Chris Kohlhoff，John Maddock, Howard Hinnant ，Jeff Garland


First of all,thanks to the open source community guys
to provide the excellent documentation of the database theory for me,
For your selfless and erudite, human can promote himself persistently in the beautiful
road of science.
Eric Niebler， Kevlin Henney，Chris Kohlhoff，John Maddock, Howard Hinnant ，
Jeff Garland

说明：以下文档非专业文档，也非严谨学术论文，只是我在解读数据库技术资料时的自身理解，可能有不少的错误，希望各位高手大侠指正，

首先，我们先明确下VDBE的概念，其实我们在执行sql的过程中，比如Insert的语句时，是由VDBE将命令分拆成数据操作的原子指令（instruction），VDBE将其解析，拆分，排序，才执行出我们最后的结果。而VDBE可以理解为解析这些虚拟机器指令，并执行机器操作的虚拟机。VDBE可以说是数据库技术中最核心的技术，我们完善了一个数据库的VDBE，那么我的征途就胜利了一半了。
但令我惊奇的是VDBE没什么难以理解的高深知识，先人将一个复杂的系统用简单的方法巧妙的实现了。
在这个数据库虚拟机中，每一种指令（instruction）都虚拟机中都是固化的，就是说每一种一执行都是按照固定的逻辑去操作，而每一种指令（instruction）都有五种或数种数据操作（operand）作为操作的参数（我的理解）。而这数种数据操作都是跟虚拟机中的注册机（register）*注1*相关联的。

以下是sqlite文档中提供的数据库指令操作的实例
比如 delete from tbl1 where two<20;
我们执行以上这条简单的语句。
addr opcode p1 p2 p3 p4 p5 comment
---- ------------- ---- ---- ---- --------- -- -------
1 Goto 0 20 0 00
2 OpenRead 0 2 0 00 tbl
3 SetNumColumns 0 2 0 00
4 Rewind 0 11 0 00
5 Column 0 1 2 00 tbl.two
6 Integer 20 3 0 00
7 Ge 3 10 2 cs(BINARY) 6a
8 Rowid 0 1 0 00
9 FifoWrite 1 0 0 00
10 Next 0 5 0 00
11 Close 0 0 0 00
12 OpenWrite 0 2 0 00 tbl
13 SetNumColumns 0 2 0 00
14 FifoRead 1 18 0 00
15 NotExists 0 17 1 00
16 Delete 0 1 0 tbl 00
17 Goto 0 14 0 00
18 Close 0 0 0 00
19 Halt 0 0 0 00
20 Transaction 0 1 0 00
21 VerifyCookie 0 1 0 00
22 TableLock -1 2 0 tbl 00
23 Goto 0 2 0 00
数据库中执行以上机器指令列表
其中的opcode就是如上说的机器指令，而 p1,p2,p3,p4,p5 就是数据操作，我将其理解为我们程序中函数的参数。
我先逐个介绍下指令的功能
Goto：跳转至p2所指的指令地址（Addr）
Transaction：这个我们很眼熟，开启一个事务，P1是数据库的Id,0为主数据库，1，2为附加关联的数据库，如果
P2为非0值，代表一个写事务开始执行，这时操作会提交一个（RESERVED lock）乐观锁，没有一个进程可以执行写
事务。如果P2大于等于2，那么事务会提交一个（EXCLUSIVE lock）悲观锁，即其他进程不能读也不能写。
OpenRead:为一个数据表打开一个只读的数据库游标，根数据叶（root page）是数据操作P2。
Rewind：读取数据表或索引的第P1个实体，如数据表或索引为空，且P2大于0，指令地址跳转至p2,如果P2为0并数据表
或索引为空跳转至下一个地址的指令。
SetNumColumns：根据P2设定游标的列数
等等，指令的意思就不一一解释了，有兴趣的同学可以参看sqlite文档,
该内容也相当重要，也许在后面的版本我会将指令的内容补全


VDBE正是将一个个简单的数据操作，执行出delete from tbl1 where two<20;的动作。

那么我们可以知道了VDBE究竟做了什么东西

从图上我们可以看到，我们数据库的内核是由三部分构成，
1，实现我们熟悉嵌入sql语句的c\c++接口。
2，将sql语句解析成各个虚拟机指令（instruction），多亏了SQLite我们有一个优秀的解析器可以借鉴。
3，由VDBE去实现各个机器指令的算法。说白了就是一个又一个的C函数。

注1：又一个重要的机制，我稍后补充文档。

4，sql解析器初步设计文档

在构思sql 解析器之前，参看了sqlite的相关文档，sql解析器的难度在于脚本与C逻辑的复杂映射关系，在这里sqlite为我们提供了一个可借鉴的解决方案，就是C代码的脚本生成器，以下给出我大致构思的流程图

1，首先用逻辑分支，将语句中的符号归类，构建语法树 。

2，将逻辑脚本生成C语言，让程序获取解析sql脚本的能力。

3，解析器调用程序逻辑，执行VDBE指令。

内存数据库内核开发 工作日志（innodb的原理，算法详细剖析）(九)
几个星期来一直在数据库文档的大海中浸泡，突然发现我还是没能深入到数据库内核开发的真正核心，始终停留在sqlite这个简单的框架无法突破,我需要重新思考一个新的切入点，最开始研究SQLite数据库，收获是数据库引擎开发的基本原理，虚拟机，代码生成，B-tree的各种算法，但当我考虑拓展其功能时我傻眼了，我没有一种专业的手法去扩展其中一种功能，比如，当我想把并发控制由整个数据的数据锁拓展到表级甚至行级时，就束手无策了。
我们必须从专业数据库去了解数据库的每个方面，才能从整体把握。
数据库内核开发的最艰难的一步就是从借鉴到创新，对于打算商业的数据库，以sqlite为模版还是太业余了，最后必须从商业的数据库入手来改造.
innodb的简单介绍请参照(内存数据库内核开发 工作日志（Mysql的架构体系初读）(八))
innodb的原理，算法详细剖析大致内容如下，innodb代码很有来头，是现oracle副总裁Heikki Tuuri写的,嘿嘿
重要的技术部分包括以下几个要点，要做出出色专业的内存数据库，单单要改造sqlite就成功是不对的，一定要把每一部分摸清摸透。
现在进度目前是停留在以下数据库各模块的操作关联，所幸代码并不难读，很快的这样标题会逐个加上链接来分析具体的实现。
1，内存管理
2, 缓存池
3，B-tree操作
4，数据页
5，事务
6, 日志
7, 系统IO （磁盘操作）
8, 数据字典
9，解析器 （脚本详细）
10，数据锁
11, 数据库数据类型定义

ps:很多人多觉得自己做数据库是幼稚的,山寨的，不切实际的，事实上也是困难重重，但你要知道innodb也就Heikki Tuuri一个人就啃出来的,为了我最爱的数学，我依然想再坚持一下，虽然有点孤单,但充满求知的快乐。

之前由于考虑到使用Page的内存和磁盘互换的机制实现了B-tree做为数据库的键值索引，在真实的生产环境下2000万以上的数据建立索引会使到B-tree层数增多，效率明显下降，在运算工程中使用AIX大型机都用了数天才将2000多万的数据生成出来，效果非常不理想。
全新的框架采用了纯内存的红黑树作为数据的索引，效果很好，性能测试中，用thinkpad 201i 电脑建立1000万的红黑树只用了3分钟，消耗内存270M这在电信项目的生产环境是完全可以接受的。
该代码使用内存池和红黑树的技术，参考主要文献包括：
http://zh.wikipedia.org/zh/%E7%BA%A2%E9%BB%91%E6%A0%91 维基百科
IBM文章，http://www.ibm.com/developerworks/cn/linux/l-cn-ppp/index6.html
当然网上许多人的实现也给了我很好的启示，恕在下不能一一列出。
也许你会说，不就实现了STL MAP的功能吗？可以这么说，因为内存中建立数据结构，红黑树是最优的方案，我只能使用这样的---像map一样的东西。
以下是大致实现代码的思路，使用内存池来存放两类数据，一类是存放红黑树节点的内存池，一类是存放键值节点的内存池。

实例代码并不是用于项目中的实现，而是呈现内存索引的DEMO,其中delete的实现我没有实现内存释放，读者可以自己添加,相信它是网上能找到的最好，最清晰的红黑树能直接编译并稳定使用的代码，网上文章的代码都有这样那样的问题，最后还是根据理论自己实现了。

很多朋友对于内存数据库开发Email给我不能一一回复很抱歉，希望代码对各位有帮助。

另外内存池的代码请参考我的另一篇文章，内存池的实现 内存池完整实现代码及一些思考