Scalable Timestamp Allocation for Deadlock Prevention in Two-phase Locking based Protocols

• Item type: Trans(1)
• 公開日: 2023-04-14
• タイトル: Scalable Timestamp Allocation for Deadlock Prevention in Two-phase Locking based Protocols
• タイトル / 言語: en
• タイトル: Scalable Timestamp Allocation for Deadlock Prevention in Two-phase Locking based Protocols
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: [研究論文] database system, transaction processing, concurrency control, two-phase locking, single centralized atomic counter
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: Keio University
• 著者所属: Scalar, Inc.
• 著者所属: Cybozu Labs, Inc.
• 著者所属: Keio University
• 著者所属(英): en
• 著者所属(英): Keio University
• 著者所属(英): en
• 著者所属(英): Scalar, Inc.
• 著者所属(英): en
• 著者所属(英): Cybozu Labs, Inc.
• 著者所属(英): en
• 著者所属(英): Keio University
• 著者名: Tatsuhiro, Nakamori; Jun, Nemoto; Takashi, Hoshino; Hideyuki, Kawashima
• 著者名(英): Tatsuhiro, Nakamori; Jun, Nemoto; Takashi, Hoshino; Hideyuki, Kawashima
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Concurrency control ensures the correctness of databases when transactions are processed in parallel. Bamboo is a state-of-the-art concurrency control protocol extended from 2PL Wound-Wait. 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 three methods of decentralization to address the problem. The first is the thread-ID method (TID), which dismisses the process of fetching timestamps entirely by assigning an ID to each thread, and transactions use the thread IDs as their timestamps. In high-contention settings, the performance of TID plummets, but the second method FairTID, which is an extension of TID, sustains the performance even in such settings. The third method (RandID) allocates timestamps using random-number generators. Experiments were conducted to evaluate the performance of the proposed methods. The results indicated that there were up to 62% and 59% improvement in throughput from Bamboo with FairTID and RandID, respectively. In high-contention settings, TID underperformed Bamboo, but FairTID and RandID showed consistent improvement from Bamboo.; ------------------------------; This is a preprint of an article intended for publication Journal of; Information Processing(JIP). This preprint should not be cited. This; article should be cited as: Journal of Information Processing Vol.31(2023) (online); ------------------------------
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Concurrency control ensures the correctness of databases when transactions are processed in parallel. Bamboo is a state-of-the-art concurrency control protocol extended from 2PL Wound-Wait. 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 three methods of decentralization to address the problem. The first is the thread-ID method (TID), which dismisses the process of fetching timestamps entirely by assigning an ID to each thread, and transactions use the thread IDs as their timestamps. In high-contention settings, the performance of TID plummets, but the second method FairTID, which is an extension of TID, sustains the performance even in such settings. The third method (RandID) allocates timestamps using random-number generators. Experiments were conducted to evaluate the performance of the proposed methods. The results indicated that there were up to 62% and 59% improvement in throughput from Bamboo with FairTID and RandID, respectively. In high-contention settings, TID underperformed Bamboo, but FairTID and RandID showed consistent improvement from Bamboo.; ------------------------------; This is a preprint of an article intended for publication Journal of; Information Processing(JIP). This preprint should not be cited. This; article should be cited as: Journal of Information Processing Vol.31(2023) (online); ------------------------------
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464847
• 書誌情報: 情報処理学会論文誌データベース（TOD）; 巻 16, 号 2, 発行日 2023-04-14
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7799
• 出版者 / 言語: ja
• 出版者: 情報処理学会