Scalable indexing for large-scale distributed storage systems

PhD Student: Dimitrios Vassilas
Advisor: Marc Shapiro (Sorbonne-Université & Inria)


An object storage system stores objects (files) identified by keys. An object contains raw, uninterpreted data, and the key specifies its location (address). The Scality object storage system, known as The Ring, is highly distributed, uses replication and erasure coding for fault-tolerance, supports hierarchical archival storage, and is designed for high throughput and low latency. Its design leverages the separation of data files from metadata (the key-to-location database): data is essentially immutable, while adding, removing and updating objects is done by modifying the meta-data. Thanks to this design, The Ring is able to store petabytes of data, updated at a very high rate. In order to support fast search, the system requires an indexing sub-system that tracks the inverse mapping from content (patterns of data or tags) to key. Indexing a large, distributed, heavily-updated storage system is a difficult problem.

Research topic

The research problem to be solved in this PhD is to design a flexible distributed indexing and search system that scales to petabytes, and that remains up-to-date incrementally as the store is updated. Some specific requirements include the following: The PhD student will design and implement a decentralised indexing and querying system that solves the above problem efficiently.

State of the art

Formally, the problem of index search is related to subset pattern matching, and more specifically to the distributed pattern matching problem (DPM) [ 1 ]. Existing centralized algorithms are not suitable to the more peer-to-peer environment of an object storage system [ 2 ]. Many distributed indexing algorithms exist in the literature, e.g., inverted indexes [ 5, 6, 7, 15 ], hypercubes [ 8 ] and unit vector matching [ 9 ]. These are often designed for Distributed Hash Tables (DHTs), and focus on efficient DHT routing, for instance using Bloom filters [ 10, 11 ] or erasure coding with super-peers [ 1, 21 ]. Conversely, algorithms based on skip-lists do not require a DHT, but instead use multi-level indexing mechanisms based on hierarchies of lists [ 12, 13, 14 ]. Alternatively, there exists a variety of file systems optimized for indexing [ 16, 17, 18, 19 ]. In contrast, the desired approach should not depend on any specific file system and should integrate into the object store at a low level.


The research is advised jointly by Marc Shapiro and Vianney Rancurel (Dir. of Research of Scality), in cooperation with Pr. Umut Acar. It is funded by a "bourse CIFRE" (joint industry-academia research).


Marc.Shapiro =at=
Last modified: Mon Sep 24 15:32:21 CEST 2018