事务处理的数据存储

在上篇文章我们讨论了数据模型，今天试着讨论更基础的数据存储和搜索。数据存储根据开发者使用，可以分为一般的事务处理和数据分析，因为这两者面临的情况不一样。事务处理聚焦于快速的存储和搜索少量的数据，但是数据分析需要读取大量的数据去进行聚合，而不怎么考虑读取花费的时间。后者一般称为数据仓库。

首先我们先看看传统数据库和大部分NoSQL的数据存储引擎。这个实际上分为两个流派，一个是基于日志结构，主要使用了LSM树，另一个是基于OS的页的结构，就是所谓的B树。这么说可能比较难懂。让我们想象一下，假设你有一个excel，里面存储了一条数据a,b，如果我们想查询a，我们可以遍历excel找到满足以a开头的数据a,b。这就是一个简单的数据库，存储数据时，只要简单的添加在下一列。查找时进行遍历，找到符合条件的。让我们想想这会有什么问题。对于数据存储，我们只需要简单的添加数据，对于磁盘这样极有效率，当然实际上的数据库还要考虑并行处理、磁盘存储空间不足等等情况。存储数据的file，就是所谓的log。另一方面，对于搜索数据，这个效率就相当慢了，因为每次搜索数据都需要遍历整个文件，时间复杂度是线性的增长，这时候我们就需要索引了。显然索引对于整个数据存储文件而言，是额外的存储结构，维护索引结构会牺牲write的效率。

对于索引结构，首先想到的是key-value结构。例如对于数据a,b c,f,d这种数据，我们可以用一个索引a,0 b,3这种hash map的形式0和3代表着文件的offset，我们查找数据的时候，先去hash map找到对应的key值，获得offset，我们就能获得key值对应的value。这听起来很简单，然而这就是Bitcask的实现方式。这个索引结构是完全存储在内存当中，如果超出内存的话，就会放在磁盘上。如果数据一直在增长，磁盘空间肯定会有不足的那一刻，解决办法就是将数据拆分为固定大小的segment，以及在合适的时候，合并segment，根据时间戳，保留最新的value值，重新写入新的segment，对旧的进行删除。对于实际的工程，我们还需要考虑

1.文件存储的格式，一般而言应该是以bytes存储

2.删除数据时，应该加上一个标签，比如tombstone，在合并segment时，对数据进行删除

3.数据库崩溃重新恢复，Bitcask使用的是快照的方式在磁盘保存索引结构

4.并发的写入数据，这个需要检查点来处理数据写入时数据库崩溃

5.并发控制，因为文件的immutable，所以并发控制相当简单。

但是这个依然存在问题，让我们想想，那就是hash table必须存储在内存中，这个对于大数据时很不友好，即使你是存储在磁盘上。并且对于范围查找很不友好，因为你需要遍历所有key去查找一个范围内的一个key。

为了解决范围查找，人们又提出了在创建索引时，我们可以按照key值进行排序，这样的存储方式叫做SSTable。这样有下面的几个好处，合并segment变得更有效率了，因为你只需要读取开始的key和结束的key就可以了。在保存索引时，也不需要将所有的key存储在内存里，只需要保存每个segment的开始key和结束key。读取数据时，也不需要遍历所有的key值了。那么对于维护索引呢？我们在写入数据时，会先写入memtable（存储在内存的例如红黑树之类的数据结构）。当memtable超过某个阈值时，会将memtable写入到磁盘的segment中。在读取数据时，我们会首先在memtable中查找数据，然后再根据时间逐步读取segment。每隔一段时间，后台进程便会合并segment，清理垃圾数据。这样处理的唯一问题，就是memtable遇到服务器崩溃。我们可以牺牲一部分write的效率，生成一个独立的log去立马保存写入的数据，这个log的唯一用途就是防止memtable的丢失。

上面的就是现在HBase、LevelDB、Lucene这些使用的LSM树结构。对于其的优化，目前可以使用布隆过滤器、size-tiered等方式去优化读取和合并segment。除了LSM树，目前还有一个广泛使用的索引，那就是B树。

B树主要是利用了操作系统的页结构，将数据拆分成一个固定尺寸的block块，使用存储address和location，类似于指针的方式存储数据。具体细节不多说，网上的文章一大堆。我们需要考虑的是负载因子和二叉树的平衡。对于每次的写入和修改数据，我们都需要找到key值在系统里对应的address去修改数据，重新写入，同样为了防止数据崩溃，一般的数据库会使用预写日志(WAL)去保存每一次数据的修改和写入。

除了这些索引，还有所谓的二级索引。这个类似于倒排索引。不仅如此，还有基于列的存储方式，这个大多是为了数据仓库服务的。