STI-BT: A Scalable Transactional Index

Distributed Key-Value (DKV) stores have been intensively used to manage online transaction processing on large data-sets. DKV stores provide simplistic primitives to access data based on the primary key of the stored objects. To help programmers to efficiently retrieve data, some DKV stores provide distributed indexes. Besides that, and also to simplify programming such applications, several proposals have provided strong consistency abstractions via distributed transactions. In this paper we present STI-BT, a highly scalable, transactional index for Distributed Key-Value stores. STI-BT is organized as a distributed B $^+$ Tree and adopts an innovative design that allows to achieve high efficiency in large-scale, elastic DKV stores. As such, it provides both the desirable properties identified above, and does so in a far more efficient and scalable way than the few existing state of the art proposals that also enable programmers to have strongly consistent distributed transactional indexes. We have implemented STI-BT on top of an open-source DKV store and deployed it on a public cloud infrastructure. Our extensive study demonstrates scalability in a cluster of $100$ machines, and speed ups with respect to state of the art up to $5.4\times$ .