MARK-OPT: A Concurrency Control Protocol for Parallel B-Tree Structures to Reduce the Cost of SMOs
T. YOSHIHARA, D. KOBAYASHI, Haruo Yokota · IEICE Transactions on Information and Systems · 2007
In this paper, we propose a new concurrency control protocol for parallel B-tree structures capable reducing the cost of structuremodification-operation (SMO) compared to the conventional protocols such as ARIES/IM and INC-OPT.We call this protocol the MARK-OPT protocol, since it marks the lowest SMO occurrence point during optimistic latch-coupling operations.The marking reduces middle phases for spreading an X latch and removes needless X latches.In addition, we propose three variations of the MARK-OPT, which focus on tree structure changes from other transactions.Moreover, the proposed protocols are deadlockfree and satisfy the physical consistency requirement for B-trees.These indicate that the proposed protocols are suitable as concurrency control protocols for B-tree structures.To compare the performance of the proposed protocols, the INC-OPT, and the ARIES/IM, we implement these protocols on an autonomous disk system adopting the Fat-Btree structure, a form of parallel B-tree structure.Experimental results in various environments indicate that the proposed protocols always improve system throughput, and 2P-REP-MARK-OPT is the most useful protocol in high update environment.Additionally, to mitigate access skew, data should be migrated between PEs.We also demonstrate that MARK-OPT improves the system throughput under the data migration and reduces the time for data migration to balance load distribution.