高级数据库二十四：内存存不下的内存数据库

小灰灰 2022-06-01 01:48 221阅读 0赞

# Larger-than-Memory Databases #

## 背景 ##

我们知道DRAM价格非常昂贵，且运行耗电量也非常大。

那么当内存数据库存储的信息更大了之后，我们就希望使用更加便宜的存储设备，希望改善DRAM带来的一些不利条件。

### 新技术 ###

因此就产生了Larger-than-Memory Databases这种技术。即，允许内存中的DBMS存储/访问磁盘上的数据，而无需重新引入面向磁盘的DBMS的所有慢速缺点。

需要了解硬件访问方法

*  内存中存储 = 面向元组（从比特位上来解决问题）
 *  磁盘存储 = 块定位（基于页的方式）

### OLAP vs. OLTP ###

OLAP查询通常访问整个表。因此，DBMS不能利用任何面向磁盘的缓冲池，来处理事务或者减少工作量。

![15161400566044.jpg][]

例如，你在内存中存储了zone map这类聚合函数的一些信息，而其他的数据有一部分在内存中，有一个部分在磁盘中。

当程序发现无法简单地用zone map中的聚合函数做统计信息的时候，还是一样地要扫描磁盘来获得数据。那么和面向磁盘的数据库没有区别。

因此这项技术是无法适用于OLAP的，它仅能够解决OLTP的问题。

对于OLTP的工作负载，总是可以将数据分成冷热两个部分。

*  之前的课堂上，我们可以假设txns将几乎总是访问热元组。

DBMS需要一种机制来将冷数据移出内存，移到磁盘。当有查询访问磁盘上的冷数据时，DBMS能够再次检索它。

### 需要解决的问题 ###

![15161405303371.jpg][]

在内存中，我们原有Tuple\#00至Tuple\#04的5个元组。我们发现，Tuple\#01、Tuple\#03、Tuple\#04是冷数据，那么我们将它们从内存中移出来，并存入磁盘中。

随之而来的就有一系列问题：

1.  内存中，原先三个Tuple占有的位置应该填充什么数据？
2.  内存中的索引原先指向的是原数据，现在原数据没有了，应该指向哪里？
3.  当一个查询来了的时候，我们发现它访问的是内存中没有的冷数据，那么我们应该将它停止并放到任务队列中等待重启，还是继续执行？
4.  当我们将冷数据取回至内存的时候，我们是只取回需要的那个元组，还是讲整个页都移入内存？
5.  根据1、2、4三个问题，我们可能做出不同的决定。如，原有位置被其他数据顺序占有。那么，冷数据应该以怎样的方式和内存中的热数据进行合并？

## 决策分析 ##

### 为什么不用MMAP ###

MMAP是一种内存映射到磁盘文件的方式，具体可参见[维基百科][Link 1]，你一定要去[百度百科][Link 2]也行。

性能评估的论文[In-Memory Performance for Big Data][]。

按照老师的观点，他非常不喜欢用mmap。这种方式依赖于操作系统自己的内核，会带来如下的问题：

1.  预写日志记录要求修改的页面在写入这些更改的日志记录之前不能写入磁盘。
2.  没有同步预读或同时写多个页面的机制  
    
    
     *  导致并发性能极差。

不是说不能用mmap，而是mmap不能有效地解决本文讨论的所有问题。

那么接下来就看看每个问题分别可以用怎样的策略去实现。

### 冷数据识别 ###

选择1：在线

*  DBMS监视txn访问模式并跟踪元组的使用频率。用类似LRU的方式去辨别哪些是冷数据。
 *  直接在元组中嵌入跟踪元数据。
 *  这种方式更为被老师推崇，尽管维护使用频率的代价也比较大。

选择2：离线

*  在执行txn期间维护一个元组访问日志。
 *  在后台进行计算频率。
 *  效率会稍微低一些，因为需要维护的计算的日志可能会非常长。

### 冷数据移出时间 ###

选择1：阈值

*  DBMS监视内存使用情况，并在达到阈值时开始移出元组。
 *  DBMS必须手动移动数据。

选择2：OS虚拟内存

*  操作系统决定何时将数据移出到磁盘。它知道内存的使用情况，但是也仅仅会使用mmap的方式去维护。
 *  这是在后台完成的。

### 冷数据的元数据 ###

#### 选择1：Tombstones ####

*  在内存中独立一块空间，留下指向磁盘元组的标记，这些标记被称为Tombstone元组。
 *  更新索引以指向Tombstone元组。即，有些索引指向正常的元组，有些索引指向Tombstone元组。
 *  这种方式只有当Tombstone元组的大小小于正常的元组时才有效。如果正常的元组的大小是32位，而Tombstone是64位，那么这样存储反而消耗了更多内存。

