| |
Click here for full text:
A practical scalable distributed B-tree
Aguilera, Marcos K.; Golab, Wojciech
HPL-2007-193
Keyword(s): distributed data structures, distributed algorithms, scalability, fault tolerance
Abstract: We propose a new algorithm for a practical, fault- tolerant, and scalable B-tree distributed over a set of servers. Our algorithm supports practical features not present in prior work: transactions that allow atomic execution of multiple operations over multiple B-trees, online migration of B-tree nodes between servers, and dynamic addition and removal of servers. Moreover, our algorithm is conceptually simple: we use transactions to manipulate B-tree nodes so that clients need not use complicated concurrency and locking protocols used in prior work. We implemented our approach and show that its performance and scalability are comparable to previous schemes, yet it offers many additional practical features. We believe that our approach is quite general and can be used to implement other distributed data structures easily.
16 Pages
Back to Index
|
Printable version
