Technical Report MSC-2017-10

Title: A Scalable Linearizable Multi-Index Table
Authors: Gal Sheffi
Supervisors: Erez Petrank
PDFCurrently accessibly only within the Technion network
Abstract: Concurrent data structures typically index data using a single primary key and provide fast access to data associated with a given key value. However, it is often required to access information via multiple primary and secondary keys, and even through additional properties that do not represent keys for the given data. One way to implement a data structure that allows access via multiple indexing is to use an existing data structure that allows access via a single index, and traverse the items exhaustively to find items by a secondary key. However, using this method, it is difficult to achieve either correctness (linearizability) or good performance. In this thesis, we propose to obtain multi-indexing access by using an efficient concurrent data structure for each of the indexed fields. We then coordinate these structures to obtain correctness and good performance. We propose lock-free and lock-based designs of a table with multiple indexing, supporting linearizable inserts, deletes, and retrieve operations. We have implemented the proposed designs and ran measurements on a 64-core AMD platform. The obtained performance demonstrates efficiency and high scalability. In particular, measurements show that lock-free solutions perform better than lock-based ones when contention is high, as well as in most practical scenarios.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2017
To the main CS technical reports page

Computer science department, Technion