索引管理器(IM)

引言

IM基于DM(和TBM基于VM不同), 维护了索引的结构. 目前为止, NYADB中只有B+树这一种索引结构. 关于B+树本身的算法, 就不多做赘述了.

本小节重点要描述的是, 1)IM中的B+树为TBM提供了怎么样的接口, 2) B+树上并发控制协议.

B+树接口: 只增加, 不删除

IM中的B+只提供了两个接口! 分别是:

  1. void I(key, value) : 将key和value作为键值对插入到树中;
  2. value S(key) : 根据key, 在树中查找对应的value. 通常, key为记录的某个字段, value为该记录的VM地址, 也就是VM返回的此记录的句柄.

你或许会非常惊讶为什么没有Delete的接口, 下面解释原因, 和VM有关.

如果用户想要删除某条记录X, 那么实际的执行过程大致是:

  1. TBM解析语句;
  2. TBM利用IM, 查询到X的地址;
  3. TBM调用VM, 将X删除;
  4. VM将X对该事务可见的那个版本的XMAX设置为该事务的XID;
  5. 删除结束.

上述过程并没有要求从IM中删除X对应的索引, 假如T1删除X之后, 又有T5事务, 尝试读取X, 那会怎样呢? 过程大致如下:

  1. TBM解析语句;
  2. TBM利用IM, 查询到X的地址;
  3. TBM利用VM读取X;
  4. 由于X已经被删除, VM将找不到合适的版本, 于是返回nil;
  5. TBM接受到nil, 当做该条记录不存在, 返回给用户这个结果.

可见, 由于VM的存在, 使得IM不用删除这些索引也没关系.

但是如果IM一直不删除这些索引的话, 索引树又会变得极其的庞大, 占用资源, 也降低NYADB效率. 所以, 在必要的时候, 可以让IM对索引树进行整理.

B+树并发控制协议

本小节描述B+树上的并发控制协议, 并证明该协议是无死锁的.

我们用u来表示B+树上的某个节点, 用s(u)来表示它右边的那个兄弟节点. 每个节点都有一个读写锁, 并规定, 在对u做任意读取之前, 都必须要调用u.RLock(), 在对u做任意修改之前, 都必须要调用u.WLock(). 且u.Leaf()能够返回该节点是否为叶子节点.

另外, 我们规定, 任意的事务Ti, 在某一时刻, 最多只能取得一个节点的锁. 也就是说, 现在Ti取得u的锁, 如果它想访问下一个节点v, 那么它必须先释放掉u的锁. 该协议能够保证在并发访问的情况下, 不会出现死锁.

(下面的过程叙述需要你熟知B+树的算法, 请自行查阅资料.)

下面先描述I(k, v)操作的过程, 假设初始u为B+树根节点:

  • 1)u.RLock();
  • 2)如果u.Leaf() == false, 则在u中查找下一个需要迭代的子节点v;
  • 2.1)如果查找失败(失败原因见后文), u.RUnlock(), u:=s(u), 重复2.
  • 2.2)如果查找成功, u.RUnlock(), 则另u:=v, 重复1.
  • 3)如果u.Leaf() == true, u.RUnlock(), u.WLock(), 并尝试向u中插入(k, v);
  • 3.1)如果插入失败(失败原因见后文), u.WUnlock(), 则另u:=s(u), 重复3.
  • 3.2)如果插入成功, 检测u是否需要分裂;
  • 3.2.1)如果不需要, u.WUnlock(), 插入成功, 直接返回.
  • 3.2.2)如果需要, 则依照B+树算法, 创建新节点v, 另s(u):=v, u.WUnlock().
  • 4)递归的向父亲节点插入新增加的节点(如果需要的话), 直至根节点.

现在说明插入失败, 和查找失败的原因. 假设T1准备向B+树中插入(10, 10), 并有如下的执行序列:

  1. T1当前在u节点, 并查询到它下一个需要访问的节点是v; // 注意此时T1并没有v的锁
  2. T2向v中插入了(8, 10), 使得v从原来的[(1, 1), (2, 2), (10, 10)], 变成了[(1, 1), (2, 2), (8, 8), (10, 10)], 并被分裂成为v[(1, 1), (2, 2)], s(v)[(8, 8), (10, 10)]
  3. T2执行v.WUnlock()
  4. T1取得v, 并执行v.RLock(), 接着进行查询

可见, 在T1对v进行查询时, 便会发生查询失败, 原因也很显而易见: 在T1得知要查询v, 到T1对v进行查询期间, 有其他事务对v操作并让其产生了分裂.

v被分裂过后, 它原本的一部分数据就会被移动到s(v)中, 于是则需要在查询失败后, 继续对s(v)进行查询. 插入操作也是同理.

对于S(key)的操作就不用赘述了, 就是I(key, value)中的1), 2), 3)步, 只不过把对应的插入操作改为查询操作.

B+树的事务无关和错误处理

B+树是事务无关的, 既B+树直接以超级事务在执行. 试想如果某个事务, 在B+树中插入了很多索引, 然后又被回滚了, 会怎么样? 结果就是该事务的索引依然留在B+树种, 但是VM却”读不出来”, 和B+树没有Delete操作类似, 因此不会对其他事务造成影响, 这些废弃的索引是安全的.

现在再来看看如果B+树在执行过程中, 发生了崩溃会怎么样? 如果Ti在对u进行修改时, 发生了崩溃, 那么节点u的内部结构就被破坏了, 但是由于B+树是建立在DM上的, 在下一次数据库重启时, u就会被恢复成修改之前的状态. 也就是说, 由于DM的保护, 对B+树节点的操作, 是原子性的!

于是我们现在就不用考虑节点内部错误的情况了, 只需要考虑节点间错误的情况, 而这样的错误情况只有一种: 某次对u的插入操作创建了新节点v, 此时s(u)=v, 但是v却并没有被插入到他的父节点中. 于是成了大致如下的状态:

[parent]
    |
    v
   [u] -> [v]

而正确的状态应该如下:

[ parent ]
 |      |
 v      v
[u] -> [v]

和正确状态相比, 错误状态下, 少了一支从父亲节点到v的指针. 但是这样是没问题的! 因为在插入和查询操作中, 如果失败, 就会不断的向右兄弟节点迭代. 因此, 在错误的状态下, 如果想找v中的内容, 那么情况是: 1)找到parent, 2)通过parent找到u, 3)在u中查找失败, 4)通过u找到v, 5)查找成功.

于是, 在DM的原子性保护下, 结合B+树本身的算法过程, 能够证明B+树是完全能够应对数据库崩坏的.

总结

  1. B+树基于DM.
  2. B+树只提供了Insert和Search两种操作.
  3. 和TBM依赖VM不同, B+树自己管理锁来进行并发控制.
  4. B+树的并发协议是不会产生死锁的.
  5. B+树本身的算法性质和DM原子性保证,使得它能够应对错误情况.