分布式KV存储系统的设计清单（一）
11 Mar 2017分布式系统所面临的基本问题
一个分布式存储系统首先也是个分布式系统。所以分布式系统所面临的问题。KV同样需要解决。
必须是一个能够容错的系统。设计容错系统的一个基本原则：网络永远是不可靠。任何一个消息只有收到Ack后才能认为发送成功的。 所以在系统设计的时候我们必须总是假设网络一定会出问题。典型的网络问题：网络抖动，闪断。等等。如果网络异常出现系统依然能够具有相应的服务能力。而不是出现：消息丢失，乱序。在诸多的网络异常中：“网络分区”是极为特殊的。通常表现为，集群被划分成了多个几个相对自治的小区域。这个小区域内能够互相通信，而多个“区域”之间无法正常通信。解决此类办法通常是要依靠，多数派协议——Paxos，Raft等。
磁盘故障 在大规模的集群中是一种概率较高的异常。因为分布式的存储系统必须将数据分布到多台个几点上。以保障系统数据可恢复。
系统状态如何同步。经典的分布式系统架构通常有两种：去中心化的，及有中心节点的。对于去中心化的节点，会用gossip协议来做。相对有中心管控的节点Master会知晓集群内节点的所有状况。该节点相当于集群内的大脑。另外，一个分布式系统在实现上永远是个“三态”系统。既——成功，失败，超时。对于超时状态调用方不应该做任何假设。这是一种未知的状态。具体的处理结果可能成功，也可能失败。典型的处理方式是把系统操作设计成幂等。比如说覆盖写就是典型的幂等操作。如果不能够做到幂等。在每个改变系统状态的操作的时候，都要读取之间的状态来进行验证了。
分布式的存储系统所需考虑的核心关注点
下面列出了一个分布式存储系统必须面临的问题。这些问题是必须要面对解决的。
- 数据分布问题
- 数据一致性问题
- 引擎选择问题
- 架构考量，核心关注点——内存管理，IO管理，故障隔离，必须可恢复，必须高可用。
数据如何分布，其实数据的分布问题不仅要解决得是将数据分散到多个节点上。更为关键的是，数据在分散到多个节点之后，依然能够保障，多台机器之间的负载比较均衡的。衡量机器负载的关键因素无外乎是：Load值，CPU，内存，网络，磁盘。等使用情况，读请求，及写请求的数量。一个合格的分布式存储系统需要能够识别出高负载的节点，并能够做出合理的“迁移计划”，是整个系统的负载相对平均。对于数据分布来说：主要有两种方式：Hash分布，Range分布。典型的代表：Dynamo，HBase。
Range分布，一般的做法是将大表分拆，将其拆分成连续的多个小范围的子表。在HBase中对应的是Region。Range分布的一个好处是，数据有序，这是一个巨大的优势，不仅能够支持随机的Read，Write，还支持数据Scan。Range分布时候需要考虑的问题是子表的分裂与合并（过程及其复杂，可以看成是一个分布式事务问题）。这与B+树的结构类似，子表相当于B+树叶子节点。随着数据的写入，很可能造成Region数据分布不均。在时序数据的场景唯有突出。数据存储如果有热点那么在计算上必然存在热点。集群内的资源很难保证均衡了。那么如何避免数据热点，或者说如何能够让数据均匀分布呢。这跟数据使用场景是个正相关的。通常来说需要在应用层多做些工作。比如在key上加Salt。似数据尽量的能够散裂开。
Hash分布，Hash分布很常见，其方法一般是通过指定一个Hash Key，对Key做Hash之后在与集群中的具体节点关联。Hash分布的好处显而易见，如果Key的散列性很好，那么数据分布相对均匀，Dynamo使用的是一致性Hash的算法，一致性Hash是将Key跟Node同时做Hash之后映射到一个数值空间内，然后通过一个环形的地址空间找到一个对应的映射关系。这样就避免了在增减节点时候对大量的地址变动。Hash分布的缺点就是打破了数据的有序性。不能够支持Scan操作。那么如果这种Scan的需求要怎么办？通常是在应用层出一些妥协。比如：按照UserId Hash。这样对就可以支持对用一个用户的Scan操作。然后由上层来merge多个用户的结果。通常来说Hash key一定要选择区分度大的来做。
综上所述，不论是数据如何分布，都可以映射到下面的通用的模型，这是一个典型的两层结构:
- Key -> Partition。将数据映射到数据分片。
- Partition -> Node。将分片映射到一个物理节点上。
分片是什么？分片是个逻辑概念。类比于RDBMS中的表。对于数据分片创建的基本原则——多个分片不能在同一个节点上，在同一节点上的分片也要尽量分布在不同磁盘上。这样IO才能尽量平衡，同时可用性也是有保障的。
数据一致性问题，严格的来说一致性只有一种——数据强一致。包括RDBMS中的各种事务隔离级别，都可以看成是为了追求性能对一致性的打破。在分布式系统中由于数据分布在不同节点一致性问题更被放大。我们从用户角度思考一致性问题。 假设有2个不同的用户，UserA，UserB。如果UserA能够在数据写成功之后马上读到他写的数据。那么这个一致性至少是Session 一致的。如果写完之后不仅UserA 能够成功读到。UserB也能够读到。这是强一致性的。如果在一个不一致的时间窗内能够读到数据，这是最终一致性。不保证一定能够读到最新数据。弱一致性。不同的一致性选择，对应的复制方式也是不同的。如果是强同步复制，对应所有副本都成功才返回客户端。如果是异步复制，通常至少一半以上的副本返回成功即可(可参考NWR模型)。弱一致性的应用场景有限，客户端需要做很多额外的工作。一致性跟可用性之间是矛盾的。强一致性的复制协议虽说可以保证副本之间的一致性。但一旦副本出现故障，很有可能阻塞系统的正常服务。好在现在Raft，Paxos都相对成熟解决这些问题了。
单机的存储引擎，对数据的基本操作无非是CRUD，其中读操作严格的说以可以分为随机读和顺序读。从数据结构上来说，Hash存储引擎，刚刚前面说了，不支持顺序扫描。B Tree的存储引擎，除了CRUD，还支持顺序扫描。B Tree最大的问题就是破坏了磁盘IO的顺序性。叶子节点之间的分裂也会导致数据在物理存储上不连续。LSM引擎跟B Tree在功能上一样。通过批量转存的技术避免磁盘的随机写入问题。以LevelDB为例，写入操作比较简单，只需要一次顺序磁盘操作，跟一次内存的写入。但是读操作就相对复杂。需要在内存的各个Level中按照数据的新老依次查找，好在磁盘上的数据是有序的。通常这一类的引擎会定期执行compaction操作来对已有的数据进行压缩整理。这样能够减少数据的规模。不过LSM类的引擎也不是万能的，写入放大的问题依然存在，尤其是写入的key非常随机的时候。
本来想一篇写完，但是细节实在太多。尤其是架构跟一些通用的。下次在写吧。