Metadata

Many distributed systems have a leader-based consensus protocol at their heart. The protocol elects one server as the "leader" who receives all writes. The other servers are "followers", hot standbys who replicate the leader’s data changes. Paxos and Raft are the most famous leader-based consensus protocols. These protocols ensure consistent state machine replication , but reads are still tricky. Imagine a new leader L1 is elected, while the previous leader L0 thinks it's still in charge. A client might write to L1, then read stale data from L0, violating Read Your Writes . How can we prevent stale reads? The original Raft paper recommended that the leader communicate with a majority of followers before each read, to confirm it's the real leader. This guarantees Read Your Writes but it's slow and expensive. A leader lease is an agreement among a majority of servers that one server will be the only leader for a certain time. This means the leader can run...

This is our most recent work, started and led by Aleksey Charapko . (This is a joint post with him.) You can get the paper at arxiv.org . The paper is currently under submission to a journal. The story One day I challenged Aleksey to give me a ballpark number on how much he thinks we can scale Paxos vertically . While sharding --as in CockroachDB and Spanner-- helps for scaling Paxos deployments horizontally, vertical scaling is about how many nodes you can cram in a single Paxos cluster, with a single conflict domain. Aleksey, who is not known for being an optimist, said that we can scale Paxos to several hundreds of nodes! He said this may be possible by employing intermediate proxy nodes to relay the communication between the leader and followers, as this would relieve the communication bottleneck at the leader. I thought "yeah, it is a neat trick, but maybe not that impressive, because it is very simple". Surely others must have tried this, and there must be a cat...

I am trying to recruit PhD students and since this is the application season for graduate school, I thought I should also advertise here. If you are interested, please contact me via email. Below are the two projects I plan to get new students started on. Yes, it snows a lot in Buffalo. But the summer is beautiful, and Niagara Falls region is 20 minute drive from the university. Paxos Unpacked Due to their excellent fault-tolerance and consistency benefits, Paxos protocols are employed at the core of many distributed systems infrastructures at Google, Facebook, Amazon, and Microsoft. When properly tailored and optimized, Paxos family of protocols can deliver efficiency, performance, and scalability at par with weakly consistent protocols, while providing a stable and strong foundation to build services and applications on top. In this project, we will explore performant, scalable, practical and usable variants of Paxos. We already implemented the Paxi framework to facilit...

Dissecting performance bottlenecks of strongly-consistent replication protocols Ailidani Ailijiang, Aleksey Charapko, and Murat Demirbas. Hey, this is our paper! This appeared in Sigmod 2019 couple weeks back. This paper came out of the dissertation work of Ailidani Ailijiang . He has build the Paxi framework in Go, available on GitHub, to prototype any Paxos flavor quickly. His dissertation is called: "Strongly Consistent Coordination for Wide Area Networks".  Writing blog posts about one's own papers is harder than writing posts about others' papers. When you write a summary of your work, you want to include everything, and cannot detach yourself from specifics easily. I found that I neglected posting about many of our papers, even though it is important to provide brief and accessible summaries of these papers to enhance their reach. It is important to reach more people, because then we can see whether the paper can stand the test of time and push the state o...

This is what I (along with some collaborators) have been thinking about lately. This is still raw, but the idea is exciting enough that I wanted to share early and get feedback, recommendations, pointers. Using synchronized time for distributed coordination A fundamental problem in distributed systems is to coordinate the execution of nodes effectively to achieve performance while preserving correctness. Unfortunately, distributed coordination is a notoriously tricky problem. Since the nodes do not have access to a shared state and a common clock, they need to communicate and synchronize state frequently in order to coordinate on the order of events. However, excessive communication hinders the performance/scalability of a distributed system. A key component of distributed coordination is the enforcement of consistent views at all nodes for the ordering of significant events. Distributed algorithms employed logical clocks and vector clocks predominantly for this coordination. Th...

Paxos is great for solving the fault-tolerant coordination problem in a datacenter. But for cross datacenter coordination (which is needed for distributed databases, filesystems, configuration management, etc.), it hits  the WAN latency barrier. The multi-decree Paxos (Multi-Paxos) algorithm, implemented in variants like Raft and Zab, relies on electing a distinguished leader to serialize updates and hence cannot deal with write-intensive scenarios across the wide area networks (WAN). An alternative is the leaderless Paxos algorithms . Generalized Paxos and EPaxos employ opportunistic leaders for non-interfering commands and are able to reduce 3 message delays to 2, and allow concurrent leaders to commit. But the fast agreement incurs the cost of a much larger quorum named fast-quorum (3/4ths of the nodes) and hits the WAN latency barrier as well. Another alternative (as employed in Google Spanner) is to use multiple Paxos groups with partitioned data/object space . In order to...

This post continues the discussion on monitoring distributed systems with Retroscope . Here we focus on cut monitoring approach Retroscope uses. (This post is jointly written with  Aleksey Charapko and Ailidani Ailijiang.) Retroscope is a monitoring system for exploring global/nonlocal state history of a distributed system. It differs from other monitoring tools due to the way it inspects the system state. While request tracers inspect the system by following the trace of a request (i.e. request r in the figure), Retroscope performs cut monitoring and examines the system at consistent global cuts, observing the state across many machines and requests. It moves along the system history and scans a progression of states one cut at a time, checking cut  Ts1 and then Ts2 and so on. Retroscope’s cut monitoring approach is complementary to the request tracing solutions, and brings a number of advantages. First, by exposing the nonlocal state, Retroscope enables users to examine...

This post, part 2, focuses on monitoring distributed systems using Retroscope. This is a joint post with Aleksey Charapko . If you are unfamiliar with hybrid logical clocks and distributed snapshots, give part 1 a read first. Monitoring and debugging distributed applications is a grueling task. When you need to debug a distributed application, you will often be required to carefully examine the logs from different components of the application and try to figure out how these components interact with each other. Our monitoring solution, Retroscope, can help you with aligning/sorting these logs and searching/focusing on the interesting parts. In particular, Retroscope captures a progression of globally consistent distributed states of a system and allows you to examine these states and search for global predicates. Let’s say you are working on debugging ZooKeeper, a popular coordination service. Using Retroscope you can easily add instrumentation to the ZooKeeper nodes to log and ...