Bizur is a consensus algorithm exposing a key-value interface. It is used by a distributed file-system that scales to 100s of servers, delivering millions of IOPS, both data and metadata, with consistent low-latency. Bizur is aimed for services that require strongly consistent state, but do not require a distributed log; for example, a distributed lock manager or a distributed service locator. By avoiding a distributed log scheme, Bizur outperforms distributed log based consensus algorithms, producing more IOPS and guaranteeing lower latencies during normal operation and especially during failures. Paxos-like algorithms (e.g., Zab and Raft) which are used by existing distributed file-systems, can have artificial contention points due to their dependence on a distributed log. The distributed log is needed when replicating a general service, but when the desired service is key-value based, the contention points created by the distributed log can be avoided. Bizur does exactly that, by reaching consensus independently on independent keys. This independence allows Bizur to handle failures more efficiently and to scale much better than other consensus algorithms, allowing the file-system that utilizes Bizur to scale with it.
Consensus algorithms have attracted a lot of attention in areas requiring high-availability and fault tolerance. Mainly because they provide the ability to replicate a service across multiple servers, in a way that allows the service to continue working when some of the servers fail. This scheme of using consensus to achieve a replicated service is called state machine replication'' (SMR) @cite_17 .
@cite_17
2129467152 2147524598 2303620077 2025713377
There are currently two approaches to providing Byzantine-fault-tolerant state machine replication: a replica-based approach, e.g., BFT, that uses communication between replicas to agree on a proposed ordering of requests, and a quorum-based approach, such as Q U, in which clients contact replicas directly to optimistically execute operations. Both approaches have shortcomings: the quadratic cost of inter-replica communication is un-necessary when there is no contention, and Q U requires a large number of replicas and performs poorly under contention. We present HQ, a hybrid Byzantine-fault-tolerant state machine replication protocol that overcomes these problems. HQ employs a lightweight quorum-based protocol when there is no contention, but uses BFT to resolve contention when it arises. Furthermore, HQ uses only 3f + 1 replicas to tolerate f faults, providing optimal resilience to node failures. We implemented a prototype of HQ, and we compare its performance to BFT and Q U analytically and experimentally. Additionally, in this work we use a new implementation of BFT designed to scale as the number of faults increases. Our results show that both HQ and our new implementation of BFT scale as f increases; additionally our hybrid approach of using BFT to handle contention works well. A fault-scalable service can be configured to tolerate increasing numbers of faults without significant decreases in performance. The Query Update (Q U) protocol is a new tool that enables construction of fault-scalable Byzantine fault-tolerant services. The optimistic quorum-based nature of the Q U protocol allows it to provide better throughput and fault-scalability than replicated state machines using agreement-based protocols. A prototype service built using the Q U protocol outperforms the same service built using a popular replicated state machine implementation at all system sizes in experiments that permit an optimistic execution. Moreover, the performance of the Q U protocol decreases by only 36 as the number of Byzantine faults tolerated increases from one to five, whereas the performance of the replicated state machine decreases by 83 . Consensus mechanisms for ensuring consistency are some of the most expensive operations in managing large amounts of data. Often, there is a trade off that involves reducing the coordination overhead at the price of accepting possible data loss or inconsistencies. As the demand for more efficient data centers increases, it is important to provide better ways of ensuring consistency without affecting performance. In this paper we show that consensus (atomic broadcast) can be removed from the critical path of performance by moving it to hardware. As a proof of concept, we implement Zookeeper's atomic broadcast at the network level using an FPGA. Our design uses both TCP and an application specific network protocol. The design can be used to push more value into the network, e.g., by extending the functionality of middleboxes or adding inexpensive consensus to in-network processing nodes. To illustrate how this hardware consensus can be used in practical systems, we have combined it with a mainmemory key value store running on specialized microservers (built as well on FPGAs). This results in a distributed service similar to Zookeeper that exhibits high and stable performance. This work can be used as a blueprint for further specialized designs. The consensus problem is at the heart of solutions related to the development of modern reliable distributed systems. This paper studies necessary and sufficient conditions under which fault-tolerant consensus become solvable in dynamic systems and self-organizing networks. Those conditions are related to the synchrony requirements of the environment, to the connectivity of the knowledge graph constructed by the nodes in order to communicate with their peers, as well as to the knowledge about global parameters in the system, such as, the total number of participants and the maximum number of node crashes.