LMDB技术原理总结

2022-04-15 00:00:00 索引 数据 文件 事务 内存
  • Linux内存布局
    • 低址到高址分别是Text segment（代码段），数据段（已初始化的全局，静态变量），BSS段（未初始化的全局，静态变量），堆，内存映射区以及栈。
    • 内存分配的两种方式：
      • brk
        • brk是将数据段(.data)的高地址指针_edata往高地址推。
        • malloc小于128k的内存，使用brk分配内存。
        • brk分配的内存需要等到高地址内存释放以后才能释放。
      • mmap
        • mmap是在进程的虚拟地址空间中（堆和栈中间，称为文件映射区域的地方）找一块空闲的虚拟内存。
        • malloc大于128k的内存，使用mmap分配内存。
        • mmap分配的内存可以单独释放。
    • 这两种方式分配的都是虚拟内存，没有分配物理内存。在次访问已分配的虚拟地址空间的时候，发生缺页中断，操作系统负责分配物理内存，然后建立虚拟内存和物理内存之间的映射关系。


  • LMDB（Lightning Memory-Mapped Database）是一个小型数据库，具有一些强大的功能：
    • 有序映射接口（键始终排序，支持范围查找）
    • 带有MVCC（多版本并发控制）的完全事务性，完全ACID（原子性，一致性，隔离性，耐久性）语义。
    • 读者/写者事务：读者不会阻止写者，写者也不会阻止读者。
      • 写入程序已完全序列化，因此写入始终无死锁。
    • 读事务非常低开销，可以不使用malloc或任何其他阻塞调用来执行。
    • 支持多线程和多进程并发，环境可以由同一主机上的多个进程打开。
    • 可以创建多个子数据库，其中事务覆盖所有子数据库。
    • 内存映射，允许零拷贝查找和迭代。
    • 免维护，无需外部过程或后台清理/压缩。
    • 防崩溃，无需日志或崩溃恢复过程。
    • 没有应用程序级缓存。
      • LMDB充分利用了操作系统的缓冲区高速缓存。
    • 32KB的目标代码和C的6KLOC。

  • LMDB的基本结构


  • 内存映射（Memory Map）
    • 内存映射就是把物理内存映射到进程的地址空间之内，这些应用程序就可以直接使用输入输出的地址空间。
      • 使用内存映射文件处理存储于磁盘上的文件时，将不需要由应用程序对文件执行I/O操作，这意味着在对文件进行处理时将不必再为文件申请并分配缓存，所有的文件缓存操作均由系统直接管理，由于取消了将文件数据加载到内存、数据从内存到文件的回写以及释放内存块等步骤，使得内存映射文件在处理大数据量的文件时能起到相当重要的作用。

    • 一般文件的io过程（两次数据拷贝）
  1. 首先调用read()（系统调用）先将文件内容从硬盘拷贝到内核空间的一个缓冲区（一次数据拷贝）。
  2. 然后再将这些数据拷贝到用户空间。（一次数据拷贝）
  • 内存映射的文件io过程（一次数据拷贝）
    1. 调用mmap()（系统调用）分配逻辑地址。
    2. 逻辑地址转换成物理地址。
    3. 进程次访问ptr指向的内存地址，发生缺页中断。由中断处理函数将数据拷贝到相应的内存地址上。（一次数据拷贝）
    4. 虚拟地址置换。
      • lmdb使用mmap文件映射,不管这个文件存储实在内存上还是在持久存储上。
        • lmdb的所有读取操作都是通过mmap将要访问的文件只读的映射到虚拟内存中，直接访问相应的地址。
        • 因为使用了read-only的mmap，同样避免了程序错误将存储结构写坏的风险。
        • 写操作，则是通过write系统调用进行的，这主要是为了利用操作系统的文件系统一致性，避免在被访问的地址上进行同步。
        • lmdb把整个虚拟存储组织成B+Tree存储,索引和值读存储在B+Tree的页面上（聚集索引）。
        • LMDB中使用append-only B+树，其更新操作终都会转换为B+树的物理存储的append操作，文件不支持内部的修改，只支持append。
          • append增加了存储开销，因为旧的数据依然存在。带来一个额外的好处就是，旧的链路依然存在，依然可以正常的访问，例如过去有个人持有了过去的root（root9）的指针，那么过去的整棵树都完整的存在。
    • COW(Copy-on-write)写时复制
      • 如果有多个调用者（callers）同时要求相同资源（如内存或磁盘上的数据存储），他们会共同获取相同的指针指向相同的资源，直到某个调用者试图修改资源的内容时，系统才会真正复制一份专用副本（private copy）给该调用者，而其他调用者所见到的初的资源仍然保持不变。
      • 因此多个调用者只是读取操作时可以共享同一份资源。
      • 优点
        • 如果调用者没有修改该资源，就不会有副本（private copy）被创建。

    • 当前读
      • 读取的是记录的新版本，读取时还要保证其他并发事务不能修改当前记录，会对读取的记录进行加锁。
        • 例如select lock in share mode(共享锁), select for update ; update, insert ,delete(排他锁)这些操作都是一种当前读
    • 快照读
      • 快照读的实现是基于多版本并发控制，即MVCC，避免了加锁操作，降低了开销。
    • MVCC(Multiversion concurrency control )多版并发本控制
      • 当MVCC数据库需要更新数据项时，它不会用新数据覆盖旧数据，而是将旧数据标记为已过时并在其他位置添加新版本。
        • 因此存储了多个版本，但只有一个是新版本。
      • MVCC通过保存数据的历史版本，根据比较版本号来处理数据的是否显示，从而达到读取数据的时候不需要加锁就可以保证事务隔离性的效果。
      • 数据库系统维护当前活跃的事务ID列表m_ids，其中小值up_limit_id和大值low_limit_id，被访问的事务ID：trx_id。
        • 如果trx_id< up_limit_id，说明trx_id对应的事务在生成可读视图前已经被提交了，可以被当前事务访问
        • 如果trx_id> low_limit_id，说明事务trx_id生成可读视图后才生成的，所以不可以被当前事务访问到。
        • 如果up_limit_id <=trx_id<= low_limit_id，判断trx_id是否在m_ids中，若在，则说明trix_id在生成可读视图时还处于活跃，不可以被访问到；弱国不在m_ids中，说明在生成可读视图时该事务已经被提交了，故可以被访问到。

    • MVCC/COW在LMDB中的实现
      • LMDB对MVCC加了一个限制，即只允许一个写线程存在，从根源上避免了写写冲突，当然代价就是写入的并发性能下降。
        • 因为只有一个写线程，所以不会不需要wait日志、读写依赖队列、锁队列等一系列控制并发、事务回滚、数据恢复的基础工具。
      • MVCC的基础就是COW，对于不同的用户来说，若其在整个操作过程中不进行任何的数据改变，其就使用同一份数据即可。若需要进行改变，比如增加、删除、修改等，就需要在私有数据版本上进行，修改完成提交之后才给其他事务可见。
    • LMDB的事务实现
      • Atom（A）原子性：LMDB中通过txn数据结构和cursor数据结构的控制，通过将脏页列表放入 dirtylist中，当txn进行提交时再一次性统一刷新到磁盘中或者abort时都不提交保证事务要不全成功、要不全失败。对于长事务，若页面spill到磁盘，因为COW技术，这些页面未与整棵B-Tree的rootpage产生关联，因此后续的事务还是不能访问到这些页面，同样保证了事务的原子性。
      • Consistency(C)一致性： 有如上的操作,保证其数据就是一致的，不存在因为多线程同时写数据导致数据产生错误的情况。
      • Isolation（I）隔离性：事务隔离通过锁控制（MUTEX），LMDB支持的锁互斥是进程级别/线程级别，支持的隔离方式为锁表支持，读读之间不锁，写等待读完成之后开始，读等待写完成后开始。
      • Duration（D）持久性：，没有使用WAL、undo/redo log等技术来保证系统崩溃时数据库的可用性，其保证数据持续可用的技术是COW技术和只有一线程写技术。
        • 假如LMDB或者系统崩溃时，只有读操作，那么数据本来就没有发生变化，因此数据将不可能遭到破坏。假如崩溃时，有一个线程在进行写操作，则只需要判断后的页面号与成功提交到数据库中的页面号是否一致，若不一致则说明写操作没有完成，则后一个事务写失败，数据在后一个成功的页面前的是正确的，后续的属于崩溃事务的，不能用，这样就保证了数据只要序列化到磁盘则一定可用，要不其就是还没有遵循ACI原则序列化到磁盘。

    • 聚集索引和辅助索引
      • 聚集索引
        • 指索引项的排序方式和表中数据记录排序方式一致的索引，每张表只能有一个聚集索引，聚集索引的叶子节点存储了整个行数据。
          • 如果一个主键被定义了，那么这个主键就是作为聚集索引。
          • 如果没有主键被定义，那么该表的个非空索引被作为聚集索引。
          • 如果没有主键也没有合适的索引，那么innodb内部会生成一个隐藏的主键作为聚集索引，这个隐藏的主键是一个6个字节的列，该列的值会随着数据的插入自增。
        • 由于实际的数据页只能按照一颗B+树进行排序，因此每张表只能有一个聚集索引。
      • 辅助索引
        • 一个表中的所有索引除了聚集索引，其他的都是二级（辅助）索引（secondary index）。
        • 辅助索引，其叶子节点并不包含行记录的全部数据，叶子结点除了包含键值以外，每个叶子结点中的索引行还包含了一个书签，该书签用来告诉存储引擎可以在哪找到相应的数据行，由于innodb引擎表是索引组织表，因此innodb存储引擎的辅助索引的书签就是相应行数据的聚集索引键，
    • 示例代码
    import lmdb
# map_size定义大储存容量，单位是kb，以下定义1TB容量
env = lmdb.open("./train", map_size=1099511627776)

# 参数write设置为True才可以写入
txn = env.begin(write=True) # 开启事务

# 通过cursor()遍历所有数据和键值
for key, value in txn.cursor():
        print (key, value)

# 添加数据和键值
txn.put(key = '1', value = 'aaa')
txn.put(key = '2', value = 'bbb')
txn.put(key = '3', value = 'ccc')

# 通过键值删除数据
txn.delete(key = '1')

# 修改数据
txn.put(key = '3', value = 'ddd')

# 通过commit()函数提交更改
txn.commit()                        # 提交事务

env.close()         # 关闭事务

    相关文章