高并发集群监控系统中内存数据库的设计与应用

高并发集群监控系统中内存数据库的设计与应用周游弋金城复旦大学计算机科学技术学院上海200433复旦大学计算机科学技术学院上海200433摘要在具有大量并发连接的高并发集群监控系统中，传统磁盘数据库由于内外存交换开销过大，无法支撑数据的实时存储与处理，因此大量实时系统都选择采用内存数据库作为数据支撑模块。从介绍内存数据库的关键技术点出发，通过引入虚拟影子内存和粗粒度意向锁来分别改进内存数据库的数据组织和并发控制，设计实现了一个用于支撑高并发集群监控系统的高效内存数据库模块，并且研究了其在实际系统中应用情况。关键词内存数据库数据组织并发控制DESIGNANDAPPLICATIONOFMAINMEMORYDATABASEINHIGHCONCURRENCYCLUSTERMONITORINGSYSTEMZHOUYOUYI1JINCHENG21SCHOOLOFCOMPUTERSCIENCEANDTECHNOLOGY,FUDANUNIVERSITY,SHANGHAI200433，CHINA2SCHOOLOFCOMPUTERSCIENCEANDTECHNOLOGY,FUDANUNIVERSITY,SHANGHAI200433，CHINAABSTRACTINAREALTIMECLUSTERMONITORINGSYSTEMWITHLARGEAMOUNTOFCONCURRENTCONNECTIONS,TRADITIONALDISKRESIDENTDATABASESYSTEMSAREUNABLETOPROCESSDATAINREALTIMEDUETOCONSIDERABLEOVERHEADSCAUSEDBYI/OSWAPPINGOPERATIONSTHEREFOREMANYREALTIMESYSTEMSADOPTMAINMEMORYDATABASESYSTEMSASDATASUPPORTMODULESAFTERINTRODUCINGSOMEKEYTECHNIQUESUSEDINMAINMEMORYDATABASES,WEPROPOSEADESIGNANDIMPLEMENTATIONTHATISIMPROVEDINDATAORGANIZATIONANDCONCURRENCYMANAGEMENTBYVIRTUALSHADOWMEMORYANDCOARSEGRAINEDINTENTSHARELOCKITALSOPRESENTSTHEDATABASESAPPLICATIONSTATUSINAREALTIMECLUSTERMONITORINGSYSTEMWITHHIGHCONCURRENCIESKEYWORDSMAINMEMORYDATABASEDATAORGANIZATIONCONCURRENCYMANAGEMENT0引言随着应用程序功能变得越来越复杂，高性能计算集群正在被大量投入到各种规模的计算系统中。在各种集群系统中，高并发集群主要用于处理在同一时刻有大量同步事务的应用。随着集群规模的不断增大，根据概率推算可知整个集群的故障率会变得越来越高，对于集群系统中各个计算节点的各种状态信息进行实时的检测就是十分必要的。检测所得数据必须实时存储于数据库中。在高并发集群中，各种事务的并发度非常之高，每个事务的操作都必须限制在几十个甚至十几个微秒之内，传统的基于磁盘文件的数据库系统在处理这种事务时候就会显得力不从心，因为磁盘I/O操作的时间不确定性消耗了大量的CPU计算时间6，在这种情况下可以引入内存数据库作为数据信息的存储手段。内存数据库，顾名思义就是将数据放在内存中直接进行操作的数据库。相对于磁盘，内存的数据读写速度要高出几个数量级，将数据保存在内存中相比从磁盘上访问能够极大地提高性能，同时，内存数据库抛弃了磁盘数据管理的传统方式，基于全部数据都在内存中的特点重新设计了体系结构，并且在数据缓存、快速算法、并行操作方面也进行了相应的改进，所以数据处理速度比传统数据库的数据处理速度要快很多，一般都在10倍以上。本文从实际应用出发，针对内存数据库的特点和应用程序的要求设计实现了一个支撑高并发集群监控系统的内存数据库系统，并且研究了该数据库在实际环境中的应用状况。1内存数据库的关键技术11数据组织与传统的关系型数据库类似，内存数据库中的数据也基于关系表来组织和管理；与传统基于磁盘的数据库不同，内存数据库中的数据需要全部或者大部分存放于物理内存才能获得大幅度的性能提升。目前内存数据库在物理内存中组织数据的方式主要有两种区段式和影子内存式。区段式组织是基于关系数据模型的，这种组织方式的一个实现是STARBURST5。收稿日期20100329。上海市科委科研计划项目资助（08511500902，08511501903）。周游弋，硕士，主研领域WEB数据处理，内存数据库。区段式存储每次操作都可以直接应用于实际内存中的数据，因此比较适合应用于数据实时性要求较高的场合，但是，这个特点也同时要求数据库具有良好的锁机制以及恢复机制，否则会影响到数据库的执行效率和错误恢复能力。按影子内存式组织的内存数据库空间，如SYSTEMM8，可以划分为两个部分一部分是内存数据库的主拷贝PDBPRIMARYDATABASE；另一部分为“影子拷贝”SMSHADOWMEMORY。在数据库操作期间，每次查询总是先对影子拷贝试探，若不成功，再对主拷贝操作。所有的更新操作都在影子拷贝中进行，且都记录在活动日志中。每当一个事务提交时，由它所产生的在影子拷贝中的更改都会被拷贝到主拷贝中。使用影子内存式存储首先可以简化事务失败或者系统故障时候的撤销操作，只需要清除相应的影子拷贝即可；其次，它减少了对主存内主拷贝的存取次数，各个事务可以并发地对影子拷贝进行操作；此外，它还一定程度上避免了在事务重做之前的撤销，同一个事务可以不必先撤销而直接重新提交。影子内存在事务并发度较高但是数据实时性要求不高的场合具有较大的应用优势，开发人员可以通过引入影子拷贝的概念来简化事务处理，进而提高了事务之间的并发程度4。12并发控制内存数据库中使用的并发控制与磁盘数据库中的并发控制基本相同，细节上存在一定差异。由于数据存储在内存中，事务执行时间较短，持有锁的时间也较短，系统中并发冲突较少，所以可以通过以下方法减少锁的开销1采用较大的锁粒度如表级锁；2采用乐观加锁方式；3减少锁的类型；4将锁信息存储在数据本身。对于内存数据库，封锁产生的CPU代价会对性能产生严重的影响，特别是在工作负载主要由短小事务构成的应用场合，每个事务要求极短的响应时间，在几十毫秒甚至几毫秒之内完成。针对此问题，有学者提出了接近串行的并发控制协议ALMOSTSERIALPROTOCOL，该协议的创新之处在于，写事务在整个数据库上施加互斥锁MUTEX，并且通过时间戳和互斥锁在前导事务的提交记录没有到达磁盘之前，即允许新事务开始，并且保证任何提交的读事务不会读到未提交的数据。实验表明，与严格的两阶段锁协议相比，对于查询密集型和更新密集型的工作负载，该协议在最大吞吐量上分别提高了7倍和2倍1。13恢复技术由于内存的脆弱性和易失性，数据更容易被破坏和丢失，所以需要在磁盘等非易失性存储介质中进行备份以便出现错误时可以恢复数据库的正常状态7。目前，应用在内存数据库中的恢复技术主要有日志和检查点。日志中有三种类型的记录关于系统运行、事务行为和数据库变更记录,其中,系统运行记录包含系统运行情况的信息，事务记录记载活动事务的信息，数据库变更记录包含了所变更的数据的定位及其前后映像。日志为数据库的恢复提供了操作依据。检查点操作一般是让数据库处于静止状态，由系统记录数据的部分或者整体快照，以便作为恢复源。处于静止状态的数据库会阻止新事务的开始，这在实时性要求很高的现代应用（例如无线网络漫游管理、移动终端计费等）中是不适合的。为了尽量减少恢复机制给内存数据库带来的额外开销，可以将日志记录记载于独立的缓冲区内，当缓冲区写满或者事务提交时，再将日志写回磁盘。这样牺牲了一定的数据容错性，尤其是当一段时间内没有事务提交且缓冲区未满时，这时候如果系统出错就会造成缓冲区丢失，但是在实时性应用中，以此代价换来性能提升是可接受的。2内存数据库的设计尽管内存数据库已不是传统磁盘数据库的概念，但是内存数据库本质上还是数据库，它也具有一般数据库的基本功能。内存数据库的存储介质是内存，与传统的磁盘在数据的物理组织上有较大区别，在设计数据组织的时候必须考虑这种差异。此外，物理存储的不同，也使得索引设计不能完全按照传统数据库的方式思考，需要考虑内存数据库中数据连续，索引和数据共存等特点。恢复机制也是在设计中必须慎重考虑的一个方面，内存数据的易失性对于内存数据库恢复机制的设计提出了更严峻的要求，恢复技术无可避免地要同外设备进行I/O通信，这势必会影响到内存数据库的整体效率，在稳定和高效中寻求最佳平衡点也是设计中的一个关键问题2。21内存数据库内存组织和数据表设计在高并发集群监控系统中，事务的并发程度和数据实时性要求都比较高，因此内存数据库将区段式方式和影子内存方式结合使用，设计一个基于区段式存储的影子内存数据表结构。数据在主存中以区段式组织形成主拷贝，以表为单位将数据抽取拷贝作为影子拷贝“虚拟影子表”。查询操作与影子内存类似，先访问虚拟影子表，如果失败再访问主拷贝，更新操作直接操作虚拟影子表和主拷贝，同时进行两部分的更新，以确保数据一致性。这种双向更新操作需要同时对虚拟影子拷贝和主拷贝加锁，会引起一定的额外开销，却提高了数据的实时可用性，在实际应用中取得了良好的表现。在设计上，二维数据表可以表述为具有数据表元信息的一块连续内存空间，即将二位数据表定义为一个储存有数据库名、数据表名、关键字和数据字典字段描述表等信息的对象，并为其分配一块连续的内存空间用于数据存储。一般来讲，数据库系统为了兼顾数据的扩展性和稳定性需要动态地增加或者减小分配给二位数据表的存储空间，这在具有接近无限容量外存的传统数据库中是较为普遍的实现机制，而在内存数据库中，一方面受内存大小的限制，数据表不可能无限制的增大；另一方面，频繁改变数据表存储空间的大小势必引起内存中产生大量的内存碎片，无疑又会严重影响内存数据库的执行效率。在状态检测系统中，检测所得信息往往具有有限的时效性，人们关心的是集群系统在一个相对有限的时间周期中的运行状态，失去时效性的数据信息不需要被实时高效地存放于内存数据库，可以选择性的丢弃或者存放于外存设备中。基于这种时效性的特点，在分配存储空间时，可以采用事先确定的固定大小，这样可以避免改变空间大小时需要移动数据的开销，同时也可以通过固定的地址偏移来简化和加速表内数据的检索以及更新。22内存数据库索引设计在高并发集群监控系统中，信息的实时性要求索引更新速度要紧跟数据的产生速度，大量并发的事务也要求索引在更新时不能产生过高的代价。基于哈希链表的随机分布式索引技术相比于顺序索引在查找开销上有更好的理论值，在哈希函数设计合理的情况下查找时间可以接近常数值，然而哈希结构的缺点是无法很好解决哈希冲突问题，随着冲突的不断增多，索引的整体性能也在不断下降，因此不适合应用于内存数据库索引中。B树的特点是每个节点携带的数据信息多、树的高度低而且只需访问较少的节点便可获取所需数据，所以很适合作为面向磁盘的索引结构3。但是B树节点信息覆盖率太低，只有55，这对于空间资源相对紧张的内存数据库来讲十分低效，而通过调整节点中关键字的数量，T树节点的信息覆盖率可以达到80以上，同时T树还保留了类似于B树的良好二分查找性，在节点内部关键字已排序的情况下，查找操作的平均时间开销为，其中M为每个节点的关键22LOGLN字数量，N为关键字总数，因此从时间空间复杂度上综合考虑，T树是最适合内存数据库的索引结构。23内存数据库并发控制设计在内存数据库中，乐观加锁引起数据错误或者更新冲突的概率会随着并发度的增大而不断提高，频繁的修正和事务检查会降低整体效率，减少锁类型将大幅降低事务之间的并发度，都不适合应用于实际集群环境中。基于集群的这些特点，本内存数据库的并发控制机制采用了大粒度锁和锁粒度动态变换的方法。通过提供数据库级锁和表级锁两种粒度的锁，事务可以根据需要在操作时加锁，锁类型分为读锁、写锁、读意向锁和写意向锁四种。读锁为共享锁而写锁为非共享锁。意向锁的含义是如果对一个结点加意向锁，则说明该节点的下层节点正在被加锁；对任意节点加锁时，必须先对他的上层节点加锁。如果对一个数据对象加读意向锁，表示它的后裔结点拟意向加读锁。如果对一个数据对象加写意向锁，表示它的后裔节点拟意向加写锁。并发阻塞是否有数据库级写意向锁加数据库级读意向锁对表加读锁相关表是否有锁请求结束请求加读锁加数据库级写意向锁是否有数据库级写意向锁是否有数据库级读意向锁对表加写锁相关表是否有锁是否否是否是否是否是并发阻塞请求加写锁请求结束A读锁请求流程示意B写锁请求流程示意图1事务锁请求流程示意图在此基础上，为了进一步提高并发度，引入了锁粒度动态变换的机制，即数据库级锁和表级锁可以根据事务对关系共享程度的需求进行锁粒度的动态智能转换。因为数据库级锁比表级锁开销小，因此当不需要较细的锁粒度时使用数据库级锁。如果一个或者多个事务在访问表时被其他事务的锁阻塞，数据库级锁会被分解为表级锁，并且再次尝试加锁。当不需要细粒度锁时，表级锁被转化为数据库级锁。过程可以由图1的流程图来表示。以读事务为例，当事务需要读取某些数据记录时，系统会提前分析事务中涉及到的数据表，首先对数据库请求数据库级读意向锁，然后检查数据库是否存在全局的写意向锁，如果存在，则说明有写事务正在更新数据库的某一部分并且尚未结束，此时系统会检查读事务相关的数据表是否被写事务加锁，如果写事务正在更新相关表，那么读事务不得不等待写事务完成；如果相关表没有被写事务加锁，则读事务可以并发的上读锁读取数据。写事务请求加锁的过程基本与此类似。区别是写事务之间是绝对互斥的。不存在两个写事务同时向数据库写入的情况。24内存数据库恢复设计数据库恢复过程无可避免的要跟外存设备进行I/O通信，一定程度上会影响内存数据的整体性能，从集群系统实时性和时效性的特点出发，为了尽量避免额外的I/O代价，日志功能被单独设计为一个独立的服务进程，在内存中开辟一块固定大小的日志缓冲区，所有事务的日志以时序记录到缓冲区中，如果缓冲区被记录填满或者事务提交则一次性将所有日志记录写入外存并清空缓冲区以容纳新日志的写入。当需要恢复数据时，从磁盘中取出所有日志条目进行恢复。这是一种以牺牲小部分容错性为代价换取执行效率的做法，如果在一段时间内没有事务提交且缓冲区未满，则缓冲区的日志记录可能因为系统错误而全部丢失，这时先前已完成但未提交的事务便有可能无法重做，在实时性应用中，我们认为这种代价是可以接受的，因为未提交的事务理论上不应该对数据库的一致性产生影响，而且由于内存数据库中的事务大都短小且执行快，这种极端情况发生的概率相当小。3基于内存数据库的高并发集群监控系统在实际应用中，内存数据库位于整个高并发集群监控系统的核心部分，作为数据中心模块支撑所有数据应用。整个检测系统的模块化设计可由图2来表示，左半部分的客户端应用程序接口和服务进程状态监控与控制模块是客户端的应用业务模块，可根据不同的业务需要衔接不同的应用逻辑，物理信息模块作为基础支撑应用，向整个系统提供集群中各个节点的物理监控信息。客户端信息和物理监控信息经由XML封装之后在网络传输模块中传送到主控逻辑处理模块，该模块完成对信息的解包分析和逻辑处理等功能，处理过的信息存储至数据中心模块的内存数据库中。调度算法模块是与业务逻辑相关的模块，主要完成客户提出的业务需求。报警模块和日志模块作为系统的附属支撑模块向用户提供更加友好的信息界面和操作体验。在该系统中，由于系统的并发性要求较高，因此内存数据库被作为嵌入式模块应用，直接使用API接口操作数据库，以便能够获得更好的性能表现。图3给出了本数据库系统与其他几种磁盘数据库的比较测试。测试步骤为按顺序进行1,000,000次插入INSERT，查询SELECT，修改UPDATE和删除DELETE操作，分别记录各项操作所消耗的平均时间。横坐标为四项基本操作，纵坐标为平均消耗时间，单位毫秒MS。可以看出，磁盘数据库在进行数据操作时需要进行大量磁盘读写操作，从而增加了系统的开销，拖慢了整个系统的执行效率，本文提出的内存数据库CLUSTERDB因为所有操作都在内存中进行，避免了磁盘I/O开销，性能上明显优于其他基于磁盘的数据库，在应对高并发集群时有着良好的应用情况。报警模块日志模块主控逻辑服务器逻辑处理模块调度算法模块数据中心模块主控服务器网络传输模块客户端应用程序接口服务进程状态监控与控制模块物理信息监控采集模块XML数据图2监控系统模块组成图图3对比测试结果4结论在高并发集群监控系统中，虽然依旧可以使用传统基于磁盘的数据库技术，但是在整体性能上却无法与轻量快速的内存数据库相比。尽管传统数据库中也有很多已经采用或者加入了实时性技术用于支撑高实时要求的应用，然而在效率上还是不能超越基于内存的数据库技术，更何况还会带来更高的开发成本和维护开销。文中提出的内存数据库轻量、快速、灵活，既可以单独运行，也可以嵌入系统中作为单独模块合并应用，使用简单，开发和维护成本较低廉，在实际使用中的情况也满足了客户对系统性能的要求。然而值得一提的是，该内存数据库在查询处理，数据存储和恢复技术上仍然有改进余地，如何合理安排缓存使得查询效率更高，如何合理规划存储空间和空间申请来减少碎片的影响以及恢复日志的存储，提交和处理都是可以进一步研究和改进的课题。参考文献1BLOTTS,KORTHHFANALMOSTSERIALPROTOCOLFORTRANSACTIONEXECUTIONINMAINMEMORYDATABASESYSTEMSCPROCEEDINGSOFTHE28THINTERNATIONALCONFERENCEONVERYLARGEDATABASESVLDB02HONGKONGVLDBENDOWMENT,20027172BONCZP,MANEGOLDS,KERSTENMLDATABASEARCHITECTUREOPTIMIZEDFORTHENEWBOTTLENECKMEMORYACCESSCPROCEEDINGSOF25THINTERNATIONALCONFERENCEONVERYLARGEDATABASESVLDB99EDINBURGHMORGANKAUFMANN,199954653DOUGLASCUBIQUITOUSBTREEJACMCOMPUTINGSURVEYSCSUR,1979,1121211374LAMKY,KUOTWREALTIMEDATABASEARCHITECTUREANDTECHNIQUESMBOS