事务的并发问题可以通过两阶段封锁协议或者多版本并发控制等方法解 决,这类方法也同样适用于索引的并发访问控制。但是由于索引访问更加频繁,更容易触达性能瓶颈,导致低并发度。对事务而言,对一个索引查找两次,并在查找期间发现索引结构发生变化,这是完全可以接受的,只要索引查找返回正确的元组集。因此,只要维护索引的准确性,对索引进行非可串行化并发存取是可接受的。
AntDB 分布式内存数据库为了避免在获取另一个节点的锁的时候还占有当前节点的锁,对 B+ 树进行改进,在每个 B+ 树节点,包括叶子节点和内部节点都维护一个指向右兄弟节点的指针(link pointer),这个指针的作用是,当一个节点正在分裂时可以在查到该节点的同时查找到其兄弟节点。在节点内部增加一个字段 high key,在查询时如果目标值超过该节点的 high key,就需要循着 link pointer 继续往后继节点查找。
AntDB 分布式内存数据库的封锁协议过程如下:
(1) 查找。
B+ 树的每个节点在访问之前必须加共享锁,非叶子节点的锁应该在对其子节点申请共享锁之前被释放。如果节点分裂与查找同时发生,所希望的记录可能不再位于查找过程中所访问的某个节点内。在这种情况下,记录在由一个右兄弟节点表示的范围内,这是由系统循着指向右兄弟节点的指针而找到的。不过,系统封锁叶节点遵循两阶段封锁协议,以避免幻读。
(2) 插入与删除。
系统遵循查找规则,定位要进行插入或删除的叶节点。该节点的共享锁升级为排他锁,然后进行插入或删除。受插入或删除影响的叶节点封锁遵循两阶段封锁协议以避免幻读。
(3) 分裂。
如果事务使一个节点分裂,则创建新节点,并作为原始结点的右兄弟节点。设置原始节点与新产生节点的右兄弟指针,接着,事务释放原始节点的排他锁,假设它是一个内节点,叶节点以两阶段形式加锁,然后,发出对父节点加排他锁的请求,以便插入指向新节点的指针。
(4) 合并。
执行删除后,如果一个节点的记录太少,则必须对要与之合并的那个节点加排他锁。一旦这两个节点合并,则发出对父节点加排他锁的请求,以便删除需要删除的节点,此时,事务释放合并节点的锁,该过程与查询操作相反,封锁从下向上传播。除非父节点也需再合并,不然释放其锁。
(5) 插入与删除操作可能封锁一个节点,释放该节点,然后对它重新封锁。
分裂或合并节点会加排他锁,此外,与分裂或合并操作并发执行的查找可能发现要查找的记录被分裂或合并操作移到右兄弟节点,但这并不影响查询操作,因为查询操作会同时查找该节点的右兄弟节点。
(6) 当每个节点增加两个额外字段,link pointer 和 high key,在查询时需要额外判断,如果查询时超过 high key,需要额外通过 link pointer 查询其后继节点,可能会产生一次额外的 I/O,从而造成单次查找性能的下降,但由于树结构调整是一个频率较低的动作,而且查询后继节点的操作也只会发生在子节点调整和父节点调整过程之间,一旦父节点调整完毕,就可以通过父节点的指针直接查询而无须再通过子节点的后继指针查找。
通过以空间换时间的设计, 通过在每个中间节点增加后继指针来避免在树结构调整时全局加锁而带来的整体性能衰退。




