在文件上实现 malloc 和 free

[roy2220]

有时候需要在文件上构建一颗 B 树、一张巨大的哈希表（动态数据结构）

面临的第一个问题：在文件上还能存数据结构的内存指针吗？——不能，只能存文件偏移代替

第二个问题：怎么对文件的存储空间进行管理？

构建 B 树、哈希表要为数据结构申请存储空间（文件偏移），删除数据会释放存储空间（文件偏移），已释放的存储空间能被重新利用吗？会不会有碎片化的问题？

看起来都指向了这个答案：在文件上实现 malloc 和 free

目前想到的方案：

• 大块存储空间使用 buddy 分配算法、小块存储空间使用 freelist （改良变种）管理
• “内存”管理的元数据和普通数据一起持久化到文件
• 使用 mmap 映射文件方便读写，使用 truncate 伸缩文件

初步做了一个 naive 的实现（使用 go ）： https://github.com/roy2220/fsm

有兴趣一起讨论交流！

[codehz]

第一个问题是错的，任何现代操作系统都提供了内存映射功能。。。

[roy2220]

@codehz 实现上已经使用了 mmap 映射文件，但是每次内存映射的地址不确定（虽然 mmap 可以指定写死的映射地址，数据结构也就可以直接引用这个地址，因为不会变化，但是这样做太 trick ？）。还是记录文件偏移更健壮，外加使用 protobuf 做数据结构的序列化，这样大小端、内存对齐就和平台无关了

[codehz]

@roy2220 这个解释可以，只是你不能说它没这个功能（（
另外你做这个是要折腾数据库吧。

[Mithrandir]

mmap + 地址重定位可解

[roy2220]

@Mithrandir 现在的方案是运行时用 mmap 地址+文件偏移定位数据块

[zhuyie]

可以看看微软是怎么做的。微软开源了 Outlook 所用的 PST 文件格式，它由底至上抽象了 3 个层：
1. NDB Level: Node database, basic storage
2. LTP Level: Heap, BTree, Property bags, Tables
3. Messaging Level: Folders, Messages, Attachments

https://docs.microsoft.com/en-us/openspecs/office_file_formats/ms-pst/141923d5-15ab-4ef1-a524-6dce75aae546