菜鸟笔记
提升您的技术认知

rocksdb原理与实现-ag真人游戏

rocksdb是facebook的项目,目的是开发一套能在服务器压力下,真正发挥高速存储硬件性能的高效数据库系统;使用c 实现;

是嵌入式数据库kv数据库;不提供网络服务,只提供数据持久化的方案。

rocksdb是基于leveldb实现的,原始代码是从leveldb 1.5上fork出来的;

分布式三篇著名的论文,源自于google:

  1. gfs, 分布式文件存储;
  2. bigtable,分布式kv存储;
  3. mapreduce,大数据处理。

leveldb的作者就是bigtable的作者。

主要解决写多读少的问题,牺牲读性能来加速写性能;

mysql innodb b 树,解决了读多写少的问题;

rocksdb是基于lsm-tree(log structure merge-tree)实现的;

利用lsm-tree来提升写性能;

主要思想是利用磁盘顺序io来提升写性能;lsm-tree并不是tree数据结构,仅仅是一种存储结构;lsm-tree是为了写多读少(对读的性能实时性要求相对较低)的场景而提出的ag真人游戏的解决方案;如日志系统、海量数据存储、数据分析等。

以下问题需要考虑:

  • 磁盘顺序写,会记录同一个key的多次写操作,存在数据冗余,怎么解决数据冗余的问题?
  • 怎么提高读性能?
  • 数据肯定是先写到缓存里面的,缓存使用什么样的数据结构?
  • 缓存中的数据通过什么样的策略刷到磁盘中?
  • 怎么保证缓存和磁盘中数据的一致性?

memtable

memtable是一个内存数据结构,它保存了落盘到sst文件前的数据;写入数据的时候总是先将数据写入到memtable,读取的时候也是先查询memtable;一旦一个memtable被写满,它会变为immutable memtable,即只读的memtable;然后会创建一块新的memtable来提供写入操作;immutable memtable将异步落盘的sst文件中,之后该memtable将会被删除。

memtable默认使用的数据结构是skiplist;

immutable memtable的两个作用?

  • 用来落盘
  • 提高并发读写性能

memtable中为什么使用skiplist?

缓存中应该使用什么数据结构来存储?

有序结构,并且缓存中没有冗余数据

为什么不使用rbtree?

  • 红黑树查找下一个节点的复杂度是o(log2n);skiplist查找一个节点是的时间复杂度是o(1); rocksdb需要实现iterator功能,需要进行遍历,skiplist更加合适;
  • 并发读写,skiplist锁粒度比rbtree小;skiplist锁单个节点,rbtree锁整个红黑树。

rbtree与skiplist使用场景比较

  • 定时器,查找最小的节点; rbtree时间复杂度o(log2n), skiplist时间复杂度o(1);
  • nginx slab使用红黑树,能不能使用skiplist?最好不要用skiplist,因为共享内存一开始要分配固定大小内存,skiplist节点大小不是固定的,节点层级不确定,有冗余数据;

skiplist加锁位置:

  1. max_height; 需要对它进行并发读写;增删改查,第一步都需要先进行查找,先在最高层进行查找;新增节点,生成的随机高度,有可能大于max_height;
  2. 对node加锁;

落盘策略

  1. 定时刷新
  2. 阈值刷新

wal(write ahead log)

mysql中,redo log 实现wal,写前日志;用来恢复数据,异步刷盘;rocksdb也有wal日志;在出现宕机的时候,wal日志可以用于恢复memtable的数据;当memtable中的数据落盘到sst文件后,才会删除对应的wal日志。

ss table(sorted string table)

每个immutable memtable都会落盘为一个ss table文件;

l0层可能会有重复数据,会有数据冗余,不利于快速查找;文件间无序,文件内部有序;

l1 ~ ln 层会对重复数据进行合并,思想与时间轮算法一致;根据数据的冷热程度进行分层;

l1 ~ ln 每层数据没有重复,跨层可能有重复;文件间是有序的,同一层的每个文件,key的范围不同;

磁盘数据读性能的提升

blockcache

rocksdb在内存中缓存数据,以提高读性能;

rocksdb有两种实现方式,lrucache,clockcache;lrucache读写都需要加锁;clockcache写加锁,读不加锁;nginx定时器使用clockcache,32个操作槽位,提升并发性能;

布隆过滤器

布隆过滤器使用前提:不支持删除,ss table中的数据不存在删除;

特征:能确定一定不存在,不能确定一定存在(有误判率,并且可控);可控,提供预期存储元素个数和误判率,算出所占存储空间和hash函数个数;

在sst每一层增加一个布隆过滤器,提高查找效率。

怎么合并压缩?

怎么制定合并压缩的策略?

需要综合考虑lsm-tree的三大问题;

lsm-tree三大问题

类似于隔离级别,cap原则;只能减小其中的一个,另外两个会被放大。

读放大

b 树是2-4层,最多4次io,读性能高;lsm-tree最多7层,读性能相比b 树要差;

b 树为什么读性能高,写性能低?

b 树分裂造成写性能比较低;

空间放大

所有的写操作都是顺序写,而不是就地更新,无效数据不会被马上清理掉;

b 树是就地更新,但是由于b 树以页(16k)为单位存储,但是页内有很大的空间浪费,空间放大更严重;

写放大

同一条数据多次写入磁盘;sst不同层级之间可能存在重复数据;

b 树分裂的时候有写放大,其他时候不会。

压缩策略

为了在读放大、空间放大以及写放大之间进行取舍,以适应不同的业务场景;所以需要选择不同的合并算法;

默认策略:leveled compaction & tiered

放大**

同一条数据多次写入磁盘;sst不同层级之间可能存在重复数据;

b 树分裂的时候有写放大,其他时候不会。

压缩策略

为了在读放大、空间放大以及写放大之间进行取舍,以适应不同的业务场景;所以需要选择不同的合并算法;

默认策略:leveled compaction & tiered

内存中多线程,磁盘合并也是多线程的。

网站地图