The ART of Practical Synchronization
Viktor Leis Florian Scheibner Alfons Kemper Thomas Neumann
Technische Universität München
{leis,scheibnf,kemper,neumann}@in.tum.de
ABSTRACT
The performance of transactional database systems is critically de-
pendent on the efficient synchronization of in-memory data struc-
tures. The traditional approach, fine-grained locking, does not scale
on modern hardware. Lock-free data structures, in contrast, scale
very well but are extremely difficult to implement and often require
additional indirections. In this work, we argue for a middle ground,
i.e., synchronization protocols that use locking, but only sparingly.
We synchronize the Adaptive Radix Tree (ART) using two such
protocols, Optimistic Lock Coupling and Read-Optimized Write
EXclusion (ROWEX). Both perform and scale very well while be-
ing much easier to implement than lock-free techniques.
1. INTRODUCTION
In traditional database systems, most data structures are pro-
tected by fine-grained locks
1
. This approach worked well in the
past, since these locks were only acquired for a short time and
disk I/O dominated overall execution time. On modern servers with
many cores and where most data resides in RAM, synchronization
itself often becomes a major scalability bottleneck. And with the
increasing number of CPU cores—Intel’s current server platform
Broadwell EP supports up to 24 cores per socket—efficient syn-
chronization will become even more important.
Figure 1 gives an overview over the synchronization paradigms
discussed in this paper. Besides traditional fine-grained locking,
which is known to scale badly on modern CPUs, the figure shows
the lock-free paradigm, which offers strong theoretical guarantees,
and Hardware Transactional Memory (HTM), which requires spe-
cial hardware support. When designing a data structure, so far, one
had to decide between the extreme difficulty of the lock-free ap-
proach, special hardware support of HTM, and poor scalability of
locking. In this paper, we present two additional points in the de-
sign space that fill the void in between. Optimistic Lock Coupling
and ROWEX are much easier to use than lock-free synchronization
but offer similar scalability without special hardware support.
1
In this paper, we always use the term “lock” instead of “latch”
since we focus on low-level data structure synchronization, not
high-level concurrency control.
Permission to make digital or hard copies of all or part of this work for personal or
classroom use is granted without fee provided that copies are not made or distributed
for profit or commercial advantage and that copies bear this notice and the full cita-
tion on the first page. Copyrights for components of this work owned by others than
ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or re-
publish, to post on servers or to redistribute to lists, requires prior specific permission
and/or a fee. Request permissions from permissions@acm.org.
DaMoN’16, June 26-July 01 2016, San Francisco, CA, USA
c
2016 ACM. ISBN 978-1-4503-4319-0/16/06. . . $15.00
DOI: http://dx.doi.org/10.1145/2933349.2933352
scalability
ease of use
fine-grained locking
(lock coupling)
optimistic
lock coupling
HTM
lock-free
ROWEX
Figure 1: Overview of synchronization paradigms
We focus on synchronizing the Adaptive Radix Tree (ART) [12],
a general-purpose, order-preserving index structure for main-memory
database systems. ART is an interesting case study, because it is a
non-trivial data structure that was not designed with concurrency
in mind rather with high single-threaded performance. We present
a number of synchronization protocols for ART and compare them
experimentally.
Our main goal in this paper, however, is to distill general prin-
ciples for synchronizing data structures in general. This is impor-
tant for two reasons. First, besides index structures, database sys-
tems also require other data structures that must be concurrently ac-
cessible like tuple storage, buffer management data structures, job
queues, etc. Second, concurrent programs are very hard to write
and even harder to debug. We therefore present our ideas, which,
as we discuss in Section 6, are not entirely new, as general building
blocks that can be applied to other other data structures.
The rest of this work is organized as follows. We first present
necessary background about the Adaptive Radix Tree in Section 2.
The two new synchronization paradigms Optimistic Lock Coupling
and Read-Optimized Write EXclusion are introduced in Section 3
and Section 4. Section 5 evaluates the presented mechanisms. Fi-
nally, after discussing related work in Section 6, we present our
conclusions in Section 7.
2. THE ADAPTIVE RADIX TREE (ART)
Trie data structures, which are also known as radix trees and
prefix trees, have been shown to outperform classical in-memory
search trees [12, 10]. At the same time, and in contrast to hash
下载后可阅读完整内容，剩余7页未读，立即下载
weixin_38560797
- 粉丝: 5
- 资源: 997
我的内容管理
展开
最新资源
- 最优条件下三次B样条小波边缘检测算子研究
- 深入解析：wav文件格式结构
- JIRA系统配置指南：代理与SSL设置
- 入门必备：电阻电容识别全解析
- U盘制作启动盘：详细教程解决无光驱装系统难题
- Eclipse快捷键大全：提升开发效率的必备秘籍
- C++ Primer Plus中文版：深入学习C++编程必备
- Eclipse常用快捷键汇总与操作指南
- JavaScript作用域解析与面向对象基础
- 软通动力Java笔试题解析
- 自定义标签配置与使用指南
- Android Intent深度解析：组件通信与广播机制
- 增强MyEclipse代码提示功能设置教程
- x86下VMware环境中Openwrt编译与LuCI集成指南
- S3C2440A嵌入式终端电源管理系统设计探讨
- Intel DTCP-IP技术在数字家庭中的内容保护
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
