大量文件名记录的树形结构存储

2020 年 2 月 14 日

大量文件名记录的树形结构存储

2017 年初,为满足“824 监管”的要求,我们开发了备份系统,对涉及客户资料的 NAS 卷进行定期备份。十多年来,NAS 中已经存在的目录和文件达到 10 亿之多,在设计和开发备份系统的过程中碰到了很多挑战,今天拿出其中一个与大家分享。


1.引言


既然是定期备份,肯定会有 1 次以上的备份。对于一个特定目录,每次备份时都要与上次备份时进行比较,以期找出哪些文件被删除了,又新增了哪些文件,这就需要每次备份时把该目录下的所有文件名进行保存。我们首先想到的是把所有文件名用特定字符进行拼接后保存。由于我们使用了 MySQL 保存这些信息,当目录下文件很多时,这种拼接的方式很可能超出 MySQL 的 Blob 长度限制。根据经验,当一个目录有大量文件时,这些文件的名称往往是程序生成的,有一定规律的,而且开头一般是重复的,于是我们想到了使用一种树形结构来进行存储。


例如,一个有 abc、abc1、ad、cde 4 个文件的目录对应的树如图 1 所示。


1512096471356016343.png


图 1 树形结构示例


图 1 中,R 表示根节点,青色节点我们称为结束节点,从 R 到每个结束节点的路径都表示一个文件名。可以在树中查找是否含有某个文件名、遍历树中所有的文件名、对树序列化进行保存、由序列化结果反序列化重新生成树。


2. 涉及的数据结构


注意:我们使用 java 编写,文中涉及语言特性相关的知识点都是指 java。


2.1 Node 的结构


包括根节点在内的每个节点都使用 Node 类来表示。代码如下:


col 1col 2


1


2


3


4


5 | ``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 的操作


col 1col 2


1


2


3 | ``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 的结构


col 1col 2


1


2


3 | ``class Tree {


``public Node root = ``new Node();


``}


字段说明:


Tree 只含有 root Node。如前所述,root 的 value 无值,end 为 0。初始时的 children 长度为 0。


2.4 Tree 的操作


col 1col 2


1


2


3


4


5 | ``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:此方法是静态方法。从一个输入流来重新构建树。


3. 树的构建


在新建的 Tree 上调用 addName 方法,将所有文件名添加到树中,树构建完成。仍然以含有 abc、abc1、ad、cde 四个文件的目录为例,对树的构建进行图示。


1512096497414062148.jpg


图 2 树的构建过程


图 2 中,橙色节点表示需要在该节点上调用 addChild 方法增加子节点,同时 addChild 的返回值作为新的橙色节点。直到没有子节点需要增加时,把最后的橙色节点标记为结束节点。


4. 树的查询


查找树中是否含有一个某个文件名,对应 Tree 的 contain 方法。在图 2 中的结果上分别查找 ef、ab 和 abc 三个文件来演示查找的过程。如图 3 所示。


1512096517803088375.jpg


图 3 树的查询示意图


图 3 中,橙色节点表示需要在该节点上调用 findChild 方法查找子节点。


5. 树的遍历


此处的遍历不同于一般树的遍历。一般遍历是遍历树中的节点,而此处的遍历是遍历根节点到所有结束节点的路径。


我们采用从左到右、由浅及深的顺序进行遍历。我们引入了 Found 类,并作为 next 方法的参数进行遍历。


5.1 Found 的结构


col 1col 2


1


2


3


4 | ``class Found {


``private String name;


``private int``[] idx ;


``}


为了更加容易的说明问题,在图 1 基础上进行了小小的改造,每个节点的右下角增加了下标,如图 4。


1512096533851061505.jpg


图 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. 序列化与反序列化


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 序列化示例


col 1col 2col 3col 4col 5col 6


  | 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. 讨论


7.1 关于节省空间


为方便讨论,假设目录下的文件名是 10 个阿拉伯数字的全排列,当位数为 1 时,目录下含有 10 个文件,即 0、1、2……8、9,当位数为 2 时,目录下含有 100 个文件,即 00、01、02……97、98、99,以此类推。


比较 2 种方法,一种使用“/”分隔,另一种是本文介绍的方法。


表 2 2 种方法的存储空间比较(单位:字节)


col 1col 2col 3col 4col 5col 6col 7


位数


方法 | 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 的堆内存有比较高的要求;另外,使用“/”拼接时,查找会比较麻烦。


本文转载自宜信技术学院网站。


原文链接:http://college.creditease.cn/detail/145


2020 年 2 月 14 日 18:46294

评论

发布
暂无评论
发现更多内容

【第一周作业】食堂就餐卡系统设计

黑莓

玄姐公开课总结【构建基于ServiceMesh的普适业务中台架构】

魔曦

架构 Service Mesh

钟离昧的第一张架构设计图之旅

X中倪

【第一周】学习总结

黑莓

架构师训练营-Week1-作业2

车小勺的男神

Intellij IDEA 右击没有run

程李文华

食堂就餐卡系统设计文档

秤须苑

极客大学架构师训练营

架构师训练营作业一:食堂就餐卡系统设计

常江舟

极客大学架构师训练营

架构方法:架构师如何做架构

SpringBoot分布式任务中间件开发 附视频讲解 (手把手教你开发和使用中间件)

小傅哥

小傅哥 中间件 springboot 分布式任务

02-kubernetes自建CA及双向TLS认证

绿星雪碧

Kubernetes TLS CA证书

LocalDateTime和Date的比较与区别

彭阿三

时间格式化 LocalDateTime Date

Week 01 食堂饭卡系统设计

Geek_165f3d

架构师训练营第一周学习总结

常江舟

极客大学架构师训练营

食堂就餐卡设计说明书

小师妹学JavaIO之:NIO中Channel的妙用

程序那些事

io nio 小师妹 buffer channel

你并不理解i++和++i

flyhero

Java 程序员 JVM i++

钟离昧的一梭子架构师之旅

X中倪

架构师课程学习第一周心得

秤须苑

极客大学架构师训练营

数据库周刊27丨6月最新国产数据库排行;OB成立新公司奥星贝斯;腾讯云发布图数据库TGDB;Oracle坏块修复;MySQL故障排查导图;经典SQL语句大全...

墨天轮

数据库

week01总结

seki

极客大学架构师训练营

架构师训练营-Week1-作业1

车小勺的男神

架构第一课学习总结

师哥

游戏夜读 | 如何成长为游戏人?

game1night

week01作业

seki

架构师训练营--第1周总结感想

芥菜

让独立思考成为习惯

Neco.W

学习 深度思考 思考

使用VSCode连接到IBM Cloud区块链网络

程序那些事

智能合约 hyperledger fabric ibm cloud

Android 无埋点从入门到放弃:了解 Java 字节码

GrowingIO技术专栏

系统/子系统/模块/组件/框架/架构

gen_jin

量子技术到底有哪些突破值得重点关注?

蔡芳芳

大量文件名记录的树形结构存储-InfoQ