不是面试题：存储系统设计

本帖最后由 xunen 于 2010-08-18 17:31 编辑

一个存储系统将每个文件存储成一系列的数据块（数据块总数不超过10w），除了最后一个，
所有的数据块都是同样大小的。比如在目录 /var/lib/chunk 存储这些块，如下： 存储的文件以 blk_%fid_%bid 命名。但目录中的块数增加到一定规模时，该存储系统
将建一个子目录，用于保存新的数据块。目录中的块数达到64时，就新建一个子目录。
这种安排主要使每个目录中的文件数量可控。

该存储系统对外提供数据块存储、下载、删除等服务。

请用 C 语言 设计该存储系统的数据结构，以支持下列操作：
1）、根据fid、bid查找指定数据块的路径（比如 /subdir5/subdir9/blk_988_25，其中
fid = 988，bid = 25），以便存储系统提供数据块下载服务。
2）、根据fid、bid，删除指定的数据块。
3）、根据fid，删除所有指定 fid 的数据块。
4）、在满足目录限制的情况下，找到一个可用数据块存放位置，以便存储系统
提供数据块存储服务。
5）、返回该存储系统中的数据块总数以及所占空间。

限制条件;
内存： 2G
不能使用额外的磁盘空间。

如果考录并发呢？

回复 xunen


    有点像linux页高速缓存里的基树，看看“linux内核详解”600页，也许有所帮助。我不是行家。