分布式内存数据库设计与实现

分布式内存数据库设计与实现 西安电子科技大学 学位 论文 政研论文下载论文大学下载论文大学下载关于长拳的论文浙大论文封面下载 创新性声明 秉承学校严谨的学分和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果;也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名: 日期 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即:研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 留送交论文的复印件，允许查阅和借阅论文;学校可以公布论文的全部或部分内 容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后 结合学位论文研究课 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 再攥写的文章一律署名单位为西安电子科技大学。 (保密的论文在解密后遵守此规定) 本学位论文属于保密，在 年解密后适用本授权书。 本人签名: 日期 导师签名: 日期 摘 要 信息系统基于大数据量的数据采集与分析，需要数据库系统能够同时具备大 容量存储、实时性处理以及可扩展性的能力。传统的关系数据库在面对日益增多 的大量数据时暴露了很多问题，不能对其高效、实时的处理。对系统提出的新需 求，传统的关系数据库并不能很好的解决。 非关系型数据库是为弥补关系数据库的不足而产生的，Key-Value 数据库就 是非关系型数据库的一种。目前现有的 Key-Value 型内存数据库系统对于小数据 量的处理速率和实时性较好，但是对大数据量的处理能力还稍显不足，不能满足 当前系统的需求。 因此，本文通过分析用户需求，分析当前 Key-Value 型内存数据库的不足之 处，将分布式技术与内存数据库技术相结合，设计并实现了一种分布式内存数据 库。本文首先对系统架构与系统功能进行设计和论述。其次，详细设计并实现了 分布式管理节点中的分布式数组模块、消息包转发模块和内存数据库节点中的内 存资源管理模块、业务处理模块等主要模块。在解决分布式系统的数据分布问题 上，提出了一种用分布式数组来管理数据分布的方法。在解决系统数据索引的问 题上用哈希算法来实现。再次，对系统的功能和性能进行测试，并给出了测试结 果。最后，总结本文的不足之处和后续改进点。 关键词: 内存数据库 分布式技术 哈希算法Key-Value Abstract Information systems have the requirement of a large amount of data’s collection and analysis, which need the database system having the ability of large capacity storage, real-time processing and scalability. The traditional relational databases expose a lot of problems when it process a large amount of data, which can not process data efficiently. Therefore, the traditional relational database can not solve the new demands of the information system. Non-relational database compensate the shortage of a relational database. Existing Key-Value main memory database system have good ability of processing a small amount of data, but not good at processing a large amount of data, which can not meet the new demand of the current system . Therefore, we analyze user requirement, the shortage of current Key-Value main memory database and the technology of distributed system, implement a kind of distributed main memory database. Firstly, we design and describe the system architecture and functions. Secondly, we focus on the detailed design and implementation of the distribution array module, the message transfer module, main memory resource management modules and business processing module. In order to solve the problems of data distribution of distributed systems, we put forward a distribution array method with hash algorithm to solve the problems. Thirdly, test the functionality and performance of the system, and give the test results. Finally, summarize the shortage of this paper and the improvement aspect. Keywords: MMDB Distributed Technology Key-Value Hash Algorithm 目 录 第一章 绪论..............................................................................................................1 1.1 选题背景......................................................................................................1 1.2 选题研究意义 ..............................................................................................2 1.3 国内外研究现状 ..........................................................................................4 1.4 论文工作内容 ..............................................................................................5 1.5 论文结构......................................................................................................6 第二章 分布式内存数据库相关技术 .......................................................................9 2.1 分布式数据库 ..............................................................................................9 2.1.1 分布式数据库的定义 .........................................................................9 2.1.2 分布式数据库的特点 .........................................................................9 2.2 内存数据库 ................................................................................................10 2.2.1 内存数据库的定义 ...........................................................................10 2.2.2 内存数据库的特点 ........................................................................... 11 2.3 哈希表........................................................................................................13 2.3.1 哈希表的定义...................................................................................13 2.3.2 哈希表常用构造算法 .......................................................................13 2.3.3 哈希表冲突处理的常用算法 ...........................................................14 2.4 FNV 哈希算法 ............................................................................................15 2.5 本章小结....................................................................................................16 第三章 分布式内存数据库系统需求分析与设计 ..................................................17 3.1 系统需求分析 ............................................................................................17 3.1.1 系统功能需求...................................................................................17 3.1.2 系统功能用例...................................................................................18 3.2 系统总体设计 ............................................................................................21 3.2.1 系统架构设计...................................................................................21 3.2.2 系统功能设计...................................................................................23 3.3 分布式数组模块设计.................................................................................24 3.3.1 分布式数组模块原理 ........................................................................25 3.3.2 分布式数组的初始化流程 ................................................................26 3.3.3 分布式数组的维护机制 ....................................................................29 3.4 消息包转发模块设计.................................................................................30 3.5 内存资源管理模块设计.............................................................................31 3.5.1 内存资源初始化过程 ....................................................................... 31 3.5.2 内存资源申请过程 ........................................................................... 32 3.5.3 内存资源回收过程 ........................................................................... 33 3.6 业务处理模块设计.................................................................................... 34 3.6.1 新增数据过程................................................................................... 34 3.6.2 数据查询和修改过程 ....................................................................... 34 3.6.3 数据删除过程................................................................................... 35 3.7 本章小结 ................................................................................................... 35 第四章 系统实现 ................................................................................................... 37 4.1 分布式数组模块关键技术实现 ................................................................ 37 4.1.1 分布式数组管理表结构定义............................................................ 37 4.1.2 分布式数组相关算法实现 ............................................................... 38 4.1.3 分布式数组初始化和维护流程实现 ................................................ 39 4.2 消息包转发模块关键技术实现 ................................................................ 42 4.3 内存资源管理模块关键技术实现............................................................. 43 4.3.1 内存资源管理模块类图 ................................................................... 43 4.3.2 内存资源初始化过程实现 ............................................................... 44 4.3.3 内存资源申请过程实现 ................................................................... 44 4.3.4 内存资源回收过程实现 ................................................................... 45 4.4 业务处理模块实现.................................................................................... 46 4.4.1 新增数据过程实现 ........................................................................... 46 4.4.2 数据查询和修改过程实现 ............................................................... 47 4.4.3 数据删除过程实现 ........................................................................... 48 4.5 本章小结 ................................................................................................... 49 第五章 系统测试 ................................................................................................... 51 5.1 测试方法 ................................................................................................... 51 5.2 测试环境 ................................................................................................... 51 5.3 测试内容与结果 ....................................................................................... 51 5.4 本章小结 ................................................................................................... 54 第六章 总结与展望 ............................................................................................... 55 致 谢 .................................................................................................................... 57 参考文献 ................................................................................................................ 59 第一章 绪论 1 第一章 绪论 1.1 选题背景 随着科学技术的飞速发展，信息化已逐渐渗透入工作、生活的各个领域。基 于现有信息系统对大数据量的数据采集与分析的要求，使得数据库系统要处理的 数据量、信息量急剧增长，这对数据库的数据存储和运算速度提出了新的要求， 即要满足大容量存储和实时性、可扩展性处理。从而对数据的存储和管理提出了 新的挑战。 针对这一新应用的需求，现有系统通常并不需要数据库具有强大而完备的功 能和进行非常复杂的事物处理的能力，却需要数据库具备能在指定时刻或时间内 对大量甚至海量的数据进行采集、处理并能正确响应的高速性能特性。传统的关 系数据库在应付日益增长的大量数据时暴露了越来越多难以克服的问题，例如: 传统的关系数据库可以应付上万次 SQL 查询，但是应付上万次 SQL 写数据请 求，硬盘 I/O 就已经无法承受了 [1] 。对于关系数据库来说，在如此海量的信息中 进行 SQL 查询，效率是极其低下乃至不可忍受的。并且关系数据库具有固定的 表结构，因此，其扩展性极差，而在大多数数据通信软件中，系统的升级，功能 的增加，往往意味着数据结构的巨大改动，这一点关系型数据库也难以应付，需 要新的结构化数据存储。因此，研究开发适用于新应用的数据管理的新型数据库 十分必要。 随着近些年来半导体产业的迅猛发展，使得存储器芯片的集成度越来越高， 一方面，存储器芯片的价格变得越来越便宜，存储量很大而且廉价的内存在市场 上不断出现，并且内存的存储量不断增大而价格却越来越低的趋势似乎还在延续 [ 2] ;另一方面，目前计算机广泛使用的 32 位操作系统使得它能提供 4G 的地址 空间，因而每个进程能够对 4G 内存进行寻址，而 4G 内存完全能够容纳一般应 用的数据库保存其数据所需的空间。而且，目前 64 位的操作系统也已经推向了 市场，并能够逐渐取代 32 位操作系统。64 位的操作系统使得系统能够为进程提 64 64 供 2 的地址空间，即每个进程能够对 2 大小的内存进行寻址，相比较于 32 位 操作系统其内存可寻址的空间有了很大程度的提高。因此，随着硬件的能力的不 断升级和制造成本的降低，完全可以将数据库的全部数据保存在内存中 [3] 。而内 存数据库(Main Memory Database，MMDB)，顾名思义就是将数据放在内存中 直接操作的数据库 [ 4] 。通过将数据完全存储在内存中或其工作版本常驻在内存 中，可以极大的提高系统的性能。相对于磁盘，内存的数据读写速度要高出几个 数量级，将数据保存在内存中相比从磁盘上访问能够极大地提高应用的性能。同 分布式内存数据库的设计与实现 2 时，内存数据库摒弃了磁盘数据管理的传统方式，基于全部数据都在内存中重新 设计了体系结构，并且在数据缓存、快速算法方面也进行了相应的改进，所以数 据处理速度比传统数据库的数据处理速度要快很多，一般都在 10 倍以上 [5] 。 与此同时，由于单个计算机节点的限制，传统关系数据库系统的可扩展性局 限于单个节点上的逻辑扩展，并不能在计算能力、存储资源上进行扩展，这对系 统的容量和可扩展性都带来了限制。随着分布式数据存储技术和数据管理技术迅 速的发展，使得数据库系统并不仅限于单个的计算机节点，它能够使系统扩展到 多个物理节点，构成一个计算机网络来共同存储数据，实现大容量存储;还可以 根据存储容量的大小灵活调整节点的数量。因此，分布式技术能很好的满足数据 库系统基于可扩展性与大容量的需求。 因此，基于上述新应用的需求和应用环境的成熟，迫切需要开发将分布式技 术与内存数据库技术相结合的非关系型数据库系统，即分布式内存数据库系统， 来解决系统对大容量、实时性和可扩展性的需求。 1.2 选题研究意义 [6] ，又称数据获取，是利用一种装置，从系统外部采集数据并输入 数据采集 到系统内部的一个接口，对其进行分析处理。被采集的数据是已被转换为电讯号 的各种物理量，如温度、水位、风速、压力、坐标信息等，这些大量的数据信息 被发送到上位机系统后，需要系统能够对数据进行实时存储和实时处理，并且能 够根据存储容量的大小进行实时的调整，因此对上位机系统的数据存储和处理能 力提出了更高的要求。 从单机角度来看，传统的关系型数据库系统由于其整体的设计和实现较为复 杂，尤其是数据库本身的物理设计，这些复杂度大大增加了输入/输出开销，也 导致底层访问效率难以被优化;而内存数据库系统将数据保存在内存中，相比从 磁盘上访问数据能够极大地提高系统的处理能力;从多机角度看，传统的关系模 型导致数据之间难以切分，从而造成数据库无法扩展，最终导致性能瓶颈，因此 开发人员从这个角度着手改造数据库，NoSQL 的概念就是由此产生。NoSQL [7 ] 概 念的普及源于 2009 年的一次数据库会议，设定 NoSQL 是一种非关系型的分布式 的数据库设计模式。作为 NoSQL 模型的一种主要类型，Key-Value 数据库的应 用范围较为广泛，Key-Value 是为了弥补关系型数据库的不足而产生的，比起关 系型数据库，Key-Value 在性能和可扩展性方面有着天生的优势，可用于构建大 规模的分布式集群，从而支持海量的数据存储和查询。 本文为了提高内存数据库系统的处理效率，采用非关系型的Key-Value型内 存数据库。目前现有的Key-Value型内存数据库系统对于小数据量的处理速率和 第一章 绪论 3 实时性较好，但是对于分布化的考虑不多，更没有同下层的基础设施(硬件、操 作系统，运行时等)综合考虑。而事实上存储服务作为信息处理的根基，一方面 常常使用数量庞大的服务器支撑，另一方面往往面临数据和访问量的高速增长， 因此软件层的设计和基础设施会互相影响，如果考虑不周，没有在设计和架构上 将两者综合考量，软件层和基础设施往往会相互制约，极大的影响集群的部署和 稳定性，甚至对数据中心本身也会造成影响。对于数据采集系统而言，数据量往 往比较大，现有的Key-Value型内存数据库不能很好的满足系统需求。因此，本 文针对现有Key-Value型内存数据库无法同时满足实时性、大容量、可扩展性的 问题，从此角度出发设计系统，突出主要功能需求，用原型化的软件开发模型， 设计了一种Key-Value型分布式内存数据库，并提出了一种用分布式管理节点来 实现分布式的方法以扩展系统的容量，得到大容量的数据存储，实现了系统主要 功能需求。由此，证明了本文的Key-Value型分布式内存数据库的设计是可行的。 一旦成功实现这种分布式内存数据库系统之后，将会给系统和软件平台带来以下 好处: 1(提高系统消息路由效率 分布式管理节点作为分布式内存数据库系统的中心节点，负责路由消息到指 定的内存数据库，分布式管理节点采用哈希算法来实现消息的路由，算法执行效 率高。应用于大型的分布式系统时，中心节点能明显提高消息路由效率。 2(提高系统的访问效率 本文设计的分布式内存数据库系统，对数据的存储与管理均放在内存中进 行，而且消息的路由和内存中数据的存储均用Key-Value型的哈希表结构，而哈 希表的理想时间算法复杂度是O(1)，索引时速度更快，处理效率更高。 3(提高系统的可扩展性 本文设计的分布式管理节点，后期应用于分布式网络系统中，能够管理分布 式内存数据库系统中消息的转发，根据存储容量的大小调整节点的数量，提高系 统的可扩展性。在系统需要扩容时，只需要增加一个或几个内存数据库节点就能 够提高系统的整体容量;在系统不需要大容量存储时，可以减少一个或几个内存 数据库节点降低系统的整体容量。 4(提高系统可移植性 分布式内存数据库系统全套代码由C语言实现，在Windows操作系统和Linux 操作系统之间，代码的可移植性较强，方面后续跨平台应用。 5(方便后续开发应用 由于系统开发采用的是原型化的设计模型，作为项目前期的工作，为项目后 续的开发提供了有力的支持，方便了后续的开发应用。 分布式内存数据库的设计与实现 4 1.3 国内外研究现状 目前市场上存在的 NoSQL 数据库主要为商用数据库, 表 1.l 列举了较为典型 和常见的 NoSQL 数据库类型: 表 1.1 主要的 NoSQL 数据库类型 类型 特点 代表性的数据库 文档存储 存储的内容是文档型的，数据库可以解析 MongoDB 其结构并进行建立索引等操作，从而实现关系 (Document Store) CouchDB 数据库的某些功能。 列存储 按列存储数据，最大的特点是方便存储结构化 Hbase 和半结构化数据，方便做数据压缩，对针对某 (Column Families) Cassandra 一列或者某几列的查询有非常大的IO优势。 Hypertable Key-Value存储 通过key映射到value的内容，通常数据库不需 Redis (Key Value) 了解value的结构，对value的解析交由客户进 Tokyo Cabinet/Tyrant 行。 MemcacheDB ) k ) 下面对几种代表性的 NoSQL 型数据库进行简要的介绍。 查询数据 用例名称 1. Redis Redis [8] 是一个使用C语言开发的内存型数据库，其本质上是一个Key-Value 类型的内存数据库，很像memcached，整个数据库统统加载在内存当中进行操作， 定期的通过异步IO操作把数据库数据写回到硬盘上进行保存。由于Redis是内存 型数据库，其性能非常好，官方给出的数字是每秒可以处理超过数万次的读写操 作，是性能最好的Key-Value数据库之一。有很多著名的网站使用了Redis，如 Github等。Redis最大的特色是保存数据时支持各种数据结构，如List链表、有序 集合和哈希表等数据结构，而且还支持对这些数据结构进行各种操作，例如从List 两端push和pop数据，取List区间，排序等等，对Set支持各种集合的并集交集操 作。此外，在Redis中单个value的最大限制是1GB，不像memcached只能保存1MB 的数据，因此Redis可以用来实现很多有用的功能，比方说用它的List来做FIFO 双向链表，实现一个轻量级的高性能消息队列服务，用它的Set可以做高性能的 Tag系统等等。另外Redis也可以对存入的Key-Value设置过期时间，因此也可以被 当作一个功能加强版的memcached来用。 Redis 的主要缺点是数据库容量受到物理内存的限制，不能用作海量数据的 高性能读写，并且它没有原生的可扩展机制，不具有 scale(可扩展)能力，要 依赖客户端来实现分布式读写，因此 Redis 适合的场景主要局限在较小数据量的 高性能操作和运算上。 第一章 绪论 5 2. Tokyo Cabinet 和 Tokyo Tyrant Tokyo Cabinet [9] 和Tokyo Tyrant的开发者是日本人Mikio Hirabayashi，主要被 用在日本最大的SNS网站mixi.jp上。Tokyo Cabinet发展的时间比较早，现在已经 是一个非常成熟的项目，也是Kye-Value 数据库领域最大的热点，现在被广泛的 应用在很多网站上。Tokyo Cabinet是一个高性能的存储引擎，它除了支持 Key-Value存储之外，还支持保存哈希表数据类型，因此很像一个简单的数据库 表，并且还支持基于列的条件查询、分页查询和排序功能，基本上相当于支持单 表的基础查询功能了，所以可以简单的替代关系数据库的很多操作，这也是Tokyo Cabinet受到大家欢迎的主要原因之一。Tokyo Cabinet在mixi的实际应用当中，存 储了2000万条以上的数据，同时支撑了上万个并发连接，是一个久经考验的项目。 Tokyo Cabinet在保证了极高的并发读写性能的同时，具有可靠的数据持久化机 制，同时还支持类似关系数据库表结构的hashtable(哈希表)以及简单的条件， 分页和排序操作，是一个很棒的NoSQL数据库。 Tokyo Cabinet的主要缺点是在数据量达到上亿级别以后，并发写数据性能会 大幅度下降，尤其是当数据量上亿条的时候，TC性能开始大幅度下降。 3. Berkeley DB Berkeley DB [10] 数据库系统简单、小巧、可靠、高性能，提供了一系列应用 程序接口，应用程序和Berkeley DB 所提供的库在一起编译成为可执行程序。每 一个记录由关键字和数据(KEY/VALUE)组成的键值对构成。 它的缺点是，其提供的数据类型过于单一，键值记录构成比较单一，不方便 数据库内部管理数据，也同时增加了外部应用对于数据的管理成本。 4. MongoDB MongoDB [11] 是一个介于关系数据库和非关系数据库之间的产品，是非关系 数据库当中功能最丰富，最像关系数据库的。他支持的数据结构非常松散，是类 似 json的bjson格式，因此可以存储比较复杂的数据类型。Mongo最大的特点是 他支持的查询语言非常强大，其语法有点类似于面向对象的查询语言，几乎可以 实现类似关系数据库单表查询的绝大部分功能，而且还支持对数据建立索引。 Mongo主要解决的是海量数据的访问效率问题，根据官方的文档，当数据量达到 50GB以上的时候，Mongo的数据库访问速度是MySQL的10倍以上。 Mongo 的并发读写效率不是特别出色，根据官方提供的性能测试表明，大约 每秒可以处理 0.5 万,1.5 次读写请求。 1.4 论文工作内容 本文主要研究分布式内存数据库的设计与实现，在整个过程中主要完成以下 分布式内存数据库的设计与实现 6 工作: 1. 分析分布式内存数据库系统的业务需求 在分析项目背景和业务现状的基础上，站在用户的角度，仔细并反复分析了 系统的功能与性能需求，确定了系统的核心需求，为后续的开发工作提供了良好 的设计基础。 2. 设计分布式内存数据库系统的架构和功能模块 在系统整体需求分析的基础上，设计了分布式内存数据库系统的整体架构， 并根据逻辑分工进行功能模块化分解，重点对分布式管理节点中分布式数组模 块、消息包转发模块以及 MMDB 中内存资源管理模块和业务处理模块的进行详 细设计。 3. 分布式内存数据库系统实现 根据系统设计，对分布式管理节点中分布式数组模块、消息包转发模块以及 内存数据库中内存资源管理模块和业务处理模块的实现进行详细论述。 4. 系统运行并给出测试结果 当前数据库系统做完以后，需要对系统进行各项软件测试，包括功能测试， 性能测试等，以验证系统是否满足需求，达到了系统设计的目标。 1.5 论文结构 论文共分为六章，各章主要内容如下: 第一章:绪论。阐述论文的选题背景及研究意义、国内外研究现状分析及论 文主要的工作内容和组织结构。 第二章:分布式内存数据库相关理论及技术简介。简要描述了项目开发过程 中涉及到的一些相关理论和关键技术，其中包括分布式技术、内存数据库技术、 哈希表等。 第三章:分布式内存数据库系统需求分析与设计。从系统用户的角度出发， 对分布式内存数据库进行详细、切合实际的需求分析，并在需求分析的基础上， 对分布式内存数据库的整体架构等进行设计，按照功能分解结构细化、模块化系 统功能，并对各个模块进行再划分。重点对分布式数组模块、消息包转发模块、 内存资源管理模块、业务处理模块等关键模块进行详细设计。 第四章:系统实现。按照系统的架构设计和功能设计，对分布式内存数据库 系统中分布式数组模块、消息包转发模块、内存资源管理模块、业务处理模块等 关键模块的实现进行具体的阐述。 第五章:系统测试。阐述系统运行和部署环境，采用测试用例对分布式内存 数据库进行软件测试，并得出测试结论。 第一章 绪论 7 第六章:结束语。总结了本文的主要工作，指出工作的不足及进一步的改进 方向。 分布式内存数据库的设计与实现8 第二章 分布式内存数据库相关技术 9 第二章 分布式内存数据库相关技术 2.1 分布式数据库 2.1.1 分布式数据库的定义 分布式数据库 [12] 是由一组数据组成的，这组数据分布在计算机网络的不同计 算机上，每个计算机中的数据组成了自己的数据库单元，在网络中被连接起来的 数据库单元叫做节点或站点。计算机网络中的每个节点具有独立处理的能力，称 为场地自治，它可以执行局部应用，同时，每个节点也能通过网络通信子系统执 行全局应用。 这个定义强调了场地自治性以及自治场地之间的协作性。这就是说，每个场 地是独立的数据库系统，它有自己的数据库，自己的用户，自己的 CPU，运行 自己的数据库管理系统，执行局部应用，具有高度的自治性，同时又相互协作组 成一个整体。这种整体性 [13] 的含义是:对于用户来说，一个分布式数据库系统 逻辑上看如同一个集中式数据库系统一样，用户可以在任何一个场地执行全局应 用。 分布式数据库系统是在集中式数据库系统成熟技术的基础上发展起来的，但 不是简单地把集中式数据库分散来实现，它是具有自己的性质和特征的系统。 2.1.2 分布式数据库的特点 (数据独立性 1 分布式数据库系统中，每个系统节点都具有数据独立性。数据独立性包括了 数据的逻辑独立性和物理独立性，逻辑独立性是指用户的应用程序与数据库的逻 辑结构是相互独立的，即当数据的逻辑结构改变时，用户程序也可以不变;物理 独立性是指用户的应用程序与存储在磁盘上的数据库中数据是相互独立的。即， 数据在磁盘上怎样存储由 DBMS 管理，用户程序不需要了解 ，这样当数据的物 理存储改变了，应用程序不用改变。 2. 分布透明性 分布式数据库还具有分布透明性，该特性使用户不必关心数据的逻辑分片， 不必关心数据物理位置分布的细节及局部场地上数据库支持哪种数据模型。分布 透明性的优点显而易见;有了分布透明性，用户的应用程序书写起来就如同数据 没有分布一样，当数据从一个场地移到另一个场地时，不必改写应用程序，当增 加某些数据的重复副本时，也不必改写应用程序。 分布式内存数据库的设计与实现 10 3. 节点自治性 构成分布式数据库的每一个物理数据库都是独立的，可以由数据库管理员分 别进行管理，如同一个非网络本地数据库。 4(复制透明性 用户不用关心数据库在网络中各个节点的复制情况。被复制的数据，一般更 新都由系统自动完成，在分布式数据库系统中，可以把一个场地的数据复制到其 他场地存放，应用程序可以使用复制到本地的数据在本地完成分布式操作，避免 通过网络传输数据，从而提高了系统的运行和查询效率。但是对于复制数据的更 新操作，就要涉及到对所有复制数据的更新。 5(易于扩展性 在大多数网络环境中，单个数据库服务器最终会不满足使用。如果服务器软 件支持透明的水平扩展，那么就可以增加多个服务器来进一步分布数据和分担处 理任务。 2.2 内存数据库 2.2.1 内存数据库的定义 内存数据库 [14] (Main Memory Database，简称 MMDB)，简单定义就是将数据 完全加载到内存，在内存中实现对数据进行管理的数据库。这是一个较新的研究 领域，与以往的磁盘数据库不太一样。目前，对于内存数据库的定义有以下几种 不同的观点 [15] : 观点一，整个数据库全部常驻内存，存取数据时无须 I,O 操作。这就要求 内存足够大，以容纳数据库的所有数据。 观点二，数据库常驻磁盘，在事务执行前将所需数据集调入内存，提交时所 有对数据库的修改必须写回磁盘。 观点三，数据库常驻磁盘，在内存中开辟一个大缓冲区或缓存(Cache)，通 过适当的缓冲管理以减少内外存 I,O 操作。 目前，大多数内存数据库都是基于第一种观点的。然而在很多现实应用中， 往往难以保证内存总是能够容纳整个数据库。因此，内存数据库的含义必须包含 内存不足以容纳整个数据库的情形。所以我们认为，内存数据库的本质特征是其 主拷贝或“工作版本”常驻内存。内存数据库的定义不应涉及内存的大小、I,O 次数及数据被调入内存的时机等。据此，我们给出如下定义。 定义 [16] :设有数据库 DB，DBM(t)是 t 时刻 DB 在内存中的数据集，DBM(t) 是 DB 的子集;TS 为所有事务的集合，AT(t)是 t 时刻的活动事务集，AT(t)是 TS 第二章 分布式内存数据库相关技术 11 的子集:PT, AT(t)，Dt(T)为 T 在 t 时刻的操作数据集，Dt(T)是 DB 的子集;若 在任一时刻 t，均有:PT, AT(t)，Dt(T)是 DBM(t)的子集成立，则称 DB 为一个 内存数据库，简记为 MMDB。 即按此定义， MMDB 的“工作版本”(当然也可以是整个数据库)常驻内存， 任何一个事务在执行过程中没有内外存间的数据 I,O。因此它需要一定的内存 容量，但并不要求整个数据库都必须常驻在内存。需要指出的是，传统的磁盘数 据库即使缓冲区足够大，以致可以容纳所有数据也不能算是一个 MMDB。因为 它是针对磁盘特性、在数据库常驻磁盘的假定下设计的。例如，索引结构还是针 对磁盘存取的，数据的存取仍必须经过缓冲区管理等。 内存数据库的组织与管理要求新的适于内存特点的数据结构和算法，对于数 据的组织与安置、数据库存取、内外存数据交换、查询处理及优化、并发控制及 数据库恢复都需要研究新的策略与机制。 2.2.2 内存数据库的特点 内存数据库有效地解决了基于磁盘的数据库中 CPU 和磁盘 I,O 之间的主要 矛盾，内存中数据读写的速度比磁盘要高出几个数量级，将数据保存在内存中相 比从磁盘上访问数据能够极大地提高应用的性能。同时，内存数据库抛弃了磁盘 数据管理的传统方式，以全部数据都在内存中的指导思想为基础，对数据库的体 系结构进行重新设计 [17] ，并且在数据组织结构、索引技术、并行操作等方面也 进行了相应的改进，所以数据处理速度比传统数据库的数据处理速度要快很多。 基于磁盘的数据库，磁盘上的数据在访问之前通过缓存技术加载到内存中;内存 数据库，内存中的数据全部放在内存中或主版本常驻内存，为了实现数据的持久 化，有的 MMDB 会在磁盘上建立拷贝。 内存数据库与基于磁盘的数据库有很多不同，比如计算机上的内存和磁盘在 物理机制上就有很大的不同，这些不同之处影响了数据库的设计、实现和性能。 简要说来，内存和磁盘有如下一些不同之处 [18] : 1. 磁盘属于永久存储介质，在断电后磁盘中的数据将继续保持。而内存属 于易失性存储介质，断电之后内存中的数据就将全部丢失。但目前，也有非易失 性内存，它们在断电之后仍将保持原有的数据。非易失性内存的访问速度在内存 和磁盘之间。 2. 磁盘为机械结构，每次访问数据时都需要有磁头寻道和定位的过程。这 使得磁盘访问的代价很高。但是磁盘的访问代价又相对固定，与访问的数据量无 关。即便是访问一块数据中的若干数据，也会将整块数据读取(一页数据)，因此 磁盘是块用户。而内存不是块用户，它的最小数据访问单位是字节。 分布式内存数据库的设计与实现 12 3. 由于磁盘的物理机械方面的原因，使得磁盘的访问速度比内存的访问速度 慢数十倍。 4. 磁盘中的数据存储方式与内存中的数据存放方式有着显著的不同。磁盘是 块用户，访问磁盘中连续存储的数据的效率明显高于访问随机存储的数据，这需 要所访问的数据要尽可能的连续才能获得较高的访问性能。而在内存中，对被访 问数据的连续存放没有特别的要求。总体上讲，访问内存中连续存放的数据和随 机存放的数据，在性能上只有少量的差别。 5. 内存中的数据能被处理器直接访问，而磁盘中的数据不能被处理器直接访 问。因此，当软件出错时，软件可能会任意破坏内存中的数据，却并不能直接破 坏磁盘中的数据。可以说，磁盘和内存的这些差异，影响了数据库管理系统从并 发控制、数据存储到数据访问、程序访问的各个方面。 内存数据库和磁盘数据库相比，除了在数据主拷贝的存储位置不同之外，两 者在实现机制、性能和系统开发上也有较大不同 [19] : 1. MMDB 能够减少数据库和应用程序之间的通讯开销。传统数据库管理系 统(Database Management System，DBMS)和应用程序之间使用多地址空间体 系，这样有利于进程保护，但是进程间通讯的开销制约了系统性能。而 MMDB 系统可以直接和应用程序代码链接，两者共用相同的进程空间，省略了进程间通 讯的开销。 2. MMDB 因为所有数据都常驻在内存中，因此对所访问的数据统一用内存 地址进行编址。而磁盘数据库只有被操作数据存放在内存中的缓冲池中，而数据 主拷贝都存放在磁盘上，因此在磁盘数据库内有内存地址和磁盘地址两套编址方 式，两者之间需要通过地址翻译进行转换。 3. MMDB 系统因为没有磁盘 I,O 访问的开销，因而也不需要有缓冲管理器， 简化了系统实现，提高系统访问数据的性能。而磁盘数据库系统需要依赖缓冲管 理器来均衡磁盘 I,O 访问开销。因此在磁盘数据库中，访问数据时需要访问缓 冲管理器来决定所访问数据是否已从磁盘载入到内存中。增加了访问数据操作的 复杂性，影响了系统性能。 4. 由于 MMDB 系统在近十年才开始兴起，没有太大的系统向后兼容需求， 因此它能使用一些最新的数据库技术。而传统的磁盘数据库系统开发事件很早， 早已在众多重要的场合被应用，因此每一个新的磁盘数据库系统的研制，都需要 考虑向后兼容的问题，需要加入大量的兼容性代码，增加了系统运行的负担。 综上所述，内存数据库与磁盘数据库相比最大的不同之处就是其主拷贝常驻内 存，这也是内存数据库的一大特点。而这一点对于内存数据库的体系结构和访问 方式等有着非常重要的影响。 第二章 分布式内存数据库相关技术 13 2.3 哈希表 2.3.1 哈希表的定义 在我们查找记录时，理想的情况是希望不经过任何比较，一次存取便能得到 所查记录，那就必须在记录的存储位置和它的关键字之间建立一个确定的对应关 系 f，使每个关键字和结构中一个唯一的存储位置相对应。因而在查找时，只要 根据这个对应关系 f 找到给定值 K 的像 f(K)。若结构中存在关键字和 K 相等的 记录，则必定在 f(K)的存储位置上，由此，不需要进行比较便可直接取得所 查记录。在此，我们称这个对应关系 f 为哈希(Hash)函数，按这个思想建立的 表称为哈希表 [ 20] ，因此哈希表是种数据结构。 从以上表述可见，(1)哈希函数是一个映像，因此哈希函数的设定很灵活， 只要使得任何关键字由此所得的哈希函数值都落在表长允许范围之内即可;(2) 对不同的关键字可能得到同一哈希地址，即 key1 , key2，而 f(key1)=f(key2)， 这种现象称为冲突。然而，在一般情况下，因为哈希函数是一个压缩映像，冲突 只能尽可能的少，而不能完全避免。哈希函数选得合适可以减少这种冲突现象， 所以在建造哈希表时不仅要设定一个合适的哈希函数，还要设定一种处理冲突的 方法。 综上所述，可如下描述哈希表:根据设定的哈希函数 H(key)和处理冲突 的方法将一组关键字映像到一个有限的连续的地址集(区间)上，并以关键字在 地址集中的“像”作为记录在表中的存储位置，这种表便称为哈希表，这一映像 过程称为哈希造表或散列，所得存储位置称为哈希地址或散列地址。 哈希表优点很多，它可以提供快速的插入操作和查找操作 [ 21] 。不论哈希表中有 多少数据，插入和删除(有时包括侧除)只需要接近常量的时间即 0(1)的时间 级。实际上，这只需要几条机器指令。对哈希表的使用者来说，这是一瞬间的事。 哈希表运算得非常快，在计算机程序中，如果需要在一秒种内查找上千条记录通 常使用哈希表(例如拼写检查器)。哈希表的速度明显比树快，树的操作通常需 要 O(N)的时间级。哈希表不仅速度快，编程实现也相对容易。哈希表也有一些 缺点它是基于数组的，数组创建后难于扩展某些哈希表被基本填满时，性能下降 得非常严重，所以程序虽必须要清楚表中将要存储多少数据。 2.3.2 哈希表常用构造算法 构造哈希函数的方法很多，在构造之前首先要明确什么是“好的”哈希函数。 若对于关键字集合中的任一关键字，经哈希函数映像到地址集合中任何一个地址 的概率是相等的，则称此类哈希函数为均匀的哈希函数。 分布式内存数据库的设计与实现 14 常用的构造算法有: 1. 直接定址法 取关键字或关键字的某个线性函数值为哈希地址，即: H (key) , key 或 H (key) , a , key ， b (2-1) 其中 a 和 b 为常数;直接定址对于不同的关键字不会发生冲突，但这种方法 的效率不高，它的时间复杂度是 O(1)，空间复杂度是 O(n),，n 是关键字的个数。 2. 数字分析法 对于哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位 组成哈希地址。原则是能尽量避免产生哈希冲突，所以需要对关键字进行分析。 3. 平方取中法 取关键字平方后的中间几位为哈希地址。取的位数由表长决定。 4. 折叠法 取关键字位数相同的几部分的叠加和(舍去进位)作为哈希地址。折叠法适 用于关键字位数很多，而且关键字中每一位上数字分布大致均匀时的情况。 5. 除留余数法 除后所得余数为哈希地址。即: 取关键字被某个不大于哈希表表长 m 的数 p H (key) , key MOD p, ( p ,, m) (2-2) 这是一种最简单，也最常用的构造哈希函数的方法，它不仅可以对关键字直 接取模(MOD)，也可在折叠、平方取中等运算之后取模。 6. 随机数法 选择一个随机函数，取关键字的随机函数值为它的哈希地址，即: H (k e y , r a n d o(me y (2-3) ) k ) 其中 random 为随机函数。通常用于关键字长度不等时。 2.3.3 哈希表冲突处理的常用算法 1. 开放寻址法 i , 1,2, ... , k (k , m ,1) (2-4) H i , (H (key) ， d i ) MOD m 其中 H (key) 为哈希函数;m 为哈希表表长， d i 为增量序列，可有下列 3 种 取法: (1)如果 di 值可能为 1,2,3, ... , m , 1，称线性探测再散列。 (2)如果 di 取值可能为 12 ,-12 ,22 ,-22 ,32 , ... ,,k 2 , (k , m/2) 称二次探测再散列。 (3)如果 di 取值为伪随机数列，称伪随机探测再散列。 2. 再哈希法 i , 1,2, ... , k (2-5)H i , RH i (k e )y 第二章 分布式内存数据库相关技术 15 RH i 均是不同的哈希函数，即在同义词发生冲突时计算另一个哈希函数地 址，直到冲突不再发生。这种方法不易产生聚集的现象，但缺点是增加了计算的 时间。 3. 链地址法 将所有关键字为同义词的记录存储在同一线性链表中。 4. 建立一个公共溢出区 假设哈希函数的值域为 [0, m - 1] ,则设向量 HashTable[0...m - 1] 为基本表，每 个分量存放一个记录，另外设立存储空间向量 OverTable[0...v] 为溢出表，用以存 储发生冲突的记录。 FNV 哈希算法 2.4 FNV 哈希算法的背景: FNV 哈希算法 [ 22] 的基础，是取自发送至 IEEE 的 POSIX P1003.2 委员会的评 审意见，此意见由 Glenn Fowler 和 Phong Vo 在 1991 年的时候提出。在委员会 对此评审意见随后的一轮投票中，Landon Curt Noll 改进了 Glenn Fowler 和 Phong Vo 的哈希算法，有些人尝试用这种方法去做哈希运算，结果发现这种哈希算法 很不错。于是他们在给 Landon Curt Noll 的一封电子邮件中，把这种算法命名为 "Fowler/Noll/Vo" 或者 FNV hash。FNV 哈希算法即取自 Glenn Fowler 、Phong Vo、Landon Curt Noll 这三个人的姓。 FNV 哈希算法的设计使其能够实现快速的查找，并同时保持一个较低的冲突 率，这也是它的一大优点。 目前常用的是 FNV-1a 算法，其伪码如下: hash = offset_basis for each octet_of_data to be hashed hash = hash xor octet_of_data hash = hash * FNV_Prime return hash 其中，hash 表示的是哈希值;offset_basis 表示的是基础偏移量，是一个给定 了的初始值;FNV_Prime 表示的是 FNV 哈希素数，offset_basis 和 FNV_Prime 的 取 值 由 hash 的 取 值 范 围 决 定 ， 而 hash 的 取 值 范 围 可 以 是 [0 ~ 232 ],[0 ~ 264 ],[0 ~ 2128], ... ,[0 ~ 21024] 。 下 面 对 算 法 中 的 FNV_Prime 和 offset_basis 的计算方法作说明。 对于一个 n bit 的 FNV 哈希，当 n , 32 时，FNV_Prime(FNV 哈希素数)的 计算公式如下: 分布式内存数据库的设计与实现 16 F N V_ P r i m ,e 2t ， 28 ， b (2-6) 注:当 n , 32，t , (int)(3 * n)/4 , 24 ; 当 n , 64，t , 8 * int((n ， 5)/12) ; 当 b 是一个整型数， 0 , b , 28 ; 经验证明，当 FNV_Prime 满足上述约束时，可以使哈希算法得到一个比较 理想的分散性，尽量减少哈希冲突。 在 FNV-1a 算法中，offset_basis 的值是将字符串"chongo /\\../\\"作为输入，利用 FNV-0 算法计算出此输入的哈希值作为输出，这个输出值 即作为 FNV-1a 算法中的 offset_basis 值。FNV-0 算法与 FNV-1a 算法公式相同， 只是 FNV-0 算法中的 offset_basis 等于 0;对于 32 位哈希的 FNV-1a 算法， offset_basis 的值等于 2166136261。 当希望获取到的最大哈希值不是 2 的整数次幂时，FNV 哈希提供了一个简易 的处理方法。 例如，当希望得到的哈希值的范围是在 0 ~ 199999时，此时的 max , 199999 , 而 199999 , 232 ， 那 么 应 选 取 最 小 哈 希 ( 即 n=32 位 的 哈 希 ) 并 且 满 足 2n , max, (n , 32,64...1024)，此时 FNV-1a 算法的计算公式为: , FNV _ 32 MOD ( ma x ， 1) hash -7) (2FNV _ 32 32 FNV 综上所述，FNV 哈希算法速度允许它能够快速哈希大量的数据，同时保持 一个合理的冲突率。FNV 哈希算法具有高分散性，这种特性使它适用于哈希几 乎相同的字符串，如网址，主机名，文件名，文本，IP 地址等。 2.5 本章小结 本章主要介绍了分布式内存数据库所使用的相关技术或理论，主要包括以下 内容:分布式数据库的定义及特点，内存数据库的定义和特点，哈希表的概念及 算法介绍，其中重点介绍了 FNV 哈希算法，它将应用到关键模块的实现中。本 章为后面的系统分析以及实现提供了强有力的技术支持。 第三章 分布式内存数据库系统需求分析与设计 17 第三章 分布式内存数据库系统需求分析与设计 系统需求分析 [ 23] 的工作阶段是软件开发过程的开始阶段，是软件生命周期中 的一个重要环节，对于整个软件开发过程以及软件产品的质量是至关重要的，因 为构建软件系统最艰难的一个部分就是准确的决定要构建什么，没有其他的概念 性工作像建立详细的技术需求这样难，包括所有对人的界面、对机器的接口、以 及对其他软件系统的接口。如果做错了会对最终系统造成相当大的损害，并且后 期难以调整。而设计是将问题转换为解决 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 的的创造性过程，系统设计是在系 统分析的基础上研究系统如何实现需求中所描述的功能，给出满足需求的解决方 案。本章的主要内容是介绍分布式内存数据库系统的需求分析与设计，需求分析 主要包括整个系统的需求分析与功能分析，并根据系统的需求分析划分出系统内 的主要模块;系统设计主要包括系统架构设计、功能设计与各个模块的详细设计。 3.1 系统需求分析 需求阶段的目标是理解客户的问题和需要，需求分析是在综合分析用户对系 统提出的一组需求(功能、性能、数据等方面)的基础上，构造一个从抽象到具 体的逻辑模型表达软件将要实现的需求，并以“软件需求规格说明书”的形式作 为本阶段工作的结果，为下一阶段的软件设计提供设计基础。 3.1.1 系统功能需求 本论文所研究的分布式内存数据库系统，主要对大数据量进行高效处理，需 要系统具备大容量存储和高速率运算。传统的关系数据库在应付日益增长的大量 数据时暴露了越来越多难以克服的问题，而现有的内存数据库系统对于小数据量 的处理速率和实时性较好，但是对于分布化的考虑不多。因此，本文结合分布式 技术与内存数据库技术，来设计能够对大量数据进行高效处理的分布式内存数据 库系统。作为项目的前期工作，本文所设计的分布式内存数据库系统的主要功能 如下: 1.提供消息路由功能 本文所述的分布式系统，为了实现系统中各个内存数据库节点的负载均衡， 需要系统具有良好的分散性，即客户端发送的请求消息能够均匀的发送到各内存 数据库节点。因此本文提出一种基于哈希算法的消息转发功能，该功能构成本文 的分布式管理模块的主要功能，其实现对客户端请求消息的均匀转发功能。分布 式管理节点并不存储消息，它只需要根据消息中的数据标识查找到对应的内存数 分布式内存数据库的设计与实现 18 据库节点，将消息转发到对应的内存数据库。 2.提供用户访问数据库的接口 站在客户的角度，需要本系统能够提供增加、删除、修改、查询等数据库基 本功能操作。对于内存数据库系统而言，实现数据库的基本功能的前提是实现对 内存资源的自主管理，包括新增数据时对内存资源的申请、删除数据时对内存资 源的回收等。 因此，基于对整个分布式内存数据库系统的功能需求的分析，系统可分为两 部分，提供消息路由功能和保持负载均衡的分布式管理节点，提供增加、删除、 修改、查询等数据库基本功能操作的内存数据库节点。分布式管理节点又可以分 为分布式数组模块、消息包转发模块、消息包接收模块等模块;内存数据库节点 可以分为业务处理模块、内存资源管理模块、消息包接收模块等模块。 3.1.2 系统功能用例 用例图用于描述一组用例、参与者及它们之间的连接关系。一个用例描述了 一组动作序列，每一个序列表示系统的外部设施(系统的参与者)与系统本身的 交互。本系统的用例图是从参与者使用系统的角度来描述系统中的信息，即站在 系统外部查看系统应该具有何种的功能，而不是描述功能在系统内是如何实现 的。本文设计的分布式内存数据库系统的主要功能为新增数据、查询数据、修改 数据、删除数据。系统总体的用例图如图 3.1 所示。 分布式内存数据库系统 数据维护 <> <> <> <> 系统管理员 新增数据 修改数据 查询数据 删除数据 用户 图 3.1 系统用例图 分布式内存数据库的主要功能用例为新增数据、查询数据、修改数据、删除 数据等，下面对这几种操作的用例进行说明。 1. 新增数据是用户从客户端向系统发起新增数据请求，具体用例见表 3.1。 第三章 分布式内存数据库系统需求分析与设计 19 表 3.1 新增数据用例 用例名称 查询数据 用例描述 用户通过客户端发起数据查询请求 参与者 分布式内存数据库用户 前置条件 1、 分布式内存数据库系统各模块运行正常。 2、 数据信息已经存入数据库。 3、 用户已成功登陆客户端。 后置条件 分布式内存数据库系统能够处理客户端请求，返回用户查询数据。 基本操作 1、 运行客户端，选择数据查询选项。 2、 在客户端上填写数据标识作为查找的关键字。 3、 在客户端上确认信息后，请求消息被发送到存储该数据的内存数据 库。 4、 内存数据库查询成功后返回数据信息，如果失败，返回失败原因值。 客户端填写数据信息时，携带数据标识作为查找关键字，数据标识由数据 业务规则 2. 数据查询是指利用用户在客户端上输入指定数据标识作为关键字，查询 采集设备名称和发送数据时间组成。 该条数据的基本信息，具体用例见表 3.2。 用例名称 新增数据 表 3.2 查询数据用例 用例描述 客户端发送新增数据请求到服务器端 ) k ) 查询数据 参与者 分布式内存数据库用户 用例名称 用例描述 用户通过客户端发起数据查询请求 前置条件 1、 系统各模块运行正常。 参与者 分布式内存数据库用户 2、 用户已成功登陆系统。 前置条件 1、 分布式内存数据库系统各模块运行正常。 后置条件 分布式内存数据库系统能够处理客户端请求，保存数据。 2、 数据信息已经存入数据库。 基本操作 1、 运行客户端，用户登陆，选择新增数据信息选项。 3、 用户已成功登陆客户端。 2、 在客户端上填写数据基本信息。 后置条件 分布式内存数据库系统能够处理客户端请求，返回用户查询数据。 3、 在客户端上确认信息后，请求消息被发送到分布式内存数据库。 基本操作 1、 运行客户端，选择数据查询选项。 4、 内存数据库存储成功后返回操作成功，如果失败，返回失败原因值。 2、 在客户端上填写数据标识作为查找的关键字。 1、 客户端填写数据信息时，携带的数据标识作为唯一标识数据信息的 业务规则 key(关键字)，数据标识包括数据采集设备名称和发送数据时间。 3、 在客户端上确认信息后，请求消息被发送到存储该数据的内存数据 2、 如果数据信息已经存在，同一则不能重复插入同一数据标识的数据。 库。 4、 内存数据库查询成功后返回数据信息，如果失败，返回失败原因值。 用例名称 修改数据 客户端填写数据信息时，携带数据标识作为查找关键字，数据标识由数据 业务规则 用例描述 管理员通过客户端发起数据修改请求 采集设备名称和发送数据时间组成。 参与者 分布式内存数据库管理员 用例名称 新增数据 前置条件 1、 分布式内存数据库系统运行正常。 3. 删除数据是指当数据无效时，客户端发送删除信息请求分布式内存数据 库系统删除该条数据，具体用例见表 3.3。 用例描述 客户端发送新增数据请求到服务器端 2、 数据信息已经存在。 3、 管理员已成功登陆系统。 参与者 分布式内存数据库用户 后置条件前置条件 分布式内存数据库系统能够处理客户端请求，修改该条数据发生变化的部1、 系统各模块运行正常。 分。 2、 用户已成功登陆系统。 基本操作后置条件 1分布式内存数据库系统能够处理客户端请求，保存数据。、 运行客户端，选择数据修改选项。 基本操作 21、、 在客户端上填写数据标识和数据发生变化的部分。运行客户端，用户登陆，选择新增数据信息选项。 3、 在客户端上确认信息后，请求消息被发送到分布式内存数据库。 2、 在客户端上填写数据基本信息。 分布式内存数据库的设计与实现 20 表 3.3 删除数据用例 用例名称 查询数据 用例描述 用户通过客户端发起数据查询请求 参与者 分布式内存数据库用户 前置条件 1、 分布式内存数据库系统各模块运行正常。 2、 数据信息已经存入数据库。 3、 用户已成功登陆客户端。 后置条件 分布式内存数据库系统能够处理客户端请求，返回用户查询数据。 基本操作 1、 运行客户端，选择数据查询选项。 2、 在客户端上填写数据标识作为查找的关键字。 3、 在客户端上确认信息后，请求消息被发送到存储该数据的内存数据 库。 4、 内存数据库查询成功后返回数据信息，如果失败，返回失败原因值。 客户端填写数据信息时，携带数据标识作为查找关键字，数据标识由数据 业务规则 采集设备名称和发送数据时间组成。 4. 修改数据是指当数据需要修正时，管理员通过客户端发送修改消息请求， 用例名称 新增数据 通知 关于发布提成方案的通知关于xx通知关于成立公司筹建组的通知关于红头文件的使用公开通知关于计发全勤奖的通知 分布式内存数据库系统存入新数据，刷新数据变化部分，具体用例见表 3.4。 用例描述 客户端发送新增数据请求到服务器端 表 3.4 修改数据用例 参与者 分布式内存数据库用户 用例名称 查询数据 前置条件 1、 系统各模块运行正常。 用例描述 用户通过客户端发起数据查询请求 2、 用户已成功登陆系统。 参与者 分布式内存数据库用户 后置条件 分布式内存数据库系统能够处理客户端请求，保存数据。 前置条件 1、 分布式内存数据库系统各模块运行正常。 基本操作 1、 运行客户端，用户登陆，选择新增数据信息选项。 2、 数据信息已经存入数据库。 2、 在客户端上填写数据基本信息。 3、 用户已成功登陆客户端。 3、 在客户端上确认信息后，请求消息被发送到分布式内存数据库。 后置条件 分布式内存数据库系统能够处理客户端请求，返回用户查询数据。 4、 内存数据库存储成功后返回操作成功，如果失败，返回失败原因值。 基本操作 1、 运行客户端，选择数据查询选项。 1、 客户端填写数据信息时，携带的数据标识作为唯一标识数据信息的 业务规则 2、 在客户端上填写数据标识作为查找的关键字。 key(关键字)，数据标识包括数据采集设备名称和发送数据时间。 2、 如果数据信息已经存在，同一则不能重复插入同一数据标识的数据。 3、 在客户端上确认信息后，请求消息被发送到存储该数据的内存数据 库。 用例名称 修改数据 4、 内存数据库查询成功后返回数据信息，如果失败，返回失败原因值。 用例描述 管理员通过客户端发起数据修改请求 客户端填写数据信息时，携带数据标识作为查找关键字，数据标识由数据 业务规则 参与者 分布式内存数据库管理员 采集设备名称和发送数据时间组成。 前置条件 1、 分布式内存数据库系统运行正常。 用例名称 新增数据 2、 数据信息已经存在。 用例描述 客户端发送新增数据请求到服务器端 3、 管理员已成功登陆系统。 参与者 分布式内存数据库用户 后置条件 分布式内存数据库系统能够处理客户端请求，修改该条数据发生变化的部 前置条件 1、 系统各模块运行正常。 分。 2、 用户已成功登陆系统。 基本操作 1、 运行客户端，选择数据修改选项。 后置条件 分布式内存数据库系统能够处理客户端请求，保存数据。 2、 在客户端上填写数据标识和数据发生变化的部分。 基本操作 1、 运行客户端，用户登陆，选择新增数据信息选项。 3、 在客户端上确认信息后，请求消息被发送到分布式内存数据库。 第三章 分布式内存数据库系统需求分析与设计 21 3.2 系统总体设计 3.2.1 系统架构设计 原型化设计意味着构建一个系统的小版本，通常只有有限的功能，它可用于: 1.帮助用户和客户标识系统的关键需求。 2.证明设计或方法的可行性。 通常，原型化过程是迭代的:首先构建原型，然后对原型进行评估(利用用 户和客户的反馈)，考虑如何改变可以改进产品或设计，之后再构建另外一个原 型。当开发团队和客户认为解决方案满意时，迭代过程就终止了。 由于本文所涉及的分布式内存数据库系统是作为预研项目的前期工作，不能 确定是否一定能够构造系统，因此采用了原型化模型的软件开发方式开发一个数 据库原型。重点针对分布式内存数据库系统的大容量、实时性和可扩展性进行设 计，主要完成数据库的增加、查询、修改、删除等功能，所以对系统的架构作了 简化调整。系统的网络拓扑结构如图 3.2 所示。 服务器端 客户端 内存数据库节点 终端设备 分布式管理节点 图 3.2 系统网络拓扑结构 在系统网络拓扑结构图中，客户端模拟负责采集数据的终端设备，各个内存 数据库节点和分布式管理节点(中心节点)构成了系统的服务器端。其中，分布 式管理节点作为中心节点接收所有的消息，并通过哈希算法找到目的内存数据库 节点的 IP 地址和端口号，将各个消息重新路由到适当的目的地—某个对应的内 存数据库节点存储起来，分布式管理节点并不存储采集的数据信息。 根据原型化模型和系统的网络拓扑结构图，本文所涉及的分布式内存数据库 系统的整体结构是:有两台计算机，一台作为客户端使用，另一台作为服务器使 用，根据需求设定服务器端的内存数据库节点数个数 N。这 N 个内存数据库之 分布式内存数据库的设计与实现 22 间相互独立、存储各自的数据信息。它们的数据结构、存储方式都是相同的，由 服务器端的分布式管理节点负责把客户端发来的数据分发到对应的内存数据库， 因此不同的内存数据库中存放着不同的数据。每一个内存数据库构成了自己的内 存数据库单元，每个内存数据库单元具有独立处理的能力，它可以执行局部应用。 同时，如果这 N 个内存数据库物理上应用于多台计算机时，每个内存数据库节 点也能通过网络通信子系统执行全局应用。本系统的架构图如图 3.3 所示。 服务器端 MMDB 节点1 请求消息 请求消息 分布式管 响应消息 (Data ID) MMDB (Data ID) 客户端 节点2 理节点 MMDB 节点3 图3.3 系统架构图 本系统中，客户端模拟真实终端设备，按照其与服务器端之间的接口消息类 型模拟发送用户请求消息到系统。消息中的数据标识作为关键字，它由设备名称 和采集时间点组成，每条数据标识都是唯一的。分布式管理节点将客户端发送的 请求消息转发到该数据所在的内存数据库中，内存数据库负责对请求消息进行处 理，包括增加、删除、修改、查询等操作，并将响应消息返回给客户端。分布式 管理节点与各个内存数据库模块在同一台机器中运行。 在系统可靠性保护方面，当出现某个内存数据库模块发生故障时，分布式管 理节点会实时调整其记录的正常 MMDB 模块的信息，在转发消息时不会将消息 转发到故障的 MMDB 模块。对于系统中内存数据库节点的故障恢复机制，将由 项目的后期工作完成。针对这一问题目前可行的方案有两种;第一种方案是建立 MMDB 系统的硬盘恢复机制，在系统处理客户端的用户请求时，将数据同步复 制到磁盘数据库中，如果出现故障或掉电情况，则从磁盘数据库中恢复数据;第 二种方案是为每个内存数据库进程建立一个备用进程，主用进程数据实时备份到 备进程中，当主用进程故障时备用进程会接管主用进程的业务。 在项目后期的工作中，将把这 N 个内存数据库分别放到 N 个不同的计算机 上，组成一个小型的计算机网络，实现真正意义上的分布式内存数据库系统。实 际应用时，分布式管理节点可以是网络中一个单独的节点，每个内存数据库也是 第三章 分布式内存数据库系统需求分析与设计 23 一个单独的节点，此时分布式管理节点与内存数据库之间的通信需要通过以太网 连接，组成一个局域网。 3.2.2 系统功能设计 根据系统的需求分析，采用模块化分解结构划分本系统，使系统能够进行增 加、删除、查询、修改等数据库基本操作。系统采用传统的C/S架构，分布式管 理节点和内存数据库节点共同组成了服务器端。分布式内存数据库系统的功能模 块分解图如图3.4所示。 分布式内存 数据库系统 客户端 服务器端 分布式管理 内存数据库 节点 节点 分布 消息 消息 内存 消息 业务 数据 式数 包包接 资源 包接 转 处理 备份 组模 发收模 管理 收模 模 模块 模块 块 块 块 模块 块 图3.4 分布式内存数据库系统功能模块分解图 以下对图 3.4 中服务器端各个模块的功能进行简要说明。 分布式管理节点按逻辑功能划分为三个子模块，分布式数组模块、消息包转 发模块、消息包接收模块。下面分别对三个子模块的功能作介绍。 1. 分布式数组模块:此模块用于查找与数据标识(key)对应的内存数据库 节点，同时负责维护分布式数组的状态和数组中的数据。主要存储两类信息，一 类是分布式数组存储的各个内存数据库进程的 PID 信息;另一类是与 PID 信息 相对应的网络信息的对照表，即各个 MMDB 节点 PID 及其 IP 地址和端口号。 2. 消息包转发模块:处理消息队列中的消息包。利用分布式数组中存储的 PID 信息，查询到目标内存数据库的网络信息即 IP 地址和端口号，进而用消息 包接收模块提供的接口函数将消息包转发到某个内存数据库。 3. 消息包接收模块:建立了分布式管理节点的进程消息队列，同时为其它两 分布式内存数据库的设计与实现 24 个模块即分布式数组模块和消息包转发模块提供发送数据的接口函数。 内存数据库节点由业务处理模块、内存资源管理模块、消息包接收模块、数 据备份模块组成， 下面分别对 4 个模块的功能进行介绍。 1. 业务处理模块:负责从消息包接收模块建立的消息队列中读取请求消息， 利用内存资源管理模块提供的接口，完成数据的增加、删除、修改、查询等业务 功能，并将响应消息返回给客户端。本文所实现的内存数据库的业务处理模块采 用单线程串行处理，按照消息队列中的顺序进行处理，因此不涉及多线程的并发 控制。 2. 内存资源管理模块:负责内存数据库系统中内存资源的初始化以及对所有 资源的申请和回收，例如新增数据时要申请内存资源，删除数据时要回收内存资 源等;同时，通过链表等数据结构实现对内存数据库系统中所有资源的组织和管 理，例如建立空闲链来存储数据资源、建立哈希数组来用于查找和管理数据信息 等;该模块还为消息包接收模块和上层业务处理模块提供资源申请和数据查询的 接口，并实现对资源的自我管理。 3. 消息包接收模块:建立了内存数据库的消息处理队列，对分布式管理节点 转发过来的消息进行入消息队列处理;并利用内存资源管理模块提供的接口，获 取消息缓存资源;该模块还负责给业务处理模块提供与客户端进行通信的接口函 数。 4. 数据备份模块:为提高系统可靠性，本系统中的内存数据库节点都具有一 个备份节点，在主用节点正常时由主用节点处理业务，备份节点不处理业务;当 主用节点故障后，备份节点自动转换为主用节点，当主用节点恢复正常时自动转 换为备用节点;当备份节点重启后，备份节点的数据备份模块需要主动向主用节 点发起数据恢复请求，完成数据恢复操作。主、备内存数据库节点中都具有数据 备份模块，数据备份模块主要功能是在主用内存数据库节点处理完业务后，将数 据信息发送到备份内存数据库节点，备份节点同步刷新数据信息，保持主、备内 存数据库节点数据一致性。 由于本文的工作是对服务器端分布式管理节点中分布式数组模块、消息包转 发模块和内存数据库节点中内存资源管理模块、业务处理模块进行设计与实现， 因此以下重点对这几个模块进行论述。 3.3 分布式数组模块设计 分布式管理节点的核心是对分布式数组的管理，下面针对分布式数组的原理 和管理方法等几个关键点进行详细设计。 第三章 分布式内存数据库系统需求分析与设计 25 3.3.1 分布式数组模块原理 分布式系统需要解决的一个重要问题便是决定数据在集群中的分布策略，好 的分布策略应该能将数据均衡地分布到所有节点上，并且还应该能适应集群节点 的变化，本文采用的分布式数组方式较好地满足了这两点。分布式数组实际是实 现了数据标识和目标内存数据库进程的映射关系，数据标识通过哈希算法的计算 可以在分布式数组中唯一对应一个内存数据库进程。 对于分布式系统，系统中每个节点的负载均衡是非常重要的，分布式数组必 须具有良好的分散性，使消息能够均匀的转发到各个内存数据库节点。哈希算法 对分散性的支持很好的满足了系统对分散性的要求，并且利用哈希算法能够保证 同一号码经过哈希算法计算后，每次的哈希值都是相同的，这可以保证分布式管 理节点对同一数据标识的消息多次转发时，每次都能将消息正确转发到同一内存 数据库中。数据标识(key)利用分布式数组查找目标节点的流程如图 3.5 所示。 开始 数据标识 哈希算法 分布式数 组下标 得到节点PID 得到节点 的IP和Port 找到节点 进行相应操作 结束 图 3.5 关键字查找目标节点流程图 计算过程中，数据标识作为key输入，经过哈希算法计算后得到的hash value 就是分布式数组的数组下标，对应该下标的分布式数组中的数组元素即是该目标 内存数据库节点的PID(进程标识)，因为每一个进程唯一对应一个进程PID，所 以找到目标进程的PID就可以在网络信息对照表(即该进程的IP地址与端口号) 中找到该PID对应的IP地址和端口号，分布式管理节点就可以将信息转发到对应 的MMDB进程中。分布式数组的结构信息如表3.5所示。 分布式内存数据库的设计与实现 26 表 3.5 分布式数组信息表 分布式数组下标 分布式数组元素的值(进程 PID) 0 PID1 1 PID2 2 PID3 3 PID1 4 PID2 5 PID3 ... … 999 PID1 网络信息对照表 分布式数组的大小是一个固定值，这个固定值应该远大于一个集群的物理机 进程端口号 器数，由于本文中分布式数组是需要和系统中每个内存数据库节点同步的，所以 进程 PID 进程 IP PID1 IP PORT1 不能太大，不然同步将带来较大的开销。所以，经分析计算后，设定分布式数组 PID2 IP PORT2 的长度为 1000，即数组有 1000 个元素。数据标识通过 FNV 哈希算法时会和分 PID3 IP PORT3 布式数组的长度取余，根据哈希算法的分散性余值会均匀的落在 0~999 之间，即 每个数组元素的数组下标被选到的概率是一样的。因此由哈希算法来保证分布式 数组中每个元素被选择的概率是近似相等的，我们需要做的是将分布式数组中各 数组元素的值用各节点的 PID 来填充，这就需要对多个节点进行平均分配。分布 式数组的长度定为 1000，有 3 个内存数据库节点，那么 3 个节点占分布式数组 的个数分别为(334，333，333)的组合，这 3 个内存数据库的 PID 在分布式数 组中按照轮选方式排列，这种分配方式使分布式数组中各元素存储的 PID 也保持 了均匀的分散性。 PID 与网络信息的对照表如表 3.6 所示，由于本文所设计各内存数据库都在 同一 PC 中，因此各内存数据库进程的 IP 是一样的，但是不同内存数据库进程的 端口号不同，网络规划时给各内存数据库分配的端口号要唯一。 表 3.6 网络信息对照表 分布式数组下标 分布式数组元素的值(进程 PID) 0 PID1 1 PID2 2 PID3 3 PID1 4 PID2 3.3.2 分布式数组的初始化流程 5 PID3 ... … 在本文所述的系统中，分布式数组有效是实现系统正常处理业务的前提条 999 PID1 件，当分布式数组无效时，分布式管理节点不能将消息转发到正确的MMDB中， 网络信息对照表 进程端口号 进程 PID 进程 IP PID1 IP PORT1 PID2 IP PORT2 PID3 IP PORT3 第三章 分布式内存数据库系统需求分析与设计 27 因此在分布式管理节点重启后必须先完成对分布式数组的初始化操作，分布式数 组的初始化过程主要通过下面的流程来保证。分布式数组初始化顺序如图3.6所 示。 分布式管理模块 MMDB1 MMDB2 分布式数组初始化函数调用 分布数组状态检查 发送进程信息请求 发送进程信息请求 获取本进程ID 获取本进程ID 发送进程信息响应 发送进程信息响应 判断是否收齐进程信息 发送分布式数组请求 发送分布式数组请求 获取分布式数组 获取分布式数组 发送分布式数组响应 发送分布式数组响应 各模块分布式数组一致 返回分布式数组初始化成功 重新计算分布式数组 发送生成的分布式数组 发送生成的分布式数组 刷新分布式数组 刷新分布式数组 发送分布式数组接收成功响应 发送分布式数组接收成功响应 判断是否收齐所有响应 返回分布式数组初始化成功 图 3.6 分布式数组初始化顺序图 在初始化流程开始之前，分布式数组管理表的结构中会记录包括下面几方面 的信息: 分布式内存数据库的设计与实现 28 1.分布式数组状态，初始值是“无效”。 2.PID 与网络信息(IP 地址&PORT)对照表，其中每个 MMDB 的 PID 信息 是无效的(后续需要向各 MMDB 请求 PID 信息)，每个 MMDB 的 IP 地址和 PORT 需要提前配置好。 3.当前的分布式数组，初始值是无效值(全 F)。 根据分布式数组初始化顺序图，可知分布式数组初始化的处理流程如下: 第一步，分布式管理节点重启后会根据“PID 与网络信息(IP 地址&PORT) 对照表”中配置的所有 MMDB 进程的 IP 地址和 PORT 信息向各 MMDB 发送进 程信息请求，在收到响应后，根据消息中带的 PID 刷新“PID 与网络信息(IP 地址&PORT)对照表”中的 PID 信息。当分布式管理节点扫描“PID 与网络信 息对照表”时，如果发现某个 MMDB 模块的 PID 是无效的，则向该进程发送进 程信息请求，最多发送 5 次。在收到响应后，分布式管理节点将进程 PID 信息保 存到“PID 与网络信息对照表”中，如果在 25 秒内没有收齐所有 MMDB 进程的 响应，就以当前收到响应的 MMDB 进程 PID 来初始化当前的分布式数组。后续 分布式管理节点就可以利用响应的 MMDB 进程 PID 完成对分布式数组的初始 化。 第二步，在完成对 MMDB 进程信息的收集后，分布式管理节点会启动分布 式数组的初始化操作。分布式管理节点在初始化分布式数组时，可能是由于自身 重启导致，这时各 MMDB 进程的状态并没有发生变化，因此需要先向各个 MMDB 进程收集分布式数组，如果各 MMDB 的分布式数组有效并且相同，则分 布式管理节点只需要保存收集到的分布式数组，将分布式数组状态置为“有效”， 后续就不需要向各 MMDB 进程发送分布式数组了;如果各进程的分布式数组无 效或者有不相同的，则向各个 MMDB 进程发送分布式数组请求消息。 第三步，当MMDB进程收到了分布式管理节点的分布式数组请求消息后，无 论其保存的分布式数组是否有效，都将分布式数组发送给分布式管理节点，消息 中携带本进程的进程PID;当分布式管理节点在收到MMDB返回的分布式数组 后，将其保存起来，并判断是否收齐了所有内存数据进程的响应，如果没有收齐， 则再次发送分布式数组请求消息到未响应的MMDB进程，最多发送5次。如果在 发送5次后没有收齐响应，分布式管理节点判断收到响应的MMDB进程返回的分 布式数组是否有效且相同，如果相同且有效，则保存分布式数组，向各MMDB 进程回分布式数组有效响应。如果不相同或分布式数组无效，则分布式管理节点 按照当前响应的MMDB进程个数和各个进程的PID来生成分布式数组，将分布式 数组状态置为“有效”状态，之后发送分布式数组到响应的内存数据进程。分布 式管理节点判断分布式数组状态有效，会向所有活动的MMDB发送心跳请求消 第三章 分布式内存数据库系统需求分析与设计 29 息。MMDB进程在收到分布式数组后，给分布式数组模块回响应，消息类型为 分布式数组成功接收。 3.3.3 分布式数组的维护机制 在系统运行过程中，可能由于某些异常导致 MMDB 进程故障，如果在 MMDB 进程故障的情况下不及时调整分布式数组，会导致后续客户端发送过来 的请求消息被转发到故障的 MMDB，导致业务失败，因此在分布式管理节点发 现有 MMDB 进程故障时应及按照影响最小的原则调整分布式数组，即调整不应 该影响到原来正常 MMDB 模块的业务。 当分布式管理节点正常运行时，需要和各个 MMDB 进程间维护心跳响应机 制;当分布式管理节点检测到某个 MMDB 进程状态异常时，需要根据当前活动 的 MMDB 模块重新调整分布式数组，并向其余活动的 MMDB 广播该分布式数 组，此时会有两种场景，场景一:有 MMDB 进程故障;场景二:有 MMDB 进 程故障后又恢复正常，对于场景一的处理方式如图 3.7 所示。 分布式管理模块 MMDB1 MMDB2 MMDB状态变化函数通知函数调用 重新生成分布式数组 发送分布式数组 发送分布式数组 保存分布式数组 保存分布式数组 发送分布式数组保存成功响应 发送分布式数组保存成功响应 返回分布式数组调整成功 图 3.7 MMDB 进程故障处理顺序图 根据 MMDB 进程故障处理顺序图，对场景一中有 MMDB 进程故障的处理 步骤如下: 步骤一，分布式管理节点发送心跳请求到各 MMDB 进程，在收到响应后将 该 MMDB 进程的未响应次数置为零。 步骤二，分布式管理节点判断某个 MMDB 进程在 25 秒内没有回心跳响应， 将分布式数组的状态由“有效”置为“无效”，并根据当前“有效”的 MMDB 进程重新计算分布式数组，并将其发送到各个“有效”MMDB 进程。 步骤三，MMDB 进程收到分布式数组后刷新保存的分布式数组，向分布式 分布式内存数据库的设计与实现 30 管理节点回响应，消息类型为分布式数组成功接收。 对于场景二:有 MMDB 进程故障后又恢复正常的处理顺序如图 3.8 所示。 分布式管理模块 故障重启的MMDB 重启后分布式数组请求函数调用 分布式数组请求 重新计算分布式数组 转发分布式数组到所有正常MMDB 发送分布式数组响应 发送刷新分布式数组请求到所有正常MMDB 返回分布式数组请求成功 图 3.8 MMDB 进程故障恢复处理顺序图 根据 MMDB 进程故障恢复处理顺序图，对场景二中有 MMDB 进程故障后 又恢复正常的处理步骤如下: 步骤一，MMDB 进程重启后，判断自己保存的分布式数组是无效的，会先 向分布式管理节点请求分布式数组。 步骤二，分布式管理节点根据当前活动的 MMDB 进程数量重新生成分布式 数组并广播给所有活动的 MMDB 进程。 步骤三，分布式管理节点主动向所有活动的 MMDB 进程发送心跳消息，建 立与 MMDB 进程间的同步心跳机制。 通过上述机制，分布式管理节点可以实现对分布式数组的动态管理，在分布 式管理节点自身状态发生变化或者 MMDB 进程状态发生变化时可以及时调整分 布式数组，使客户端发送来的请求消息可以发送到活动的 MMDB 进程，尽可能 的减少模块故障对业务的影响。 3.4 消息包转发模块设计 本文所设计的分布式内存数据库系统中，每个内存数据库进程都是一个独立 工作的单元，进程之间没有通信。而分布式内存数据库系统需要知道系统中各个 模块的状态是否正常，以便能够将客户端发送来的请求消息正确、均匀的转发到 各个 MMDB 即内存数据库节点，并能够根据各 MMDB 进程的状态实时刷新分 布式数组中活动的 MMDB 进程的信息。 第三章 分布式内存数据库系统需求分析与设计 31 因此系统中需要分布式管理节点来统一管理数据的分发以及各个内存数据 库进程状态。分布式管理节点中消息包接收模块就建立了自己的消息队列接收消 息包，并负责提供发送数据的接口函数。消息包转发模块则负责读取并处理接收 到的消息包，进而用消息包接收模块提供的接口函数将消息包转发到某个内存数 据库。分布式管理节点主线程负责从消息队列中循环读取消息包，并根据消息类 型做不同的处理，该线程的功能构成了消息包转发模块的基本功能。消息包转发 模块处理消息的主要流程如下: 第一步，消息包转发模块在读取消息后，需要判断消息包的合法性，包括对 必选信元的判断、消息类型的判断。 第二步，对于一个合法的业务请求类消息包，在判断分布式数组状态有效的 情况下，将消息包中的数据标识作为输入，利用 FNV 哈希算法计算出哈希值。 第三步，该哈希值作为分布式数组下标可以获取到目标 MMDB 的进程 PID， 再利用目标进程的 PID 在分布式数组结构中记录的网络信息对照表中获取目标 进程的 IP 和端口号，将业务请求消息转发到目的 MMDB。 3.5 内存资源管理模块设计 内存资源管理模块作为内存数据库系统的核心模块之一，其主要作用是实现 对内存的自我管理，即资源申请、组织和回收这一资源利用的全过程都是由本模 块负责完成。内存资源管理模块中的消息包接收模块功能和分布式管理节点的基 本相同，都是为了建立对应进程的消息队列，因此本节不作重复介绍。 3.5.1 内存资源初始化过程 内存数据库系统向操作系统申请完资源后，需要将数据资源用双向链表组织 起来形成空闲链，供后续业务处理模块申请资源时使用;对于数据哈希节点资源， 在系统启动时应将每个哈希节点资源的值都初始化成无效的，等待后续业务处理 模块将数据资源挂到哈希节点。 在内存资源的描述上，本模块借用了面向对象的思想，将内存管理功能抽象 为两个层次。第一层称为资源管理表，该表用来描述资源在内存中的各种属性， 如资源起始地址，资源 ID，资源数量，每个单元字节长度;第二层称为资源描 述表，该表记录了资源空闲链表的信息和哈希数组的信息，在访问资源时通过表 ID 来获取空闲链表或哈希链表地址信息，应用层的模块不直接访问资源表中的 信息。 在系统为各种资源分配内存前，需要先初始化资源管理表，之后根据资源管 理表中的信息确定所有资源需要向系统申请的总内存长度。在计算出所有需要申 分布式内存数据库的设计与实现 32 请的内存资源数量后，内存数据库系统向操作系统统一申请一片连续的内存，资 源管理表再根据每种资源的长度和单元个数找到对应资源的起始地址，完成对资 源管理表的初始化操作。 完成资源管理表的初始化操作后，资源描述表需要根据资源管理表中各资源 的信息将数据资源、消息队列资源等数据资源组织成空闲的双向链表;对哈希数 组各节点的初始化操作主要是初始化头节点指针和将冲突链个数置为零。此时各 种资源在内存中的排列如图 3.9 所示，这样就完成了内存资源的初始化操作。 数据资源 Null 空闲链 消息队列 Null 空闲链 哈希数组 Null Null Null Null Null Null 图 3.9 内存资源初始化示意图 3.5.2 内存资源申请过程 内存资源申请和回收机制是内存资源管理模块的主要功能，从这个过程可以 看出 MMDB 对内存资源的全流程管理方式，因此重点介绍内存资源申请和回收 机制。 由于各种内存资源的作用和索引方式不同，因此内存资源的申请过程也不全 相同。 对于消息队列节点资源，在申请时需要根据内存资源描述表来找到它的空闲 双向链表，从链表头取一个空闲资源，然后业务处理模块会将该消息队列节点进 行赋值等操作后挂到消息队列的队尾。 对于数据资源，首先需要根据内存资源描述表来找到它的空闲双向链表，从 链表头取一个空闲资源，之后需要利用 FNV 哈希算法对数据标识进行计算，得 到数据标识对应的哈希值，将该哈希值和数据哈希数组的长度取模后得到数组下 标，再通过内存资源描述表找到数据哈希数组的哈希节点，将数据资源挂到该哈 希节点的冲突链上。 图 3.10 描述了申请三个数据资源后的内存资源组织形式，其中部分数据资 源从数据资源空闲链上断开后被挂到了哈希数组的某个节点上(即哈希数组中的 指针指向该节点)，此节点的地址是由数据标识通过哈希算法计算出的。同时， 空闲链表的头节点后移，指向相应节点。当断开的空闲资源被挂到数据哈希数组 上不同的哈希节点时，形成这些节点的哈希冲突链。访问数据记录时就可以通过 第三章 分布式内存数据库系统需求分析与设计 33 数据标识快速索引到相应的哈希节点，在该节点下遍历哈希冲突链就可以找到数 据记录。因此，这种以空间换时间的索引方式在一定程度上有效提高了内存数据 库的查询速度。 Null 消息队列 Null 空闲链 数据资源 Null Null 空闲链 Null 哈希数组 Null Null Null 图 3.10 内存资源申请后示意图 3.5.3 内存资源回收过程 当数据资源被删除后，其占用的内存资源也需要被重新回收利用。内存资源 回收过程是指将申请的资源重新挂回各资源的空闲链表的过程，并不是将内存直 接释放。 对于消息队列节点资源，当业务处理模块从消息队列上处理完一个消息包 后，该消息包所占用的消息队列节点资源就被释放，重新挂回到消息队列节点资 源的尾部。 对于数据资源，在业务处理模块删除数据时，先根据数据标识利用 FNV 哈 希算法得到该号码对应的哈希值，将该值与将该哈希值和数据哈希数组的长度取 模后得到哈希数组下标，通过内存资源描述表找到对应的哈希节点，在该哈希节 点的冲突链上找到数据记录后，将数据记录从冲突链上摘除，并将记录重新挂回 到数据资源的空闲链表尾部。 分布式内存数据库的设计与实现 34 3.6 业务处理模块设计 内存数据库的业务处理模块主要负责根据消息类型来完成对应的业务逻辑 处理。本模块利用内存资源管理模块提供的接口，完成数据的增加、删除、修改、 查询等业务功能，并将响应消息返回给客户端。 3.6.1 新增数据过程 第一步:客户端发送新增数据请求消息，消息包到达服务器端的分布式管理 节点，由分布式管理节点的消息包接收模块接收到该请求消息，放入其消息队列 中。 第二步:分布式管理节点的消息包转发模块从消息队列中读取该消息包，解 析消息中的数据标识信元，根据数据标识利用 FNV 哈希算法计算出该数据标识 的哈希值，即分布式数组的数组下标，此下标对应的数组元素即是目的内存数据 库节点的 PID，进而从网络信息对照表中获取到目的内存数据库进程的 IP 地址 和端口号。消息包转发模块就可以将客户端请求消息转发到对应的内存数据库 中。 第三步:当内存数据库节点接收到该请求消息时，由业务处理模块判断是否 是新增数据请求消息，需要利用内存资源管理模块提供的接口查询该条数据是否 已经存在，如果存在，则不允许新增重复数据，业务处理模块需要向客户端发回 业务失败响应，指示该条数据已经存在;如果该数据标识对应的记录不存在，业 务处理模块需要利用内存资源管理模块提供的结构向内存管理模块申请一个空 闲的数据资源，并从请求消息中解析出所有的信元，例如消息中的数据标识、温 度、压强、经纬度等信息，将这些信息保存到申请的空闲资源中;之后，业务处 理模块需要利用内存资源管理模块提供的接口计算出该条数据中的数据标识的 哈希值，并将该条数据挂到对应哈希节点的冲突链上，完成新增数据的处理过程。 3.6.2 数据查询和修改过程 第一步:数据查询和修改过程中，数据从客户端发送到内存数据库的过程 和新增数据过程相同，当业务处理模块从消息队列中读取消息后，判断是查询或 修改类的消息，会解析出消息中的数据标识，利用数据标识通过 FNV 哈希算法 计算出该条数据的哈希值，在以该哈希值为数据下标的哈希数组中就可以找到该 数据标识对应的数据记录。 第二步:如果是查询操作，在查询到该条数据记录后，业务处理模块需要利 用消息包收发模块提供的消息发送接口将数据信息响应返回给客户端;如果是修 第三章 分布式内存数据库系统需求分析与设计 35 改操作，业务处理模块需要解析出消息中被修改的信元值，将其刷新到数据记录 中。 3.6.3 数据删除过程 第一步:数据删除过程，数据从客户端发送到内存数据库的过程和新增数据 过程相同，当业务处理模块从消息队列中读取消息后，判断是删除数据，需要解 析出信元中的数据标识，利用数据标识通过 FNV 哈希算法计算出该条数据的哈 希值，在以该哈希值为数据下标的哈希数组中就可以找到该数据标识对应的数据 记录。 第二步:在找到了数据记录的情况下，业务处理模块需要利用内存资源管理 模块提供的接口将该条记录从哈希数组中对应哈希节点的冲突链上摘除，并利用 内存资源管理模块提供的接口将此数据记录重新挂回到数据资源的空闲链链尾。 3.7 本章小结 本章对分布式内存数据库系统进行需求分析与设计。首先，站在用户的角度 对系统的需求进行具体的分析，描述系统的功能需求，并结合系统用例图给出功 能用例;其次，在需求分析的基础上，简要说明了系统的整体架构设计和功能设 计;最后，作为本文的主要工作内容，对分布式管理节点中分布式数组模块、消 息包转发模块及内存数据库节点中内存资源管理模块、业务处理模块等模块进行 了详细设计，用顺序图描述了具体的设计过程。本章是系统实现的前提。 分布式内存数据库的设计与实现36 第四章 系统实现 37 第四章 系统实现 本章主要按照第三章中对系统关键模块的设计，对分布式管理节点中分布式 数组模块、消息包转发模块及内存数据库节点中内存资源管理模块、业务处理模 块等功能进行实现。 分布式数组涉及的两个算法对于其实现机制而言是相对独立的，因此本章对 分布式数组的哈希算法和分布式数组调整算法单独进行介绍。 4.1 分布式数组模块关键技术实现 4.1.1 分布式数组管理表结构定义 分布式数组管理表包括分布式数组和网络信息对照表，它的结构定义如图 4.1 所示。 <<结构>> MmdbDistriManageTbl +ucArrayStatus : char DistArray +CurArrayValue : DistArray +NetInforTable : MmdbDistNetInfoTable <>(unsigned short,1000) T, size:int <<结构>> MmdbDistNetInfoTable Array +usPid : unsigned short +arr:T[]=T[size] +ulIP : unsigned long +usPort : unsigned short 图 4.1 分布式数组管理表类图 其中，MmdbDistriManageTbl 为分布式数组管理表的结构定义，ucParaStatus 记录当前分布式数组的状态，其取值范围为“无效状态”、“初始化状态”、“有效 状态”，其中“无效状态”指分布式管理节点刚启动时的状态;“初始化状态”指 分布式管理节点启动后向所有 MMDB 进程发送分布式数组请求消息后的状态; “有效状态”是指在分布式管理节点在将重新生成的分布式数组发送到各 MMDB 节点后的状态。CurArrayValue 数组记录了当前的分布式数组，是一个无 符号短整形的数组，其数组下表是采集数据标识经过哈希算法计算后的哈希值， 内容存储的是各个活动的 MMDB 的进程 PID。NetInforTable 为网络信息对照表， 利用从分布式数组中获取到的进程 PID，可以在该表中查询到对应的 IP 和端口 号信息。 分布式内存数据库的设计与实现 38 4.1.2 分布式数组相关算法实现 分布式数组涉及两个算法，一个是根据数据标识计算其对应内存数据库 PID 的 FNV 哈希算法，另一个是分布式数组的调整算法，下面对这两个算法的实现 进行说明。 1. FNV 哈希算法实现 在利用分布式数组计算出目标进程 PID 时，用到了 FNV 哈希算法，下面说 明该算法的实现原理。对于 FNV-1a 哈希算法，本文在计算哈希值时算法过程如 图 4.2 所示。 算法名称:FNV哈希算法 输入:Identity字符数组(数据标识) 输出:ulhashind(分布式数组下标) 步骤一:用无符号整型变量ulhashind(首次计算时，值为32位F NV哈希初始值)与Identity字符数组第一个字节进行异或运算，结果 赋值给ulhashind; 步骤二:用ulhashind乘以32位FNV哈希素数，将结果赋值给ulhas hind; 步骤三:重复执行步骤一和步骤二，直到循环到Identity字符数 组的结尾; 步骤四:将ulhashind与分布式数组的长度(1000)取余，结果赋 值给ulhashind; 图 4.2 FNV 哈希算法过程 其中，32 位哈希算法的哈希初始值等于 0x811C9DC5;32 位哈希算法的素 数，等于 16777619。 对于 FNV 哈希算法，当希望哈希值落在 0~MAX_NUMBER 之间，并且该 值不是 2 的 n 次方时，可以让计算出的哈希值与(MAX_NUMBER + 1)取模。 计算出的哈希值为 MmdbDistriManageTbl 中 CurArrayValue 数组的下标，该下标 对应的数组元素就是目标 MMDB 的进程 PID，再通过目标进程 PID 在 NetInforTable 表中就可以找到该用户目的 MMDB 对应的 IP 地址和端口号。 2. 分布式数组调整算法 分布式数组在初始化时，会将每个 MMDB 节点对应的 PID(进程标识号) 平均分配给分布式数组中的元素进行存储，例如本文中分布式数组长度为 1000， MMDB 节点个数为 3 个，系统先按轮选机制将 3 个 MMDB 节点的 PID 分配给 1000 个分布式数组元素进行存储，即每个 MMDB 节点的 PID 占有约 333 个分布 式数组元素，实现了平均分配。 当分布式内存数据库系统中某个 MMDB 节点故障时，分布式数组的状态将 变成“无效”。此时系统需要对分布式数组中，故障模块所占有的分布式数组元 第四章 系统实现 39 素进行调整，调整算法过程如图 4.3 所示。 算法名称:分布式数组调整算法 输入:分布式数组状态变为“无效” 输出:不包含故障MMDB的分布式数组 步骤一:计算出每个MMDB模块占有的分布数组个数; 步骤二:遍历分布式数组，如果某个数组元素的值是故障MMDB模块 的PID，则将该元素的值刷新为当前占有分布式数组元素最少的PID; 图 4.3 调整算法过程图 按照上面算法对分布式数组进行调整后，会有三个优点，第一，分布式数组 中存储的 MMDB 进程 PID 都是状态正常的，因此整个系统的业务不会被转发到 故障的 MMDB;第二，故障的 MMDB 模块占有的分布式数组元素被均匀的分配 给其它正常的 MMDB 模块，保证了分布式数组调整后各 MMDB 占有的分布式 数组元素的比例基本相同;第三，对正常的 MMDB 不会造成影响，按照变化前 分布式数组转发到各 MMDB 的数据，在分布式数组变化后数据依然可以被查询 到，只有之前被发送到故障 MMDB 的数据才会丢失，这样对系统中其它正常的 模块的影响做到了最小。 4.1.3 分布式数组初始化和维护流程实现 当分布式管理节点正常启动后，首先会进行分布式数组的初始化过程。分布 式数组初始化过程分为两个阶段。第一阶段，分布式管理节点需要先创建进程信 息请求线程，向所有的 MMDB 收集进程 PID 信息，该线程的处理流程如图 4.4 所示。 分布式内存数据库的设计与实现 40 开始 Y 分布式数组状态 线程关闭 是否为Valid, N Y 发送进程请求消息 分布式数组状态 是否为Invalid, 到所有MMDB N N 分布式数组状态 异常状态线程关闭 是否为Initial, Y N 是否收齐所有MMDB 发送进程请求消息到 没有回响应的MMDB 进程信息, Y 线程关闭 结束 图 4.4 PID 信息请求线程处理流程图 当分布式模块启动时，分布式数组的初始状态是 Invalid，进程信息请求线程 检测到该状态后，需要根据分布式数组的网络信息对照表中所有 MMDB 节点的 IP 地址和端口号信息向这些 MMDB 进程发送进程 PID 请求消息。并将分布式数 组状态设置为初始化(Initial)状态。 当完成了进程信息请求后，进程信息请求线程会关闭，分布式数组初始化的 第二阶段主要在主线程中完成，主线程从消息队列中读取消息包，判断是分布式 数组维护类消息后，其处理流程如图 4.5 所示。 第四章 系统实现 41 开始 N 是不是分布数组 其他类型消息 维护类消息, 处理 Y N 回错误响应 消息包是否合法, Y Y N 是否收齐MMDB 进程信息请求响应, Y 的PID信息, N Y 发送分布数组请求消 N 息到所有MMDB 分布数组响应, 其它类型消息处理 Y Y Y 所有MMDB返回的 是否收齐分布 分布式数组一致, 数组信息, N N Y 重新生成分布数组，发MMDB 向未响应发送MMDB 送到响应的分布数组请求次数>5, N 发送分布数组请求消 息到未响应MMDB N 结束 图 4.5 主线程处理流程图 主线程在收齐响应后，如果发现所有 MMDB 返回的分布式数组是相同的， 这种情况可能是分布式管理节点重启导致，因此不用再重新计算分布式数组，如 果各 MMDB 返回的分布式数组不全相同，此时就需要重新计算分布式数组，并 发送给所有的 MMDB。 分布式数组的维护过程主要依赖于和 MMDB 进程之间的心跳机制，在分布 式管理节点启动后，会创建心跳发送线程用于发送与内存数据库之间的心跳消 息，该线程判断分布式数组状态有效，会向网络信息对照表中 PID 信息有效的进 程发送心跳请求，这就建立其了分布式管理节点和 MMDB 间的心跳机制。 当有 MMDB 进程和分布式管理节点间的心跳响应停止超过 5 次时，就认为 该模块故障，此时分布式管理节点的心跳发送线程会将分布式数组的状态置为 Invalid 状态，并根据当前活动的 MMDB 进程调整分布式数组，将调整后的分布 分布式内存数据库的设计与实现 42 式数组发送到各活动的 MMDB。 4.2 消息包转发模块关键技术实现 消息包转发模块的功能主要是处理消息包中的业务请求类消息，将该消息发 送到对应的内存数据库节点。图 4.6 为该模块读取到消息包后的处理。 如图中所示，主线程在读取消息包后判断是业务类消息，解析出消息中的数 据标识，将数据标识作为输入利用 FNV 哈希算法计算出其哈希值，再将该哈希 值和分布式数组长度求余后得到分布式数组下标，从分布式数组中得到目的 MMDB 进程的进程 ID，最后利用进程 ID 在网络信息对照表中查询到目的 MMDB 的 IP 地址和端口号信息就可以将消息转发到目的内存数据库节点了。 开始 N 其他类型消息处理是不是业务类消息, Y N 回错误响应 消息包是否合法, Y N 分布式数组状态 回错误响应 是否正常, Y 利用数据标识计算出哈希值 利用哈希值从分布式数组获取进程PID 利用PID在网络信息对照表找到和该PID对应的IP和端口号 创建消息包转发消息到目标内存数据库 结束 图 4.6 消息包转发模块消息包处理流程 第四章 系统实现 43 4.3 内存资源管理模块关键技术实现 4.3.1 内存资源管理模块类图 在第三章中，我们已经提到了内存资源管理模块在管理内存资源时将管理功 能抽象为了两层，第一层是资源表，第二层是资源描述表，实际实现过程中，整 个内存资源资源管理模块的功能都是围绕着这两个表展开的，如图 4.7 所示是内 存资源管理模块的类图。 MmdbGlobarVar MMDB +g_MmdbResTbl : MmdbResMangeTbl +g_MmdbTbl : MmdbResDiscripTbl 1 * <<结构>> <<结构>> MmdbResMangeTbl MmdbResDiscripTbl +*pStartAddr : char +stDataTbl : MmdbDataTbl +ulTotalLen : unsigned long +stHashTbl : MmdbHashTbl +MmdbResTable : MmdbRes <<结构>>MmdbDataTbl <<结构>>MmdbHashTbl <<结构>>MmdbList +ucResID : signed char +ucResID : unsigned char +ulNumber : unsigned long +ulFreeNumber : unsigned long +ulMaxUnitLen : unsigned long -*pListHead : char +ulTotalNumber : unsigned long +ulTotalLen : unsigned long -*pListTail : char +*pFreeList : MmdbList 1 * <<结构>>MmdbHashList +ulNumber : unsigned long +*pFirstRec : char <<结构>>MmdbRes +*pStartAddr : char +ucResID : signed char +ulUnitNumber : unsigned long +ulUnitLen : unsigned long 图 4.7 内存资源管理类图 内存资源管理模块在管理资源时，主要依赖于全局变量 g_MmdbResTbl 和 g_MmdbTbl。g_MmdbResTbl 相当于是资源表的一个实例，描述了各种内存资源 在内存中的物理信息，其负责在系统启动时给各类资源按照其规格分配内存，是 对内存资源的底层描述;g_MmdbTbl 相当于是资源描述表的一个实例，其将资 源具体划分为两类，一类是数据资源，一类是哈希资源;对于数据资源， g_MmdbTbl 利用 MmdbList 将空闲资源组织成一个双向链表，在其它模块需要获 取数据资源时，需要通过 g_MmdbTbl 的 pFreeList 来访问;对于哈希资源， g_MmdbTbl 记录了哈希资源的资源表 ID，在访问哈希资源时，其它模块需要利 用资源 ID 和哈希值作为输入，利用 g_MmdbTbl 来访问哈希资源。 实际上，系统对内存资源的管理分层后，底层的内存操作对业务处理模块不 分布式内存数据库的设计与实现 44 可见，上层业务处理模块不需要关注底层模块对资源的操作，这样提高了数据的 封装性，使系统架构比较清晰。 4.3.2 内存资源初始化过程实现 内存数据库所需要的内存资源都是由系统统一申请和管理的，在系统向操作 系统申请到所需的内存资源后，系统需要利用自身的数据结构将申请到的内存资 源组织起来，这就是初始化过程的主要功能。内存资源初始化流程如图 4.8 所示。 开始 系统启动 计算所有资源所需内存总量 向系统申请资源 初始化MmdbResTbl表 初始化每种资源的起始地址 初始化MmdbResDiscripTbl表 初始化数据资源空闲链表 初始化哈希资源节点 结束 图 4.8 内存资源初始化流程图 在完成内存资源初始化后，对于数据资源，例如空闲的数据资源在内存中会 被组织成双向链表，MmdbDataTbl 表中的 pFreeList 结构指针将记录该空闲链的 头、尾指针和链表上空闲资源个数;对于哈希资源，例如数据标识哈希节点资源， 这部分元素的冲突率指针和冲突率个数会被初始化成 NULL 和零。这样，后续 业务处理模块就可以利用资源描述表来申请内存资源了。 4.3.3 内存资源申请过程实现 内存资源申请过程包含了两个过程，首先是从空闲链上申请内存资源，其次 是将申请到的内存资源挂到对应哈希节点下，该过程流程图如图 4.9 所示: 第四章 系统实现 45 开始 采集数据资源申请 从采集数据资源空闲链链 头取一个空闲资源 用消息中信息填充 空闲资源 数据标识经哈希算法，计 算出对应的哈希节点 将采集数据资源挂到哈希 节点首个记录 结束 图 4.9 内存资源申请过程流程图 申请数据资源时，首先需要从空闲链的链头取一个空闲资源，并调整链表的 后向指针，使获取到的资源与空闲链断开，之后需要利用消息中的信息来填充获 取到的资源。 在计算数据标识对应的哈希节点时，用的是 FNV-1a 哈希算法，该算法在本 章 4.1 小节已经介绍，本小节与之前的不同点是，本文中为了获得比较理想的分 散性，减少冲突数据个数，哈希数组的元素个数与内存数据库支持的最大记录数 相同。在利用数据标识计算出 32 位哈希的哈希值后，需要和哈希数组的元素个 数取余，使计算出的哈希值落在数据哈希数组的范围之内。 在计算出数据标识的哈希值后，通过该哈希值和哈希资源 ID 可以利用资源 描述表获取到对应的哈希节点，之后将申请到的数据资源地址挂到哈希节点的冲 突链上，就完成数据了申请过程。 4.3.4 内存资源回收过程实现 内存资源回收过程与申请过程相反，当删除一个数据记录时，需要将数据记 录从对应的哈希节点上取下来，并重新挂回数据空闲链的尾部，操作流程如图 4.10 所示。 分布式内存数据库的设计与实现 46 开始 采集数据资源删除 将数据记录从哈希节点 的冲突链上删除 将数据记录挂到采集数 据资源空闲链表尾部 结束 图 4.10 内存资源回收过程流程图 删除数据前，首先需要利用数据标识计算出该条数据所在的哈希节点，在对 应的哈希节点冲突链上查询待删除记录，如果记录存在，调整该条记录在冲突链 上的位置，将其从冲突链上取下，之后利用 MmdbDataTbl 表中的 pFreeList 指针 找到数据资源的空闲链链尾，将待删除的数据挂到空闲链尾部。 4.4 业务处理模块实现 4.4.1 新增数据过程实现 在分布式管理节点中，消息包接收模块是一个独立的线程，专门用于接收发 送到本节点的数据，并将数据放入进程消息队列;消息包转发模块循环从消息队 列中读取消息包，按照消息包类型作不同的处理。 对于新增数据过程，业务处理模块在判断消息包中信息有效的情况下，需要 利用内存资源管理模块提供的数据资源申请接口申请一个空闲资源，并将消息包 中的信息刷新到该空闲资源中，之后需要利用消息中的数据标识通过哈希算法计 算出该标识对应的哈希节点，最后利用内存资源管理模块提供的插入哈希链表接 口函数将申请到的数据资源挂到哈希节点的冲突链上。新增数据过程模块间顺序 图如图 4.11 所示。 第四章 系统实现 47 分布式管理节点 内存数据库节点 消息包接收模块 消息包转发模块 消息包接收模块 内存资源管理模块 业务处理模块 新增数据请求 检查消息包合法性 消息包检查合法，将消 息包挂入消息队列 消息包接收线程 和主线程切换 从消息队列中读取消息包 判断消息包合法性， 非法则回失败响应 经过哈希算法计算，在分布式数组 管理表中得到目标MMDB网络信息 转发请求消息到目标MMDB 收到分布式管理 节点转发的消息 检查消息包合法性，如果 非法，则返回失败响应 申请消息队列资源 申请成功 将请求消息拷贝到申请的 消息包中，挂入消息队列 消息包接收线程和主线程切换 读取消息队列中消息包， 解析出其中所有信元 判断消息包合法性， 非法则回失败响应 申请数据资源 申请成功 将数据信息保存到数据 资源中，将新申请的数 据挂到哈希节点冲突链 返回成功响应 上 图 4.11 新增数据顺序图 4.4.2 数据查询和修改过程实现 数据查询和修改过程中，不需要申请和释放数据资源，对于数据查询操作， 业务处理模块只需要利用消息包中的数据标识通过哈希算法计算出其在哈希数 组中的节点位置，就可以从该节点的冲突链中找到目标数据信息，此时，业务处 理模块只需要将数据信息返回给客户端就完成了该操作;对于数据修改过程，在 找到数据信息后，需要利用消息中的信元刷新该条数据中对应的信息，并给客户 端回操作成功响应。查询数据的模块间顺序图如 4.12 图所示。 分布式内存数据库的设计与实现 48 分布式管理节点 内存数据库节点 消息包接收模块 消息包转发模块 消息包接收模块 内存资源管理模块 业务处理模块 查询数据请求 检查消息包合法性，如果 非法，则返回失败响应 消息包检查合法，将消 息包挂入消息队列 消息包接收线 程 和主线程切换 从消息队列中读取消息包 判断消息包合法性， 非法则回失败响应 经过哈希算法计算，在分布式数组 管理表中得到目标MMDB网络信息 转发客户端请求消息 到目标MMDB 收到分布式管理 模块转发的消息 检查消息包合法性，如果 非法，则返回失败响应 申请消息队列资源 申请成功 将请求消息拷贝到申请到 的消息包，挂入消息队列 消息包接收线程和主线程切换 读取消息队列中消息包， 解析出其中所有信元 判断消息包合法性，非 法则回失败响应 利用消息中的数据标识查 询到数据记录，并将查询 返回查询数据 信息返回给客户端 图 4.12 查询数据顺序图 4.4.3 数据删除过程实现 数据删除过程，需要释放数据资源并将此内存资源回收，即利用数据标识经 哈希算法查询到该数据记录，将数据记录从哈希节点的冲突链上断开，再挂回空 闲链，并给客户端回操作成功的响应。删除数据的过程顺序如图 4.13 所示。 第四章 系统实现 49 分布式管理节点 内存数据库节点 消息包接收模块 消息包转发模块 消息包接收模块 内存资源管理模块 业务处理模块 删除数据请求 所耗时间(单位微妙) 检查消息包合法性，如果 非法，则返回失败响应 消息包检查合法，将消 息包挂入消息队列 消息包接收线程 和主线程切换 从消息队列中读取消息包 判断消息包合法性， 非法则回失败响应 经过哈希算法计算，在分布式数组 管理表中得到目标MMDB网络信息 转发客户端请求消息 到目标MMDB 收到分布式管理 模块转发的消息 检查消息包合法性，如果 非法，则返回失败响应 申请消息队列资源 申请成功 将请求消息拷贝到申请到 的消息包，挂入消息队列 消息包接收线程和主线程切换 读取消息队列中消息包， 解析出其中所有信元 判断消息包合法性，非 法则回失败响应 则利用消息中的数 据标识查询到数据 记录，将数据记录 从哈希冲突链断开 数据资源挂空闲链 挂空闲链成功 返回成功响应 图 4.13 删除数据顺序图 4.5 本章小结 本章根据系统设计对分布式内存数据库系统的关键模块进行具体实现。主要 对分布式管理节点中分布式数组、消息包转发模块以及内存数据库中内存资源管 理模块、业务处理模块的功能进行实现，用类图描述了各模块的内部结构和模块 间的关系，流程图描述了实现的具体步骤和方法。 分布式内存数据库的设计与实现50 第五章 系统测试 51 第五章 系统测试 系统测试是软件开发过程的重要组成部分，是用来确认一个程序的品质或性 能是否符合开发之前所提出的一些要求。系统测试的目的是对最终软件系统进行 全面的测试，确保最终软件系统满足产品需求并且遵循系统设计。因此，能够发 现程序缺陷的测试是成功的测试。本章将主要描述对内存数据库系统的测试，并 针对系统特点，主要采用黑盒测试为主，白盒测试为辅的测试方法，对系统进行 功能测试和性能测试。 5.1 测试方法 软件测试常用方法有白盒测试法和黑盒测试法。白盒测试又称为结构测试、 逻辑测试和基于程序的测试。白盒测试是对软件的过程性细节做细致的检查。这 种方法是把测试对象看作一个打开的盒子，它允许测试人员利用程序内部的逻辑 结构及有关信息设计或选择测试用例，对程序所有逻辑路径进行测试。通过在不 同点检查程序状态，确定实际状态是否与预期的状态一致。 黑盒测试又称为功能测试、数据驱动测试或基于规格说明的测试，是把测试 对象看作一个黑盒子，测试人员完全不考虑程序内部的逻辑结构和内部特征，只 依据程序的需求规格说明书，检查程序的功能是否符合它的功能说明。黑盒测试 注重于测试软件的功能性需求，即黑盒测试使软件 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 师派生出执行程序所有功 能需求的输入条件。黑盒测试并不是白盒测试的替代品，而是用于辅助白盒测试 去发现其他类型的错误。 对于本项目将主要采用黑盒测试的方法进行测试。 5.2 测试环境 本系统是基于 WINDOWS 操作系统进行开发的，代码编写工具采用 SourceInsight 3.5 版本，程序的编译和调试用 VC++6.0。 测试时使用 VC 进行系统的功能和性能测试，系统的配置如下: 1.客户端: CPU 2GHz，1GB 内存，Microsoft Windows XP 操作系统 2.服务器端:CPU 3GHz，3GB 内存，Microsoft Windows XP 操作系统 5.3 测试内容与结果 1.功能测试 功能测试主要是测试程序模块是否实现了需求分析中所要求的功能。本系统 分布式内存数据库的设计与实现 52 需要实现数据的新增、修改、查询和删除这四个功能，因此以下对系统的这四个 功能进行测试。 (1)新增数据测试 测试步骤:输入用户姓名和密码，允许进入系统，选择数据插入功能的代码 1，输入数据回车并查看输出结果。 输入:数据标识:XD—Y2012M11D20H15M30S5，环境温度:12，压强: 120035，经度:D116M3S30，纬度:D39M9S25。 预期输出:成功插入一条新的数据。 实际输出:成功插入一条新的数据。 测试结果如图 5.1 所示: 图 5.1 新增数据测试结果图 (2)修改数据测试 测试步骤:输入管理员姓名和密码，允许进入系统，选择数据修改功能的代 码 2，输入数据标识并确定对此数据信息进行修改，输入新的修改数据回车并查 看输出结果。 输入:数据标识:XD—Y2012M11D20H15M30S5，确认修改，输入新数据。 预期输出:成功修改数据。 实际输出:成功修改数据。 测试结果如图 5.2 所示。 第五章 系统测试 53 图 5.2 修改数据测试结果图 (3)查询数据测试 测试步骤:输入管理员姓名和密码，允许进入系统，选择数据查询功能的代 码 3，输入数据回车并查看输出结果。 输入:数据标识:XD—Y2012M11D20H15M30S5。 预期输出:显示查询的数据信息，成功查询该数据信息。 实际输出:显示查询的数据信息，成功查询该数据信息。 测试结果如图 5.3 所示。 图 5.3 查询数据测试结果图 (4)删除数据测试 测试步骤:输入管理员姓名和密码，允许进入系统，选择数据查询功能的代 码 3，输入数据回车并查看输出结果。 分布式内存数据库的设计与实现 54 输入:XD—Y2012M11D20H15M30S5 数据标识 预期输出:确认删除的数据信息，成功删除该数据信息 实际输出:确认删除的数据信息，成功删除该数据信息 测试结果如图 5.4 所示。 图 5.4 删除数据测试结果图 2.性能测试 服务器端测试机器配置为单核 CPU:3Ghz，内存:3G。 测试方法为在各种数据库操作函数调用前后使用 C 语言的 gettimeofday 函 数，用于记录调用该操作接口函数前后所消耗的时间，然后经过计算得到每秒可 进行此操作的次数。 经测试，本系统执行增、删、改、查等操作时，系统操作平均达到每秒 6500 次左右，能够达到实际应用对系统性能的要求。 表 5.1 系统性能测试表 所耗时间(单位微妙) 新增数据 153 查询数据 144 修改数据 153 删除数据 137 5.4 本章小结 本章主要描述了分布式内存数据库系统的测试方法，并给出了测试结果。在 一定测试环境下，对系统按照功能测试、性能测试的顺序，进行了多次测试。经 测试，系统符合设计要求，满足了用户需求。 第六章 总结与展望 55 第六章 总结与展望 随着科学技术的飞速发展，信息化已逐渐渗透入工作、生活的各个领域。信 息系统对于大数据量的数据采集与分析的要求，使得系统对数据处理的大容量、 实时性提出了更高的要求，内存数据库系统的发展为解决这些问题提供了方法和 技术。内存数据库将数据常驻内存，并且在数据组织结构、索引技术上的优化， 极大的提高了数据库系统的处理速度。 本文所研究的的分布式内存数据库系统，对传统的 Key-Value 型内存数据库 系统作了改进，提出一种用分布式数组来管理系统中各内存数据库节点的方案， 本系统具有以下优点: 1.利用分布式数组实现了分布式系统中数据的存储和访问机制，分布式数组 与 FNV 哈希算法相结合一方面提高了数据转发时的计算效率，另一方面哈希算 法的分散性使系统中各内存数据库节点的负载更均匀。 2.分布式数组的动态调整机制使分布式管理节点能够动态感知各内存数据 库节点的状态，并对分布式数组进行调整，降低了由内存数据库故障导致的业务 失败。 3.本文对内存数据库系统的架构设计上，采用了面向对象的思想，将对内存 资源的管理分为两个层次，架构清晰，易于后续开发和维护。 与此同时，由于本人的技术水平和经验的欠缺，肯定还存在许多不足和需要 改进的地方，系统目前还不够完善，存在许多需要优化之处，总结起来有下面几 个方面: 1.系统的数据恢复机制不够完善，后续对于每个内存数据库系统需要建立各 自的硬盘恢复机制。 2.由于分布式数组变化而导致的各内存数据库进程间的数据同步转移功能 还没有实现。 3.本文的分布式系统采用了星型拓扑结构，分布式管理节点是系统中的中心 节点，在大数据量的情况下，该模块容易成为系统的瓶颈。 相信随着信息技术的不断发展和革新，以及网络建设步伐的加快，日趋完善 的内存数据库系统必将发挥越来越重要的作用。 分布式内存数据库的设计与实现56 致 谢 57 致 谢 时光飞逝，转眼间宝贵的研究生学习生涯即将结束，回顾以往两年多的 学习、实习历程感慨万千。两年来自己的点滴进步无不凝结了身边每一个人的无 私帮助和真诚奉献。在论文成稿之际，衷心感谢给予自己悉心指导和热情帮助的 各位老师和同学们。 论文的完成，首先要感谢我的校内导师覃桂敏教授，在整个论文的的写作过 程中，覃老师都给予了我莫大的关心和帮助。从我毕业论文的选题、写作一直到 最后的完成的过程中，老师都在百忙的工作中以一贯认真负责的态度仔细阅读论 文，给予我耐心的指导，使论文能够顺利的完成。她严肃的科学态度，严谨的治 学精神，精益求精的工作作风，深深地感染和激励着我。 在一年的实习期间，实习单位的领导和同事们都给与了我无私的帮助和指 导，尤其是十室和我朝夕相处的同事们，谢谢你们。特别感谢我的实习单位指导 老师余松涛高工，在我论文写作遇到疑惑时，他都给与我耐心的指导和细致的解 答。他严谨细致的态度和不急不躁的工作作风时常影响和感染着我，让我受益良 多。 还要对宋胜利老师和刘伟老师表示最诚挚的谢意，两位老师对论文提出了许 多宝贵的建议，让我很受启迪，他们的热情帮助和指导让我避免了许多错误，使 论文得以顺利进行。感谢我的同学们，正是有了你们的帮助和支持，我才能克服 一个个的困难，完成论文的写作。 在论文即将完成之际，我的心情无法平静，从开始进入课题到论文的顺利完 成，有很多可敬的同学、朋友给了我无言的帮助，在这里请接受我诚挚的谢意。 最后我还要感谢培养我长大含辛茹苦的父母，谢谢你们。