[随笔]文件系统上存储哈希对象：哈希算法以及目录结构对性能的影响

Miigon

发布于 2023-03-31 14:52:14

1.1K0

发布于 2023-03-31 14:52:14

文章被收录于专栏：Miigon's Blog

从文件系统的实现原理角度讨论 /77/e1/77e1cccccc... 模式的 hash object 命名的优点以及必要/不必要性，以及算法选择。

原贴

原贴：https://0xffff.one/d/1395-wen-jian-xi-tong-zuo-wei-huan-cun

一个常见的业务场景，需要实现一个 Key-Value Cache Storage，除了 Redis 等外，有一个方向是用设备本身的文件系统来落地。

大概操作是，用 Key 生成 Path，再基于这个 Path 去读写文件，再将结果返回给业务，这个操作通常是

Key 经过 hash 函数算出一个值
取这个值的前四位，做一个二级目录，如 77e1ba46ee3a2b2d1558d7c5d07c4c0caa46c7bf，生成一个 77/e1/77e1ba46ee3a2b2d1558d7c5d07c4c0caa46c7bf 的路径
基于生成的路径读写

有俩个考虑的点：

hash 函数如何选择（sha256？还是古老的 sha1 / md5）
路径的划分，大量 key 下，对性能的影响

哈希算法

哈希算法，作为一个将大数据映射到一个固定范围内的值的算法，有几个主要的因素要考虑：

速度
碰撞概率，在期望的数据集上，计算出来的哈希分布是否均匀
安全性，从某个已知哈希，恶意构建哈希值一致的数据的难度

不同用途的哈希算法

当然用于不同用途的哈希，权衡的点也不同：

Cryptographic Hash：用于密码学用途，比如密码哈希，碰撞概率和安全性要求都比较高。逆向构造难度大，没有已知快速（within reasonable time）破解的方法，速度相对要求不高，甚至要求速度不能太快，以抵御暴力攻击。常见：SHA-2（SHA256、SHA512）、SHA-3。
Checksum/Digest/Non-cryptographic Hash：用于校验消息传输的完整度，或者大致打乱数据，不要求十分随机，也不要求抗恶意攻击。一般都是优化计算速度。比较常见：取模、TCP/UDP的补码和checksum、CRC32、MD4、MD5、SHA1、xxhash、murmurhash。

其中MD4、MD5、SHA1属于比较典型的原本作为 Cryptographic Hash 被使用，但是由于计算机算力发展/捷径攻击方式被发现，而被认为不再安全，从而退化到只被作为 Checksum 使用。

一般来说，Checksum 使用的 Hash 算法的速度要比 Cryptographic Hash 要快。当然，使用 Cryptographic Hash 来算 Checksum 是完全可行的（虽然 overkill）。而反过来使用 Checksum 用的算法去当做 Cryptographic Hash 用就是认为是不安全的了。

key hash 场景下的算法选择

KV存储场景下 key 的哈希算法，属于比较介于两种用途之间，既不是完全不担心出现碰撞，但也不需要很高程度的密码学安全性。

如果 key 是用户自定义的输入的话，可能需要考虑稍微好一点点的防碰撞特性，可以考虑使用 SHA1。如果想要追求极致的性能，而不担心 hash collision 或者有额外的机制用来处理 hash collision 的话，可以考虑用 xxhash 或 murmurhash 等性能较高的非密码学 hash 算法。

当然，不同 hash 算法在不同的数据特性下表现也不同，数据内容/长短都可能会影响 hash 算法的相对快慢。特别是 kv 数据的 key 一般较短，需要对 key 常见的字符组成以及长度进行具体测试才能知道哪一个更快。大文件上跑得飞快的算法不一定在几个字节的 key 上也能打赢其他算法。（当然如果哈希计算不是瓶颈，就无所谓了，KV存储场景下估计存储才是瓶颈）

碰撞概率

关于 SHA1，以及其他几种常见的 non-cryptographic hash 算法的碰撞概率，可以参考： https://crypto.stackexchange.com/a/2600 https://softwareengineering.stackexchange.com/a/145633/414841 https://stackoverflow.com/questions/9392365/how-would-git-handle-a-sha-1-collision-on-a-blob

如果这对你的信心能有任何帮助，基本上：

对于 SHA-1 来说，只要不是天文数字数量的 key，一台服务器生命周期内出现碰撞的概率比主板或硬盘烧掉的概率还小得多得多。
git 也是使用 SHA-1 算法，并且并没有对哈希碰撞做特殊处理，因为它实在是太稀有了。
如下直观感受（https://stackoverflow.com/a/9392518/7509248）：Here’s an example to give you an idea of what it would take to get a SHA-1 collision. If all 6.5 billion humans on Earth were programming, and every second, each one was producing code that was the equivalent of the entire Linux kernel history (1 million Git objects) and pushing it into one enormous Git repository, it would take 5 years until that repository contained enough objects to have a 50% probability of a single SHA-1 object collision. A higher probability exists that every member of your programming team will be attacked and killed by wolves in unrelated incidents on the same night.

