Report
Transactional Composition of Nonblocking Data Structures
| العنوان: | Transactional Composition of Nonblocking Data Structures |
|---|---|
| المؤلفون: | Cai, Wentao, Wen, Haosen, Scott, Michael L. |
| سنة النشر: | 2023 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Distributed, Parallel, and Cluster Computing, Computer Science - Data Structures and Algorithms, Computer Science - Performance |
| الوصف: | This paper introduces nonblocking transaction composition (NBTC), a new methodology for atomic composition of nonblocking operations on concurrent data structures. Unlike previous software transactional memory (STM) approaches, NBTC leverages the linearizability of existing nonblocking structures, reducing the number of memory accesses that must be executed together, atomically, to only one per operation in most cases (these are typically the linearizing instructions of the constituent operations). Our obstruction-free implementation of NBTC, which we call Medley, makes it easy to transform most nonblocking data structures into transactional counterparts while preserving their liveness and high concurrency. In our experiments, Medley outperforms Lock-Free Transactional Transform (LFTT), the fastest prior competing methodology, by 40--170%. The marginal overhead of Medley's transactional composition, relative to separate operations performed in succession, is roughly 2.2$\times$. For persistent data structures, we observe that failure atomicity for transactions can be achieved "almost for free" with epoch-based periodic persistence. Toward that end, we integrate Medley with nbMontage, a general system for periodically persistent data structures. The resulting txMontage provides ACID transactions and achieves throughput up to two orders of magnitude higher than that of the OneFile persistent STM system. |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2301.00996 |
| رقم الانضمام: | edsarx.2301.00996 |
| قاعدة البيانات: | arXiv |
| ResultId |
1 |
|---|---|
| Header |
edsarx arXiv edsarx.2301.00996 1051 3 Report report 1050.97668457031 |
| PLink |
https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&scope=site&db=edsarx&AN=edsarx.2301.00996&custid=s6537998&authtype=sso |
| FullText |
Array
(
[Availability] => 0
)
Array ( [0] => Array ( [Url] => http://arxiv.org/abs/2301.00996 [Name] => EDS - Arxiv [Category] => fullText [Text] => View record in Arxiv [MouseOverText] => View record in Arxiv ) ) |
| Items |
Array
(
[Name] => Title
[Label] => Title
[Group] => Ti
[Data] => Transactional Composition of Nonblocking Data Structures
)
Array ( [Name] => Author [Label] => Authors [Group] => Au [Data] => <searchLink fieldCode="AR" term="%22Cai%2C+Wentao%22">Cai, Wentao</searchLink><br /><searchLink fieldCode="AR" term="%22Wen%2C+Haosen%22">Wen, Haosen</searchLink><br /><searchLink fieldCode="AR" term="%22Scott%2C+Michael+L%2E%22">Scott, Michael L.</searchLink> ) Array ( [Name] => DatePubCY [Label] => Publication Year [Group] => Date [Data] => 2023 ) Array ( [Name] => Subset [Label] => Collection [Group] => HoldingsInfo [Data] => Computer Science ) Array ( [Name] => Subject [Label] => Subject Terms [Group] => Su [Data] => <searchLink fieldCode="DE" term="%22Computer+Science+-+Distributed%2C+Parallel%2C+and+Cluster+Computing%22">Computer Science - Distributed, Parallel, and Cluster Computing</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+Science+-+Data+Structures+and+Algorithms%22">Computer Science - Data Structures and Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+Science+-+Performance%22">Computer Science - Performance</searchLink> ) Array ( [Name] => Abstract [Label] => Description [Group] => Ab [Data] => This paper introduces nonblocking transaction composition (NBTC), a new methodology for atomic composition of nonblocking operations on concurrent data structures. Unlike previous software transactional memory (STM) approaches, NBTC leverages the linearizability of existing nonblocking structures, reducing the number of memory accesses that must be executed together, atomically, to only one per operation in most cases (these are typically the linearizing instructions of the constituent operations). Our obstruction-free implementation of NBTC, which we call Medley, makes it easy to transform most nonblocking data structures into transactional counterparts while preserving their liveness and high concurrency. In our experiments, Medley outperforms Lock-Free Transactional Transform (LFTT), the fastest prior competing methodology, by 40--170%. The marginal overhead of Medley's transactional composition, relative to separate operations performed in succession, is roughly 2.2$\times$. For persistent data structures, we observe that failure atomicity for transactions can be achieved "almost for free" with epoch-based periodic persistence. Toward that end, we integrate Medley with nbMontage, a general system for periodically persistent data structures. The resulting txMontage provides ACID transactions and achieves throughput up to two orders of magnitude higher than that of the OneFile persistent STM system. ) Array ( [Name] => TypeDocument [Label] => Document Type [Group] => TypDoc [Data] => Working Paper ) Array ( [Name] => URL [Label] => Access URL [Group] => URL [Data] => <link linkTarget="URL" linkTerm="http://arxiv.org/abs/2301.00996" linkWindow="_blank">http://arxiv.org/abs/2301.00996</link> ) Array ( [Name] => AN [Label] => Accession Number [Group] => ID [Data] => edsarx.2301.00996 ) |
| RecordInfo |
Array
(
[BibEntity] => Array
(
[Subjects] => Array
(
[0] => Array
(
[SubjectFull] => Computer Science - Distributed, Parallel, and Cluster Computing
[Type] => general
)
[1] => Array
(
[SubjectFull] => Computer Science - Data Structures and Algorithms
[Type] => general
)
[2] => Array
(
[SubjectFull] => Computer Science - Performance
[Type] => general
)
)
[Titles] => Array
(
[0] => Array
(
[TitleFull] => Transactional Composition of Nonblocking Data Structures
[Type] => main
)
)
)
[BibRelationships] => Array
(
[HasContributorRelationships] => Array
(
[0] => Array
(
[PersonEntity] => Array
(
[Name] => Array
(
[NameFull] => Cai, Wentao
)
)
)
[1] => Array
(
[PersonEntity] => Array
(
[Name] => Array
(
[NameFull] => Wen, Haosen
)
)
)
[2] => Array
(
[PersonEntity] => Array
(
[Name] => Array
(
[NameFull] => Scott, Michael L.
)
)
)
)
[IsPartOfRelationships] => Array
(
[0] => Array
(
[BibEntity] => Array
(
[Dates] => Array
(
[0] => Array
(
[D] => 03
[M] => 01
[Type] => published
[Y] => 2023
)
)
)
)
)
)
)
|
| IllustrationInfo |