0%

FILT

LMS-Tree(Log-Structured Merge-Tree,日志结构合并树)

LSM-tree是由两个或两个以上存储数据的结构组成的。最简单的LSM-tree有两个部分,如下图所示。常驻内存部分,称为$C_0$树(或$C_0$),其可以设计为任何方便键值查找的数据结构,常驻硬盘部分,称为$C_1$树(或$C_1$)。C1进一步可延申为$C_2$,$C_3$等等。

img

数据结构名称解析

  1. 日志:磁盘可以看做是一个日志,就好像日记本一样。在向日志中存放永久性数据及其索引,每次都会添加在日志的末尾。

  2. 合并:

    image-20200703075918216

    内存中无法保存太多的数据,毕竟内存贵。$C_0$是有一个设定阈值的,当达到阈值后,就会merge到$C_1$中,毕竟磁盘中的$C_1$容量大,还便宜。$C_1$到$C_2$的合并也是如此

  3. 树:不多言。

LevelDB

详细介绍

从本周的周报开始,请详细描述你对FILT的理解。如架构、数据流、各函数的调用流程等,务必做到对代码深入理解,为FILT改进做准备。

FILT其实可以看作LevelDB的改进版本。LevelDB是一种持久键值存储容器,其仅仅存储了文件,key-value这种形式的文件。日常使用的文件管理器,还有文件夹这种东西,当然在Linux中也可以当作是一种文件。那么就产生了把文件夹(但可以当作文件)存储到LevelDB这种储存容器中这种想法。通过把文件夹路径Flat indexing,扁平化索引,设计成key-value形式存储到LSM-tree中。

那么问题来了:常规查找一个文件,LSM-tree中查找就可以解决,先从C0内存中查找,查找不到再到C1,C2中找。但是查找指定目录文件夹下有没有特定文件怎么做?这个指定目录可以方便找到,但包含在其中的文件怎么说?

重命名:比如把根目录root重命名为root1,很简单的想法就是把所有含有root及其以下展开的目录文件夹变更成root1.

查找某一文件所属文件夹?

其实应该考虑一下LSM-tree特性,它对写入操作比较擅长,而查找,这属于读操作。

难道有些功能其实可以不予理睬。只需要专注于提供某些特定接口。

那么FLIT做的是啥?是像LevelDB一样的数据库管理程序,还是像xfs一样的文件系统。应该是后者,但代码为什么是LevelDB代码,其中好多都是LevelDB源码?