V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
zxCoder
V2EX  ›  数据库

像 InnoDB 这种底层存储结构,在代码层面是如何实现的呢

  •  
  •   zxCoder · 2021-01-05 14:05:46 +08:00 · 3385 次点击
    这是一个创建于 1178 天前的主题,其中的信息可能已经有所发展或是发生改变。

    比如很多书上以及文档都会讲这个存储引擎的存储结构,比如记录的结构,页的结构,那么这些东西映射到代码层面是怎么实现的呢?

    比如一个页,里面有很多个记录,对应到内存和硬盘里,是一堆字节,那我们的程序代码要处理的时候,是需要讲这块的内容读到内存,然后类似反序列化转化为我们代码中的一些结构体比如 Page,Record 对吗?然后操作的逻辑就是对这些对象操作,最后再序列化刷回磁盘这样子吗?

    按书上的做法,页面的 UserRecords 里的记录删除后只是会先打一个标记,那么为什么不这样做,比如这个页面的记录在我们代码中体现的就是一个 LinkList,我们可以直接删掉要删掉的记录,再序列化写回磁盘里。

    这块想不太清楚,希望各位大佬指点一下。

    第 1 条附言  ·  2021-01-05 18:44:14 +08:00
    可能我序列化的表达有的问题,我想说的是比如有一些标志位用一个 bit 来表达嘛,那代码里是否可以用一个 bool 来代替,然后当需要写入的时候再判断,比如某一个字段 15 个 bit,代码里是否能用一个 short 来代替,当需要写入的时候再把这个 short 的 15 个 bit 写入,

    还是说只是用 byte 数组代替整个结构,然后直接操作每一位,比如我要读取 15bits 这个字段,我再去计算得到一个值?
    25 条回复    2021-01-06 17:24:41 +08:00
    wps353
        1
    wps353  
       2021-01-05 14:39:16 +08:00   ❤️ 2
    1 、因为数据库本身是一个很复杂的东西。要考虑很多层面上的东西,比如事务隔离级别,MVCC,锁等等相关的情况。暴露外面的接口看上去都是 CRUD 的简单接口,但事实上内部实现极其复杂,要考虑很多东西。
    2 、「按书上的做法,页面的 UserRecords 里的记录删除后只是会先打一个标记,那么为什么不这样做,比如这个页面的记录在我们代码中体现的就是一个 LinkList,我们可以直接删掉要删掉的记录,再序列化写回磁盘里。」这里为什么不能直接删除了?打个比方,在 RR 隔离级别下,事务 A select id=1,事务 B 然后 delete=1,commit;然后事务 A 在 select id=1,你会发现事务 B 的删除根本对事务 A 没什么影响。所以这里要考虑数据在不同的隔离级别的可见性。
    dynastysea
        2
    dynastysea  
       2021-01-05 14:41:08 +08:00
    没有什么序列化的操作,都是直接修改内存,然后 buf 更新到磁盘
    la2la
        3
    la2la  
       2021-01-05 14:45:36 +08:00
    实现太复杂了,可以翻翻 MySQL 的源码。
    zxCoder
        4
    zxCoder  
    OP
       2021-01-05 14:47:14 +08:00
    @dynastysea 啊 这么硬核的吗
    dynastysea
        5
    dynastysea  
       2021-01-05 14:52:16 +08:00
    @zxCoder 一点也不硬核,可能你不是 C 程序员
    zxCoder
        6
    zxCoder  
    OP
       2021-01-05 14:54:10 +08:00
    @dynastysea 能举个例子吗 “直接修改内存”, 我修改数组某个值也算修改是直接修改内存吗
    dynastysea
        7
    dynastysea  
       2021-01-05 15:01:25 +08:00
    @zxCoder 就是这个意思,比如你说的 Page 结构体,你改了其中一个字段,它是内存的一个 buf,然后调用 write(fd, buf,len)更新到文件即可。
    zxCoder
        8
    zxCoder  
    OP
       2021-01-05 15:08:56 +08:00
    @dynastysea 可能我序列化的表达有的问题,我想说的是比如有一些标志位用一个 bit 来表达嘛,那代码里是否可以用一个 bool 来代替,然后当需要写入的时候再判断,比如某一个字段 15 个 bit,代码里是否能用一个 short 来代替,当需要写入的时候再把这个 short 的 15 个 bit 写入,

    还是说只是用 byte 数组代替整个结构,然后直接操作每一位,比如我要读取 15bits 这个字段,我再去计算得到一个值?
    newlife
        9
    newlife  
       2021-01-05 16:23:53 +08:00
    可以看下 boltdb,项目很小,几千行把, 这个是 go 写的单文件的 k-v 数据库, 索引也用的 b+树。看完了你就可以回答你提出的问题了
    zxCoder
        10
    zxCoder  
    OP
       2021-01-05 16:33:44 +08:00
    @newlife 啊这
    zxCoder
        11
    zxCoder  
    OP
       2021-01-05 16:35:38 +08:00
    @newlife 我觉得还是先弄懂我的问题吧 这项目看起来跟我想的差的有点多,至少我看不太懂 page.go 里写的啥
    extreme
        12
    extreme  
       2021-01-05 19:29:31 +08:00
    如何实现,看你需求
    例如你有 32 个 bool 值
    假如你想省储存空间,当然可以用 bitmap,例如你用一个 int32 就能储存这 32 个 bool 值
    当然你也可以直接选择使用 32 个 int8 去表示,操作起来方便,但是耗空间

    如果要你储存十亿个 IPv4 地址,你打算咋存呢?
    直接存 int32 你需要接近 4GB 储存空间,用 bitmap 只需要 120MB
    neoblackcap
        13
    neoblackcap  
       2021-01-05 20:03:35 +08:00
    内存跟数据结构没有什么关系
    当然你粗略地理解存储引擎在处理数据的时候是会序列化与反序列,这并没有什么问题。
    像 C 那样能直接操作内存的语言,字节就是数据结构,取决你如何“解释”而已
    xiangbohua
        14
    xiangbohua  
       2021-01-05 20:04:41 +08:00
    我感觉的吧,不考虑事务这些复杂的功能的话,其实 InnoDB 这种数据库引擎做的事情,也就是通过合理的算法将需要写入的数据写入合适的硬盘块。
    Mohanson
        15
    Mohanson  
       2021-01-05 20:10:18 +08:00
    500 lines 有个叫 dbdb 的项目, 用的 btree + 单文件, 入门推荐

    http://www.aosabook.org/en/500L/dbdb-dog-bed-database.html
    zxCoder
        16
    zxCoder  
    OP
       2021-01-05 21:35:31 +08:00
    @extreme

    比如我看 innodb 一个 page 里有多个记录,通过一个“下一个记录相对偏移量”,将所有记录连成一个单链表,

    那比如我用 c 语言现在读取这个 page,也就是对应了一个字节数组对吧,比如我现在要遍历这个 page 查找某个记录,就是直接这样 bytes[i]到 bytes[i+next1]到 bytes[i+next1+next2]这样直接去操作对吧,比如遍历到 bytes[x],然后因为这个列是 32 位整数,就需要往后读 4 个字节到 bytes[x+3],然后转成一个整数,和我要查询的值比较判断。

    也就是从始至终我都是直接在这个字节数组里操作的对吗

    脑子有点乱表达有点乱,希望得到解答 orz
    extreme
        17
    extreme  
       2021-01-05 23:28:28 +08:00
    对的,把数据从硬盘读取到内存当中,有一个指针存了那份内存的起始地址。
    那个指针在 C 语言里面一般是个“uint8 *”类型的指针,可以当作一个 uint8 数组来操作,也就是你 Java 里面的“字节数组”。
    后面要读写那份在内存里面的数据,就通过 uint8 的指针去操作。

    至于你说的往后读 4 个字节,转成一个整数,其实转换的只是类型,直接用一个 int32 类型的指针指向那个内存地址,就可以读出一个整数了,例如 bytes[x]是你说的一个 32 位的整数,假设它是无符号的,直接*(unit32 *) (bytes + x)就能把这个 uint32 读取出来,转的只是指针的类型,而不是值:
    uint8_t *bytes = ...; // 指向“页”所在的内存地址
    uint32_t x = ...; // 你那个 32 位整数的在这个页里面的偏移量
    uint32_t *uint32_pointer = (uint32_t *) (bytes + x);
    printf("%d\n", *uint32_pointer); // 输出那个整数的值

    *uint32_pointer = 0x0A0B0C0D; // 更改整数的值
    printf("%x, %x, %x, %x\n", bytes[x + 0], bytes[x + 1], bytes[x + 2], bytes[x + 3]); // 输出 d, c, b, a
    extreme
        18
    extreme  
       2021-01-05 23:44:38 +08:00
    @zxCoder 具体如何读写其内存中的数据,还得看那种类型的具体实现。
    例如说 NULL 值其实 InnoDB 是通过 bitmap 储存的,就通过指针读取那一行用来记录 NULL 列的 bitmap,通过位运算进行 NULL 值的读写
    反正,都是通过指针,在内存中对数据进行读写,也就是你所说的“在字节数组里操作”,涉及的只有指针类型的转换,一般不会发生值的转换
    carlclone
        20
    carlclone  
       2021-01-06 01:15:02 +08:00 via Android
    @wps353 不直接删除是为了减少碎片,后面重用,而不是什么事务隔离级别的问题,内存里也有这种策略,分页
    extreme
        21
    extreme  
       2021-01-06 02:11:57 +08:00
    @carlclone
    https://dev.mysql.com/doc/refman/5.6/en/innodb-purge-configuration.html

    InnoDB does not physically remove a row from the database immediately when you delete it with an SQL statement. A row and its index records are only physically removed when InnoDB discards the undo log record written for the deletion. This removal operation, which only occurs after the row is no longer required for multi-version concurrency control (MVCC) or rollback, is called a purge.

    需要翻译成中文给你吗
    carlclone
        22
    carlclone  
       2021-01-06 07:05:57 +08:00 via Android
    @extreme 一条记录是怎么被 physically remove 的? 在 record 的 delete mask 上标记删除然后放入 free list 不是吗?事务这里根本都还没对 record 进行标记删除
    zxCoder
        23
    zxCoder  
    OP
       2021-01-06 08:56:22 +08:00
    @extreme 多谢多谢 这个指针的转换看懂了
    extreme
        24
    extreme  
       2021-01-06 17:09:52 +08:00
    @carlclone 那为什么事务这里还没删除呢?那一段英文需要翻译成中文给你吗?
    xxxyh
        25
    xxxyh  
       2021-01-06 17:24:41 +08:00
    @extreme @carlclone
    我认为你俩说的都没错,只是维度不一样.
    1.一个事务删除一条记录的时候实际上是没有立即删除的,只是记录了 undolog,因为考虑到 mvcc 还有其他事务要读,这里的删除指的是内存里的删除。
    2.删除的时候只标记为删除,后续复用的理解也是没问题的,这里的删除指的是从磁盘删除。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   965 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 21:16 · PVG 05:16 · LAX 14:16 · JFK 17:16
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.