OceanBase的memtable设计成key为主键，value为行操作链表的目的是什么?

来源：千锋教育

发布人：xqq

时间： 2023-10-19 03:52:21

一、OceanBase的memtable设计成key为主键，value为行操作链表的目的

这是MVCC多版本并发控制的一种实现方式，写不阻塞读，并且读可以读到一个快照版本。实现MVCC可以有多种方法，下面我解释一下几种可能的实现方法，并分析一下各方法的优劣

B+tree是索引，可以通过一行的key，索引到其value，索引还可以是其它的，比如Rocksdb和MemSQL用的是skiplist，还可以是Hashtable，还有一些新的数据结构微软Hekaton用的bw-tree，HyPer用的adaptive radix tree等。B+tree是非常合适的，对范围查询和点查询都不错，对于CPU Cache非常友好，可以做到很高的性能，至于用skiplist的数据库，看了一他们选择这个的理由，文档里基本都是说因为实现起来比较简单，B+tree实现起来太复杂了。不过OceanBase的前辈们把内存B+tree实现的非常好，可以看到实力非常强，不需要因为某些东西简单而去选择用那个东西。

下面说一下几种实现方法，主要说的是MVCC，就不说B+tree了

1. 完整数据直接存Row里，新版本在前

读的时候，有一个snapshot version，比如是7，就需要找到名列前茅个小于7的版本，v=6的那个数据

优点：如果更新不频繁，大部分查询所需的数据版本都是最新的，通过索引找到某一行，直接通过指针就可以找到所需数据。通过指针就是一次内存的随机访问，100ns，当然还有其它处理数据的开销。

缺点：更新数据的时候，需要申请一块新的内存空间存储数据，由于它需要被放链表首位置，索引就需要指向它，因此需要更新一下索引的指针，使其指向新的数据。

2. 完整数据直接存Row里，老版本在前

优点：更新的时候，直接插到链表的最后就好了，不需要再更新索引的指针

缺点：查询的时候，可能需要顺着链表找很多结点才能找到所需版本的数据，而每一次都是一次内存随机访问，需要(n*100)ns。

3. 更新数据存在Node里，然后通过Row指向Node，定期做压缩

优点：更新的时候，直接插入Row的指针指向的名列前茅个位置就好了，而且不需要像第1种方法那样更新索引。另一个优点是，由于只存储增量数据，能节省很多内存，尤其是当一个表的列数非常多的时候

缺点：查询的时候，就算是需要查询最新的版本，也可能需要遍历多个node才能得到完整的数据。不过当更新过多时，可以通过压缩，将多个更新合并成完整数据，存到一个新的node中，一定程度上缓解这个问题

4. 数据存到一块连续的内存中

前面几种方法都是，当插入一行新的数据时，申请一块内存，存数据，或者存更新node，这会导致做scan的时候比较慢。因为做scan的时候，需要通过索引中的指针才能找到数据，做scan是先对索引进行scan，再找到相应的数据，而每一次内存随机访问是100ns，也就是每秒扫描的数据量不可能超过1s/100ns=1000万

所以可以申请一块大内存，类似一个存struct的数组，然后把每一行存到这个数组里，定长数据直接存，变长数据用指针，对于小字符串，可以做一个优化，将字符串分成2部分，前面小的一部分可以直接存数据里，然后通过指针指向另一部分

至于多版本和增量数据，可以按照前面几种方法做选择

做点查询的时候，通过索引查，做scan的时候，看查询的数据情况，当数据量大时，直接scan数组是更快的，数据量小时，仍然通过索引做范围查找

优点：一些情况下，scan的性能更高

缺点：由于是原地更改row里的数据，读写的时候都需要加锁（latch），更新多的时候，对读不友好

延伸阅读：

二、网络附加存储(NAS)

NAS指Network Area Storage，即网络附加存储。它一般是将本地的存储空间共享给其他主机使用，一般通过C/S架构实现通信。它实现的是文件级别的共享，计算机通常将共享的设别识别为一个文件系统，其文件服务器会管理锁以实现并发访问。网络文件系统，以文件模块的形式进行共享，工作在应用层上，常见的NAS有NFS和CIFS(FTP)。

声明：本站稿件版权均属千锋教育所有，未经许可不得擅自转载。