文档章节

利用leveldb实现文件系统的目录树

yvxiang
 yvxiang
发布于 2016/12/19 09:16
字数 1257
阅读 211
收藏 3

利用leveldb实现文件系统的目录树

目录树维护了整个文件系统的元信息,所有对文件系统中文件的增删查改操作都首先需要经过目录树的操作才能进行。百度开源的分布式文件系统BFS(开源地址:https://github.com/baidu/bfs)利用leveldb,实现了目录树的管理,使得目录树的实现非常简洁,同时对目录树的操作十分高效。本文将为你解析其具体设计及实现思路。

目录树为一个树型结构,而leveldb是一个kv存储引擎,因此,如果想用通过leveldb实现目录树,则需要把树型结构映射成kv的扁平化结构。

单独就每个文件或者目录来讲,其信息只需要一条kv记录即可保存,而这条kv中的value需要保存该目录或文件的属性信息,可变动的空间不大。所以,从树型结构到kv记录的映射 ,关键在于key的选取。

在BFS的目录树中,定义了一个int64_t的整型数字作为EntryID,每个文件或目录拥有一个EntryID,并且全局唯一,根目录的EntryID规定为1。假设有如下目录结构:

/home/dirx/
          /filex
      diry/
          /filey
/tmp/
     filez

按照创建顺序,我们依次给/home分配的EntryID为2,/tmpEntryID为3,/home/dirxEntryId为4,/home/diryEntryID为5,/home/tmp/filezEntryID为6,/home/dirx/filexEntryID为7,/home/diry/fileyEntryID为8。

注意到每个目录拥有一个自己的EntryID的同时,又肯定拥有一个父目录,其父目录又肯定拥有一个EntryID,可以利用这一点,通过父目录的EntryID和子目录中的文件名,来确定一条记录的key:对于每个文件或者目录,我们规定:每条kv记录的key为 "父目录的EntryID+自身文件名",同时在value中存储自己的EntryID这样编码后,上述目录树便可以表示为如下kv记录:

1home -> 2 + xxx
1tmp -> 3 + xxx
2dirx -> 4 + xxx
2diry -> 5 + xxx
3filez -> 6 + xxx
4filex -> 7 + xxx
5filey -> 8 + xxx

其中,xxx表示该目录或文件的其它信息,如大小,创建时间,实际数据存放位置等。

到此,目录树这个树型结构,便已经平展成为一条条的kv记录,对目录树的操作,便转化成了对某几条kv记录的操作:

  • 对于创建文件操作,比如想创建/home/work/目录,则首先在/目录中查找home目录,由于/EntryID为1,所以第一次查找时,key为1home,然后读出其value,解析后发现/homeEntryID为2,则将此EntryID记下,继续往下走,发现work即为所需要创建的文件,则为其申请一个EntryID(假设为9),此时,写入一条记录,按照上面的规则,其key为2work,value为work创建的时间等信息,以及workEntryID(9)
  • 对于删除操作,比如把刚刚创建的/home/work目录删除,只需要将key为2work的这条记录删除即可
  • 对于读取操作,比如想读取/home/dirx/filex文件中的内容,则首先读取1home这条key所对应的value,解析发现value中记录的EntryID为2,然后再去读取2dirx这条key所对应的value,解析发现value中记录的EntryID为4,然后再去读取4filex这条key所对应的value,从里面解析出/home/dirx/filex的实际数据存放位置,进行文件内容的读取
  • 对于List目录操作,比如想看看根目录下有哪些文件和目录,由于每个文件和目录在存储时,其key中都包含父目录的EntryID,因此,只需进行一次扫描即可。比如ls /,则只需扫描leveldb中,以1\0x0为前缀的key即可,当遇到2时停止,所得结果即为/目录下的所有内容
  • 对于Rename操作,只需要改动其key即可。比如想要把/home/diry/filey文件移动到home/dirx目录中,按照之前的规则,/home/diry/filey在leveldb中存储的key为5filey/home/dirxEntryID为4,把5filey这条记录中的内存读取出来,以4filey为key,再次存储到leveldbk ,然后将5filey这条记录删除,即完成了Rename操作

这样,一个目录树所需要的基本操作便已经支持,由于leveldb引擎本身写入速度较快,并且在读取时,内部本身已经有cache来缓存住较热的kv数据,并且缓存大小可配置,所以一个非常简洁高效的目录树便实现了~

想要了解BFS实现中的其它细节 ,请关注https://github.com/baidu/bfs,或者关注微信公众号『百度网页搜索基础架构团队』获取更多技术信息

© 著作权归作者所有

yvxiang
粉丝 16
博文 3
码字总数 3053
作品 0
北京
私信 提问
用Kyoto Tycoon挂载LevelDB存储

Kyoto Tycoon(以下简称KT)是TokyoTyrant的作者Mikio Hirabayashi 的系列作品之一,KT 是一个数据库网络层服务,它提供一个插件机制,可以挂载几乎所有的数据库存储设备。之前已经有过KT嫁接...

红薯
2011/07/31
2.3K
2
cpy-leveldb 0.3.2 发布

概述 cpy-leveldb(https://github.com/forhappy/cpy-leveldb)是根据leveldb c api的基础上写的python 绑定,并且0.3.x系列版本重写了代码,由以前的单文件项目结构分为目前的多文件结构,代码...

大卷卷
2011/09/17
638
0
LevelDB、TreeDB、SQLite3性能对比测试

下面是对LevelDB、TreeDB、SQLite3 这几个数据库的性能对比测试,分别使用了LevelDB (revision 39) SQLite3 (version 3.7.6.3) 及 Kyoto Cabinet’s (version 1.2.67)这三个版本的数据库。 ...

红薯
2011/08/17
26K
16
兄弟连区块链入门教程以太坊源码分析ethdb源码分析

区块链入门教程以太坊源码分析ethdb源码分析,2018年下半年,区块链行业正逐渐褪去发展之初的浮躁、回归理性,表面上看相关人才需求与身价似乎正在回落。但事实上,正是初期泡沫的渐退,让人...

1505139910833337
2018/10/23
0
0
盘点移动开发中最流行的5个数据库

嵌入式数据库是轻量级的,独立的库,没有服务器组件,无需管理,一个小的代码尺寸,以及有限的资源需求。目前有几种嵌入式数据库,你可以在移动应用程序中使用。让我们来看看这些最流行的数据...

kouxunli1
2014/11/21
430
0

没有更多内容

加载失败,请刷新页面

加载更多

JavaScript设计模式——适配器模式

  适配器模式是设计模式行为型模式中的一种模式;   定义:   适配器用来解决两个已有接口之间不匹配的问题,它并不需要考虑接口是如何实现,也不用考虑将来该如何修改;适配器不需要修...

有梦想的咸鱼前端
31分钟前
3
0
Andorid SQLite数据库开发基础教程(1)

Andorid SQLite数据库开发基础教程(1) Android数据库访问方式 SQLite是Android系统默认支持的文件数据库。该数据库支持SQL语言,适合开发人员上手。本教程将讲解如何开发使用SQLite的Andro...

大学霸
34分钟前
3
0
Handler简解

Handler 这里简化一下代码 以便理解 Handler不一定要在主线程建 但如Handler handler = new Handler(); 会使用当前的Looper的, 由于要更新UI 所以最好在主线程 new Handler() { mLooper = Lo...

shzwork
56分钟前
4
0
h5获取摄像头拍照功能

完整代码展示: <!DOCTYPE html> <head> <title>HTML5 GetUserMedia Demo</title> <meta charset="utf-8"> <meta name="viewport" content="width=device-width, initial-scale=1.0, maximum......

诗书易经
58分钟前
3
0
正向代理和反向代理

文章来源 运维公会:正向代理和反向代理 1、正向代理 (1)服务对象不同 正向代理服务器的服务对象是客户端,可以将客户端和代理服务器看作一个整体。 (2)配置方法不同 需要在客户端配置代...

运维团
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部