标题： LARK - Aerospike中复制键的线性化算法 显示英文标题

标题： LARK - Linearizability Algorithms for Replicated Keys in Aerospike

摘要： 我们提出LARK（复制键的线性化算法），这是一种同步复制协议，在最小化延迟和基础设施成本的同时，实现了线性化，其可用性显著高于传统的多数日志共识。 LARK引入了分区可用性条件（PAC），而不是固定的副本集，对整个数据库集群进行推理，在容忍一个故障时，独立故障下的分区可用性提高了约3倍，在容忍两个故障时提高了10倍。 与Raft、Paxos和视图确认复制不同，LARK消除了有序日志，使得在领导更换后能够立即准备好分区——当新领导没有最新副本时，最多需要一次每键的重复解决往返。 在相同的存储预算下——两个系统都仅维护f+1个数据副本以容忍f个故障——LARK在数据节点故障时仍能继续提交，而基于日志的协议必须暂停提交以重建副本。 这些特性还使得即使仅维护两个副本，也能实现零停机时间的滚动重启。 我们提供了形式化的安全论证和TLA+规范，并通过分析和实验表明，LARK实现了显著的可用性提升。 显示英文摘要

摘要： 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.