Bodega : Serving Linearizable Reads Locally from Anywhere at Anytime via Roster Leases DOI: xxxxxxx.xxxxxxx ISBN: 978-1-4503-xxxx-x/xxxx/xx
Guanzhou Hu, Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau · 2025
Read Bodega : Serving Linearizable Reads Locally from Anywhere at Anytime via Roster Leases DOI: xxxxxxx.xxxxxxx ISBN: 978-1-4503-xxxx-x/xxxx/xx by Guanzhou Hu, Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-07158.txt.
Introduction
Guanzhou Hu and 2 co-authors introduce Bodega in 2025, a protocol that lets computers in a distributed system read the latest data from a nearby copy. Distributed systems keep copies of data on many machines so work can continue if one fails. Linearizable reads must return the newest value, and older systems usually force such reads to travel to a leader machine, which slows distant users.
Bodega solves this with roster leases, an agreement scheme that tracks which sets of copies may answer reads locally. Guards against interfering writes, early accept notices, and light heartbeats keep the scheme practical. In tests on real wide-area clusters, Bodega sped up average reads by about 5.6 to 13.1 times over earlier methods under moderate write traffic. Write speed stayed comparable, and the design layers onto classic consensus without special demands.
Catalog record
| CREATOR | Guanzhou Hu, Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 73 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-07158
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Bodega : Serving Linearizable Reads Locally from Anywhere at Anytime via Roster Leases DOI: xxxxxxx.xxxxxxx ISBN: 978-1-4503-xxxx-x/xxxx/xx Guanzhou Hu, Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau Abstract . We present Bodega , the first consensus protocol that serves linearizable reads locally from any desired node, regardless of interfering writes. Bodega achieves this via a novel roster leases algorithm that safeguards the roster , a new notion of cluster metadata. The roster is a generalization of leadership; it tracks arbitrary subsets of replicas as responder nodes for local reads. A consistent agreement on the roster is established through roster leases, an all-to-all leasing mechanism that generalizes existing all-to-one leasing approaches (Leader Leases, Quorum Leases), unlocking a new point in the protocol design space. Bodega further employs optimistic holding and early accept notifications to minimize interruption from interfering writes, and incorporates smart roster coverage and lightweight heartbeats to maximize practicality. Bodega is a non-intrusive extension to classic consensus; it imposes no special requirements on writes other than a responder-covering quorum. We implement Bodega and related works in Vineyard, a protocol-generic replicated key-value store written in async Rust. We compare it to previous protocols (Leader Leases, EPaxos, PQR, and Quorum Leases) and two production coordination services (etcd and ZooKeeper). Bodega speeds up average client read requests by 5.6x ∼ \sim 13.1x on real WAN clusters versus previous approaches under moderate write interference, delivers comparable write performance, supports fast proactive roster changes as well as fault tolerance via leases, and closely matches the performance of sequentially-consistent etcd and ZooKeeper deployments across all YCSB workloads. We will open-source Vineyard upon publication. 1. Introduction Paxos-based consensus ( Lamport 1998 ; Lamport 2001 ; Lampson 2001 ) (and protocols alike ( Ongaro and Ousterhout 2014 ; Oki and Liskov 1988 ) ) serves as a critical foundation for modern distributed systems infrastructure. Originally used in limited contexts, e.g., for bespoke configuration information as in Petal ( Lee and Thekkath 1996 ) , for critical metadata stores such as etcd ( etcd 2023 ; Rensin 2015 ) and FireScroll ( FireScroll 2023 ; Redpanda 2024 ) , and for lock services such as Chubby ( Burrows 2006 ) , consensus now forms the foundation of widely used cloud-native databases such as Spanner ( Corbett et al. 2013 ) , CockroachDB ( VanBenschoten et al. 2022 ) , TiDB ( Huang et al. 2020 ) , ScyllaDB ( ScyllaDB 2023 ) , and Physalia ( Brooker et al. 2020 ) . In these systems, simple access semantics are critical, enabling scalable services to be readily built atop them ( Artem on StackOverflow 2017 ; Barr 2023 ) . In particular, linearizability is a strong consistency level they strive to provide: for interrelated requests, clients observe a real-time serial ordering, as if talking to a single node ( Herlihy and Wing 1990 ; Hu et al. 2024a ) . Local Linearizable Reads . Delivering high performance in linearizable systems remains a daunting challenge. In the cloud era, systems replicate critical data across multiple geographically-distinct availability zones ( AWS 2024a ; Cloud 2024 ; Microsoft 2024 ) , to guard against correlated failures caused by power outage, fire, natural disaster, or operator error ( Centre 2024 ; Veeraraghavan et al. 2018 ; Gunawi et al. 2014 ; Butler 2024 ) . By spreading replicas globally, robustness is achieved, but at the cost of performance due to quorum round trips ( Lee et al. 2015 ) . The physical distribution of replicas yields an opportunity to serve read requests locally from a client’s nearest replica. Reads comprise a majority of the workloads ( Cooper et al. 2010 ; Pasuparthy and Agarwal 2023 ; Optics 2021 ; AWS 2024b ) ; achieving local reads can greatly reduce read latency and drastically increase overall throughput. Existing Solutions Fall Short . Existing consensus protocols have demonstrated effective wide-area optimizations, but none, to our knowledge , supports coherently fast linearizable reads for workloads containing even small amounts of interfering writes . Leaderless protocols ( Lamport 2005 ; Mao et al. 2008 ; Moraru et al. 2013 ; Katsarakis et al. 2020 ; Charapko et al. 2019 ; Ryabinin et al. 2024 ) allow near quorums but not local reads. Others explore flexible quorums ( Howard et al. 2016 ; Guarnieri and Charapko 2023 ; Uluyol et al. 2020 ; Herlihy 1987 ; Lamport et al. 2009 ) , utilize special hardware or client validation ( Geng et al. 2022 ; Yi et al. 2023 ; Li et al. 2016 ; Ports et al. 2015 ; Du et al. 2014 ; Takruri et al. 2020 ; Arun et al. 2017 ) , or exploit API semantics favoring writes ( Ganesan et al. 2020 ; Ganesan et al. 2021 ; Luo et al. 2024 ; Park and Ousterhout 2019 ; Ongaro 2014 ; Renesse and Schneider 2004 ; Fouto et al. 2022 ; Zhao et al. 2018 ) . Read leases (covered later) ( Baker et al. 2011 ; Chandra et al. 2007 ; Moraru et al. 2014a ; Moraru et al. 2014b ; Gray and Cheriton 1989 ; Chandra et al. 2016 ; Bi et al. 2022 ) are so far the most compelling, but are only effective at the leader or during quiescent periods without interfering writes. Figure 0 . Frequency of touching a node on the critical path of reads by a client near S4, in a cluster where S0 is the leader, with infrequent writes. Ideal outcome is 100% at S4. Self-Containment Necessitates Leases . A primary challenge of designing consensus protocols for critical workloads is that the protocols must be self-contained , i.e., they cannot depend on external services to deliver essential information about the current role of nodes. Self-containment is needed for several reasons. First, to provide local linearizable reads, the consensus protocol must know whether or not the local data is the most recent; contacting an external service to obtain this information would defeat the purpose of local reads. Second, given that fault tolerance must be provided, having external dependencies would reduce its guarantees to those of the external services ( KRaft 2025 ; Redpanda 2024 ; VanBenschoten et al. 2022 ) . Within the design space of self-contained protocols, we observe that leases are a vital and powerful primitive. They carry timed promises that naturally tolerate faults through expiration ( Gray and Cheriton 1989 ) , while only requiring bounded clock drifts (typical in today’s cloud environments ( Martin et al. 2010 ; Hunt 2017 ; Geng et al. 2022 ; Lee et al. 2016 ) ). This opens the gateway to local linearizable read protocols. Leases Were Not Fully Exploited . Existing lease-infused protocols, however, do not employ the most suitable types of promises for local reads, and thus cannot fully realize their potential. As a motivating example, Figure 1 shows a 5-site cluster where S0 is the leader (and S4 is a local-read-enabled replica, if eligible), and reports the frequency of servers being touched by read requests from a client near S4. The workload contains 99% reads and only 1% writes, which favors existing approaches. Classic consensus (MultiPaxos) requires a majority accept quorum around S0. Leader Leases only protect