HyperLevelDB LevelDB 英文原文：Inside HyperLevelDB LevelDB是非常流行的数据存储，它远远超出了在谷歌Chrome的最初使用，已经应用在多个领域。毫不令人吃惊的是许多创业公司和大型的公司都在使用LevelDB：LevelDB内部采用连续的块存储数据，充分发挥了顺序磁盘I/O的性能，并且运用了现代操作系统里的高性能缓冲区管理。这样的结构正好迎合了现代内存的层次式结构， 避免了与产生高性能的操作系统决策之间的冲突。 其它翻译版本 (1) 加载中

常用的LeveDB是良好的基础，我们对HyperDex的经验使我们看到了几个进一步提高LevelDB性能的机会。这篇文章阐述了我们对LevelDB所作的更改满足了HyperDex客户端的高标准的需求。
尤其是我们在两个方面的更改提高了LevelDB性能:

• 通过细致的所管理机制增加了并行性
• 通过改进压缩过程增加了吞吐量

这篇文章详细的描述了这些更改，以给你这样的直觉：为什么因更改而产生的HyperLeveDB分支如此之快。

改进并行

保持Stock LevelDB的互斥锁特性，确保能同时多线程安全的写入数据库。类似Python的全局解释锁，

这种简单的单线程互斥锁进行多任务处理时很耗性能。现在的CPU都有多个核心，它的优点就是利用多核心高效的执行指令。所以，我们首先要做的就是解锁。

当然，做的时候要小心谨慎以避免数据错乱。简单地检查Stock LevelDB的并行事件然后重新认识的HyperLevelDB。

常见的LeveDB提供了内部同步机制，这样就允许多个线程并行地访问数据存储。在内部，写是按照FIFO顺序进行的：处于FIFO最先位置的写线程是唯一一个可以写入数据库的线程，而且所有正在排队的其他线程必须等待。每次写都向磁盘的备份日志和内存的备份“内存表”里插入数据。这个日志是只增加的文件，他可以为崩溃恢复提供持久性支持，而这个内存表是已经排序的跳跃表，它能够使读线程快速地查找存储在日志里的数据。在向FIFO里的下一个写线程发送信号之前，当前写线程必须向日志和内存表里写入数据。

为了克服排队所造成的影响，常见的LevelDB分批写FIFO最开始部分所包含的数据，在一个分批处理里有许多写线程在写入数据。这样的分批处理提高了性能，尤其是提高了同步写的性能，不过从根本上来说，没有更改顺序写这个特性。还可能花费更多资源，因为做分批处理的线程必须读，并且可能拷贝其他线程写入的数据。只要FIFO的最先位置的线程正在做任何真正的写工作的话，内核就阻塞其他写线程，以等待最先位置的写线程所发送信号。

HyperLeveDB并行性

HyperLevelDB改进了写线程的并发性：允许多个写线程独立地插入自身要写的内容到日志和内存表里，同时仅仅为了维护写的顺序而使用同步机制。为了了解HyperLevelDB是如何做这些工作的，理解LevelDB里读和写交互的方式就特别重要。

在LevelDB内部，LevelDB为每次写都指定了一个由不断增长的计数器产生的唯一序号。这些序号使得读线程能够及时地从某个特定的位置读取数据，序号适时地标注这个位置，而且忽略了任何在这个序号之后所发生的写。LevelDB快照捕捉在创建快照那个时刻的最后一个序号，使得在不用查看任何后续的写内容的情况下不断地替换快照或者读取数据。任何不能在快照上执行的读都隐含地使用了最新的序号。序号是HyperLeveDB并行优化的关键，因为它们给出控制读线程可看到的数据范围的一种方法。

HyperLevelDB保持这样一个不变的事实：读线程选择的序号从不取决于任何仍然未完成的写线程。写线程可以以任何顺序更新日志和内存表，而且从不关心写线程各自的序号。写完后，每个写线程使用同步机制去更新全局序号，这样写线程看起来是按照FIFO的顺序来执行的，这保持了所要求的顺序不变。每个写线程负责独立地更新日志和内存表-这导致了大量的工作，并且只有使用同步机制递增便于即将到来的读线程使用的序号才能解决这个问题。

为了充分利用这个新发现的并发特性，HyperLevelDGB修改了LevelDB的日志和内存表的实现，以达到允许安全地并发插入。

