原文

• PALM: Parallel Architecture-Friendly Latch-Free Modifications to B+ Trees on Many-Core Processors
  http://www.vldb.org/pvldb/vol4/p795-sewall.pdf

关键词

Latch-free: 无锁(且无自旋锁)
scalable： 可扩展的
Transitions： 转换 过度
state-of-the art: 最新，最先进

40M: 
The suffix ‘K’ indicates ‘thousand’, the suffix ‘M’ indicates ‘million’, and the suffix
‘B’ indicates ‘billion.

locks and latches
按照Graefe [11]，我们对锁和闩锁进行了区分。 前者是与数据库事务的语义有关的概念，
而使用后者在线程级别控制对内存中数据的更新-这些是指的“锁”到数据库社区之外

本文没有特殊标注locks 的锁， 都指latches.

PALM: 一个并行友好架构，在多核处理器上可无锁修改的B+树

作者

Jason Sewall Jatin Chhugani Changkyu Kim Nadathur Satish Pradeep Dubey
Parallel Computing Lab
Intel Corporation
Contact: jason.sewall@intel.com

ABSTRACT 摘要

B +树上的并发控制主要是通过闩锁实现的，但是序列化和竞争会阻碍可扩展性。 如今，随着处理器的数量在增加，必须发展可扩展的无闩锁技术，用于并发控制。
我们提出PALM，这是一种新颖的内存B +树，为了实现多并发查询操作，PALM基于批量同步并行模型，可确保没有死锁和竞争。输入查询会被分组，并按原子批次( atomic batches)进行处理，然后分阶段进行工作，排除竞争。 阶段之间过度的实现，具有可扩展的点对点通信。PALM利用现代多核体系结构上，的数据和线程级并行性，实现40M updates/second on tree with 128M keys, 128M updates/second on trees with 512K keys 在最新的CPU 架构上。我们的吞吐量是内存B +树上最新并发修改算法的2.3倍至19倍。
372/5000
PALM在非常低的响应时间下(小于350µs)可获得接近峰值的吞吐量，即使对于大树也是如此。
我们还在以下方面评估PALM：英特尔多核集成（Intel MIC）架构，并在Intel Knights Ferry上展示了 out-of-cache tree sizes的1.5–2.1倍加速, 超过了一对 dual-socket配置的，Intel Xeon 处理器 DP X5680（Westmere-EP) 。

1. INTRODUCTION 介绍

B +树是中使用最广泛的数据结构之一，在数据库中[12]，并且曾经很多工作是通过他们实现最佳性能。其中 很大一部分工作涉及并发控制，以实现并行计算[3、4、23、33、18、24、11]。
该领域的许多工作集中在基于磁盘的数据库上。 这些系统的性能通常受磁盘I / O带宽的限制。 但是，随着内存容量的急剧增加，现在许多数据库表及其对应的索引结构，完全驻留在主内存中-消除了磁盘I / O操作。 现在已有的系统具有超过1TB的内存; 这预示下一代系统的未来。
此外，现代处理器提高了计算能力，通过在单个芯片上集成多个内核，极大地提高了每个中扩展单指令多数据（SIMD）单元核心。 在可预见的未来，计算能力的最大增长，将来自不断增加的并行性； 可扩展并行算法至关重要。

2. RELATED WORK 相关工作

B树[2]旨在加速对基于磁盘的数据库的搜索查询，同时支持修改。 早期就意识到，查询同时并发执行更新的重要性，很大的工作量在B树上的并发的控制。 许多早期的论文专注于闩锁耦合，使用读取闩锁和更新闩锁来支持并发和摆脱死锁。 Bayer 和McCreight [3]]提出了很多依靠预测分裂的锁方案； Bernstein等 [4]涵盖了许多用于B树的锁的协议。
Lehman和 Yao 提出的B-link树[23]，放宽了B-树的结构，以允许节点使用高隔离的键和指针分别指向后继节点

3. PARALLEL BATCHED TREE QUERIES 并行批处理树的查询

3.1 Motivation 动机

PALM 在内存中操作B+树， 该树索引了数据库D的某一列的键的自全序集合K，该树存储键值对pairs(K, r*k)
指针r r∗k 指向了第二个结构rk, rk枚举了D数据库中 所有键值为K的元组的id。
此间接寻址为典型数据库，支持多个元组的有相同键值。对于树 TD索引了数据库D，
PALM支持三个具有以下语义的查询：

取 
RETRIEVE (TD, k): Return rk, or ∅ if k /∈ TD.
插入 
INSERT (TD,(k, e)): 
If k ∈ TD, append e to rk; 
otherwise, add anew rk = {e}, and add the new pair (k, r∗k) to TD.
删除 
DELETE (TD,(k, e)): If k ∈ TD, remove e from rk, 
then if |rk| = 0, remove (k, r∗k) from TD. If k /∈ TD, do nothing.

取操作是严格 read query and returns results, 然而插入和删除是 read/write (modify) queries returning nothing。
此外，取操作之间互相没有影响，插入和删除会影响其他操作的结果，仅当他们使用相同键时
这些特性 These properties allow O to reordered (see Sec. 3.2.5).

3.1.1 Asynchronous tree queries 异步

3.1.2 Synchronous tree queries 同步

3.2 Algorithm 算法

3.2.1 Cooperation in REDISTRIBUTE-WORK

3.2.2 Ensuring correctness with RESOLVE-HAZARDS

3.2.3 Bulk node modification with MODIFY-NODE

3.3 Load balancing

4. IMPLEMENTATION

5. RESULTS

6. DISCUSSION AND CONCLUSION

7. REFERENCES

APPENDIX 附录

A. POINT-TO-POINT SYNCHRONIZATION
B. NODE REPRESENTATION
C. PERFORMANCE MODELING