![15161418946115.jpg][]

根据使用频率将冷数据存入磁盘。

![15161419352415.jpg][]

用Tombstone去追踪存入磁盘中的元组的位置，类似于一种索引。

#### 选择2：Bloom Filters ####

*  一种使用索引的模糊数据结构，它存在于数据库表的上方，类似于索引的作用，但是比B+树占据了更小的内存空间。
 *  如果通过聚集索引访问，则先查看聚集索引，若没有再查看Filter；如果通过非聚集索引访问，即，索引值不唯一，那么同时检查索引和Filter。
 *  Filter只会有false postive，即，数据不在磁盘，但是Filter会告诉DBMS数据在磁盘。不会有false negative，即，数据在磁盘，但是Filter告诉DBMS数据不在磁盘。**以此来保证永远不会page fault。**
 *  Filter只能判断数据是否在磁盘，而不能判断数据在磁盘中的位置。所以需要额外的数据结构去维护位置信息。如下图所示的，磁盘中的索引。

![15161424600182.jpg][]

#### 选择3：OS Virtual Memory ####

*  依赖操作系统跟踪磁盘上的数据，使用mmap。
 *  DBMS不需要维护任何额外的元数据。

### 数据取回策略 ###

选择1：只取回需要tuples

*  仅将通过查询访问的元组重新合并到内存中的表堆中。
 *  需要额外的记录来追踪。

选择＃2：所有元组在块

*  将页中所有元组都移入内存，无论是否需要。
 *  更多的CPU开销来更新索引。假设tuple大小较小，一个页内会存在非常多的tuple，那么也就是需要维护更多的索引。
 *  部分元组很可能会被再次移出。

### 查询执行策略 ###

选择1：中止并重新启动

*  中止访问不存在与内存中的元组的事务。
 *  从磁盘中检索数据，并使用单独的后台线程将其合并到内存中。
 *  数据准备就绪后，重新启动事务。
 *  不能保证大型查询（OLAP查询）的一致性，即，如果一个查询需要访问多个页，那么一次重启只能将一个页的数据拿回，这样就会导致重启多次。同样的，如果DRAM无法存下所有需要的数据，可能会因此将第一次重启取回的数据再次移出内存，导致重启死循环。

选择2：同步检索

*  事务继续执行
 *  当事务需要修改或者访问不在内存中的数据时，再将其停止，移出数据后重启。

### 合并策略 ###

选择＃1：总是合并

*  检索到的元组总是放在原有表堆中。

选择2：仅在更新时合并

*  如果在UPDATE查询中使用已检索的元组，则只将它们合并到表堆中。
 *  所有其他元组都放在临时缓冲区中。

选择3：选择性合并

*  跟踪每个块的检索频率。
 *  如果块的访问频率高于某个阈值，则将其合并回表格堆。

[15161400566044.jpg]: https://lh3.googleusercontent.com/-V5Kv5nqF3dY/Wl6XjTUHN8I/AAAAAAAAAkM/AUA5MIK2aYwxgBqjCCgux4S7-k0eFm7_gCHMYCw/I/15161400566044.jpg
[15161405303371.jpg]: https://lh3.googleusercontent.com/-Svaejeb5JE8/Wl6Xj2UgMfI/AAAAAAAAAkQ/hiF1TESef1sGHrzuXsu4Ps0oYy-ZL_5gQCHMYCw/I/15161405303371.jpg
[Link 1]: https://en.wikipedia.org/wiki/Mmap
[Link 2]: https://baike.baidu.com/item/mmap/1322217?fr=aladdin
[In-Memory Performance for Big Data]: http://15721.courses.cs.cmu.edu/spring2017/papers/23-largethanmemory/p37-graefe.pdf
[15161418946115.jpg]: https://lh3.googleusercontent.com/-rLyTeI6WZkg/Wl6XkG-eUhI/AAAAAAAAAkU/In1MeZJyQYQJ7bAcdwG8nstY81kB8h2vgCHMYCw/I/15161418946115.jpg
[15161419352415.jpg]: https://lh3.googleusercontent.com/-KiAr1Bkx6HA/Wl6XkYGIxhI/AAAAAAAAAkY/uL6t1BIAOTsPllFpLnToitqu0XEdhuOJgCHMYCw/I/15161419352415.jpg
[15161424600182.jpg]: https://lh3.googleusercontent.com/-0HbXJFRwyhw/Wl6XkWITSsI/AAAAAAAAAkc/uDUSDrkoFLorlvfRFzZn66Sl1o7XTEzgACHMYCw/I/15161424600182.jpg