天津市建设与管理网站,wordpress安装时失败,北仑做网站,一份完整的项目计划书原文地址#xff1a;http://www.samecity.com/blog/Index.asp?SortID12#xff0c;
最近由于工作上的需求#xff0c;需要用到leveldb#xff0c;因此转载此文章用于以后的查询使用。
LevelDb日知录之一#xff1a;LevelDb 101 说起LevelDb也许您不清楚#xff0c;但是…原文地址http://www.samecity.com/blog/Index.asp?SortID12
最近由于工作上的需求需要用到leveldb因此转载此文章用于以后的查询使用。
LevelDb日知录之一LevelDb 101 说起LevelDb也许您不清楚但是如果作为IT工程师不知道下面两位大神级别的工程师那您的领导估计会Hold不住了Jeff Dean和Sanjay Ghemawat。这两位是Google公司重量级的工程师为数甚少的Google Fellow之二。 Jeff Dean其人http://research.google.com/people/jeff/index.htmlGoogle大规模分布式平台Bigtable和MapReduce主要设计和实现者。 Sanjay Ghemawat其人http://research.google.com/people/sanjay/index.htmlGoogle大规模分布式平台GFSBigtable和MapReduce主要设计和实现工程师。 LevelDb就是这两位大神级别的工程师发起的开源项目简而言之LevelDb是能够处理十亿级别规模Key-Value型数据持久性存储的C 程序库。正像上面介绍的这二位是Bigtable的设计和实现者如果了解Bigtable的话应该知道在这个影响深远的分布式存储系统中有两个核心的部分Master Server和Tablet Server。其中Master Server做一些管理数据的存储以及分布式调度工作实际的分布式数据存储以及读写操作是由Tablet Server完成的而LevelDb则可以理解为一个简化版的Tablet Server。 LevelDb有如下一些特点 首先LevelDb是一个持久化存储的KV系统和Redis这种内存型的KV系统不同LevelDb不会像Redis一样狂吃内存而是将大部分数据存储到磁盘上。 其次LevleDb在存储数据时是根据记录的key值有序存储的就是说相邻的key值在存储文件中是依次顺序存储的而应用可以自定义key大小比较函数LevleDb会按照用户定义的比较函数依序存储这些记录。 再次像大多数KV系统一样LevelDb的操作接口很简单基本操作包括写记录读记录以及删除记录。也支持针对多条操作的原子批量操作。 另外LevelDb支持数据快照snapshot功能使得读取操作不受写操作影响可以在读操作过程中始终看到一致的数据。 除此外LevelDb还支持数据压缩等操作这对于减小存储空间以及增快IO效率都有直接的帮助。 LevelDb性能非常突出官方网站报道其随机写性能达到40万条记录每秒而随机读性能达到6万条记录每秒。总体来说LevelDb的写操作要大大快于读操作而顺序读写操作则大大快于随机读写操作。至于为何是这样看了我们后续推出的LevelDb日知录估计您会了解其内在原因。
LevelDb日知录之二整体架构 LevelDb本质上是一套存储系统以及在这套存储系统上提供的一些操作接口。为了便于理解整个系统及其处理流程我们可以从两个不同的角度来看待LevleDb静态角度和动态角度。从静态角度可以假想整个系统正在运行过程中不断插入删除读取数据此时我们给LevelDb照相从照片可以看到之前系统的数据在内存和磁盘中是如何分布的处于什么状态等从动态的角度主要是了解系统是如何写入一条记录读出一条记录删除一条记录的同时也包括除了这些接口操作外的内部操作比如compaction系统运行时崩溃后如何恢复系统等等方面。 本节所讲的整体架构主要从静态角度来描述之后接下来的几节内容会详述静态结构涉及到的文件或者内存数据结构LevelDb日知录后半部分主要介绍动态视角下的LevelDb就是说整个系统是怎么运转起来的。 LevelDb作为存储系统数据记录的存储介质包括内存以及磁盘文件如果像上面说的当LevelDb运行了一段时间此时我们给LevelDb进行透视拍照那么您会看到如下一番景象 图1.1LevelDb结构 从图中可以看出构成LevelDb静态结构的包括六个主要部分内存中的MemTable和Immutable MemTable以及磁盘上的几种主要文件Current文件Manifest文件log文件以及SSTable文件。当然LevelDb除了这六个主要部分还有一些辅助的文件但是以上六个文件和数据结构是LevelDb的主体构成元素。
LevelDb的Log文件和Memtable与Bigtable论文中介绍的是一致的当应用写入一条Key:Value记录的时候LevelDb会先往log文件里写入成功后将记录插进Memtable中这样基本就算完成了写入操作因为一次写入操作只涉及一次磁盘顺序写和一次内存写入所以这是为何说LevelDb写入速度极快的主要原因。
Log文件在系统中的作用主要是用于系统崩溃恢复而不丢失数据假如没有Log文件因为写入的记录刚开始是保存在内存中的此时如果系统崩溃内存中的数据还没有来得及Dump到磁盘所以会丢失数据Redis就存在这个问题。为了避免这种情况LevelDb在写入内存前先将操作记录到Log文件中然后再记入内存中这样即使系统崩溃也可以从Log文件中恢复内存中的Memtable不会造成数据的丢失。
当Memtable插入的数据占用内存到了一个界限后需要将内存的记录导出到外存文件中LevleDb会生成新的Log文件和Memtable原先的Memtable就成为Immutable Memtable顾名思义就是说这个Memtable的内容是不可更改的只能读不能写入或者删除。新到来的数据被记入新的Log文件和MemtableLevelDb后台调度会将Immutable Memtable的数据导出到磁盘形成一个新的SSTable文件。SSTable就是由内存中的数据不断导出并进行Compaction操作后形成的而且SSTable的所有文件是一种层级结构第一层为Level 0第二层为Level 1依次类推层级逐渐增高这也是为何称之为LevelDb的原因。 SSTable中的文件是Key有序的就是说在文件中小key记录排在大Key记录之前各个Level的SSTable都是如此但是这里需要注意的一点是Level 0的SSTable文件后缀为.sst和其它Level的文件相比有特殊性这个层级内的.sst文件两个文件可能存在key重叠比如有两个level 0的sst文件文件A和文件B文件A的key范围是{bar, car}文件B的Key范围是{blue,samecity}那么很可能两个文件都存在key”blood”的记录。对于其它Level的SSTable文件来说则不会出现同一层级内.sst文件的key重叠现象就是说Level L中任意两个.sst文件那么可以保证它们的key值是不会重叠的。这点需要特别注意后面您会看到很多操作的差异都是由于这个原因造成的。 SSTable中的某个文件属于特定层级而且其存储的记录是key有序的那么必然有文件中的最小key和最大key这是非常重要的信息LevelDb应该记下这些信息。Manifest就是干这个的它记载了SSTable各个文件的管理信息比如属于哪个Level文件名称叫啥最小key和最大key各自是多少。下图是Manifest所存储内容的示意 图2.1Manifest存储示意图
图中只显示了两个文件manifest会记载所有SSTable文件的这些信息即Level 0的test.sst1和test.sst2文件同时记载了这些文件各自对应的key范围比如test.sstt1的key范围是“an”到 “banana”而文件test.sst2的key范围是“baby”到“samecity”可以看出两者的key范围是有重叠的。
Current文件是干什么的呢这个文件的内容只有一个信息就是记载当前的manifest文件名。因为在LevleDb的运行过程中随着Compaction的进行SSTable文件会发生变化会有新的文件产生老的文件被废弃Manifest也会跟着反映这种变化此时往往会新生成Manifest文件来记载这种变化而Current则用来指出哪个Manifest文件才是我们关心的那个Manifest文件。
以上介绍的内容就构成了LevelDb的整体静态结构在LevelDb日知录接下来的内容中我们会首先介绍重要文件或者内存数据的具体数据布局与结构。
LevelDb日知录之三log文件 上节内容讲到log文件在LevelDb中的主要作用是系统故障恢复时能够保证不会丢失数据。因为在将记录写入内存的Memtable之前会先写入Log文件这样即使系统发生故障Memtable中的数据没有来得及Dump到磁盘的SSTable文件LevelDB也可以根据log文件恢复内存的Memtable数据结构内容不会造成系统丢失数据在这点上LevelDb和Bigtable是一致的。 下面我们带大家看看log文件的具体物理和逻辑布局是怎样的LevelDb对于一个log文件会把它切割成以32K为单位的物理Block每次读取的单位以一个Block作为基本读取单位下图展示的log文件由3个Block构成所以从物理布局来讲一个log文件就是由连续的32K大小Block构成的。 图3.1 log文件布局 在应用的视野里是看不到这些Block的应用看到的是一系列的Key:Value对在LevelDb内部会将一个Key:Value对看做一条记录的数据另外在这个数据前增加一个记录头用来记载一些管理信息以方便内部处理图3.2显示了一个记录在LevelDb内部是如何表示的。 图3.2 记录结构 记录头包含三个字段ChechSum是对“类型”和“数据”字段的校验码为了避免处理不完整或者是被破坏的数据当LevelDb读取记录数据时候会对数据进行校验如果发现和存储的CheckSum相同说明数据完整无破坏可以继续后续流程。“记录长度”记载了数据的大小“数据”则是上面讲的Key:Value数值对“类型”字段则指出了每条记录的逻辑结构和log文件物理分块结构之间的关系具体而言主要有以下四种类型FULL/FIRST/MIDDLE/LAST。 如果记录类型是FULL代表了当前记录内容完整地存储在一个物理Block里没有被不同的物理Block切割开如果记录被相邻的物理Block切割开则类型会是其他三种类型中的一种。我们以图3.1所示的例子来具体说明。 假设目前存在三条记录Record ARecord B和Record C其中Record A大小为10KRecord B 大小为80KRecord C大小为12K那么其在log文件中的逻辑布局会如图3.1所示。Record A是图中蓝色区域所示因为大小为10K32K能够放在一个物理Block中所以其类型为FULLRecord B 大小为80K而Block 1因为放入了Record A所以还剩下22K不足以放下Record B所以在Block 1的剩余部分放入Record B的开头一部分类型标识为FIRST代表了是一个记录的起始部分Record B还有58K没有存储这些只能依次放在后续的物理Block里面因为Block 2大小只有32K仍然放不下Record B的剩余部分所以Block 2全部用来放Record B且标识类型为MIDDLE意思是这是Record B中间一段数据Record B剩下的部分可以完全放在Block 3中类型标识为LAST代表了这是Record B的末尾数据图中黄色的Record C因为大小为12KBlock 3剩下的空间足以全部放下它所以其类型标识为FULL。 从这个小例子可以看出逻辑记录和物理Block之间的关系LevelDb一次物理读取为一个Block然后根据类型情况拼接出逻辑记录供后续流程处理。
LevelDb日知录之四SSTable文件 SSTable是Bigtable中至关重要的一块对于LevelDb来说也是如此对LevelDb的SSTable实现细节的了解也有助于了解Bigtable中一些实现细节。
本节内容主要讲述SSTable的静态布局结构我们曾在“LevelDb日知录之二整体架构”中说过SSTable文件形成了不同Level的层级结构至于这个层级结构是如何形成的我们放在后面Compaction一节细说。本节主要介绍SSTable某个文件的物理布局和逻辑布局结构这对了解LevelDb的运行过程很有帮助。 LevelDb不同层级有很多SSTable文件以后缀.sst为特征所有.sst文件内部布局都是一样的。上节介绍Log文件是物理分块的SSTable也一样会将文件划分为固定大小的物理存储块但是两者逻辑布局大不相同根本原因是Log文件中的记录是Key无序的即先后记录的key大小没有明确大小关系而.sst文件内部则是根据记录的Key由小到大排列的从下面介绍的SSTable布局可以体会到Key有序是为何如此设计.sst文件结构的关键。 图4.1 .sst文件的分块结构 图4.1展示了一个.sst文件的物理划分结构同Log文件一样也是划分为固定大小的存储块每个Block分为三个部分红色部分是数据存储区 蓝色的Type区用于标识数据存储区是否采用了数据压缩算法Snappy压缩或者无压缩两种CRC部分则是数据校验码用于判别数据是否在生成和传输中出错。 以上是.sst的物理布局下面介绍.sst文件的逻辑布局所谓逻辑布局就是说尽管大家都是物理块但是每一块存储什么内容内部又有什么结构等。图4.2展示了.sst文件的内部逻辑解释。 图4.2 逻辑布局 从图4.2可以看出从大的方面可以将.sst文件划分为数据存储区和数据管理区数据存储区存放实际的Key:Value数据数据管理区则提供一些索引指针等管理数据目的是更快速便捷的查找相应的记录。两个区域都是在上述的分块基础上的就是说文件的前面若干块实际存储KV数据后面数据管理区存储管理数据。管理数据又分为四种不同类型紫色的Meta Block红色的MetaBlock 索引和蓝色的数据索引块以及一个文件尾部块。 LevelDb 1.2版对于Meta Block尚无实际使用只是保留了一个接口估计会在后续版本中加入内容下面我们看看数据索引区和文件尾部Footer的内部结构。 图4.3 数据索引 图4.3是数据索引的内部结构示意图。再次强调一下Data Block内的KV记录是按照Key由小到大排列的数据索引区的每条记录是对某个Data Block建立的索引信息每条索引信息包含三个内容以图4.3所示的数据块i的索引Index i来说红色部分的第一个字段记载大于等于数据块i中最大的Key值的那个Key第二个字段指出数据块i在.sst文件中的起始位置第三个字段指出Data Block i的大小有时候是有数据压缩的。后面两个字段好理解是用于定位数据块在文件中的位置的第一个字段需要详细解释一下在索引里保存的这个Key值未必一定是某条记录的Key,以图4.3的例子来说假设数据块i 的最小Key“samecity”最大Key“the best”;数据块i1的最小Key“the fox”,最大Key“zoo”,那么对于数据块i的索引Index i来说其第一个字段记载大于等于数据块i的最大Key(“the best”)同时要小于数据块i1的最小Key(“the fox”)所以例子中Index i的第一个字段是“the c”这个是满足要求的而Index i1的第一个字段则是“zoo”即数据块i1的最大Key。 文件末尾Footer块的内部结构见图4.4metaindex_handle指出了metaindex block的起始位置和大小inex_handle指出了index Block的起始地址和大小这两个字段可以理解为索引的索引是为了正确读出索引值而设立的后面跟着一个填充区和魔数。 图4.4 Footer 上面主要介绍的是数据管理区的内部结构下面我们看看数据区的一个Block的数据部分内部是如何布局的图4.1中的红色部分图4.5是其内部布局示意图。 图4.5 数据Block内部结构 从图中可以看出其内部也分为两个部分前面是一个个KV记录其顺序是根据Key值由小到大排列的在Block尾部则是一些“重启点”Restart Point,其实是一些指针指出Block内容中的一些记录位置。 “重启点”是干什么的呢我们一再强调Block内容里的KV记录是按照Key大小有序的这样的话相邻的两条记录很可能Key部分存在重叠比如key i“the Car”Key i1“the color”,那么两者存在重叠部分“the c”为了减少Key的存储量Key i1可以只存储和上一条Key不同的部分“olor”两者的共同部分从Key i中可以获得。记录的Key在Block内容部分就是这么存储的主要目的是减少存储开销。“重启点”的意思是在这条记录开始不再采取只记载不同的Key部分而是重新记录所有的Key值假设Key i1是一个重启点那么Key里面会完整存储“the color”而不是采用简略的“olor”方式。Block尾部就是指出哪些记录是这些重启点的。 图4.6 记录格式 在Block内容区每个KV记录的内部结构是怎样的图4.6给出了其详细结构每个记录包含5个字段key共享长度比如上面的“olor”记录 其key和上一条记录共享的Key部分长度是“the c”的长度即5key非共享长度对于“olor”来说是4value长度指出Key:Value中Value的长度在后面的Value内容字段中存储实际的Value值而key非共享内容则实际存储“olor”这个Key字符串。 上面讲的这些就是.sst文件的全部内部奥秘。
LevelDb日知录之五MemTable详解 LevelDb日知录前述小节大致讲述了磁盘文件相关的重要静态结构本小节讲述内存中的数据结构MemtableMemtable在整个体系中的重要地位也不言而喻。总体而言所有KV数据都是存储在MemtableImmutable Memtable和SSTable中的Immutable Memtable从结构上讲和Memtable是完全一样的区别仅仅在于其是只读的不允许写入操作而Memtable则是允许写入和读取的。当Memtable写入的数据占用内存到达指定数量则自动转换为Immutable Memtable等待Dump到磁盘中系统会自动生成新的Memtable供写操作写入新数据理解了Memtable那么Immutable Memtable自然不在话下。 LevelDb的MemTable提供了将KV数据写入删除以及读取KV记录的操作接口但是事实上Memtable并不存在真正的删除操作,删除某个Key的Value在Memtable内是作为插入一条记录实施的但是会打上一个Key的删除标记真正的删除操作是Lazy的会在以后的Compaction过程中去掉这个KV。 需要注意的是LevelDb的Memtable中KV对是根据Key大小有序存储的在系统插入新的KV时LevelDb要把这个KV插到合适的位置上以保持这种Key有序性。其实LevelDb的Memtable类只是一个接口类真正的操作是通过背后的SkipList来做的包括插入操作和读取操作等所以Memtable的核心数据结构是一个SkipList。 SkipList是由William Pugh发明。他在Communications of the ACM June 1990, 33(6) 668-676 发表了Skip lists: a probabilistic alternative to balanced trees在该论文中详细解释了SkipList的数据结构和插入删除操作。
SkipList是平衡树的一种替代数据结构但是和红黑树不相同的是SkipList对于树的平衡的实现是基于一种随机化的算法的这样也就是说SkipList的插入和删除的工作是比较简单的。
关于SkipList的详细介绍可以参考这篇文章http://www.cnblogs.com/xuqiang/archive/2011/05/22/2053516.html讲述的很清楚LevelDb的SkipList基本上是一个具体实现并无特殊之处。 SkipList不仅是维护有序数据的一个简单实现而且相比较平衡树来说在插入数据的时候可以避免频繁的树节点调整操作所以写入效率是很高的LevelDb整体而言是个高写入系统SkipList在其中应该也起到了很重要的作用。Redis为了加快插入操作也使用了SkipList来作为内部实现数据结构。
LevelDb日知录之六 写入与删除记录 在之前的五节LevelDb日知录中我们介绍了LevelDb的一些静态文件及其详细布局从本节开始我们看看LevelDb的一些动态操作比如读写记录Compaction错误恢复等操作。 本节介绍levelDb的记录更新操作即插入一条KV记录或者删除一条KV记录。levelDb的更新操作速度是非常快的源于其内部机制决定了这种更新操作的简单性。 图6.1 LevelDb写入记录 图6.1是levelDb如何更新KV数据的示意图从图中可以看出对于一个插入操作Put(Key,Value)来说完成插入操作包含两个具体步骤首先是将这条KV记录以顺序写的方式追加到之前介绍过的log文件末尾因为尽管这是一个磁盘读写操作但是文件的顺序追加写入效率是很高的所以并不会导致写入速度的降低第二个步骤是:如果写入log文件成功那么将这条KV记录插入内存中的Memtable中前面介绍过Memtable只是一层封装其内部其实是一个Key有序的SkipList列表插入一条新记录的过程也很简单即先查找合适的插入位置然后修改相应的链接指针将新记录插入即可。完成这一步写入记录就算完成了所以一个插入记录操作涉及一次磁盘文件追加写和内存SkipList插入操作这是为何levelDb写入速度如此高效的根本原因。 从上面的介绍过程中也可以看出log文件内是key无序的而Memtable中是key有序的。那么如果是删除一条KV记录呢对于levelDb来说并不存在立即删除的操作而是与插入操作相同的区别是插入操作插入的是Key:Value 值而删除操作插入的是“Key:删除标记”并不真正去删除记录而是后台Compaction的时候才去做真正的删除操作。 levelDb的写入操作就是如此简单。真正的麻烦在后面将要介绍的读取操作中。
LevelDb日知录之七读取记录 LevelDb是针对大规模Key/Value数据的单机存储库从应用的角度来看LevelDb就是一个存储工具。而作为称职的存储工具常见的调用接口无非是新增KV删除KV读取KV更新Key对应的Value值这么几种操作。LevelDb的接口没有直接支持更新操作的接口如果需要更新某个Key的Value,你可以选择直接生猛地插入新的KV保持Key相同这样系统内的key对应的value就会被更新或者你可以先删除旧的KV 之后再插入新的KV这样比较委婉地完成KV的更新操作。 假设应用提交一个Key值下面我们看看LevelDb是如何从存储的数据中读出其对应的Value值的。图7-1是LevelDb读取过程的整体示意图。 图7-1 LevelDb读取记录流程 LevelDb首先会去查看内存中的Memtable如果Memtable中包含key及其对应的value则返回value值即可如果在Memtable没有读到key则接下来到同样处于内存中的Immutable Memtable中去读取类似地如果读到就返回若是没有读到,那么只能万般无奈下从磁盘中的大量SSTable文件中查找。因为SSTable数量较多而且分成多个Level所以在SSTable中读数据是相当蜿蜒曲折的一段旅程。总的读取原则是这样的首先从属于level 0的文件中查找如果找到则返回对应的value值如果没有找到那么到level 1中的文件中去找如此循环往复直到在某层SSTable文件中找到这个key对应的value为止或者查到最高level查找失败说明整个系统中不存在这个Key)。 那么为什么是从Memtable到Immutable Memtable再从Immutable Memtable到文件而文件中为何是从低level到高level这么一个查询路径呢道理何在之所以选择这么个查询路径是因为从信息的更新时间来说很明显Memtable存储的是最新鲜的KV对Immutable Memtable中存储的KV数据对的新鲜程度次之而所有SSTable文件中的KV数据新鲜程度一定不如内存中的Memtable和Immutable Memtable的。对于SSTable文件来说如果同时在level L和Level L1找到同一个keylevel L的信息一定比level L1的要新。也就是说上面列出的查找路径就是按照数据新鲜程度排列出来的越新鲜的越先查找。 为啥要优先查找新鲜的数据呢这个道理不言而喻举个例子。比如我们先往levelDb里面插入一条数据 {keywww.samecity.com value我们},过了几天samecity网站改名为69同城此时我们插入数据{keywww.samecity.com value69同城}同样的key,不同的value逻辑上理解好像levelDb中只有一个存储记录即第二个记录但是在levelDb中很可能存在两条记录即上面的两个记录都在levelDb中存储了此时如果用户查询keywww.samecity.com,我们当然希望找到最新的更新记录也就是第二个记录返回这就是为何要优先查找新鲜数据的原因。 前文有讲对于SSTable文件来说如果同时在level L和Level L1找到同一个keylevel L的信息一定比level L1的要新。这是一个结论理论上需要一个证明过程否则会招致如下的问题为神马呢从道理上讲呢很明白因为Level L1的数据不是从石头缝里蹦出来的也不是做梦梦到的那它是从哪里来的Level L1的数据是从Level L 经过Compaction后得到的如果您不知道什么是Compaction那么........也许以后会知道的也就是说您看到的现在的Level L1层的SSTable数据是从原来的Level L中来的现在的Level L比原来的Level L数据要新鲜所以可证现在的Level L比现在的Level L1的数据要新鲜。 SSTable文件很多如何快速地找到key对应的value值在LevelDb中level 0一直都爱搞特殊化在level 0和其它level中查找某个key的过程是不一样的。因为level 0下的不同文件可能key的范围有重叠某个要查询的key有可能多个文件都包含这样的话LevelDb的策略是先找出level 0中哪些文件包含这个keymanifest文件中记载了level和对应的文件及文件里key的范围信息LevelDb在内存中保留这种映射表 之后按照文件的新鲜程度排序新的文件排在前面之后依次查找读出key对应的value。而如果是非level 0的话因为这个level的文件之间key是不重叠的所以只从一个文件就可以找到key对应的value。 最后一个问题,如果给定一个要查询的key和某个key range包含这个key的SSTable文件那么levelDb是如何进行具体查找过程的呢levelDb一般会先在内存中的Cache中查找是否包含这个文件的缓存记录如果包含则从缓存中读取如果不包含则打开SSTable文件同时将这个文件的索引部分加载到内存中并放入Cache中。 这样Cache里面就有了这个SSTable的缓存项但是只有索引部分在内存中之后levelDb根据索引可以定位到哪个内容Block会包含这条key从文件中读出这个Block的内容在根据记录一一比较如果找到则返回结果如果没有找到那么说明这个level的SSTable文件并不包含这个key所以到下一级别的SSTable中去查找。 从之前介绍的LevelDb的写操作和这里介绍的读操作可以看出相对写操作读操作处理起来要复杂很多所以写的速度必然要远远高于读数据的速度也就是说LevelDb比较适合写操作多于读操作的应用场合。而如果应用是很多读操作类型的那么顺序读取效率会比较高因为这样大部分内容都会在缓存中找到尽可能避免大量的随机读取操作。
LevelDb日知录之八Compaction操作 前文有述对于LevelDb来说写入记录操作很简单删除记录仅仅写入一个删除标记就算完事但是读取记录比较复杂需要在内存以及各个层级文件中依照新鲜程度依次查找代价很高。为了加快读取速度levelDb采取了compaction的方式来对已有的记录进行整理压缩通过这种方式来删除掉一些不再有效的KV数据减小数据规模减少文件数量等。 levelDb的compaction机制和过程与Bigtable所讲述的是基本一致的Bigtable中讲到三种类型的compaction: minor major和full。所谓minor Compaction就是把memtable中的数据导出到SSTable文件中major compaction就是合并不同层级的SSTable文件而full compaction就是将所有SSTable进行合并。 LevelDb包含其中两种minor和major。 我们将为大家详细叙述其机理。 先来看看minor Compaction的过程。Minor compaction 的目的是当内存中的memtable大小到了一定值时将内容保存到磁盘文件中图8.1是其机理示意图。 图8.1 minor compaction 从8.1可以看出当memtable数量到了一定程度会转换为immutable memtable此时不能往其中写入记录只能从中读取KV内容。之前介绍过immutable memtable其实是一个多层级队列SkipList其中的记录是根据key有序排列的。所以这个minor compaction实现起来也很简单就是按照immutable memtable中记录由小到大遍历并依次写入一个level 0 的新建SSTable文件中写完后建立文件的index 数据这样就完成了一次minor compaction。从图中也可以看出对于被删除的记录在minor compaction过程中并不真正删除这个记录原因也很简单这里只知道要删掉key记录但是这个KV数据在哪里?那需要复杂的查找所以在minor compaction的时候并不做删除只是将这个key作为一个记录写入文件中至于真正的删除操作在以后更高层级的compaction中会去做。 当某个level下的SSTable文件数目超过一定设置值后levelDb会从这个level的SSTable中选择一个文件level0将其和高一层级的level1的SSTable文件合并这就是major compaction。 我们知道在大于0的层级中每个SSTable文件内的Key都是由小到大有序存储的而且不同文件之间的key范围文件内最小key和最大key之间不会有任何重叠。Level 0的SSTable文件有些特殊尽管每个文件也是根据Key由小到大排列但是因为level 0的文件是通过minor compaction直接生成的所以任意两个level 0下的两个sstable文件可能再key范围上有重叠。所以在做major compaction的时候对于大于level 0的层级选择其中一个文件就行但是对于level 0来说指定某个文件后本level中很可能有其他SSTable文件的key范围和这个文件有重叠这种情况下要找出所有有重叠的文件和level 1的文件进行合并即level 0在进行文件选择的时候可能会有多个文件参与major compaction。 levelDb在选定某个level进行compaction后还要选择是具体哪个文件要进行compactionlevelDb在这里有个小技巧 就是说轮流来比如这次是文件A进行compaction那么下次就是在key range上紧挨着文件A的文件B进行compaction这样每个文件都会有机会轮流和高层的level 文件进行合并。
如果选好了level L的文件A和level L1层的文件进行合并那么问题又来了应该选择level L1哪些文件进行合并levelDb选择L1层中和文件A在key range上有重叠的所有文件来和文件A进行合并。 也就是说选定了level L的文件A,之后在level L1中找到了所有需要合并的文件B,C,D…..等等。剩下的问题就是具体是如何进行major 合并的就是说给定了一系列文件每个文件内部是key有序的如何对这些文件进行合并使得新生成的文件仍然Key有序同时抛掉哪些不再有价值的KV 数据。 图8.2说明了这一过程。 图8.2 SSTable Compaction Major compaction的过程如下对多个文件采用多路归并排序的方式依次找出其中最小的Key记录也就是对多个文件中的所有记录重新进行排序。之后采取一定的标准判断这个Key是否还需要保存如果判断没有保存价值那么直接抛掉如果觉得还需要继续保存那么就将其写入level L1层中新生成的一个SSTable文件中。就这样对KV数据一一处理形成了一系列新的L1层数据文件之前的L层文件和L1层参与compaction 的文件数据此时已经没有意义了所以全部删除。这样就完成了L层和L1层文件记录的合并过程。 那么在major compaction过程中判断一个KV记录是否抛弃的标准是什么呢其中一个标准是:对于某个key来说如果在小于L层中存在这个Key那么这个KV在major compaction过程中可以抛掉。因为我们前面分析过对于层级低于L的文件中如果存在同一Key的记录那么说明对于Key来说有更新鲜的Value存在那么过去的Value就等于没有意义了所以可以删除。 LevelDb日知录之九 levelDb中的Cache 书接前文前面讲过对于levelDb来说读取操作如果没有在内存的memtable中找到记录要多次进行磁盘访问操作。假设最优情况即第一次就在level 0中最新的文件中找到了这个key那么也需要读取2次磁盘一次是将SSTable的文件中的index部分读入内存这样根据这个index可以确定key是在哪个block中存储第二次是读入这个block的内容然后在内存中查找key对应的value。 levelDb中引入了两个不同的Cache:Table Cache和Block Cache。其中Block Cache是配置可选的即在配置文件中指定是否打开这个功能。 图9.1 table cache 图9.1是table cache的结构。在Cache中key值是SSTable的文件名称Value部分包含两部分一个是指向磁盘打开的SSTable文件的文件指针这是为了方便读取内容另外一个是指向内存中这个SSTable文件对应的Table结构指针table结构在内存中保存了SSTable的index内容以及用来指示block cache用的cache_id ,当然除此外还有其它一些内容。 比如在get(key)读取操作中如果levelDb确定了key在某个level下某个文件A的key range范围内那么需要判断是不是文件A真的包含这个KV。此时levelDb会首先查找Table Cache看这个文件是否在缓存里如果找到了那么根据index部分就可以查找是哪个block包含这个key。如果没有在缓存中找到文件那么打开SSTable文件将其index部分读入内存然后插入Cache里面去index里面定位哪个block包含这个Key 。如果确定了文件哪个block包含这个key那么需要读入block内容这是第二次读取。 图9.2 block cache Block Cache是为了加快这个过程的图9.2是其结构示意图。其中的key是文件的cache_id加上这个block在文件中的起始位置block_offset。而value则是这个Block的内容。 如果levelDb发现这个block在block cache中那么可以避免读取数据直接在cache里的block内容里面查找key的value就行如果没找到呢那么读入block内容并把它插入block cache中。levelDb就是这样通过两个cache来加快读取速度的。从这里可以看出如果读取的数据局部性比较好也就是说要读的数据大部分在cache里面都能读到那么读取效率应该还是很高的而如果是对key进行顺序读取效率也应该不错因为一次读入后可以多次被复用。但是如果是随机读取您可以推断下其效率如何。
LevelDb日知录之十 Version、VersionEdit、VersionSet Version 保存了当前磁盘以及内存中所有的文件信息一般只有一个Version叫做current version当前版本。Leveldb还保存了一系列的历史版本这些历史版本有什么作用呢
当一个Iterator创建后Iterator就引用到了current version(当前版本)只要这个Iterator不被delete那么被Iterator引用的版本就会一直存活。这就意味着当你用完一个Iterator后需要及时删除它。 当一次Compaction结束后会生成新的文件合并前的文件需要删除Leveldb会创建一个新的版本作为当前版本原先的当前版本就会变为历史版本。 VersionSet 是所有Version的集合管理着所有存活的Version。 VersionEdit 表示Version之间的变化相当于delta 增量表示有增加了多少文件删除了文件。下图表示他们之间的关系。
Version0 VersionEdit--Version1 VersionEdit会保存到MANIFEST文件中当做数据恢复时就会从MANIFEST文件中读出来重建数据。 leveldb的这种版本的控制让我想到了双buffer切换双buffer切换来自于图形学中用于解决屏幕绘制时的闪屏问题在服务器编程中也有用处。 比如我们的服务器上有一个字典库每天我们需要更新这个字典库我们可以新开一个buffer将新的字典库加载到这个新buffer中等到加载完毕将字典的指针指向新的字典库。
leveldb的version管理和双buffer切换类似但是如果原version被某个iterator引用那么这个version会一直保持直到没有被任何一个iterator引用此时就可以删除这个version。
注博文参考了郎格科技博客http://www.samecity.com/blog/Index.asp?SortID12
