Removing Performance Bottleneck of Timestamp Allocation in Two-Phase Locking Based Protocol

Tatsuhiro Nakamori, Jun Nemoto, Takashi Hoshino, Hideyuki Kawashima

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)


Concurrency control ensures the correctness of databases when transactions are processed in parallel. Bamboo is a state-of-the-art concurrency control protocol. One problem of Bamboo is that it requires transactions to fetch timestamps from a single centralized atomic counter. To replace the concentrated access to it, each transaction should generate timestamps independently. This paper proposes two methods of decentralization to address the problem. The first is the thread-ID method (TID): transactions use thread IDs as their timestamps. In high-contention settings, the performance of TID plummets, but proposed optimization FairTID sustains the performance. The second method (RandID) allocates timestamps using random-number generators. Experiments indicated that there were up to 60% and 34% improvement in throughput from Bamboo with FairTID and RandID, respectively. In high-contention settings, TID recorded 24% degradation, but FairTID and RandID showed 19% to 31% and 12% to 22% improvement from Bamboo, respectively.

Original languageEnglish
Title of host publicationDatabases Theory and Applications - 33rd Australasian Database Conference, ADC 2022, Proceedings
EditorsWen Hua, Hua Wang, Lei Li
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages8
ISBN (Print)9783031155116
Publication statusPublished - 2022
Event33rd Australasian Database Conference, ADC 2022 - Sidney, Australia
Duration: 2022 Sept 22022 Sept 4

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13459 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference33rd Australasian Database Conference, ADC 2022


  • Concurrency control
  • Database system
  • Single centralized atomic counter
  • Transaction processing
  • Two-phase locking

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Removing Performance Bottleneck of Timestamp Allocation in Two-Phase Locking Based Protocol'. Together they form a unique fingerprint.

Cite this