线程安全的内存表：内存表实现为并发跳跃表。谷歌LevelDB的跳跃表允许进行与锁无关的读，并且对写线程使用外部的同步机制。读和写具有相同的第一步：遍历跳跃表以在表中查找期望的关键字。我们线程安全级别的实现确实在没有拥有任何锁的的情况下执行这个遍历，然后验证这个遍历，获得锁之后可能还需要进一步的遍历。这把向跳跃表插入的大部分耗时的工作移到锁控制的范围之外，这个实现允许所有线程在不需要牺牲正确性的同时并行地执行插入数据到跳跃表。在我们的测量数据里使用四个写线程，我们改进的跳跃表99%的插入延迟为1.7微秒，而默认的跳跃表99%的插入延迟为2.6微秒。

线程安全的日志：只增加的日志是具有用户缓冲空间的文件。谷歌的做法是向文件末尾增加内容，必要的情况下在文件上使用mmap和munmap系统调用维护用户缓冲空间组成的滑动窗口。HyperLevelDB的做法也是使用mmap和munmap系统维护用户缓冲空间，不过允许并发线程自动向文件添加内容。日志文件同步底层的缓冲的访问，并且给不同的写线程指定非重叠区，这就允许写线程并行地拷贝自己的数据

改进了压缩

LevelDB这个名字源于它使用了层级性的存储结构。数据是存储在每个层级里的，每个层级比下面层级存储更多数据。在每个层级内部，数据是排序的，并且存储在称作排序字符串表或者SST的文件里，这儿每个排序字符串表也进行了排序，并且排序字符串表是非重叠的，因此每个关键字最多存储在一个字符串表里。写的内容将合并这棵层级树的底部，然后名字为压缩的进程将透过层级把数据上移，同时在每个层级内部保持排序。

LevelDB内部使用的增量压缩是在不压缩和全压缩两个压缩极端之间权衡的结果。如果没有任何压缩的话，那么写入系统的数据就是无序的，执行关键字查找就需要线性地访问所有数据。另外压缩也可以采用另一个极端，在这种情况下排序所有的一切，这时产生不断增大的排序字符串表，并且每次压缩都重新把全部数据写入磁盘。LevelDB里的压缩确保数据是排序的，同时提高读的效率，不过执行增量压缩可以限制压缩写入数据的数量。 任何形式的压缩的不利的一面是：它与生俱来必须承受一种形式的 写入放大，这种情形下磁盘I/O的量是写入到LevelDB数据量的几倍，因为数据将被重新写入到这个层级树的每个级别里。层级间大小的指数化差异几乎确保X层级的字符串排序表将被X+1级别的多个排序字符表覆盖。在我们的经验里，默认的LevelDB的做法将对X层级的每个字节在X+1层级将重写三个字节。只有由LevelDB产生的四分之一I/O做了富有成效的工作；其余都是在浪费I/O，是优化的目标。
可以采取许多种减少这种浪费I/O的方法，包括：

•  使用经验性分析方法调整压缩相关的常量以减少写入放大。
•  在低层级里保持数据无序，以避免线性合并所带来的资源使用，减少读延迟
•  选择可明显地使写放大减小到最小的压缩目标（即排序字符串表）

在这三种方法里，只有一种直接解决了写放大这个问题。前两种方法需要人工手把手的调整，来找到给定负载情形下最佳性能  点。我们发现这种调整非常脆弱并且不令人满意，因为它与工作负载紧密相关。HyperLevelDB使用了第三种方法，对压缩进程的原理进行了重新设计。
 

降低写放大的压缩器

HyperLevelDB更改了压缩算法，明显地选择在两个级别直接产生最小写放大的一组字符串排序表。一个后台压缩线程监控每个层级  的大小，并且对最适合压缩的一组字符串排序表进行压缩。第二个后台线程在第一个线程无法承受更多负载的时候触发，它执行  全局优化以选择可降低写放大的压缩目标，而且并不关心每个层级的大小。典型的情况是，第二个线程将在不做任何写放大的情况下  从下层级移动文件。对上面的层级来说，第二个线程抢先压缩数据，这经常足以使得高层级的大小比第一个线程所使用的限制大小的启发法所得的结果要小，同时确保第一个后台线程不和高级别的压缩紧密相连。

本文中的所有译文仅用于学习和交流目的，转载请务必注明文章译者、出处、和本文链接。 2KB翻译工作遵照 CC 协议，如果我们的工作有侵犯到您的权益，请及时联系我们。

2KB项目（www.2kb.com，源码交易平台）,提供担保交易、源码交易、虚拟商品、在家创业、在线创业、任务交易、网站设计、软件设计、网络兼职、站长交易、域名交易、链接买卖、网站交易、广告买卖、站长培训、建站美工等服务