找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 39954|回复: 2
收起左侧

【如何设计一个Key-Value存储引擎】【系统设计面经题目精选系列】

[复制链接]
发表于 11-14-2017 11:03 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
SSTable

MemTable
MemTable 是内存中的数据结构,存储的内容跟硬盘上的SSTable一样,只是格式不一样。Immutable MemTable的内存结构和Memtable是完全一样的,区别仅仅在于它是只读的,而MemTable则是允许写入和读取的。当MemTable写入的数据占用内存到达指定大小,则自动转换为Immutable Memtable,等待Dump到磁盘中,系统会自动生成一个新的MemTable供写操作写入新数据,理解了MemTable,那么Immutable MemTable自然不在话下。
MemTable里的数据是按照key有序的,因此当插入新数据时,需要把这个key-value对插入到合适的位置上,以保持key有序性。MemTable底层的核心数据结构是一个跳表(Skip List)。跳表是红黑树的一种替代数据结构,具有更高的写入速度,而且实现起来更加简单,请参考跳表(Skip List)
前面我们介绍了LevelDB的一些内存数据结构和文件,这里开始介绍一些动态操作,例如读取,写入,更新和删除数据,分层合并,错误恢复等操作。
添加、更新和删除数据
LevelDB写入新数据时,具体分为两个步骤:
  • 将这个操作顺序追加到log文件末尾。尽管这是一个磁盘操作,但是文件的顺序写入效率还是跟高的,所以不会降低写入的速度
  • 如果log文件写入成功,那么将这条key-value记录插入到内存中MemTable。
LevelDB更新一条记录时,并不会本地修改SST文件,而是会作为一条新数据写入MemTable,随后会写入SST文件,在SST文件合并过程中,新数据会处于文件尾部,而读取操作是从文件尾部倒着开始读的,所以新值一定会最先被读到。
LevelDB删除一条记录时,也不会修改SST文件,而是用一个特殊值(墓碑值,tombstone)作为value,将这个key-value对追加到SST文件尾部,在SST文件合并过程中,这种值的key都会被忽略掉。
核心思想就是把写操作转换为顺序追加,从而提高了写的效率。
读取数据
读操作使用了如下几个手段进行优化:
  • MemTable + SkipList
  • Binary Search(通过 manifest 文件)
  • 页缓存
  • bloom filter
  • 周期性分层合并
分层合并(Leveled Compaction)
我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!

0

主题

0

精华

7

积分

新米人

Rank: 1

积分
7
发表于 11-14-2017 11:03 PM | 显示全部楼层
感谢TeamEditor分享~~~好人一生平安~~~

0

主题

0

精华

4

积分

新米人

Rank: 1

积分
4
发表于 11-17-2017 09:24 AM | 显示全部楼层
感谢TeamEditor分享~~~好人一生平安~~~
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表