ABase架构

ABase是NoSQL存储引擎，架构分为Redis Client、Proxy、Abase Group三层，其中：

1. Redis Client：ABase支持Redis协议，业务层使用Jedis客户端访问数据库。其中，value值仅支持字符串。
2. Proxy：协议转换、路由、管理（如扩容、缩容等）。通过key的hash值来进行路由。
3. ABase Group：ABase的最小原子单位，通常为一个Master节点，多个Slave节点（类似于Redis Cluster）。Group内支持全复制、半复制、不复制的写入同步方式。
4. ABase Node：Abase实例。存储分为缓存与RocksDB，通过ABase Server对其进行管理。

RocksDB与LSM-Tree

block LSM-Tree算法借鉴了log的形式，将log以时间顺序追加写入磁盘，来实现高效的写入性能；同时，又采用了传统数据库的思想，在各个时间段的log内对数据重新组织并索引，保障了读性能。

• memtable：内存中的数据表。RocksDB将一段时间内的写入存储在内存中相同的memtable表中，该表通常使用红黑树，对key进行字典序排序。
• WAL：持久化日志。为防止内存中数据丢失，将写入操作追加到WAL末尾。
• sstable：硬盘中的数据表。RocksDB将从内存持久化后的数据存储到多个sstable中，每一个sstable中的key是唯一的，k-v长度不定。文件末尾存储了该table的索引，用于二分查找。

数据写入

1. 将写入操作的信息记录到WAL中；
2. 将key和value写入到当前的memtable中。

注意：此时内存中可能存在多个memtable，创建时间依次递增。我们仅将数据写入到最近的table中，如果是删除，则在该table中将key对应的值设为已删除。因此，内存中的各memtable可能会存在同一个key的不同value，最新的memtable对应的value为最新。

Merge

Mem 2 Disk L0

由于内存资源的限制，memtable的数量不会无限增长。当超过阈值时，需要将其持久化到硬盘，这就是Merge操作。

1. 合并memtable，多个key的情况下仅保留最后一个值；
2. 在L0层新建sstable，将所有数据以key字典序的形式写入到sstable中，并在文件末尾添加索引；
3. 删除memtable，和其对应的WAL。

注意：同memtable，Disk L0层的多个sstable依旧可能会存在同一个key的不同value，最新的sstable对应的value为最新。

Disk Ln 2 Disk Ln+1

在上文的基础上，每次读取，最坏情况下需要读取所有的磁盘文件，这是我们不能忍受的。LSM-Tree的核心思想，就是将多个文件按照更新时间，以树的形式分为多层，越早更新的文件，在越上层。此举将O(n)的读取复杂度降到了O(Log(n))级别。

1. 以第n层为例，每次触发merge操作时，选取该层的一个sstable，并仅在下一层中寻找关联的sstable(存在相同key)。
2. 将上一步找到的所有sstable，使用归并排序(sstable本身就是有序的)，在n+1层生成一个新的sstable。

注意：

• 从L1开始，相同层中不会出现相同的key了，可以在每一层中使用布隆过滤器来加速定位key所在的sstable
• 不同层中可能会出现相同的key，层数越低，该key对应的value越新。

数据读取

1. 按时间顺序倒叙查找memtable，若查到，返回值；
2. 按时间顺序倒叙查找第0层的sstable，若查到，返回值；
3. 依次查找各层的sstable，每层使用布隆过滤器初步筛选，直到找到key。