ByShard: Sharding in a Byzantine environment

A geo-scale aware sharded design in which four resilient clusters hold only a part of the data. Local decisions within a cluster are made via consensus (the single-lined arrows), whereas multi-shard coordination to process multi-shard transactions requires cluster-sending (the double-lined arrows).

ByShard is a unifying framework for the study of sharded resilient systems. To process multi-shard transactions, ByShard introduces the orchestrate-execute model (OEM). This model can incorporate all commit, locking, and execution operations required for processing a multi-shard transaction in at-most two consensus steps per involved shard. In specific, we have shown how two-phase commit and two-phase locking, two techniques central to providing atomicity and isolation in traditional sharded databases, can be implemented efficiently within OEM with a minimal usage of costly Byzantine resilient primitives.

Within OEM, we provide three orchestration methods based on two-phase commit and four classes of execution methods that, using two-phase locking, provide various levels of transaction isolation. Combined, these orchestration and execution methods result in eighteen practical protocols for processing multi-shard transaction. We have also shown that both AHL and a generalization of Chainspace can be expressed within OEM.

The implementation of ByShard is in C++20 and is tested using two modern C++ compiler, namely Microsoft C/C++ Compiler Version 19.26.28806 for x64 (part of Visual Studio 2019) and GNU g++ 10.0.1 20200411. The code should work with any sufficiently standard-compliant modern C++ compiler, however. The implementation is available for public use under the BSD-license (license details included in the source files). In our evaluation of ByShard, we performed three experiments. Furthermore, we provide the raw measurements of these experiments:

Project Files and Related Publications

  1. The implementation of ByShard. source code (.zip).
    Full implementation of ByShard, of the experiments, and of all supporting tooling used during the experiments. The source code contains step-by-step instructions to compile and use the code using either G++ or Microsoft Visual C++.
  2. The raw measurements of the experiments. measurement data (plain text, tab separated).
  3. VLDB 2021

    ByShard: Sharding in a Byzantine environment. Jelle Hellings and Mohammad Sadoghi. (2021). In: Proceedings of the VLDB Endowment, 14(11), 2230-2243, VLDB. DOI: 10.14778/3476249.3476275. author copy, slides, poster.

    Video Presentation
    Abstract

    The emergence of blockchains has fueled the development of resilient systems that can deal with Byzantine failures due to crashes, bugs, or even malicious behavior. Recently, we have also seen the exploration of sharding in these resilient systems, this to provide the scalability required by very large data-based applications. Unfortunately, current sharded resilient systems all use system-specific specialized approaches toward sharding that do not provide the flexibility of traditional sharded data management systems.To improve on this situation, we fundamentally look at the design of sharded resilient systems. We do so by introducing ByShard, a unifying framework for the study of sharded resilient systems. Within this framework, we show how two-phase commit and two-phase locking--two techniques central to providing atomicity and isolation in traditional sharded databases--can be implemented efficiently in a Byzantine environment, this with a minimal usage of costly Byzantine resilient primitives. Based on these techniques, we propose eighteen multi-shard transaction processing protocols. Finally, we practically evaluate these protocols and show that each protocol supports high transaction throughput and provides scalability while each striking its own trade-off between throughput, isolation level, latency, and abort rate. As such, our work provides a strong foundation for the development of ACID-compliant general-purpose and flexible sharded resilient data management systems.