大量文件名记录的树形结构存储
十多年来,NAS中已经存在的目录和文件达到10亿之多,在设计和开发备份系统的过程中碰到了很多挑战,本文将分享大量文件名记录的树形结构存储实践。
一、引言
既然是定期备份,肯定会有1次以上的备份。对于一个特定目录,每次备份时都要与上次备份时进行比较,以期找出哪些文件被删除了,又新增了哪些文件,这就需要每次备份时把该目录下的所有文件名进行保存。我们首先想到的是把所有文件名用特定字符进行拼接后保存。由于我们使用了MySQL保存这些信息,当目录下文件很多时,这种拼接的方式很可能超出MySQL的Blob长度限制。根据经验,当一个目录有大量文件时,这些文件的名称往往是程序生成的,有一定规律的,而且开头一般是重复的,于是我们想到了使用一种树形结构来进行存储。
例如,一个有abc、abc1、ad、cde 4个文件的目录对应的树如图1所示。
图1 树形结构示例
图1中,R表示根节点,青色节点我们称为结束节点,从R到每个结束节点的路径都表示一个文件名。可以在树中查找是否含有某个文件名、遍历树中所有的文件名、对树序列化进行保存、由序列化结果反序列化重新生成树。
二、涉及的数据结构
注意:我们使用java编写,文中涉及语言特性相关的知识点都是指java。
2.1 Node的结构
包括根节点在内的每个节点都使用Node类来表示。代码如下:
class Node { private char value; private Node[]children = new Node[0]; private byte end = 0; }
字段说明:
- value:该节点表示的字符,当Node表示根节点时,value无值。
- children:该节点的所有子节点,初始化为长度为0的数组。
- end:标记节点是否是结束节点。0不是;1是。叶子节点肯定是结束节点。默认非结束节点。
2.2 Node的操作
public Node(char v); public Node findChild(char v); public Node addChild(char v);
操作说明:
- Node:构造方法。将参数v赋值给this.value。
- findChild:查找children中是否含有value为v的子节点。有则返回子节点,没有则返回null。
- addChild:首先查找children中是否已经含有value为v的子节点,如果有则直接将查到的子节点返回;否则创建value为v的节点,将children的长度延长1,将新创建的节点作为children的最后一个元素,并返回新创建的节点。
2.3 Tree的结构
class Tree { public Node root = new Node(); }
字段说明:Tree只含有root Node。如前所述,root的value无值,end为0。初始时的children长度为0。
2.4 Tree的操作
public void addName(String name) ; public boolean contain(String name); public Found next(Found found); public void writeTo(OutputStream out); public static Tree readFrom(InputStream in);
操作说明:
- addName:向树中增加一个新的文件名,即参数name。以root为起点,name中的每个字符作参数调用addChild,返回值又作为新的起点,直到name中的全部字符添加完毕,对最后一次调用addChild的返回值标记为结束节点。
- contain:查询树中是否含有一个文件名。
- next:对树中包含的所有文件名进行遍历,为了使遍历能够顺利进行,我们引入了新的类Found,细节会在后文详述。
- writeTo:将树写入一个输出流以进行持久化。
- readFrom:此方法是静态方法。从一个输入流来重新构建树。
三、树的构建
在新建的Tree上调用addName方法,将所有文件名添加到树中,树构建完成。仍然以含有abc、abc1、ad、cde 四个文件的目录为例,对树的构建进行图示。
图2 树的构建过程
图2中,橙色节点表示需要在该节点上调用addChild方法增加子节点,同时addChild的返回值作为新的橙色节点。直到没有子节点需要增加时,把最后的橙色节点标记为结束节点。
四、树的查询
查找树中是否含有一个某个文件名,对应Tree的contain方法。在图2中的结果上分别查找ef、ab和abc三个文件来演示查找的过程。如图3所示。
图3 树的查询示意图
图3中,橙色节点表示需要在该节点上调用findChild方法查找子节点。
五、树的遍历
此处的遍历不同于一般树的遍历。一般遍历是遍历树中的节点,而此处的遍历是遍历根节点到所有结束节点的路径。
我们采用从左到右、由浅及深的顺序进行遍历。我们引入了Found类,并作为next方法的参数进行遍历。
5.1 Found的结构
class Found { private String name; private int[] idx ; }
为了更加容易的说明问题,在图1基础上进行了小小的改造,每个节点的右下角增加了下标,如图4。
图4 带下标的Tree
对于abc这个文件名,Found中的name值为“abc”,idx为{0,0,0}。
对于abc1这个文件名,Found中的name值为“abc1”,idx为{0,0,0,0}。
对于ad这个文件名,Found中的name值为“ad”,idx为{0,1}。
对于cde这个文件名,Found中的name值为“cde”,idx为{1,0,0}。
5.2 如何遍历
对于图4而言,第一次调用next方法应传入null,则返回第一个结果,即abc代表的Found;继续以这个Found作为参数进行第二次next的调用,则返回第二个结果,即abc1代表的Found;再继续以这个Found作为参数进行第三次next的调用,则返回第三个结果,即ad所代表的Found;再继续以这个Found作为参数进行第四次next的调用,则返回第四个结果,即cde所代表的Found;再继续以这个Found作为参数进行第五次调用,则返回null,遍历结束。
六、序列化与反序列化
6.1 序列化
首先应该明确每个节点序列化后应该包含3个信息:节点的value、节点的children数量和节点是否为结束节点。
6.1.1 节点的value
虽然之前所举的例子中节点的value都是英文字符,但实际上文件名中可能含有汉字或者其他语言的字符。为了方便处理,我们没有使用变长编码。而是直接使用unicode码。字节序采用大端编码。
6.1.2 节点的children数量
由于节点的value使用了unicode码,所以children的数量不会多于unicode能表示的字符的数量,即65536。children数量使用2个字节。字节序同样采用大端编码。
6.1.3 节点的end
0或1可以使用1位(1bit)来表示,但java中最小单位是字节。如果采用1个字节来表示end,有些浪费空间,其实任何一个节点children数量达到65536/2的可能性都是极小的,因此我们考虑借用children数量的最高位来表示end。
综上所述,一个节点序列化后占用4个字节,以图4中的根节点、value为b的节点和value为e的节点为例:
表1 Node序列化示例
value的unicode | children数量 | end | children数量/(end<<15) | 最终结果 | |
---|---|---|---|---|---|
根节点 | 0x0000 | 2 | 0 | 0x0002 | 0x00020000 |
b节点 | 0x0062 | 1 | 0 | 0x0001 | 0x00010062 |
e节点 | 0x0065 | 0 | 1 | 0x8000 | 0x80000065 |
6.1.4 树的序列化过程
对树进行广度遍历,在遍历过程中需要借助队列,以图4的序列化为例进行说明:
图5 对图4的序列化过程
6.2 反序列化
反序列化是序列化的逆过程,由于篇幅原因不再进行阐述。值得一提的是,反序列化过程同样需要队列的协助。
七、讨论
7.1 关于节省空间
为方便讨论,假设目录下的文件名是10个阿拉伯数字的全排列,当位数为1时,目录下含有10个文件,即0、1、2……8、9,当位数为2时,目录下含有100个文件,即00、01、02……97、98、99,以此类推。
比较2种方法,一种使用“/”分隔,另一种是本文介绍的方法。
表2 2种方法的存储空间比较(单位:字节)
位数 方法 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|
“/”分隔 | 19 | 299 | 3999 | 49999 | 599999 | 6999999 |
Tree | 44 | 444 | 4444 | 44444 | 444444 | 4444444 |
由表2可见,当位数为4时,使用Tree的方式开始节省空间,位数越多节省的比例越高,这正是我们所需要的。
表中,使用“/”分隔时,字节数占用是按照utf8编码计算的。如果直接使用unicode进行存储,占用空间会加倍,那么会在位数为2时就开始节省空间。同样使用“/”分隔,看起来utf8比使用unicode会更省空间,但实际上,文件名中有时候会含有汉字,汉字的utf8编码占用3个字节。
7.2 关于时间
在树的构建、序列化反序列化过程中,引入了额外的运算,根据我们的实践,user CPU并没有明显变化。
7.3 关于理想化假设
最初我们就是使用了“/”分隔的方法对文件名进行存储,并且数据库的相应字段类型是Blob(Blob的最大值是65K)。在测试阶段就发现,超出65K是一件很平常的事情。在不可能预先统计最大目录里所有文件名拼接后的大小的情况下,我们采取了2种手段,一是使用LongBlob类型,另一种就是尽量减小拼接结果的大小,即本文介绍的方法。
即使使用树形结构来存储文件名,也不能够保证最终结果不超出4G(LongBlob类型的最大值),至少在我们实践的过程并未出现问题,如果真出现这种情况,只能做特殊处理了。
7.4 关于其他压缩方法
把文件名使用“/”拼接后,使用gzip等压缩算法对拼接结果进行压缩后再存储,在节省存储空间方面会取得更好的效果。但是在压缩之前,拼接结果存在于内存,这样对JVM的堆内存有比较高的要求;另外,使用“/”拼接时,查找会比较麻烦。
作者:牛宁昌
来源:宜信技术学院
![](/img/my/wx.png)
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
进程知多少?
文章首发:进程知多少? Java 多线程系列文章第 1 篇 要讲线程,一般都得讲一讲进程,进程是何方神圣呢?下面来简单介绍一下。 先通过任务管理器看看 Windows 系统下的进程。 从图片来看,每一个进程都占有 CPU、内存、磁盘、网络等资源。站在操作系统的角度,进程是分配资源的基本单位,也是最小单位。 进程为什么出现? 引入进程的目的:为了使多个程序能并发执行,以提高资源的利用率和系统的吞吐量。怎么理解这句话呢?一个程序在运行过程中会涉及很多操作,利用 CPU 计算、通过磁盘 IO 进行数据传输等等,我们知道当程序在进行磁盘 IO 的时候,因为速度问题,会比较慢,所在在这个过程中 CPU 会空闲下来,这会造成资源的浪费,正因为引入进程,在 A 进程进行磁盘 IO 的时候,会让出 CPU 给 B 进程,合理地利用了 CPU 资源,使得程序之间可以并发执行。 从 CPU 角度,执行过程是这样子的:CPU 一直在负责执行指令,进程之间互相竞争 CPU 资源,下图有 A 和 B 进程,在一个时间点,CPU 只执行一个进程的指令,因为 CPU 运行很快,所以在咱们看起来,像是多个进程在同时跑...
- 下一篇
Maven 虐我千百遍,我待 Maven 如初恋
前言 在如今的互联网项目开发当中,特别是Java领域,可以说Maven随处可见。Maven的仓库管理、依赖管理、继承和聚合等特性为项目的构建提供了一整套完善的解决方案,可以说如果你搞不懂Maven,那么一个多模块的项目足以让你头疼,依赖冲突就会让你不知所措,甚至搞不清楚项目是如何运行起来的.....OK,博主就曾经被Maven“伤害”过,那么该专题的目的就是:彻底搞定Maven! Thinking in Maven 回想一下,当你新到一家公司,安装完JDK后就会安装配置Maven(MAVEN_HOME、path),很大可能性你需要修改settings.xml文件,比如你会修改本地仓库地址路径,比如你很可能会copy一段配置到你的settings.xml中(很可能就是私服的一些配置)。 接下来,你会到IDEA或者Eclipse中进行Maven插件配置,然后你就可以在工程中的pom.xml里面开始添加<dependency>标签来管理jar包,在Maven规范的目录结构下进行编写代码,最后你会通过插件的方式来进行测试、打包(jar or war)、部署、运行。 上面描述了我们对...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- CentOS8编译安装MySQL8.0.19
- Hadoop3单机部署,实现最简伪集群
- CentOS7设置SWAP分区,小内存服务器的救世主
- CentOS7编译安装Cmake3.16.3,解决mysql等软件编译问题
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- CentOS8安装MyCat,轻松搞定数据库的读写分离、垂直分库、水平分库
- CentOS7,CentOS8安装Elasticsearch6.8.6
- SpringBoot2整合Thymeleaf,官方推荐html解决方案
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- Windows10,CentOS7,CentOS8安装Nodejs环境