所以，其实不做专门的碰撞处理也没有太大影响。当然如果 key 是用户输入，并且哈希算法比较弱的话，可能需要考虑用户恶意攻击的可能性。

文件存储

这里假设 Linux 系统，并且假设 ext4 文件系统

这里解释为何会出现 /77/e1/77e1ba46ee3a2b2d1558d7c5d07c4c0caa46c7bf 这样的多级目录的索引方案，以及我们如何需要（或不需要）这样做。

背景知识

1.树状文件系统

ext 文件系统中（暂时忽略 ext3 加入的 htree，后面会提到），整个文件系统的结构是一颗 B Tree，每一个目录实际上也是一个特殊的文件。从根目录开始，每个目录文件的块数据，记录着该目录下直接包含（只包括直接相邻的一层，不包括子目录中间接包含的文件）的所有文件的索引信息（每一个称为一个 entry，内容包括文件名、inode号）。

2.块与块大小

文件系统上的文件的数据，并不是完全连续存储的，而是以块为单位存储。块是一个在单个文件系统内大小固定的最小空间分配单元，即即使文件只有1个字节，也需要占用至少一个块的空间来存储。而对于大文件，可以通过为该文件分配多个块，并将这些块的块编号存储在inode 中（同样，这里暂时忽略 ext4 extent tree 的细节，不影响后面讨论）。

而对于 ext4 文件系统，块的大小一般是4KiB （可自定义），即小于等于 4KiB 大小的文件就可以只用一个块来存储实际数据，而大于 4KiB 大小的文件则要用多个块。

对于线性目录结构，一个目录 entry 的大小为 4+2+2+n 字节，n=文件名长度。

3.磁盘与内存与CPU

对于文件系统来说，磁盘的访问速度在大多数情况下几乎一直是瓶颈（相比内存和 CPU 操作），一般磁盘和内存的速度差距都是很多倍的（20GB/s vs 100MB/s），延迟更是差了好几个数量级。所以对于文件系统来说，减少磁盘访问次数是很重要的优化手段。

4.每个目录块能存多少个 key？

根据背景知识2，假设我们使用 sha1 算法进行 key 哈希，并且 key 使用 hex 文本形式作为文件名，则每个文件的文件名长度为 40 字节，存到目录中，一个 entry 就需要占用 4+2+2+40=48 个字节，即一个线性目录块可以存 floor(4096/48)=85 个 key。

方案1：所有 key 文件存储在同个目录下

由背景知识1可知：（忽略 htree）在某个目录下查找某个文件，相当于要遍历这个目录的所有 entry，直到找到匹配的文件名，即 O(n) 操作，n=目录内的直接文件数。

这意味着，假如我们直接把所有的哈希 key 作为文件名，全部塞到同一个目录 foobar 下，访问的时候（最坏情况下）我们可能要遍历整个 foobar 目录的所有目录 entry 才能找到我们想要的 key。

性能

要评估这个方案的性能，根据背景知识3，我们只需要考虑整个查询操作读入了几个块，不考虑在这个块已经读入内存后CPU运算所需要的时间（因为相比读入时间来说几乎可以忽略）。

（不考虑 htree，只考虑线性目录）根据背景知识4，这个方案在 85 个 key 的时候恒定只需要读入1个目录块就可以完成查询，但是由于查询的本质是遍历目录，需要读入的目录块的数量是随着 key 的数量增加而线性增加的：当文件数量为 1000 的时候，最坏情况就已经需要读入 ceil(1000/85)=12 个块了；当文件数量为 1w，最坏需要读入 ceil(10000/85)=118 个块，可以看到文件的数量一旦多起来，性能下降得特别快。

一个粗略数据提供prespective：假设是磁盘，一次读取延迟10ms的话，118个块就已经要1秒多了。

注意注意注意：这里得出的所有结论，都是【忽略 htree 的存在】的，可以理解为 ext2 及之前文件系统的做法，不代表 ext4 的表现！请阅读下方 htree 部分。

这里提供这个方案只是为了作为分层目录方案的背景，以及性能比较的基准参考。

使用提到的，取哈希文本前两字节作为目录名创建目录，将开头两字节相同的所有 key 都放到这个目录中的方法，即 /77/77e1ba46ee3a2b2d1558d7c5d07c4c0caa46c7bf 的形式，先考虑只加一层：

根据背景知识2，计算第一层（即根目录）下的每个子目录的 entry 大小，得到每个目录 entry 需要 4+2+2+2=10 字节，则第一层目录可以存储 4096/10 = 409 个子目录，而我们取的哈希hex 文本前两字节的取值最多只有 256 个，所以第一层目录（根目录）是恒定只需要一个目录块的，查询第一层的时候不会跨多个块。

