第15章 内存数据库系统
复习笔记
一、概述
01内存数据库
内存数据库（Main Memory Duta Buse，MMDB）系统是指将数据库的全部或大部分数据放在内存中的数据库系统。内存数据库有时也称主存数据库，In Memory DataBase等。
02磁盘数据库
磁盘数据库（Disk Resident DataBase，DRDB）是使用磁盘作为常规数据存储设备，使用内存作为工作数据缓冲区的数据库系统。
内存数据库与磁盘数据库的区别如图15-1所示。
图15-1 内存数据库和磁盘数据库对比示意图
二、内存数据库的发展历程
01内存数据库的雏形期
1969 年，IBM公司研制了国际上最早的层次数据库管理系统 IMS。IMS 在一个系统中提供了两种数据管理方法，一种是采用内存存储的Fast Path，另一种是支持磁盘存储的IMS。Fast Path支持内存驻留数据，是内存数据库的雏形。
02内存数据库的研究发展期
1984年，DJ.De Witt等人发表了"内存数据库系统的实现技术"一文，第一次提出了Main Memory Data Base 的概念；1985年，IBM推出了在IBM370上运行的OBE内存数据库；1986年，RBHagman提出了使用检查点技术实现内存数据库的恢复机制；1987年，ACM SIGMOD会议中有论文提出了以堆文件（heap file）作为内存数据库的数据存储结构；1988年，普林斯顿大学设计出TPK内存数据库：1990年，普林斯顿大学又设计出System M内存数据库。
03内存数据库的产品成长期
1994年，美国 OSE公司推出了第一个商业化的、开始实际应用的内存数据库产品 POlyhedra。
三、内存数据库的特性
内存是计算机存储体系结构中能够被程序可控访问（相对于硬件控制的cache）的最高层次，是能够提供大量数据存储的最快的存储层。内存数据库具有几个重要特性：
1.高吞吐率和低访问延迟；
2.并行处理能力；
3.硬件相关性。
四、内存数据库的关键技术
通用的内存数据库管理系统要为用户提供SQL接口，具有内存存储管理、面向内存的查询处理和优化等基本模块，还应提供多用户的并发控制、事务管理和访问控制，能够保证数据库的完整性和安全性，在内存数据库出现故障时能够对系统进行恢复。
01数据存储
（1）行存储
在行存储模型中元组是连续存放的，适合事务处理中一次更新多个属性的操作，能够保证对多个属性的操作产生最小的内存访问；但对于只涉及表中相对较少属性的分析处理时，即使该查询只涉及元组的某个或某些属性，其他属性也会被同时从内存读入到缓存，降低了缓存利用率。
（2）列存储
列存储模型将关系按列进行垂直划分，相同属性的数据连续存储。当访问特定属性时只读入所需要的属性所在的分片，所以节省内存带宽，并且具有较高的数据访问局部性，可减少缓存失效，提高数据访问效率；同时列存储将相同类型的数据集中存储，能够更好地对数据进行压缩以减少内存带宽消耗，利用SIMD（单指令多数据流）技术提高并行处理效率，通过列存储的数据定长化处理支持对数据按偏移位置的访问。
（3）混合存储
该模型把同一元组的所有属性值存储在一页内，在页内对元组进行垂直划分。根据关系的属性个数 m，将每一页划分为m个Mini Page，每个 Mini Page对应一个属性，连续存放每一页中所有元组的该属性的值。由于元组在页内进行垂直划分，所以该模型具有较好的数据空间局部性，可优化缓存性能；同时，同一元组的值存储在同一页内，所以元组的重构代价比较少。
02查询处理及优化
内存数据库的查询处理性能主要由两个因素决定：内存数据访问性能和内存数据处理性能。内存数据访问性能由内存带宽和内存访问延迟决定。
（1）面向cache特性的查询处理与优化技术
①内存数据库和磁盘数据库的比较
内存数据库的基础假设是数据库的工作数据集常驻于内存中（memory resident），从而消除了传统磁盘数据库的I/O代价，内存数据库的性能较磁盘数据库有数十倍甚至数百倍的提升。
磁盘数据库使用内存缓冲区（buffer）来优化1/O代价，现代CPU使用硬件级的多级 cache机制优化内存访问，内存数据库的内存访问优化由硬件级的cache机制来完成，采用类LRU（最近最少访问）替换算法实现cache中的数据管理。
②cache失效的分类
a.强制（compulsory）失效。强制失效是数据首次访问时在cache中所产生的失效，是内存数据访问不可避免的。
b.容量（capacity）失效。容量失效是由于工作数据集超过cache容量大小而导致的数据访问时在cache中的失效。
c.冲突（conflict）失效。冲突失效则是在cache容量充足时由于大量弱局部性数据（一次性访问数据或复用周期很长的数据）将强局部性数据（频繁使用的数据集）驱逐出cache而在对强局部性数据重复访问时产生的cache失效。
③cache优化技术的分类
a.cache.conscious优化技术；
b.cache.oblivious优化技术；
c.page—coloring优化技术。
④数据存放技术
采用聚类（clustering）和染色（coloring）存放技术，优化了cache 的性能。
（2）索引技术
索引是数据库中提高查询性能的有效方法，在磁盘数据库中广泛使用的hash索引、B+树索引等不适合内存数据库的需求，所以一些针对内存数据库特性的索引得到了广泛的研究。
（3）面向多核的查询处理技术
在多核平台上，查询算法需要改写为多核并行算法，将串行操作符并行化。在多核并行优化时需要解决的关键技术包括并行处理时的共享cache优化，数据分区优化等技术。常见的三种多核并行hash连接技术为：
①无分区（no partitioning）hash连接算法；
②基于分区（partitioned）的hash连接算法；
③radix hash连接算法。
（4）面向众核的查询处理技术
多核处理器逐渐进入众核时代。内存数据库面临越来越多的计算核心，查询算法需要进化为高可扩展并行算法，以充分利用先进众核处理器提供的强大并行计算性能。数据库采用以存储为中心的设计思想，内存数据库的优化技术也一直以内存数据访问优化为核心。
03并发与恢复
（1）并发控制
①减少锁的开销的方法
a.采用较大的封锁粒度（如表级锁）；
b.采用乐观加锁方式；
c.减少锁的类型；
d.将锁信息存储在数据本身。
②串行的并发控制协议特点
写事务在整个数据库上施加互斥锁（mutex），通过时间戳和互斥锁在事务的提交记录没有到达磁盘之前允许新事务开始，并且保证任何提交的读事务不会读到未提交的数据。
（2）恢复机制
由于内存的脆弱性和易失性，内存数据库中数据容易被破坏和丢失，所以内存数据库数据需要在磁盘等非易失性存储介质中进行备份，并且在对数据更新时将日志写到非易失性存储介质中。
①TimesTen记录日志的方式
a.将日志记在内存的一个区域中；
b.可以将日志记在磁盘文件上。
②RAMCloud记录日志的方式
RAMCloud采用了一种主从式内存日志机制，即当数据被修改时将更新日志写入两个或更多的内存后备服务器。日志首先存储于后备服务器的内存中，再采用异步方式批量写入磁盘。
③恢复数据的步骤
a.首先恢复热点数据，即执行事务所必须的数据；
b.在后台恢复其他非热点数据。
