KV分布式存储

KV 数据库

KV，Key-Value,让人想定Mongo数据库，和JSON数据交换格式。 数据存储，存储的数据主要分两种：结构数据（关系表），非结构数据（大文件，杂数据（模式和内容揉合（HTML））

分布式存储系统

1、分布式文件系统：存储文本，图片，音视频等非结构化数据。如google的GFS/colossus和开源的hdfs。

2、分布式键值系统：存储简单的半结构化数据。NoSql的分布式扩展，只提供基于key的增删改查（CRUD）功能。如Amazon的Dynamo。

3、分布式表格系统：存储复杂的半结构化数据。相较于分布式kv系统，他还支持基于key的范围查找。但相对于关系型数据库，他不支持复杂的操作，如多表关联，嵌套查询。典型的系统如google的bigtable和开源的hbase。

4、分布式数据库：存储结构化数据。分布式的关系型数据库。提供SQL关系查询语言。如：google的spanner和开源的hive。

单机存储引擎

存储系统提供的基本功能包括：增删改查（CRUD==增加(Create)、读取查询(Retrieve)、更新(Update)和删除(Delete))。不同的存储方案根据业务不同侧重点不同，导致存储系统的性能和功能具有一定的差异。

目前主要的单机存储引擎有：

1、哈希存储：hash的CRUD是快的。但缺点是不支持顺序扫描。bitcask是一个基于hash表结构的存储系统。他将写操作（包括删除标识）追加到文件尾。并定期合并新老文件&记录。

2、B树：既支持随机读取又支持范围查找的系统。查找时间复杂度为logd(n)（d为每个节点的出度）。Mysql的InnoDB的引擎和OS的文件系统使用的就是B+树。（为什么选择使用B树的变种B+树，读者有兴趣可以去探究下。提示：磁盘读取）

3、LSM树(Log Structured Merge Tree)：由B+数改进而来。其思想为：将增量写操作保存在内存中，超过阈值时刷入磁盘，从而减少随机写磁盘操作。读操作则需要合并磁盘数据和内存中的写操作。通过Memtable/SSTable实现，实现细节在此不做深入探究。比较适合写操作较多的业务场景。BigTable/HBase/Cassandra中的列簇的数据存储方式采用的即是LSM树。

RocksDB

RocksDB相对传统的关系数据库的一大改进是采用LSM树存储引擎。LSM树是非常有创意的一种数据结构，它和传统的B+树不太一样.

RocksDB的主要设计目标是保证存取快速存储器和高负载服务器更高效，保证充分利用Flash或RAM子系统提供的高速率读写，支持高效的查找和范围scan，支持高负载的随机读、高负载的更新操作或两者的结合。其架构应该支持高并发读写和容量大增时系统的一致性。

RocksDB是一个嵌入式键值存储器，其中键和值是任意的字节流。RocksDB中的所有数据是按序存放的。常见操作包括Get(key), Put(key), Delete(key) and Scan(key)。 RocksDB有三个基本结构：RocksDB memtable,sstfile和logfile。memtable是一个内存数据结构——新数据会插入到memtable和日志文件（可选）。日志文件是 顺序写入的，位于磁盘。当memtable写满后,数据会被刷新到磁盘上的sstfile文件，同时相应的日志文件可以安全地删除。sstfile中的数据经过排序的,目的 是为了加快键查找。

分布式键值系统：由多个RocksDB构成的分布式键值系统

元信息节点Meta Server、存储节点Node Server及Client。Meta负责元信息的维护、Node的存活检测及元信息分发；Node负责实际的数据存储；Client的访问需要先从Meta获得当前集群的完整数据分布信息，对每个用户请求计算正确的Node位置，并发起直接请求。

为了减轻上面提到的中心节点的单点问题。我们采取了如下策略：

• Meta Server以集群的方式提供服务，之间以一致性算法来保证数据正确。
• 良好的Meta设计：包括一致性数据的延迟提交；通过Lease让Follower分担读请求；粗粒度的分布式锁实现；合理的持久化及临时数据划分等。更详细的介绍见：Zeppelin不是飞艇之元信息节点
• 智能Client：Client承担更多的责任，比如缓存元信息；维护到Node Server的链接；计算数据分布的初始及变化。
• Node Server分担更多责任：如元信息更新由存储节点发起；通过MOVE，WAIT等信息，实现元信息变化时的客户端请求重定向，减轻Meta压力。更详细的介绍见：Zeppelin不是飞艇之存储节点