levelDB学习第四篇——井然的秩序

熵桥盆景
• 阅读 378

1 存储的本质

每每讲到存储的本质,我都很喜欢拿图书馆来类比,如果单独讲存储,无非就是把东西存下去,我们当然可以把图书一股脑的塞到图书馆里,而不去考虑各类图书的排布关系。但是存的目的却并不只是存,试想一下,如果存下去的东西,需要花费大量的时间才能取出来,这样的存储系统有什么意义呢?非常认同《数据密集型应用系统设计》中的一句话,中文是“建立秩序,省却搜索”,存储系统的意义就在于要建立秩序,这样的秩序能够帮助我们快速地找到存下去的东西,这也就是存储的本质。

2 levelDB存储系统

2.1 LSM-Tree

LSM-Tree,稍微了解levelDB的人应该对此不陌生,levelDB使用了LSM-Tree作为其大方向的存储结构,网上对LSM-Tree的介绍比比皆是,此处笔者就不再赘述了。需要注意的是,LSM-Tree有如下特点

  1. 由于将整块的block顺序写(或者说levelDB不支持随机写),所以levelDB的写性能会比较高,利好磁盘。但是需要注意的是,由于其后台compaction的存在,在大量文件情况下,会对磁盘造成压力,侵占磁盘的写带宽,从而对当前写造成影响。
  2. 由于分级存储的存在,所以LSM-Tree对新数据的读取比较友好,但是对旧数据则比较糟糕,尤其是那些“深入腹地”的数据。这是一种权衡,与B+树那样的类平衡结构相比,LSM-Tree选择更倾向于新数据,B+树则在平衡中也平衡了新旧数据的读取效率。

2.2 SSTable文件结构

本小节内容参考levelDB-hook
本小节,不探讨具体的文件结构,而是通过一系列问题进行巩固,

  1. SSTable中除了data block之外,还有各种其他block,在写data block时,如何保证其他block不会因为data block的写入而向后移动呢?
  2. SSTable存储数据时,每条record(除了restart起始点之外)都是用shared key(与前一个record相比)+unshared key来存储,对于一组restart内(默认16个record),如果想要获取该组内靠后的record,岂不是要从头开始逐步处理,才能获取其完整的key?
  3. 如何获取完整的index block起始地址?data block的起始地址被记录在index block中,但是index block却没有地方记录(footer中储存了最开始的index block的起始地址和大小)?
  4. 如何逐次获取index block中的数据?
  5. 读取某个key的record的具体流程是什么?(不考虑filter block的情况下)
  6. SSTable中的block一定是4KB组织吗?(默认)
  7. filter block中存储的是什么数据?其存储的是完整的key吗?filter block可以用于定位某个record吗?filter block是如何起作用的?filter block与data block、index block一样具有restart points的设计吗?
  8. levelDB中有多少种block是按照restart points那样的格式进行组织的?

回答

  1. 为了保证数据不后移,levelDB严格按照先写data block,在整个SSTable file完成之前filter block、meta index block、、index block等数据都在内存中维护,直到需要持久整个文件时,才持久化其他block。levelDB中的4KB持久线仅对data block起效果。
  2. 确实如此,但是整个过程在内存中完整,且restart size为16,所以整个过程还是比较高效的。
  3. 整个SSTable file文件中只有一个filter block、meta index block、index block,所以对于index block而言,只需要在footer中记录其offset和size即可。
  4. index block数据格式与data block中相同,当获取到某个entry的start offset之后,首先读出前12个字节的header数据(shared length、unshared length、value length),然后解析header,再读出具体的数据即可。
  5. 流程如下:
    5.1 首先需要读SSTable文件的footer,这部分数据量是固定的,在尾部占据48字节的数据量,前32个字节分别是meta index block handle以及index block handle
    5.2 根据index block handle定位到index block,读出index block的数据,由于index block中的物理结构与data block相同,所以可以在block内部利用restart points使用二分查找方法找到具体的data block(offset和size)
    5.3 根据5.2步得到的offset和size,读出data block数据,之后再次根据restart points进行二分查找,找到该record
  6. 不是,由于压缩的存在,所以想要将block的大小严格控制在4KB是比较难的,但是其实更难的是,如果严格控制block在4KB,那么当某一条record过长,从而出现跨block的情况时,数据的组织、读取都会变得非常困难,所以levelDB并不严格控制block为4KB。4KB对levelDB来说仅代表该data block需要被flush到磁盘中。
  7. 几个小问题如下:
    7.1 存储的是连续的完整的key + 各个key的start offset,并且filter block尾部也记录了start offset的length,用于定位。
    7.2 filter block中的数据决定了其不能用于定位某个record,只能用于判断某个record是否存在。
    7.3 filter block中存储的是完整的key,所以其不需要先在index block和data block中利用restart points进行二分查找来确定record的位置,所以其可以更快地进行判定。
    7.4 没有,filter block核心是通过两个vector,分别记录原始key以及原始key的start offset,等到SSTable file要进行持久化时,再一次性写入文件中。
  8. data block、index block、meta index block