而第二层目录，由于已经在第一层里面分过一次类了，每个目录的文件数量会明显下降，假设 key 均匀分布的话（一个好的哈希算法应该尽量保证这一点，所以这个假设在现实中通常也是成立的），每个二级目录只需要存储 n/256 个 key 即可。

性能

已知查询时，第一层目录恒定会需要 1 个块的访问，同样假设 key 数量为 1w，第二层平均每个目录存储 1w/256 = 39 个 key，远远小于背景知识4中算得的一个目录块能存储 85 个 key 的上限，所以第二层的任意目录也能在一个块内完成查询，即 key 总数量即使为 1w，也只需要稳定读取 2 个块就能完成一次 key 查询。（相比方案1的 118 个块）

当然，如果 key 的数量继续增加，第二层目录也可能超过 1 个块，导致在第二级查找的时候也出现耗时的多块遍历。解决方法也很简单：加第三第四层，每次都相当于以每次访问稳定多 1 次块读取为代价，将 key 的承载能力扩大 256 倍。

一些粗略的数字，用作 rule of thumb，对于一次查询：

1 层目录，85 个 key 以内稳定 1 次块读取，超过则开始出现需要 2 次块读取的 key，170 个 key 以上则所有 key 退化为平均 3 次块读取。
2 层目录，21760 个 key 以内稳定 2 次块读取，超过则开始出现需要 3 次块读取的 key，43520 个 key 以上则所有 key 退化为平均 3 次块读取。
3 层目录，557w 个 key 以内稳定 3 次块读取，超过则开始出现需要 4 次块读取的 key，1114w 个 key 以上则所有 key 退化为平均 4 次块读取。
n 层目录，a = 85*(256^(n-1)) 个 key 以内稳定 n 次块读取，超过则开始出现需要 (n+1) 次块读取的 key，2*a 个 key 以上则所有key 退化为平均 (n+1) 次块读取。
以此类推…

本质上就是，在 n 层下，a = 85*(256^(n-1)) 个 key 以内是树查找，而超过 a = 85*(256^(n-1)) 个 key 则退化为顺序查找。根据实际场景的数量级，选择合适的层数就行了。如果需要适应宽范围的 key 数量，也可以支持不同的目录使用不同的层数，当目录过大的时候自动增加层数。当然设计上就会复杂许多。

Elephant in the Room.

ext3、ext4 的 htree？

前面我们都假设了，文件系统中的目录是 Linear Directory 线性目录，即目录下的所有文件，以一个数组的形式存储在（一个或多个）目录块下。而每一次在目录中查找文件，都需要遍历目录的（最坏情况下所有）目录块才能找到目标文件对应的 entry。

但是，文件系统的设计者们，也很早就意识到了这种方案的局限性，即在单个目录下文件过多的时候性能下降明显。

所以早在 ext3，就加入了一种新的目录类型：Hash Tree Directory 哈希树目录。原理实际上就和我们方案2做的事情几乎一模一样：对于需要访问的文件名，计算一个哈希（没错，文件系统内部其实又算了一次哈希）。根目录块中实际上存储的是一颗 htree 的根节点（以 hash 为 key 的 btree 的意思），也是同样的使用 hash 去查询第一层目录块，得到第二层的块号，如果读取第二层块，发现不是叶子块（即这个块内的结构，不是传统的线性目录，而是仍然是 htree directory）的话，就继续用 hash 查询这第二层目录块，得到第三层的块号，如此下去直到最后找到一个线性目录块，想要找的文件就在这个线性目录块中。（注意到这些块都属于同一个目录文件，而不是不同目录。该目录的所有目录块一同组成了一颗 btree）

也就是，我们的方案2实际上是 htree 在软件层面的一个复刻版本，而且很有可能是更拙劣的复刻版本。

因为多级目录下，实际上每一级目录中，”00”到”ff”这256个目录的 entry，并没有完全填满一个目录块，存在空间浪费。并且 htree 的每一段哈希段到下一级目录块的映射 entry 不需要消耗完整的一个目录文件，只是记录一个简单的 <hash, blockno> 二元组就可以了，更节约空间。（8字节 vs 10字节+一个inode块256字节）。当然，还有另一个显而易见的好处，就是 htree 是操作系统提供的功能，对用户程序完全透明，代码上只需要把所有文件都丢到同一个文件夹中就行。而且自带了前面所提到的“支持不同的目录使用不同的层数”的能力，更灵活。

htree 也有一定局限性，比如其使用的文件名 hash 算法（Legacy、半MD4、TEA）长度只有 64bit，而每一层哈希使用 32bit 作为 hash code，就限制了 btree 树高最多只能有 2 层哈希转跳，第三层必须是叶子节点（即和方案2中的三层目录方案的跳转次数相同）。

当然，htree 每一层能存储的哈希桶数量也比我们自己实现的多级目录要多，根据这个 Source，一个目录块能存储的 dx_entry （8字节长的 <hash, blockno> 二元组）的数量是 508个。即 branching factor 是 508 而不是我们自己实现的方案的 256。