EROFS 碎片去重准备
因为 EROFS 就是奔着取代 SquashFS 去的(should be),之前我们已经添加了碎片的支持,但是不支持去重。先大概看下 SquashFS 碎片去重是怎么做的。知己知彼,才能百战百胜。
Check SquashFS 碎片去重
参考 squashfs-tools 4.5.1
/* hash tables used to do fast duplicate searches in duplicate check */ |
定义了一个 hash table 用来快速查找重复的碎片。这个 table 是怎么用的呢,能看到这样的使用:
/* Look for a possible duplicate fragment */ |
也就是把 fragment_size
碎片大小用作 hash value。so,只有相同大小的碎片才能去重?继续看:
static struct file_info *frag_duplicate(struct file_buffer *file_buffer, int *duplicate) |
frag_duplicate()
这函数名起的,是要做去重 dedupe
吗?看着落款 Phillip Lougher phillip@squashfs.org.uk 应该是大英的。
/* Look for a possible duplicate fragment */ |
ok, 看了上面这一段,基本逻辑就是 fragment_size
碎片大小相同而且 fragment_checksum
相同时然后再看内容是否一致。”Am i missing sth?” (mmm…留点退路不流破绽)
简要回顾下哈希
A hash function is any function that can be used to map data of arbitrary size to fixed-size values. The values returned by a hash function are called hash values, hash codes, digests, or simply hashes. The values are usually used to index a fixed-size table called a hash table. Use of a hash function to index a hash table is called hashing or scatter storage addressing.
A hash table is typically an array of linked lists.
需要留意的是 hash table size 若过小 + link list 长度过长,效率低点, 就是 collision 的问题,不多说,知道这个即可。
EROFS 碎片去重
f哥,长度短点的不能去重么。可以使用 16bits checksum 作为 hash, table size 就 64KB。
我的想法比较简单也比较好写,就是顺着当前逻辑,在 packing fragment 分支时查表。但是有个问题,就是大碎片只有部分重复的怎么办?
Gao Xiang 建议在压缩前做去重,这样做的好处是避免把一部分重复的碎片写到 packed inode 里。不过改起来有点别扭,因为压缩 final 时要返回再读文件重新压缩。这种做法也解决了上面的疑问,rt?
Now, let’s do it.
版权声明:本站所有文章均采用 CC BY-NC-SA 4.0 CN 许可协议。转载请注明原文链接!