KV存储（Squirrel、Cellar架构）
KV存储（Squirrel、Cellar架构）
NoSQL存储：非关系型数据库，它以键值对存储，结构不固定，可减少时间和空间开销。
KV存储（键值存储、Key-Value存储）是NoSQL存储的一种方式。值可以是任意不定长数据。非常适合不涉及过多数据关系业务关系的业务数据，同时能有效减少读写磁盘的次数。
KV存储的数据主要分两种：结构数据（关系表），非结构数据（大文件，杂数据）。
关系型数据库中的表都是存储一些格式化的数据结构，便于表与表之间进行连接等操作，但也是关系型数据库性能瓶颈的一个因素。它不能满足以下“高”需求：
①对数据库高并发读写的需求；
②对海量数据的高效率存储和访问的需求；
③对数据库的高可扩展性和高可用性的需求
为了解决这类问题，非关系数据库应运而生。Google的BigTable与Amazon的Dynamo是非常成功的商业NoSQL实现。一些开源的NoSQL体系，如Membase，MongoDB，Cassandra，BeansDB，Redis等，也得到了广泛认同。
键值对存储不需要了解值中的数据，也没有任何结构。这同时表示像SQL那样用WHERE语句或者通过任何形式的过滤来请求数据中的一部分是无法做到的。如果你不知道去哪找，你必须遍历所有的键，即表示只有当键已知的时候才能体现出最佳性能（注意：一些键值对存储能够存储结构化的数据并有字段索引）。
因此，即使键值对存储在访问速度上经常比关系型数据库系统性能要好数个数量级，但对键已知的需求也限制着其应用。
分布式存储系统：
1、分布式文件系统：存储文本，图片，音视频等非结构化数据。
2、分布式键值系统：存储简单的半结构化数据。
NoSql的分布式扩展，只提供基于key的增删改查功能。
3、分布式表格系统：存储复杂的半结构化数据。
相较于分布式kv系统，他还支持基于key的范围查找。
相对于关系型数据库，他不支持复杂的操作，如多表关联，嵌套查询。
4、分布式数据库：存储结构化数据。分布式的关系型数据库。提供SQL关系查询语言。
单机存储引擎：
1、哈希存储：hash的CRUD是最快的。缺点：不支持顺序扫描。
2、B树：支持随机读取、范围查找的系统。查找时间复杂度为log(d(n))（d为每个节点的出度）。
3、LSM树(Log Structured Merge Tree)：将增量写操作保存在内存中，超过阈值时刷入磁盘，从而减少随机写磁盘操作。读操作则需要合并磁盘数据和内存中的写操作。
RocksDB：
相对传统的关系数据库采用了LSM树存储引擎。
主要设计目标是保证存取快速存储器和高负载服务器更高效，保证充分利用Flash或RAM子系统提供的高速率读写，支持高效的查找和范围scan，支持高负载的随机读、高负载的更新操作或两者的结合。其架构应该支持高并发读写和容量大增时系统的一致性。
RocksDB是一个嵌入式键值存储器，其中键和值是任意的字节流。RocksDB中的所有数据是按序存放的。常见操作包括Get(key)，Put(key)，Delete(key)，Scan(key)。
RocksDB有三个基本结构：RocksDB memtable，sstfile，logfile。
memtable是一个内存数据结构——新数据会插入到memtable和日志文件（可选）。日志文件是顺序写入的，位于磁盘。当memtable写满后，数据会被刷新到磁盘上的sstfile文件，同时相应的日志文件可以安全地删除。sstfile中的数据经过排序的，目的是为了加快键查找。
分布式键值系统：由多个RocksDB构成的分布式键值系统。
KV 存储发展历程
第一代分布式KV存储架构（左图）。在客户端内做一致性哈希，在后端部署很多的 Memcached 实例，实现了最基本的 KV 存储分布式设计。
问题：如在宕机摘除节点时，会丢数据；需要扩容时，一致性哈希会丢失一些数据等。
引入Redis（右图的架构）。服务器端变成了Redis组成的主从结构。当节点宕机时，可通过Redis哨兵完成Failover，实现高可用。
问题：扩缩容时，一致性哈希仍然会丢数据。
一个比较成熟的KV存储开源项目：阿里Tair
Tair开源版本的架构主要分成三部分：存储节点会上报心跳到它的中心节点，中心节点内部有两个配置管理节点，会监控所有的存储节点。当有任何存储节点宕机或者扩容时，它会做集群拓扑的重新构建。当客户端启动时，它会直接从中心节点拉来一个路由表（一个集群的数据分布图），客户端根据路由表直接去存储节点读写。
针对之前KV的扩容丢数据问题，它也有数据迁移机制来保证数据的完整性。
问题：
①中心节点没有类似分布式仲裁的机制，在网络分割的情况下，有可能发生“脑裂”。
②在容灾扩容时，数据迁移会影响业务可用性。
③Redis的数据结构特别丰富，而Tair还不支持这些数据结构。
redis官方发布集群版本Redis Cluster，演进出全内存、高吞吐、低延迟的KV存储 Squirrel。 基于Tair，演进出持久化、大容量、数据高可靠的KV存储Cellar。
如果业务的数据量小，对延迟敏感，建议用Squirrel ；
如果数据量大，对延迟不是特别敏感，建议用成本更低的Cellar。
内存KV Squirrel架构和实践：
先介绍两个存储系统共通的地方：分布式存储问题：Key是怎么分布到存储节点上的？
拿到一个Key，用固定的哈希算法得到一个哈希值，将哈希值对Slot数目取模得到一个Slot id（两个KV现在都是预分片16384个Slot），再根据路由表就能查到这个Slot存储在哪个存储节点上。这个路由表简单来说就是一个Slot到存储节点的对照表。
Key → H(key) → H(key) 对Slot数目取模 → Slot id → 路由表中查对应哪个存储节点
下图为Squirrel架构。中间部分跟Redis官方集群一致。它有主从的结构，Redis实例之间通过Gossip协议通信。添加了一个集群调度平台，包含调度服务、扩缩容服务和高可用服务等，它会管理整个集群，把管理结果作为元数据更新到ZooKeeper。客户端会订阅 ZooKeeper上的元数据变更，实时获取到集群的拓扑状态，直接在Redis集群进行读写操作。
高可用架构：
从宏观的角度来看，高可用就是指容灾怎么做；
从微观的角度看，高可用就是如何保证端到端的高成功率；
Squirrel节点容灾——HA高可用服务
对于Redis集群而言，官方提供的方案，任何一个节点从宕机到被标记为FAIL摘除，一般需要经过30秒。主库的摘除会影响数据的完整性，所以需要谨慎一些。从库完全没必要。
内存的KV存储数据量一般都比较小。若业务量很大，它往往会有很多的集群。如果发生交换机故障，会影响到很多的集群，宕机之后去补副本就会变得非常麻烦。为了解决这两个问题，做了HA高可用服务。
它的架构如下图所示，它会实时监控集群的所有节点。不管是网络抖动，还是发生了宕机（比如Redis 2），它可以实时更新ZooKeeper，告诉ZooKeeper摘除Redis 2，客户端收到消息后，读流量就直接路由到Redis 3上。如果Redis 2只是几十秒的网络抖动，HA节点监控到它恢复后，会把它重新加回。
如果过了一段时间，HA 判断它属于一个永久性的宕机，HA节点会直接从Kubernetes集群申请一个新的Redis 4容器实例，把它加到集群里。拓扑结构又变成了一主两从的标准结构，HA节点更新完集群拓扑后，就会去写ZooKeeper通知客户端去更新路由，客户端就能到Redis 4这个新从库上进行读操作。
通过上述方案，把从库的摘除时间从30秒降低到了5秒；把宕机补副本变成了一个分钟级的自动操作，不需要任何人工的介入。
Squirrel跨地域容灾
①相对于同地域机房间的网络而言，跨地域专线很不稳定；
②跨地域专线的带宽是非常有限且昂贵的。
如何通过集群同步服务，把北京主集群的数据同步到上海从集群上？
按照流程，首先要向同步调度模块下发“在两个集群间建立同步链路”的任务，同步调度模块会根据主从集群的拓扑结构，把主从集群间的同步任务下发到同步集群，同步集群收到同步任务后会扮成Redis 的Slave，通过Redis的复制协议，从主集群上的从库拉取数据，包括RDB以及后续的增量变更。同步机收到数据后会把它转成客户端的写命令，写到上海从集群的主节点里。
再加一个反向的同步链路，就可以实现集群间的双向同步。
如何做好微观角度的高可用，也就是保持端到端的高成功率。对于Squirrel，主要讲如下三个影响成功率的问题：
①数据迁移造成超时抖动。
②持久化造成超时抖动。
③热点Key请求导致单节点过载。
Squirrel智能迁移
对于数据迁移，主要遇到三个问题：
①Redis Cluster提供了数据迁移能力，但要迁哪些Slot，Slot从哪迁到哪，它并不管。
②迁移速度过快可能影响业务正常请求。
③Redis的Migrate命令会阻塞工作线程，尤其在迁移大Value时会阻塞特别久。
为了解决这些问题，做了全新的迁移服务。
首先生成迁移任务，核心是“就近原则”（如同机房的两个节点做迁移肯定比跨机房的快）。把任务下发到一批迁移机上。迁移机迁移的时候，有这样几个特点：
1、会在集群内迁出节点间做并发，比如同时给Redis 1、Redis 3下发迁移命令。
2、每个Migrate命令会迁移一批Key。
3、我们会用监控服务去实时采集客户端的成功率、耗时，服务端的负载、QPS 等，之后把这个状态反馈到迁移机上。迁移数据的过程就类似TCP慢启动的过程，它会把速度一直往上加，若出现请求成功率下降等情况，它的速度就会降低，最终迁移速度会在动态平衡中稳定下来，这样就达到了最快速的迁移，同时又尽可能小地影响业务的正常请求。
对于大Value的迁移，实现了一个异步Migrate命令，该命令执行时，Redis的主线程会继续处理其他的正常请求。如果此时有对正在迁移Key的写请求过来，Redis会直接返回错误。这样最大限度保证了业务请求的正常处理，同时又不会阻塞主线程。
Squirrel持久化重构
Redis主从同步时会生成RDB。生成RDB的过程会调用Fork产生一个子进程去写数据到硬盘，Fork虽然有操作系统的COW机制，但是当内存用量达到10 G或20 G时，依然会造成整个进程接近秒级的阻塞。这对在线业务来说几乎是无法接受的。我们也会为数据可靠性要求高的业务去开启AOF，而开AOF就可能因IO抖动造成进程阻塞，这也会影响请求成功率。对官方持久化机制的这两个问题，我们的解决方案是重构持久化机制。
上图是最新版的Redis持久化机制，写请求会先写到DB里，然后写到内存Backlog，跟官方一样。同时它会把请求发给异步线程，异步线程负责把变更刷到硬盘的Backlog里。当硬盘Backlog过多时，我们会主动在业务低峰期做一次RDB ，然后把RDB之前生成的 Backlog删除。
如果这时候我们要做主从同步，去寻找同步点的时候，该怎么办？第一步还是跟官方一样，我们会从内存Backlog里找有没有要求的同步点，如果没有，我们会去硬盘Backlog找同步点。由于硬盘空间很大，硬盘Backlog可以存储特别多的数据，所以很少会出现找不到同步点的情况。如果硬盘Backlog也没有，我们就会触发一次类似于全量重传的操作，不需要当场生成RDB，它可以直接用硬盘已存的RDB及其之后的硬盘Backlog完成全量重传。
Squirrel热点Key
普通主、从是一个正常集群中的节点，热点主、从是游离于正常集群之外的节点。
当有请求进来读写普通节点时，节点内会同时做请求Key的统计。如果某个Key达到了一定的访问量或者带宽的占用量，会自动触发流控以限制热点Key访问，防止节点被热点请求打满。同时，监控服务会周期性的去所有Redis实例上查询统计到的热点Key。如果有热点，监控服务会把热点Key所在Slot上报到迁移服务。迁移服务会把热点主从节点加入到这个集群中，然后把热点Slot迁移到这个热点主从上。因为热点主从上只有热点Slot的请求，所以热点Key的处理能力得到了大幅提升。
通过这样的设计，可做到实时的热点监控，并及时通过流控去止损；通过热点迁移，能做到自动的热点隔离和快速的容量扩充。
持久化KV Cellar架构和实践
跟Tair主要有两个架构上的不同：①OB，②ZooKeeper。
OB跟ZooKeeper的Observer是类似的作用，提供Cellar中心节点元数据的查询服务。它可以实时与中心节点的Master同步最新的路由表，客户端的路由表都是从OB去拿。
好处：①把大量的业务客户端跟集群的大脑Master做了天然的隔离，防止路由表请求影响集群的管理。②OB只供路由表查询，不参与集群的管理，所以它可以进行水平扩展，极大地提升了我们路由表的查询能力。
另外，引入了ZooKeeper做分布式仲裁，解决Master、Slave在网络分割情况下的“脑裂”问题，并且通过把集群的元数据存储到ZooKeeper，保证了元数据的高可靠。
Cellar节点容灾——Handoff机制
一个集群节点的宕机一般是临时的，一个节点的网络抖动也是临时的，会很快地恢复，并重新加入集群。实现Handoff机制来解决这种节点短时故障带来的影响。
如果A节点宕机了，会触发Handoff机制，这时中心节点会通知客户端A节点发生了故障，让客户端把分片1的请求也打到B上。B节点正常处理完客户端的读写请求之后，还会把本应该写入A节点的分片1&2数据写入到本地的 Log 中。
如果A节点宕机后 3~5 分钟，或者网络抖动30~50秒之后恢复了，A节点就会上报心跳到中心节点，中心节点就会通知B节点：“A节点恢复了，把它不在期间的数据传给它。”这时B节点就会把本地存储的Log回写到A节点上。等到A节点拥有了故障期间的全量数据之后，中心节点就会告诉客户端，A 节点已经彻底恢复了，客户端就可以重新把分片1的请求打回A节点。
通过这样的操作，可做到秒级的快速节点摘除，且节点恢复后加回，只需补齐少量的增量数据。另外如果A节点要做升级，中心节点先通过主动Handoff把A节点流量切到B节点，A 升级后再回写增量Log，然后切回流量加入集群。这样主动触发Handoff机制，就实现了静默升级的功能。
Cellar跨地域容灾
客户端的写操作到了北京的主集群A节点，A节点会像正常集群内复制一样，把写操作复制到B、D节点上。同时把数据复制一份到从集群的H节点。H节点处理完集群间复制写入之后，也会做从集群内的复制，把写操作复制到从集群的I、K节点上。通过在主从集群的节点间建立一个复制链路，完成了集群间的数据复制，保证了最低的跨地域带宽占用。同样，集群间的两个节点通过配置两个双向复制的链路，就可以达到双向同步异地多活的效果。
Cellar强一致——Multi Raft实现
强一致存储。之前的数据复制是异步的，在做故障摘除时，可能因为故障节点数据还没复制出来，导致数据丢失。目前业界主流的解决方案是基于Paxos或Raft协议的强一致复制。我们最终选择Raft协议。因为Raft论文非常详实，业界也有不少比较成熟的Raft开源实现。
下图是现在Cellar集群Raft复制模式下的架构图，中心节点会做Raft组的调度，它会决定每一个Slot的三副本存在哪些节点上。
Slot 1在存储节点 1、2、4 上，Slot 2在存储节点2、3、4上。每个Slot组成一个Raft 组，客户端会去Raft Leader上进行读写。由于我们是预分配了16384 个Slot，所以在集群规模很小的时候，存储节点上可能会有数百甚至上千个Slot。
这时如果每个Raft复制组都有自己的复制线程、 复制请求和Log等，资源消耗会非常大，写入性能会很差。所以我们做了Multi Raft实现。
Cellar会把同一个节点上所有的Raft复制组写一份Log，用同一组线程去做复制，不同 Raft组间的复制包也会按照目标节点做整合，以保证写入性能不会因Raft组过多而变差。Raft内部有自己的选主机制，它可以控制自己的主节点，如果有任何节点宕机，它可以通过选举机制选出新的主节点。
那么，中心节点是不是就不需要管理Raft组了？不是的。
如果一个集群的部分节点经过几轮宕机恢复的过程，Raft Leader在存储节点之间会变得极其不均。而为了保证数据的强一致，客户端的读写流量又必须发到Raft Leader，这时集群的节点流量会很不均衡。所以我们的中心节点还会做Raft组的Leader调度。
比如说Slot 1存储在节点 1、2、4，并且节点1是Leader。如果节点1挂了，Raft把节点2选成了Leader。然后节点1恢复了并重新加入集群，中心节点这时会让节点2把Leader 还给节点1 。这样，经过一系列宕机和恢复，存储节点间的Leader数目仍能保证是均衡的。
Cellar 如何保证它的端到端高成功率？
Cellar 遇到的数据迁移和热点Key问题与Squirrel是一样的，但解决方案不一样。
因为Cellar走的是自研路径，不用考虑与官方版本的兼容性，对架构改动更大些。另一个问题是慢请求阻塞服务队列导致大面积超时，这是Cellar网络、工作多线程模型设计下会遇到的不同问题。
Cellar智能迁移
上图是Cellar智能迁移架构图。把桶的迁移分成了三个状态。
第一个状态就是正常的状态，没有任何迁移。
如果这时候要把Slot 2从A节点迁移到B节点，A会给Slot 2打一个快照，然后把这个快照全量发到B节点上。在迁移数据的时候， B节点的回包会带回B节点的状态。B的状态包括什么？引擎的压力、网卡流量、队列长度等。A节点会根据B节点的状态调整自己的迁移速度。像Squirrel一样，它经过一段时间调整后，迁移速度会达到一个动态平衡，达到最快速的迁移，同时又尽可能小地影响业务的正常请求。
当Slot 2迁移完后， 会进入图中Slot 3的状态。客户端这时可能还没更新路由表，当它请求到了A节点，A节点会发现客户端请求错了节点，但它不会返回错误，它会把请求代理到B节点上，然后把B的响应包再返回客户端。同时它会告诉客户端，需要更新一下路由表了，此后客户端就能直接访问到B节点。这样就解决了客户端路由更新延迟造成的请求错误。
Cellar快慢列队
下图上方是一个标准的线程队列模型。网络线程池接收网络流量解析出请求包，然后把请求放到工作队列里，工作线程池会从工作队列取请求来处理，然后把响应包放回网络线程池发出。
我们分析线上发生的超时案例时发现，一批超时请求当中往往只有一两个请求是引擎处理慢导致的，大部分请求，只是因为在队列等待过久导致整体响应时间过长而超时了。从线上分析来看，真正的慢请求占超时请求的比例只有1/20。
如何解决？很简单，拆线程池、拆队列。
网络线程在收到包之后，会根据它的请求特点，是读还是写，快还是慢，分到四个队列里。根据请求的Key个数、Value大小、数据结构元素数等对请求进行快慢区分。然后用对应的四个工作线程池处理对应队列的请求，就实现了快慢读写请求的隔离。
不过也带来一个问题，线程池从一个变成四个，那线程数是不是变成原来的四倍？其实并不是的，某个线程池空闲的时候会去帮助其它的线程池处理请求。所以，线程池变成了四个，但线程总数并没有变。线上验证这样能把服务TP999的延迟降低86%，大幅降低超时率。
Cellar热点Key
上图是Cellar热点Key解决方案的架构图。
中心节点加了热点区域管理，图示这个集群在节点C、D放了热点区域。
如果客户端有一个写操作到了A节点，A节点处理完成后，会根据实时的热点统计结果判断写入的Key是否为热点。
如果是一个热点，那么它会在做集群内复制的同时，还会把这个数据复制有热点区域的节点（C、D）。同时，存储节点在返回结果给客户端时，会告诉客户端这个Key是热点，这时客户端内会缓存这个热点Key。当客户端有这个Key的读请求时，它就会直接去热点区域做数据的读取。
通过这样的方式，可以做到只对热点数据做扩容，不像Squirrel，要把整个Slot迁出来做扩容。有必要的话，中心节点也可以把热点区域放到集群的所有节点上，所有的热点读请求就能均衡的分到所有节点上。另外，通过这种实时的热点数据复制，我们很好地解决了类似客户端缓存热点KV方案造成的一致性问题。
发展规划和业界趋势
按照服务、系统、硬件三层来进行阐述。首先在服务层，主要有三点：
①Redis Gossip协议优化。Gossip协议在集群的规模变大之后，消息量会剧增，Failover时间也会变得越来越长。当集群规模达到TB级后，可用性会受到很大的影响，需优化。
②已经在Cellar存储节点的数据副本间做了Raft复制，可以保证数据强一致，后面会在Cellar的中心点内部也做一个Raft复制，这样就不用依赖于ZooKeeper做分布式仲裁、元数据存储了，架构也会变得更加简单、可靠。
③Squirrel和Cellar是基于不同的开源项目研发的，所以API和访问协议不同，之后会考虑将Squirrel和Cellar在SDK层做整合，虽然后端会有不同的存储集群，但业务侧可以用一套SDK进行访问。
在系统层面，正在调研并去落地一些Kernel Bypass技术，像DPDK、SPDK这种网络和硬盘的用户态IO技术。它可以绕过内核，通过轮询机制访问这些设备，可以极大提升系统的IO能力。存储作为IO密集型服务，性能会获得大幅的提升。
在硬件层面，像支持RDMA的智能网卡能大幅降低网络延迟和提升吞吐；还有像3D XPoint这样的闪存技术，比如英特尔新发布的AEP存储，其访问延迟已经比较接近内存了，以后闪存跟内存之间的界限也会变得越来越模糊；计算型硬件，比如通过在闪存上加FPGA 卡，把原本应该CPU做的工作，像数据压缩、解压等，下沉到卡上执行，这种硬件能在解放CPU的同时，也可以降低服务的响应延迟。