点赞
收藏
评论区
推荐文章
桃浪十七丶 桃浪十七丶
4年前
计算机组成原理3.7虚拟存储器
3.7.1虚拟存储器概念3.7.2页式存储器主存和Cache之间是分块映射存储,同样,利用局部性原理,也可以将主存和辅存之间进行分块映射存储。举个粒子,假如现在使用微信文字聊天,该部分程序占用大小了4KB的空间,那么可以分为大小位1KB的四块,分别映射存储到主存中。如下图,分页式存储,在这个问题中就是把程序进程逻辑上大小相等的四块页面,每个页面大小与主存块
Wesley13 Wesley13
3年前
java的char类型真的可以存汉字么?
今天偶尔看到一句话:ANSI编码表示英文字符时用一个字节,表示中文用两个字节,而unicode不管表示英文字符还是中文都是用两个字节来表示。我突然间对自己之前对java变量以Unicode编码存储产生了疑问。到底是以Unicode编码存储的还是和源文件使用的编码格式相同呢?联想到之前的一个问题java的char类型是否可以存储汉字,这个问题是
虾米大王 虾米大王
2年前
java代码088
code088.jsp通过存储过程获取数据所有图书信息ID图书名称价格数量作者<%Listlist1findBook.findAll();if(list1null||list1.size()
Stella981 Stella981
3年前
Python 版 APM 服务使用测试
后端开发与云服务云服务这个词,大概最早是从云盘开始的,那时候概念也特别简单,无非就是把一些数据存在别人的服务器上,在”云存储”这个名词火起来之前,QQ也有提供网站的功能用来存一些小东西(05年06年的样子,那时候大概只有几十M的空间),其实刚听到这个概念的时候我就很不理解,光存存东西不至于吹得这么玄乎吧。毕业后入行,云服务器才慢慢
Stella981 Stella981
3年前
Python将字符串转换成ObjectId类型
MongoDB自动生成的_id是ObjectId类型的。我需要将MongoDB的_id存到ElasticSearch中,而ElasticSearch又只能存String类型的_id,所以就涉及到两种类型的转换。ObjectId类型—→String类型这个非常简单
Stella981 Stella981
3年前
Kudu与Impala在字符串处理上与其他DB的迥异
Kudu的时间戳类型,在Impala建表上用的是timestamp,有2个与众不同的地方。1\.在Kudu里它存的时间戳是纳秒级别,所以你普通的时间戳存进去需要\1000。2\.另外,Kudu的时间戳里面存的是,UTC时间。所以存进去的时间需要自己转换时区。2\.Impala在读取时间戳的时候,会根据配置项,使用系统的本地时区。配置
Easter79 Easter79
3年前
Twitter的分布式自增ID算法snowflake (Java版)
概述分布式系统中,有一些需要使用全局唯一ID的场景,这种时候为了防止ID冲突可以使用36位的UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID一般是无序的。有些时候我们希望能使用一种简单一些的ID,并且希望ID能够按照时间有序生成。而twitter的snowflake解决了这种需求,最初Twitter把存储系统从MySQL迁移
Wesley13 Wesley13
3年前
MySQL索引那些事儿
我们都有到图书馆借书的经历,偌大的图书馆,为什么能在短的时间内找到想要找的书?如果这些书是杂乱无章的堆放,或者没有任何标识的放在书架,那么还能这么快的找到吗?这个场景就很接近我们软件开发中使用数据库的场景,图书馆的书就类似我们数据表中的数据,楼层索引牌、书架分类标识、索书号就类似我们查找数据的索引。那我们常用的数据库的索引底层的一个数据结构是什么样的呢?要了
Stella981 Stella981
3年前
Git Analyze 工具实现与原理
前言作为一个免费提供私有仓库的代码托管平台,码云时常要考虑利用现有的资源支持更多的用户,对于体积较大的存存储库,由于git的分布式特性,服务器往往需要更多的硬件资源来支撑这些存储库的访问。码云对git仓库的大小限制为1GB,用户在本地可以使用如下命令查看存储库的大小。dush.git/objects这个命令在Gi
京东云开发者 京东云开发者
2个月前
分库分表后复杂查询的应对之道:基于DTS实时性ES宽表构建技术实践
作者:京东物流王军1问题域业务发展的初期,我们的数据库架构往往是单库单表,外加读写分离来快速的支撑业务,随着用户量和订单量的增加,数据库的计算和存储往往会成为我们系统的瓶颈,业界的实践多数采用分而治之的思想:分库分表,通过分库分表应对存系统读写性能瓶颈和存
熵桥盆景
熵桥盆景
Lv1
晚来天欲雪,能饮一杯无?
文章
2
粉丝
0
获赞
0