老师好,这是大厂面试拆解——项目实战系列的第8篇文章。
知识地图:深入理解计算机系统---文件子系统
一次只讲清楚一个问题:
阅读本文你将获得以下收益:
"走暗路、耕瘦田、进窄门、见微光"告诉我,面试关键就在于深入理解自己的项目,这才是最考察基本功的地方。然而现实情况往往是这样的:
为什么会这样?
ext4文件系统为了支持单个文件最大16TB存储,采用哪些数据结构?可视化的逻辑结构和代码实现怎么对应的?
这里假设你熟悉了
小提示:为什么非要打破砂锅问到底(这个提示有点长)
主要内容
特性 | 线性目录(如Ext2) | Htree目录(如Ext4) |
---|---|---|
查找效率 | O(n)(需遍历所有项) | O(log n)(哈希过滤) |
适用场景 | 小规模目录(<1000项) | 大规模目录(百万级项) |
存储开销 | 低 | 较高(需额外索引块) |
扩展性 | 差 Directory scalability | 支持动态分裂与多级索引 |
举例说明:
一个目录下多个文件
[root@watchpoints icfs]# ls -ltra |sort
drwxr-xr-x 3 root root 4096 3月 24 11:31 ..(上个目录)
drwxr-xr-x 4 root root 4096 5月 8 16:02 . (当前目录)
-rw-r--r-- 1 root root 4194304 5月 2 17:40 file1
-rw-r--r-- 1 root root 4194304 5月 2 17:40 file2
-rw-r--r-- 1 root root 4194304 5月 2 17:40 file3
目录本质也是一种文件,但是这种目录文件的内容,
是其下文件或目录的inode与文件名信息。
inode1 file1inode2 file2inode3 file3
当然了,这只是示意,目录中记录的条目并非这么简单了,但也并不复杂,结构体如下:
1914 struct ext4_dir_entry_2 {
1915 __le32 inode; /* Inode number */
1916 __le16 rec_len; /* Directory entry length */
1917 __u8 name_len; /* Name length */
1918 __u8 file_type;
1919 char name[EXT4_NAME_LEN]; /* File name */
1920 };
https://www.kernel.org/doc/html/latest/filesystems/ext4/dynamic.html#directory-entries
Offset | Size | Name | Description |
---|---|---|---|
0x0 | __le32 | inode | Number of the inode that this directory entry points to. |
0x4 | __le16 | rec_len | Length of this directory entry. Must be a multiple of 4. |
0x6 | __le16 | name_len | Length of the file name. |
0x8 | char | name[EXT4_NAME_LEN] | File name. |
就是一个数组呀, |
dir_index 特性:
假设目录/docs
下有多个文件:file1.txt
、image.jpg
、report.pdf
等,
Htree的存储结构如下:
(根索引块DX-block)├── 哈希范围 [0-1000] → 指向数据块1 (DE-block)│ ├── file1.txt (哈希值: 250)│ └── image.jpg (哈希值: 800)├── 哈希范围 [1001-2000] → 指向数据块2 (DE-block)│ └── report.pdf (哈希值: 1500)└── 哈希范围 [2001-3000] → 指向下一级索引块 (DX-block) ├── 哈希范围 [2001-2500] → 指向数据块3 (DE-block) │ └── data.csv (哈希值: 2200) └── 哈希范围 [2501-3000] → 指向数据块4 (DE-block) └── backup.zip (哈希值: 2800)
关键组件:
[0-1000] → 块1
)**Htree的根 :struct dx_root
Hash Tree Directories
https://www.kernel.org/doc/html/latest/filesystems/ext4/dynamic.html#directory-entries
// Htree 根索引块结构(兼容传统目录格式)
struct dx_root {
// 伪造目录项:模拟传统目录的 "." 条目(当前目录)
struct fake_dirent dot; // 伪目录项头部(inode、rec_len等)
char dot_name[4]; // 固定存储 "."
// 伪造目录项:模拟传统目录的 ".." 条目(上级目录)
struct fake_dirent dotdot; // 伪目录项头部
char dotdot_name[4]; // 固定存储 "..",
// Htree 根索引元数据(关键控制信息)
struct dx_root_info {
__le32 reserved_zero; // 保留字段
u8 hash_version; // 哈希算法版本
u8 info_length; // 固定为 8(
u8 indirect_levels; // 索引层级:0=仅根节点,表示间接索引的层数
u8 unused_flags; // 未使用标志位(兼容性保留)
} info;
// 哈希映射入口数组(动态长度,通过 entries[0] 定义柔性数组)
struct dx_entry entries[0]; // 每个条目包含哈希范围及子块指针
};
索引项由结构体 dx_entry表示,本质上是文件名的哈希值和数据块的一个映射关系。
struct dx_entry
{
__le32 hash;
__le32 block;
};
如果我们要查找一个目录下面的文件名,可以通过名称取哈希。
通过索引树,我们可以将一个目录下面的 N 多的文件分散到很多的块里面,可以很快地进行查找
Ext4文件系统的目录索引采用两层哈希B树(Hash B-tree)结构 其本质是哈希表与B树的结合体
可以通过debugfs工具查看目录的哈希树信息
HTree 是一种专门用于目录索引的树形数据结构 ,类似于 B 树 。
它们的深度恒定为一级或两级,扇出因子较高,使用文件名的哈希值 ,并且不需要平衡 。
而是为了大目录场景专门设计的,HTree 索引用于 ext3 和 ext4 Linux 文件系统 ,并于 2.5.40 左右被合并到 Linux 内核中。
特性 | Htree(Ext4目录) | B/B+树(如MySQL索引) |
---|---|---|
索引键 | 文件名哈希值(非有序) | 主键或索引字段值(有序) |
存储粒度 | 目录项块(如4KB) | 数据页或磁盘块(如16KB) |
查询类型 | 精确匹配(等值查询) | 范围查询、排序、最左前缀匹配 |
结构扩展 | 哈希冲突时分裂数据块 | 节点填充度不足时分裂或合并 |
HTree 与 B-tree/B⁺-tree 的比较
特性 | HTree | B-tree / B⁺-tree |
---|---|---|
树高 | 常数(1 ~ 2 层) | 随数据量增加而增加 |
扇出 | 高(数千) | 较低(几十到数百,取决于节点大小) |
平衡 | 无需平衡 | 需分裂/合并以保持平衡 |
键排序 | 按哈希范围分布,不保证时序 | 保证键的有序存储 |
冲突处理 | 溢出块或二级索引 | 不存在哈希冲突(键唯一排序) |
查找复杂度 | O(1)~O(深度) ≈ O(1) | O(logₙ N) |
元数据开销 | 较小(只存哈希与指针) | 较大(存键-值对或指针、维持平衡信息) |
演示如下:
上图展现了一个简单的两级 HTree 结构示例:
[0–1000] → Leaf Node 1
,[1001–2000] → Leaf Node 2
。查找时,先对文件名计算哈希值,落在某个范围内就跟随指针进入相应叶子节点。HTree 关键点:
By default in ext3, directory entries are still stored in a linked list, which is very inefficient for directories with large numbers of entries.
The di-rectory indexing feature addresses this scalability issue by storing directory entries in a constant depth HTree data structure, which is a specialized BTree-like struc-ture using 32-bit hashes
Htree是持久存储于目录的数据块中,用来维护目录项布局的一种持久化数据结构。针对Htree有以下操作:
别人咀嚼过的内容,可能过时内容不是ext4的
https://github.com/torvalds/linux/blob/master/fs/ext4/ext4.h#L771
struct ext4_inode
__le32 i_block[EXT4_N_BLOCKS];/* Pointers to blocks */
ext3 文件系统使用间接块映射方案,提供从逻辑块到磁盘块的一对一映射。
这种方案对于稀疏或小文件非常有效,但对于较大文件的开销很高 现在你应该能够意识到,这里面有一个非常显著的问题,
对于大文件来讲,我们要多次读取硬盘才能找到相应的块,这样访问速度就会比较慢。
ext4_extent 就像是一张"纸条",用来记录文件里一段连续数据在硬盘上的位置和长度,比 Ext3 记"每一块"的方式要高效得多.
https://github.com/torvalds/linux/blob/master/fs/ext4/ext4.h
/*
* Structure of an inode on the disk
*/
struct ext4_inode {
__le32 i_block[EXT4_N_BLOCKS];/* Pointers to blocks */
}
An extent tree is a data structure that maintains the extents associated with an inode.
The extent tree helps in faster traversal and retrieval of data
The `i_block` field stores structures such as `struct ext4_extent_header`,
`struct ext4_extent_idx`, and
`struct ext4_extent`,
which are integral components of the extent tree.
Each of these structures have a size of 12 bytes
# 查看 inode 的 extent 树
debugfs /dev/sda1
debugfs: stat <inode号>
# 输出示例:
extent_header (eh_depth=2, eh_entries=3)
extent_idx 0: logical 0..1000 → physical 8192
extent_idx 1: logical 1001..2000 → physical 12288
...
在 ext4 文件系统中,
__le32 i_block[EXT4_N_BLOCKS]
数组通过 B+树结构 实现 extent(区段)关系
https://github.com/openwrt/make_ext4fs/blob/master/ext4_extents.h
struct ext4_extent_header {
__le16 eh_magic; // 魔数(标识有效性,固定为 0xF30A)
__le16 eh_entries; // 当前节点包含的 extent 或索引项数量
__le16 eh_max; // 节点最大容量(可存储的项数)
__le16 eh_depth; // 树深度(0 表示叶子节点,>0 表示索引节点)
__le32 eh_generation; // 树版本(用于校验)
};
eh_depth=0:直接指向叶子节点(即文件数据块映射)
eh_depth>0:指向中间索引节点,需递归遍历
i_block[3]~i_block[15]
共 12 个元素(每个 4 字节)动态存储两类数据:
ext4_extent
结构):描述文件逻辑块到物理块的连续映射struct ext4_extent {
__le32 ee_block; // 起始逻辑块号
__le16 ee_len; // 连续物理块数量(最大 32768)
__le16 ee_start_hi; // 物理块号高 16 位
__le32 ee_start_lo; // 物理块号低 32 位
};
struct ext4_extent_idx {
__le32 ei_block; // 当前索引覆盖的最大逻辑块号
__le32 ei_leaf_lo; // 下一层节点物理块号低 32 位
__le16 ei_leaf_hi; // 下一层节点物理块号高 16 位
};
ext4_extent_idx
结构):指向下一层 B+树节点 struct ext4_extent_idx {
__le32 ei_block; // 当前索引覆盖的最大逻辑块号
__le32 ei_leaf_lo; // 下一层节点物理块号低 32 位
__le16 ei_leaf_hi; // 下一层节点物理块号高 16 位
};
请问:这个图片隐藏什么内容,数组 怎么存储一个tree结果呢?
如果文件不大,inode 里面的 i_block 中,可以放得下一个 ext4_extent_header 和 4 项 ext4_extent。所以这个时候,eh_depth 为 0,也即 inode 里面的就是叶子节点,树高度为 0。
┌─────────────────────── inode 的 i_block[15] 数组 ───────────────────────┐
│ │
│ ext4_extent_header (eh_depth=0) │
│ ├── eh_magic: 0xF30A │
│ ├── eh_entries: 4 (有效 extent 数量) │
│ └── eh_max: 4 (最大容量) │
│ │
│ ext4_extent 1 │
│ ├── ee_block: 0 → 逻辑块起始号 │
│ └── ee_start_lo: 4096 → 物理块起始号 │
│ │
│ ext4_extent 2 │
│ ext4_extent 3 │
│ ext4_extent 4 │
└───────────────────────────────────────────────────────────────────────────┘
如果文件比较大,4 个 extent 放不下,就要分裂成为一棵树,eh_depth>0 的节点就是索引节点,其中根节点深度最大,在 inode 中。最底层 eh_depth=0 的是叶子节点
┌───────────────┐
│ inode 的 │
│ i_block 数组 │
├───────────────┤
│ 根节点 │
│ (eh_depth=2) │
└──────┬────────┘
│
┌──────────────────┼───────────────────┐
▼ ▼ ▼
┌─────────────┐ ┌─────────────┐ ┌─────────────┐
│ 索引节点块 │ │ 索引节点块 │ │ 索引节点块 │
│ (eh_depth=1) │ │ (eh_depth=1) │ │ (eh_depth=1) │
└──────┬──────┘ └──────┬──────┘ └──────┬──────┘
│ │ │
┌───────────┘ └───────────────┐ └───────────┐
▼ ▼ ▼
┌─────────────┐ ┌─────────────┐ ┌─────────────┐
│ 叶子节点块 │ │ 叶子节点块 │ │ 叶子节点块 │
│ (eh_depth=0) │ │ (eh_depth=0) │ │ (eh_depth=0) │
└──────┬───────┘ └──────┬───────┘ └──────┬───────┘
▼ ▼ ▼
┌─────────────┐ ┌─────────────┐ ┌─────────────┐
│ 数据块 │ │ 数据块 │ │ 数据块 │
│ (物理块) │ │ (物理块) │ │ (物理块) │
└─────────────┘ └─────────────┘ └─────────────┘
i_block
数组的两种模式请一定看 https://docs.kernel.org/6.0/filesystems/ext4/dynamic.html#the-contents-of-inode-i-block
inode.i_block
can be used in different ways.
在 ext4 中,i_block
数组(定义于 struct ext4_inode
)有两种使用模式,由 i_flags
中的 EXT4_EXTENTS_FL
标志位决定:
i_block[0-11]
直接存储数据块号,i_block[12-14]
指向间接块(一级、二级、三级)i_block
存储 B+树的根节点,包含 ext4_extent_header
和多个 ext4_extent
或 ext4_extent_idx
项EXT4_EXTENTS_FL
标志(通过 ext4_set_inode_flag()
函数最开始,ext4 extent B+树是空的
好的,现在我们把这个ext4_extent插入到ext4 extent B+树,如下所示:
好的,现在当然需要3个ext4_extent保存这3段逻辑块地址与物理块地址的映射关系,并插入到ext4 extent B+树,全插入后如下所示:
上来 先别直接分析io过程过程 ,假如io高楼大厦的话,那么 第一次地基是什么
dd if=/dev/zero of=/root/c++/test bs=1M count=16
blktrace -d /dev/loop0 -o - |blkparse -i -
对比:
阶段 | ext4 (HTree) | CephFS (MDS + dirfrags) |
---|---|---|
父目录 inode 获取 | dcache → page cache → 磁盘读取 | 本地 capability 缓存,必要时向 MDS 发起 lookup |
文件布局定位 | extent tree → dx_root → 磁盘物理块 | MDS journaling → RADOS metadata pool → 客户端缓存 inode 布局 |
目录项查找 | HTree hash 遍历 → dirent | 目录碎片化 → RADOS 对象直接读取 → 在片段中查找 dentry |
从上述对比可见,ext4 完全在单机层面依赖页缓存和 HTree,
而 CephFS 则在集群环境下通过 MDS 分发元数据与目录碎片化设计, 实现了面向大规模并发和海量条目的可扩展目录查找【大规模 通过添加机器实现,在单个数据结构设计不合理,还是常规map set实现】
. 客户端如何"知道"数据在哪 3.1 客户端侧计算
扫码关注腾讯云开发者
领取腾讯云代金券
Copyright © 2013 - 2025 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号:粤B2-20090059 深公网安备号 44030502008569
腾讯云计算(北京)有限责任公司 京ICP证150476号 | 京ICP备11018762号 | 京公网安备号11010802020287
Copyright © 2013 - 2025 Tencent Cloud.
All Rights Reserved. 腾讯云 版权所有