Amos'S Blog

聊一聊 KV 存储

 kv  2996  6 分钟

RDB

本文关键字: LSM、RocksDB、Raft、Redis Cluster

诞于脑洞

KV 的现状

  • Redis 目前大部分场景下处于「性能过剩」而「存储短缺」的状态，当然也可以发动「钞能力」
  • HBase 作为老牌的 LSM 树实现的 DB，写性能还算过得去，但是读性能就十分磕碜了
  • 早期也有 Twiter 开源的 twemproxy 方案来做 Redis、Memcached 基于 Hash 的 Cluster 实现可惜只能「单线程跑」，且数据扩缩容十分不便
  • Nefix 参考 AWS DyanmoDB 白皮书实现的 Dynomite，目前已经不怎么维护了，且一堆 Bug，有过邮件交流但是无果。PS: 当初接 SpringCloud 也被坑惨了
  • 近几年也涌现了基于 TiKV 生态的兼容 Redis 协议 的 KV 例如: Titan 等
  • 另起炉灶的 Pika 目前还是推荐用 15 年左右火爆的 Codis 引入更多的「基础组件」来做集群管理，同时也在自行实现另一套 Cluster 的管理逻辑
  • 大部分的方案最底层采用 Facebook 基于 Google 的 LSM tree 实现的 LevelDB 再针对 SSD 优化而来的 RocksDB
  • 当然还有很多很多 KV 存储在冒出来，例如: 腾讯云的 Tendis、阿里大佬整的 Tair、美图大佬整的 KVrocks，兼容 Redis 协议，字节魔改的 RocksDB 等等，是不是发现很眼熟似乎大部分都是基于 RocksDB 的
  • Redis Labs 也推出了基于 SSD 的存储版本，当然不是免费给你用的啦，可惜的是我还没去实际测试过它
  • 似乎存在不少的场景只要简单的 KV 存储，但是需要大量的存储空间，再贪心一点点「追求一下」「性能」似乎能选择的就不多了
  • 这里扯到了「性能」我为什么试着搞一个简单的 KV 而不是像 Redis 一样全都要，甚至还支持各种数据结构，譬如: SQL 的拓展插件，个人感觉 Redis 是成功到奇葩的数据库了
    • 其实原因很简单，之前也有参与以为小伙伴的 sdb 前期实现的讨论，结论是如果要支持各种数据结构那就是要「加锁」的，甚至 incr 也是，有兴趣的小伙伴可以跳转到 sdb 去了解一波
  • 说白了 KV 的集群方式也就是两种
    • Hash
      • 一致性 Hash: 譬如 Dynomite，相比普通 Hash 当节点上下线时数据移动少
      • 普通 Hash: 譬如 twemproxy
    • Raft
      • 单 Raft: 譬如 sdb，Raft 之前以 ETCD 为代表，如果完全参考 Raft 论文实现，性能会非常差，况且所有的写请求都只能由 Leader 处理，可参考 Raft 作者实现的 Logcabin
      • Mutl-raft: 譬如 TiKV，有多少个 Raft 实例就相当于有多少个写入口
  • 总结下现在已经迈出了当初需要自己解决 Redis 集群问题的时代，但是依然没有解决 持久化 的问题
  • 正好兄弟团队业务场景上需要一款高性能写入同时读性能不能太差的业务场景，之前有试过 Hbase，据说写了 2 个星期数据还没写完...
  • 所以我决定撸一个能够「开箱即用」、「可持久化」、「可扩展」、「够稳定」、「够简单」的数据库，仅仅聚焦于简单的 KV 存储
    • 之前有看到过一篇文章让我感触很深「为什么国内出不了百亿的 SaaS 公司？」
    • 大概有这么几点:
      • 不敢做取舍，什么都想要，但是很可能什么都做不好
        • 这里 AWS 让我肃然起敬，基本是专注于最底层，然后拉合作，譬如 CloudWatch 真的很难用，但是大名鼎鼎的 DataDog 的底层却是用的它，还有 EKS、ELB 等等等，跑题了...
      • 「用户成功」和 「为客户创造」价值是口号
        • 譬如: 有用 A/B 两款省成本的平台，A 是海外的公司的收费标准是从省掉的钱里抽 x%， B 是家国内的公司，采用一次性付费的方式，当我知道他们的收费模式之后心中已经有倾向了。

目标

大致的方向

  • 低成本（高性能）
  • 大存储（持久化）
  • 易使用（Redis Cluster Client 接入，单体架构没有 Proxy，没有注册中心）
  • 可扩展 (基于 Single Raft 管理集群)
  • 高可用 (拥抱 Redis Cluster 生态)

具体的实现

  • 借用 NewSQL 中的一极 CockRoach 参考 RocksDB 实现的 Pebble，来实现单点的可持久化的 KV 存储，来解「决低成本」、「高性能」的存储问题
    • LSM 的读写复杂度 O(1) / O(logn)、而 B+ 的读写复杂度 O(logn)
    • LSM Red Black Tree VS LevelDB 的 Skip List 实现，Skip List 用数据概率来实现了大概率的均分分配，代码逻辑相对简单，也能免去树的旋转。
  • 兼容 Redis Cluster 协议
    • 主流的技术栈都可通过 Redis Cluster Client 快速接入（这样可以帮我解决很多其他类型 DB 必须在 Server 上实现的逻辑，其实也可以考虑另起炉灶上 RPC）
    • 这里做了些思考最终做了「取舍」，如果「自定义协议」大概率在性能上是可以胜过 Redis 协议的，举个例子: Memcached 更为紧凑的二进制协议
    • 其实就是在「易用性」和 「效率」中做选择，实际的 DB 性能表现瓶颈也是在硬盘的 IO 上
  • 借助 Redis Cluster Slots 实现可扩展的集群，支持基于 Cluster 的 Hash Tag
  • 接入 Single Raft 来替代过于臃肿的 Gossip 协议管理集群信息
  • 其他功能，原则上「不引入任何降低」目前命令（get/set/mget/mset）性能的特性
    • 添加 Cache 层，做数据的冷热分离
    • 魔改 Redis Cluster 协议实现 Leader - Follower 的读写分离
  • 实现必要的 Redis 运维命令，如: 服务的关键性指标的统计、一键扩缩容等

