LARK -- Linearizability Algorithms for Replicated Keys in Aerospike
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915593963175936 |
|---|---|
| author | Goodng, Andrew Porter, Kevin Lopatic, Thomas Shinde, Ashish Sayyaparaju, Sunil Seshadri, Srinivasan Srinivasan, V. |
| author_facet | Goodng, Andrew Porter, Kevin Lopatic, Thomas Shinde, Ashish Sayyaparaju, Sunil Seshadri, Srinivasan Srinivasan, V. |
| contents | We present LARK (Linearizability Algorithms for Replicated Keys), a synchronous replication protocol that achieves linearizability while minimizing latency and infrastructure cost, at significantly higher availability than traditional quorum-log consensus. LARK introduces Partition Availability Conditions (PAC) that reason over the entire database cluster rather than fixed replica sets, improving partition availability under independent failures by roughly 3x when tolerating one failure and 10x when tolerating two. Unlike Raft, Paxos, and Viewstamped Replication, LARK eliminates ordered logs, enabling immediate partition readiness after leader changes -- with at most a per-key duplicate-resolution round trip when the new leader lacks the latest copy. Under equal storage budgets -- where both systems maintain only f+1 data copies to tolerate f failures -- LARK continues committing through data-node failures while log-based protocols must pause commits for replica rebuilding. These properties also enable zero-downtime rolling restarts even when maintaining only two copies. We provide formal safety arguments and a TLA+ specification, and we demonstrate through analysis and experiments that LARK achieves significant availability gains. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_01843 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | LARK -- Linearizability Algorithms for Replicated Keys in Aerospike Goodng, Andrew Porter, Kevin Lopatic, Thomas Shinde, Ashish Sayyaparaju, Sunil Seshadri, Srinivasan Srinivasan, V. Distributed, Parallel, and Cluster Computing Databases We present LARK (Linearizability Algorithms for Replicated Keys), a synchronous replication protocol that achieves linearizability while minimizing latency and infrastructure cost, at significantly higher availability than traditional quorum-log consensus. LARK introduces Partition Availability Conditions (PAC) that reason over the entire database cluster rather than fixed replica sets, improving partition availability under independent failures by roughly 3x when tolerating one failure and 10x when tolerating two. Unlike Raft, Paxos, and Viewstamped Replication, LARK eliminates ordered logs, enabling immediate partition readiness after leader changes -- with at most a per-key duplicate-resolution round trip when the new leader lacks the latest copy. Under equal storage budgets -- where both systems maintain only f+1 data copies to tolerate f failures -- LARK continues committing through data-node failures while log-based protocols must pause commits for replica rebuilding. These properties also enable zero-downtime rolling restarts even when maintaining only two copies. We provide formal safety arguments and a TLA+ specification, and we demonstrate through analysis and experiments that LARK achieves significant availability gains. |
| title | LARK -- Linearizability Algorithms for Replicated Keys in Aerospike |
| topic | Distributed, Parallel, and Cluster Computing Databases |
| url | https://arxiv.org/abs/2511.01843 |