V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
爱意满满的作品展示区。
roy2220
V2EX  ›  分享创造

在文件上实现 malloc 和 free

  •  
  •   roy2220 · 2020-02-15 19:45:03 +08:00 · 2678 次点击
    这是一个创建于 1725 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

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

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

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

    目前想到的方案:

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

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

    有兴趣一起讨论交流!

    6 条回复    2020-02-17 20:43:10 +08:00
    codehz
        1
    codehz  
       2020-02-16 02:13:31 +08:00 via Android
    第一个问题是错的,任何现代操作系统都提供了内存映射功能。。。
    roy2220
        2
    roy2220  
    OP
       2020-02-16 04:04:14 +08:00
    @codehz 实现上已经使用了 mmap 映射文件,但是每次内存映射的地址不确定(虽然 mmap 可以指定写死的映射地址,数据结构也就可以直接引用这个地址,因为不会变化,但是这样做太 trick ?)。还是记录文件偏移更健壮,外加使用 protobuf 做数据结构的序列化,这样大小端、内存对齐就和平台无关了
    codehz
        3
    codehz  
       2020-02-16 08:39:32 +08:00 via Android
    @roy2220 这个解释可以,只是你不能说它没这个功能((
    另外你做这个是要折腾数据库吧。
    Mithrandir
        4
    Mithrandir  
       2020-02-16 13:50:05 +08:00
    mmap + 地址重定位可解
    roy2220
        5
    roy2220  
    OP
       2020-02-16 15:25:08 +08:00 via iPhone
    @Mithrandir 现在的方案是运行时用 mmap 地址+文件偏移定位数据块
    zhuyie
        6
    zhuyie  
       2020-02-17 20:43:10 +08:00   ❤️ 2
    可以看看微软是怎么做的。微软开源了 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
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1074 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 58ms · UTC 19:01 · PVG 03:01 · LAX 11:01 · JFK 14:01
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.