调研

  • Redis 「可持久化」存储版百家争鸣

    • 基于 RocksDB 的单体，但官方支持 Leader - Follower 的 DB
      • ARDB 处于个人维护状态
      • SSDB 两实例间可以互为 Leader、Follower ，处于个人维护状态
    • 支持 Cluster 的 DB
      • Pika 360 开源并维护的 DB 难得的是它还很活跃
      • KVrocks 某美图大佬整的，已经进入 apache 了
      • Titan 美图似乎早起也是对 KV 有些执念的，Titan 就是其中之一基于 TiKV 的生态去整的了

  • Redis Cluster 的发展历程

    • 14 - 16 年打杀四方的 Codis，听说当时很多大厂也在用，顺便提一嘴，其实 Codis 的核心开发就是现在 PingCAP 的 CTO - Edward Huang 大佬
    • 借助 Codis 的各种组件套壳的 KV Cluster 而实现从单机到集群的组建
    • Redis Cluster 官方的简单易用的实现停止了 Redis Cluster 还需要各种折腾的时代

  • 之前提到的解法基本都是 RocksDB，既然有了 TiDB 的 TiKV 甚至天生就能组集群了，还有必要自己整 KV 吗?

    • 不在乎成本是可以的，19 年试用 TiDB Cloud 至少是 3 * 8C16G TiKV + 2 * 8C16G PD 起步了
    • TiDB 的基本思路
      • RocksDB 解决存储问题
      • Raft 解决集群问题
      • 设计 KV-SQL 的映射规则
    • TiDB 的基本概念
      • Region
      • Raft && Muti-Raft
      • 那 TiDB 是如何把 KV 变成 SQL 的呢？
      • 最近 TiDB 又弄了一个 TiFlash 似乎想一统 OLAP 和 OLTP，emmmmm 既然扯到了 SQL 了就和 rdb 没啥关系了

选型

  • B+ / LSM or LSM + B+?
    • LSM:
      • HBase
      • LevelDB -> RocksDB -> Pebble(CockRoachdb)
        • 基于 LSM tree 在存储引擎的级别已经做好了 Key 的排序
        • 必然存在「读写放大」的问题，而且「数据越多」就「越严重」
        • 单节点 500G 的情况下能做到「线上使用情况」的性能数据
        • 如果从极限的角度去算把 Redis Cluster Slots 全部耗尽，将是 16384 * 500G 约为 8PB 的数据，当然如果没那么看重读性能，可以往单节点 1T 的数据量级试试
    • B+:
      • botlDB: ETCD 的底层数据就是存储在 Golang 版本的实现，这是一个非常精简的 B+ / MVCC 实现，核心代码不过几千行，非常值得一读
    • B+ + LSM: 一位 B 站应届生写的，同样代码十分精简，想法十分骚气，我差点就用它来做底层存储了。
      • LotusDB
    • 文档型数据库 B or B+（Append-only B+
      • MongoDB: 特别有意思的选择了 B，因为如果当做 KV 文档存储来用，不需要太多的范围查询，B 的查询效率反而会更高
      • CouchDB: 总结一下，只有追加操作并利用 MVCC 去锁化
  • Memcached、 Redis or CoucseBD
    • Memcached: 单从 KV 来看性能是优于 Redis 的，据说快手的重保项目上来就是几十万个缓存节点，Redis Cluster 也没法组这么大的集群，之前用 C++ 标准库撸过一个 Memcached 的 Demo 比官方面向内存编程的 C 的实现多消耗了 30% 的内存
    • CoucseBD: 用 Restful 的方式提供服务，所以存在 HTTP 报文比实际数据还要大的问题
  • Lucene-FST 与 Tire Tree: 这里更多的检索类(倒排索引)的 DB 了，Lucene-FST 类似 Hashmap 但是内存用得更少而查询速度要慢，朴素版的 Tire Tree 就很吃内存了，当然也有不少优化的版本，例如: 三元 Tire Tree 。啊哈哈哈该项显然不是我们的选择方向。

Roadmap

    • 单节点支持 pebble
    • set/mset/get/mget 常用命令支持
    • 支持 Redis Cluster 通过 redis-benchmark && redis-py-cluster 的测试
    • 引入 Single Raft
    • [] cluster 数据交给 Raft 管理
    • [] 支持一键扩缩容
    • [] 支持更多的数据压缩算法（目前是 snappy，想试试 Kafka 较新版本所支持的的 zstd），得到硬盘与 CPU「成本和性能」的关系性结论
    • [] 添加 Prometheus 的关键性监控指标
    • [] 添加 Cache 层，做数据的冷热层
    • [] 魔改 Redis Cluster 协议实现 Leader - Follower 的读写分离
    • [] sdb 特性冻结 深入 pebble 进一步的性能优化

上线使用情况

集群总数据大概为 2T 左右，目前 7 台 8C 的节点可承载 30W QPS 大概 100Bytes 的 KV 写入，大概 10W QPS 的读取（瓶颈在 IO...），顺便一提 15 个小时内即可完成兄弟团队的数据写入需求了

updatedupdated2022-07-282022-07-28