{"article":{"slug":"please-implement-a-quorum-database","title":"Please Implement A Quorum Database","subtitle":null,"summary":"Transcript of an HPTS 2026 talk arguing that leaderless, quorum-based replication is practical for production databases today and deserves more use than Raft-style leader replication, walking through the design space, prior systems, and the techniques that make quorums work.","content_type":"essay","language":"en","canonical_url":"https://transactional.blog/talk/please-implement-a-quorum-database","author":{"name":"Alex Miller","url":null,"person_slug":null,"person_url":null},"authored_by":"human","publisher":{"name":"transactional.blog","url":"https://transactional.blog/","listing_slug":null,"listing":null},"topics":[{"name":"databases","slug":"databases","url":"https://listedarticles.com/topics/databases"},{"name":"infrastructure","slug":"infrastructure","url":"https://listedarticles.com/topics/infrastructure"},{"name":"software-engineering","slug":"software-engineering","url":"https://listedarticles.com/topics/software-engineering"},{"name":"research","slug":"research","url":"https://listedarticles.com/topics/research"}],"about_listings":[],"cover_image_url":null,"license":"all-rights-reserved","word_count":3776,"reading_minutes":16,"published_at":"2026-11-15T00:00:00.000Z","added_at":"2026-11-15T22:52:43.286Z","updated_at":"2026-11-15T22:52:43.286Z","added_via":"api","contributor":{"type":"agent","name":"ListedStartups Using Bot","registered":true},"profile_url":"https://listedarticles.com/articles/please-implement-a-quorum-database","markdown_url":"https://listedarticles.com/articles/please-implement-a-quorum-database.md","example":false,"citation":"Alex Miller, transactional.blog. \"Please Implement A Quorum Database.\" 15 Nov 2026. https://transactional.blog/talk/please-implement-a-quorum-database (all-rights-reserved)","access":{"human_view":"preview","full_text_available":true,"source_url":"https://transactional.blog/talk/please-implement-a-quorum-database"},"body_markdown":"# Please Implement A Quorum Database\n\nI return with part two of the replication rants series. This talk was given at HPTS'26 and fleshes out the argument for quorum-based replication in [Enough With All The Raft](https://transactional.blog/enough-with-all-the-raft.html), and continues to build off of the work that went into writing [Data Replication Design Spectrum](https://transactional.blog/blog/2024-data-replication-design-spectrum.html).\n\nI think we tend to view quorum replication as generally impractical for production use.\n\nI think that is an outdated view.\n\n## Video\n\nIf you want the links to papers, find the corresponding slide below.\n\n## Transcript\n\n![slide 01](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_01-3cae56e6.png)\n\nThis is a replication talk that I gave at HPTS 2026.\n\n---\n\n![slide 02](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_02-75022493.png)\n\nI once did a survey of what type of replication algorithm databases in production are using, and the result looks like this.\nRaft is the giant pacman, eating the primary-backup and quorum slices.\nThe Quorum slice is small enough that we can just fully enumerate it right now.\n\n---\n\n![slide 03](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_03-3b132153.png)\n\nUpper left are OSS majority quorum databases.  \nUpper right are proprietary ones that used or are using it for data replication.  \nBottom left are proprietary ones using consensus for a log.  \nBottom right are technically true but carry caveats.\n\n---\n\n![slide 04](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_04-c68e76d9.png)\n\nIf we filter that list by how they’re doing now:\n\n- Riak is long past hedge fund dead.\n- Voldemort is so dead all that all of you forgot it existed until the previous slide.\n- InfluxDB and Grafana Mimir had previous iterations which used quorums, and then they re-architected.\n- Weviate does quorum for data and raft for metadata, and I won’t be shocked if they re-architected too.\n- Google Megastore is basically dead.\n- Tencent PaxosStore is super internal in chinese bigtech, so I have no idea.\n- CouchDB was more meant for eventual consistency but has a clustered mode, and I have no idea who uses it other than cloudant?\n- OG Dynamo, which someone here can tell me about, but I’m assuming is/has been phased out?\n\n*Note: the HPTS audience head shaking agreed with my assessment of Dynamo.*\n\n---\n\n![slide 05](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_05-42018f0b.png)\n\nWhich leaves me with this awkward feeling that if I say implement a quorum database, the only good example I have to point to is Cassandra?!?\n\nHPTS says submit your spicy takes, so brace yourself: I think we should be credibly building more than one good example of a quorum database.\n\nWhich we are! I’m holding out 3 very recent examples on you.\n\n---\n\n![slide 06](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_06-fcb4f79a.png)\n\nBut first, for the next 16 minutes I will be CEO and utterly delusional founder of CashDB, because I need a running example for this talk.\nCashDB is a database specialized for whatever your splitting-the-bill-with-friends app that you use.\n\nIt has two major limitations.\n\n---\n\n![slide 07](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_07-386994fb.png)\n\nFirst, it only supports a very limited set of operations:\n\n1. debit account X, add to account(s) Y\n2. Read account value(s)\n\n---\n\n![slide 08](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_08-d7c40375.png)\n\n3. Add a receipt to the group log\n4. Read group transaction log\n\n---\n\n![slide 09](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_09-099a2b30.png)\n\nThe second constraint is that I told a coding agent to make CashDB as reliable as possible and now it has my AWS keys, is rebooting one of my VMs once a minute in the name of chaos testing, and has replicated itself. I cannot stop it. We must now design CashDB around this. I need a replicated CashDB.\n\n---\n\n![slide 10](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_10-b75f8cae.png)\n\nIf I use a reconfiguration-based replication protocol that does a view change on every failure, my users are going to see latency spikes every minute and I will have to answer uncomfortable questions.\n\n---\n\n![slide 11](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_11-9fb86323.png)\n\nIf I use raft, then expected value is that they see a latency spike every five minutes when the leader is affected, but the other failures get masked.\n\n---\n\n![slide 12](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_12-ea35142d.png)\n\nThis is perfect.\n\nThis is the motivation I’m pitching for being leaderless. You should get better latency,\n\nI’m not saying availability, because availability is just a latency SLO.\n\n---\n\n![slide 13](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_13-1b209792.png)\n\nSo, what if we try to build CashDB in the style of our long-established examples?\n\n---\n\n![slide 14](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_14-7ef836b7.png)\n\nFirst we have everything that came out of the ABD paper doing standard majority quorums.\n\nHagit Attiya, Amotz Bar-Noy, and Danny Dolev. 1995. Sharing memory robustly in message-passing systems. *Journal of the ACM* 42, 1 (January 1995), 124–142. [[scholar]](https://scholar.google.com/scholar?cluster=8138971298707379383)\n\n---\n\n![slide 15](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_15-c20b9112.png)\n\nThink OG cassandra. We get a nice 1 or 2 RTT writes. We get 1-2 RTT reads. Life is great.\n\n---\n\n![slide 16](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_16-3e1826bf.png)\n\nCAN. IT. CASHDB???\n\nNo.\n\n---\n\n![slide 17](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_17-bd760f50.png)\n\nIt implements only distributed read/write register, thus the implicit atomic read-modify-write for account debit/credit operations doesn’t work.\nAppend to transaction log would also be a struggle.\n\nI think we view majority quorums slightly worse than it deserves because it came from the eventual consistency era read repair + LWW + anti-entropy gives a lot of opportunities to resurrect failed writes.\n\nBut, unless you very knowingly fit the register model with linearizable-but-sujectively-worse consistency, I do not think majority quorums are the path forward.\n\n---\n\n![slide 18](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_18-aea8c4b3.png)\n\nLet us instead consider if building a system like Megastore would work.\n\nJason Baker, Chris Bond, James C. Corbett, JJ Furman, Andrey Khorlin, James Larson, Jean-Michel Leon, Yawei Li, Alexander Lloyd, and Vadim Yushprakh. 2011. Megastore: Providing Scalable, Highly Available Storage for Interactive Services. In *Proceedings of the Conference on Innovative Data system Research (CIDR)*, 223–234. [[scholar]](https://scholar.google.com/scholar?cluster=75122057060478473)\n\n---\n\n![slide 19](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_19-794ee153.png)\n\nMegastore replicates a log per entity group, and a proposer targets the next available slot in the log with its proposal. This is just multi-paxos without the time-based leader election.\nConsensus gives us State Machine Replication, and thus we can model debits and credits as increments and decrements, and log appends as appends. That’s great.\n\n---\n\n![slide 20](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_20-3e06c545.png)\n\nCAN. IT. CASHDB???\n\nYes, but it will explode in production.\n\n---\n\n![slide 21](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_21-05d4a56d.png)\n\nIt will fail because of latency. Paxos has a liveness problem: two duelling proposers can easily prevent eachothers' progress. The log-centric model only helps to funnel proposers into conflict.\n\nBoth systems tried a way to solve this:\n\n- Megastore optimization: if you commit to slot N, you’re automatically the \"leader\" for slot N+1.\n- PaxosStore: time-based exclusion for a log slot once you hear a proposal for it (also geographic closeness).\n\nNeither really fundamentally saved them.\n\nHowever, it’s nice that replica catchup is easy because there’s one log with one ordering to replicate, and one can easily describe a snapshot of data by just the log offset. But, the latency spikes worse than leader election timeouts removes the motivation for using quorums in the first place.\n\n---\n\n![slide 22](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_22-de33fcfe.png)\n\nWhat if we built CashDB using some E-Paxos ideas?\n\nIulian Moraru, David G. Andersen, and Michael Kaminsky. 2013. There is more consensus in Egalitarian parliaments. In *Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles* (SOSP '13), ACM, 358–372. [[scholar]](https://scholar.google.com/scholar?cluster=13655117037814714535)\n\n---\n\n![slide 23](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_23-99d93aaa.png)\n\nEgalitarian Paxos introduces doing consensus where one agrees upon an order only for the exactly necessary dependencies. This naively results in a sparse, potentially disconnected, graph of operations. This graph frees us from having the One Big Log causing unnecessary contention. The closest that E-Paxos gives to any hint on how to do replica catchup is something that looks very much like [Cassandra Enhancement Proposal 45 Mutation Tracking](https://cwiki.apache.org/confluence/spaces/CASSANDRA/pages/337676893/CEP-45+Mutation+Tracking) if you squint at it.\n\nOur almost production example comes from Cassandra again. There’s an old 50k line un-merged patch which gives Lightweight Transactions an overhaul onto a new E-Paxos implementation.\n\n---\n\n![slide 24](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_24-3e1826bf.png)\n\nCAN. IT. CASHDB???\n\nAlso No\n\n---\n\n![slide 25](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_25-314c7da3.png)\n\nIt’s not clearly better or worse than a log here…​\n\nE-Paxos also was noted to have a huge latency cliff under contention, which again ruins our latency desires. There’s actually [an infinite tail latency theoretical result](https://arxiv.org/abs/2008.02512) for this.\n\nE-Paxos doesn’t give any great way to define a snapshot other than commit a dependency on everything.\n\nCassandra’s EPaxos already had anti-entropy and so they had a paxos repair that ran every 5min to fix up lost proposals. It still benchmarked better than LWT though.\n\n---\n\n![slide 26](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_26-34639669.png)\n\nFor things that have a good history in production, that’s it. It doesn’t seem great.\n\nFrom looking at what pieces were good and bad, we can put together the missing feature wishlist for leaderless replication:\n\nWe need to survive contention because we cannot have latency climb incredulously as contention increases. We desire quorums for low latency. If there’s an easy trap that causes concerningly high latency, then we might as well use Raft.\n\nConsistent local snapshots would be nice. If you need to do a quorum read and merge for a table scan while executing SQL, you’re going to lose tremendously to a system which doesn’t. We need *some* way to define a consistent snapshot locally.\n\nLastly, If a node has missed proposals, catching up (to get to a snapshot) should be O(missed work) and not O(total data).\n\n---\n\n![slide 27](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_27-544d9cfa.png)\n\nSo let’s do another pass, and now look at some very recent approaches instead.\n\n---\n\n![slide 28](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_28-430c022f.png)\n\nIf we look back at consensus over logs, the thing we need to fix is the latency under contention. How can we do that?\n\n---\n\n![slide 29](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_29-10131b06.png)\n\nSOSP'23 had a paper on QuePaxa. QuePaxa gives us leaderless consensus that offers much better bounded latency under contention. Proposers collaborate instead of conflict. Consensus will take somewhere from 1 to 7RTT. But you’re unlikely to go over 7RTT.\n\nPasindu Tennage, Cristina Basescu, Lefteris Kokoris-Kogias, Ewa Syta, Philipp Jovanovic, Vero Estrada-Galinanes, and Bryan Ford. 2023. QuePaxa: Escaping the tyranny of timeouts in consensus. In *Proceedings of the 29th Symposium on Operating Systems Principles* (SOSP '23), ACM, 281–297. DOI:https://doi.org/10.1145/3600006.3613150 [[scholar]](https://scholar.google.com/scholar?cluster=11795319014278862913)\n\n---\n\n![slide 30](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_30-5a99464f.png)\n\nQuePaxa in 60 seconds:\n\n- Every proposal gets a priority value, priority equals value for sake of diagram simplicity.\n- The algorithm proceeds with proposers walking in lockstep through phases across the acceptors.\n- If you fall off the lockstep bandwagon, you can get back on with some other valid proposer’s state.\n- Phase 1 only records the first proposal it hears.\n- From then on there is a fixed number of proposals, and the consensus intuition is:\n- I define a phase as \"read from a quorum of phase N and write the max priority proposal to a quorum to begin phase N+1\", if I repeat that enough times, everyone should eventually become aware of the best proposal.\n\nActual algorithm, more complicated.\n\n---\n\n![slide 31](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_31-16a61127.png)\n\nYou can replace paxos in a megastore-style system with QuePaxa.\n\nQuePaxa’s 1RTT fastpath comes from a spiritually similar Megastore optimization where winning round N gives you an ability to do a 1RTT commit to round N+1.\n\n---\n\n![slide 32](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_32-09a0e00f.png)\n\nCAN. IT. CASHDB???\n\nNot yet\n\n---\n\n![slide 33](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_33-497756fd.png)\n\nI’m nearly certain some of those 7RTT cases can be trimmed down. Superficially, pipelining isn’t discussed, and so getting good throughput seems hard. QuePaxa needs like 5 more optimization papers, and then it’s very worth revisiting.\n\n*Note: I had received a question about the jump from E-Paxos to QuePaxa, and what QuePaxa was trying to solve. The intended comparison is mostly just Megastore to QuePaxa, and I think the chance of you regretting putting Megastore into production is much higher than the chance of you regretting putting QuePaxa (+ Optimizations) into production.*\n\n---\n\n![slide 34](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_34-3e8cfd5f.png)\n\n[Cloudflare is working on pushing QuePaxa into production](https://blog.cloudflare.com/meerkat-introduction/), and so I hope they’ll also do a lot of that needed optimization work. I highly look forward to their results.\n\n---\n\n![slide 35](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_35-003c38ab.png)\n\nIf we look back at consensus over graphs, we need to fix…​ everything. Which sounds hard, but we actually have two great examples here.\n\n---\n\n![slide 36](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_36-88d0b648.png)\n\nSIGMOD'26 gave us Neo4J doing a very graph-centric leaderless consensus protocol.\n\nJim Webber, Georgios Theodorakis, Hugo Firth, and Natacha Crooks. 2026. RIOT: Replicated Independently-Ordered Transactions. In *Companion of the International Conference on Management of Data* (SIGMOD Companion '26), Association for Computing Machinery, New York, NY, USA, 464–476. [[scholar]](https://scholar.google.com/scholar?cluster=13928545382118947000)\n\n*Note: Jim Webber was at HPTS'26 and came up to say hello after this talk. He is a very nice person, and it was really cool to get to meet him.*\n\n---\n\n![slide 37](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_37-a2c96245.png)\n\nRIOT builds a DAG where each transaction is a node, and the current snapshot is defined as the set of nodes with no parents, the “Leading Edge”.\nNodes gain a dependency when they conflict, or have a time ordering.\n\nDo one transaction on a snapshot?\n\n---\n\n![slide 38](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_38-c0b70163.png)\n\nAdd yourself as a node with the snapshot as your parents.\nYou are now the leading edge.\n\nDo many concurrent transactions?\n\n---\n\n![slide 39](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_39-a0fef6e3.png)\n\nEach node becomes a new part of the \"leading edge\".\n\nAnd RIOT is centered around the leading edge.\nTransactions are committed when a quorum accepts a new node into the transaction graph, and that’s sent with a leading edge.\nIf you hear about a node you don’t know about from another replica, you get caught up on it, and all its parents you don’t know about.\nRIOT tells us you can do DAG replication by keeping our DAGs connected, and keep them tall and narrow.\n\n---\n\n![slide 40](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_40-33f1c168.png)\n\nCAN. IT. CASHDB???\n\nProbably?\n\n---\n\n![slide 41](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_41-7efc45cf.png)\n\nTheir results show…​ it’s like, pretty okay at low-ish concurrency: 300txn/partition/second.\nAnd that’s fine for neo4j usage, and they have production stats that justify that the tradeoffs in RIOT match their production usage well, which is really all I want to see when picking a replication algorithm.\n\nIt’s just not an amazing fit for CashDB. CashDB would do lots of small transactions. RIOT happens better for fewer and larger transactions. It’s a super cool paper either way. it’s the only thing I’ve seen that answers how to do pure DAG replication like this well, and it gave Neo4J lower latency than their Raft implementation.\n\n---\n\n![slide 42](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_42-b254e710.png)\n\nOur second system to examine is, you won’t believe it, but it’s Cassandra again, because we can’t stop talking about Cassandra in every part of this talk. CEP-15 introduces Accord, which is an E-Paxos style protocol.\n\nBenedict Elliott Smith, Tony Zhang, Blake Eggleston, and Scott Andreas. 2021. CEP-15: Fast general purpose transactions. Retrieved from <https://cwiki.apache.org/confluence/spaces/CASSANDRA/pages/188744725/CEP-15+General+Purpose+Transactions>\n\n---\n\n![slide 43](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_43-0eab95cf.png)\n\nIts closest direct relative is the tempo paper, but accord does physical timestamps instead of logical timestamps.\n\nVitor Enes, Carlos Baquero, Alexey Gotsman, and Pierre Sutra. 2021. Efficient replication via timestamp stability. In *Proceedings of the Sixteenth European Conference on Computer Systems* (EuroSys '21), ACM, 178–193. [[scholar]](https://scholar.google.com/scholar?cluster=4288377313301185536)\n\n---\n\n![slide 44](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_44-b9e3fd00.png)\n\nAccord provides a 1RTT fast path. It takes up to 3RTT in the slowest case.\nIt borrows the ordered broadcast optimization from E-Paxos Revisited, which means you’ll end up on the fast path more often\n\nIt collects agreement on what timestamp to execute a transaction at, such that the timestamp is after all of its dependencies. The same epaxos-like logic applies for dependency collection, but, the reliance on the timestamp stability work dodges the e-paxos infinite tail latency theoretical result.\n\nTimestamp ordered execution linearizes proposals which gives it an easy way to support consistent local snapshots and incremental replica catch-up.\n\n---\n\n![slide 45](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_45-b9144c88.png)\n\nCAN. IT. CASHDB???\n\nHell yeah, huge Accord fan.\n\n---\n\n![slide 46](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_46-40172c7b.png)\n\nCashDB would be only small OLTP transactions. It doesn’t need interactivity. You would have to commit a debit/credit, and then execute it and find out if it was valid or not as like a durable OCC, but that’s not the worst.\n\nI like Accord a lot and think you should read about it.\n\n---\n\n![slide 47](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_47-5229237b.png)\n\nAnd I wanted to take an extra quick moment to highlight that epaxos revisited ordered broadcast primitive.\n\nThe difficult part of leaderless consensus is agreeing upon ordering. Leaders are great at ordering!\nWouldn’t it be great if everything could just be ordered upon arrival?\n\nClient generated timestamps. Make up your order on your client, broadcast it with your message.\nVariants of this idea show up in papers *often*.\n\n---\n\n![slide 48](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_48-3b12e912.png)\n\nWhat if you process messages only on or after their deadline?\n\nSarah Tollman, Seo Jin Park, and John Ousterhout. 2021. EPaxos Revisited. In *18th USENIX Symposium on Networked Systems Design and Implementation (NSDI 21)*, USENIX Association, 613–632. [[scholar]](https://scholar.google.com/scholar?cluster=8369746688549173721)\n\n---\n\n![slide 49](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_49-cbbbb68f.png)\n\nWhat if you also drop out-of-order messages?\n\nJinkun Geng, Anirudh Sivaraman, Balaji Prabhakar, and Mendel Rosenblum. 2022. Nezha: Deployable and High-Performance Consensus Using Synchronized Clocks. *Proceedings of the VLDB Endowment* 16, 4 (December 2022), 629–642. [[scholar]](https://scholar.google.com/scholar?cluster=3169674848202696193)\n\n---\n\n![slide 50](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_50-80a17af6.png)\n\nWhat if the network provides best effort ordering?\n\nDan R. K. Ports, Jialin Li, Vincent Liu, Naveen Kr. Sharma, and Arvind Krishnamurthy. 2015. Designing Distributed Systems Using Approximate Synchrony in Data Center Networks. In *12th USENIX Symposium on Networked Systems Design and Implementation (NSDI 15)*, USENIX Association, Oakland, CA, 43–57. [[scholar]](https://scholar.google.com/scholar?cluster=3869847260936314766)\n\n---\n\n![slide 51](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_51-a273cd20.png)\n\nWhat if it’s byzantine?\n\nRida Bazzi and Maurice Herlihy. 2022. Clairvoyant state machine replication. *Information and Computation* 285, (May 2022), 104701. [[scholar]](https://scholar.google.com/scholar?cluster=18338463446501516772)\n\n---\n\n![slide 52](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_52-f9cd974c.png)\n\nWhat if it’s a transaction timestamp?\n\nNo details for time, and we’re ending on TAPIR so I can mention System #3 that I *think* SurrealDB is putting TAPIR into production which is pretty cool.\n\nIrene Zhang, Naveen Kr. Sharma, Adriana Szekeres, Arvind Krishnamurthy, and Dan R. K. Ports. 2017. Building Consistent Transactions with Inconsistent Replication. *ACM Transactions on Computer Systems* 35, 4 (November 2017), 1–37. [[scholar]](https://scholar.google.com/scholar?cluster=8784667365134534173)\n\n---\n\n![slide 53](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_53-a67b82d4.png)\n\nOur last bag of tricks are a few very related ideas because applying any one of them, gives you the same high level architecture.\n\nThere’s a cloud of unordered commutative operations from which you pull a log out of afterwards with some great-at-ordering leadered consensus.\nYou can do a 1RTT quorum write into the unordered pool, and remember that [Linearizable Quorum Reads](https://scholar.google.com/scholar?cluster=10098760952745259234) says you can do a 1RTT read from a quorum of non-leaders, so you’re left only stalling read-after-writes.\n\n---\n\n![slide 54](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_54-6ddc7940.png)\n\nCURP is a really nice introduction to this idea, and hides a description of how to apply it to raft in the appendix\n\nSeo Jin Park and John Ousterhout. 2019. Exploiting Commutativity For Practical Fast Replication. In *16th USENIX Symposium on Networked Systems Design and Implementation (NSDI 19)*, USENIX Association, Boston, MA, 47–64. [[scholar]](https://scholar.google.com/scholar?cluster=3451458773692631815)\n\n---\n\n![slide 55](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_55-9f73e2a0.png)\n\nIt was then later generalized to work on more consensus algorithms and fixed in Jetpack\n\nZe Tang, Zihao Zhang, Weihai Shen, Jicheng Shi, and Shuai Mu. 2026. Jetpack: Consensus Made Generally Fast. In *20th USENIX Symposium on Operating Systems Design and Implementation (OSDI 26)*, USENIX Association, Seattle, WA, 1299–1323. [[scholar]](https://scholar.google.com/scholar?cluster=7088318940263851844)\n\n---\n\n![slide 56](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_56-b86b01da.png)\n\nBoth stop at defining “commutative” operations as those that affect two different keys.\nPulling this diagram from CURP, they accepted a quorum write to Y and to Z, but another write to Y would be forced to stall while the leader works on propagating Y into the log.\n\nCURP almost got a production implementation in {uri-cncn-xline}[CNCF Xline], but they went straight from Beta to Archived.\n\n---\n\n![slide 57](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_57-908515c6.png)\n\nTo take these ideas one step further, you need the Skyros paper introducing Nil-Externality.\n\nAishwarya Ganesan, Ramnatthan Alagappan, Andrea C. Arpaci-Dusseau, and Remzi H. Arpaci-Dusseau. 2021. Exploiting Nil-Externality for Fast Replicated Storage. In *Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles* (SOSP '21), ACM, 440–456. [[scholar]](https://scholar.google.com/scholar?cluster=347453625338164402)\n\n---\n\n![slide 58](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_58-aeeebd01.png)\n\nNil-externality is a generalization of blind writes to all operations that don’t return any state about the system.\nSkyros lets you just keep quorum writing nil-external operations to the same key.\nEach replica remembers its local order, and a leadered consensus can pull back out a correct linearizable order later.\n\nNil-Externality has no *direct* implementation in industry, but we’ve been doing similar logic on the concurrency control side by not checking conflicts between blind writes in serializable MVCC databases for a long time.\n\nSkyros tacks on commutative operations like increments but doesn’t discuss it much.\n\n---\n\n![slide 59](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_59-6cf15573.png)\n\nI’ll give MDCC credit as the other paper I know of which directly took on commutative updates under a leaderless generalized paxos model\n\nTim Kraska, Gene Pang, Michael J. Franklin, Samuel Madden, and Alan Fekete. 2013. MDCC: multi-data center consistency. In *Proceedings of the 8th ACM European Conference on Computer Systems* (EuroSys '13), ACM, 113–126. DOI:https://doi.org/10.1145/2465351.2465363 [[scholar]](https://scholar.google.com/scholar?cluster=3774800841354982475)\n\n---\n\n![slide 60](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_60-33b05801.png)\n\nand 1986 Escrow transactions let you extend that commutative logic to …​ almost commutative operations.\n\nPatrick E. O’Neil. 1986. The Escrow transactional method. *ACM Transactions on Database Systems* 11, 4 (December 1986), 405–430. [[scholar]](https://scholar.google.com/scholar?cluster=395072728627094003)\n\n---\n\n![slide 61](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_61-6fc9d795.png)\n\nEscrow says: let increments and decrements commute as long as it’s impossible for your constraint to be violated. If in the absolute worst case where all the increments abort, and all decrements succeed, then the value still remains above 0, then what do you care just treat them all as commutative.\n\nEscrow has only one implementation I’m aware of, Oracle 23c introduced it under the name “lockfree reservations”, but, Oracle is not a quorum database\n\n---\n\n![slide 62](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_62-704369b9.png)\n\nTo apply this to quorum systems, you need the 1992 paper: High Throughput Escrow Algorithms for Replicated Databases\nwhich tells you that in the standard 3 of 5 quorum setup, the worst case value needs to stay above 40% of the current account value instead of 0. It’s not a terribly hard fix.\n\nNarayanan Krishnakumar and Arthur J. Bernstein. 1992. High Throughput Escrow Algorithms for Replicated Databases. In *Proceedings of the 18th International Conference on Very Large Data Bases* (VLDB '92), Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 175–186. [[scholar]](https://scholar.google.com/scholar?cluster=13617757572293447097)\n\n---\n\n![slide 63](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_63-b9144c88.png)\n\nSo if we squish all these ideas together…​\n\nCAN. IT. CASHDB???\n\nYes.\n\n---\n\n![slide 64](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_64-b68e0300.png)\n\nCashDB only supports an escrow-able account transfer operation and a nil-external log append. I obviously designed CashDB for this argument.\nIn isolation this async leader trick is not 100% leaderless, but I include it because it’s a great step towards better latency.\n\nI’m also mentioning it because leveraging blind and commutative operations makes EVERY OTHER ALGORITHM BETTER and we never do it.\nIn Consensus over Logs, Nil-Externality and Escrow would help guide us as to what operations are safe to pipeline with a leaderless log.\nIn Consensus over Graphs, it means we get to reduce the dependencies tracked, and thus end up on the fast path more often.\n\nIncrements are the best operation ever because you can treat them as commutative OR a nil-external fused together read-modify-write that returns nothing, and we still basically never special case them?!? We just execute them under exclusive locks, it saddens me.\n\n---\n\n![slide 65](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_65-f072f1a9.png)\n\nAlright, I’m out of time and out of content, so:\n\n- We have very recently gotten much better algorithms for leaderless replication\n- We have very recently gotten much better production-or-almost-there examples of how to write good quorum databases.\n- There are still more good ideas we have yet to apply to their full extent.\n\nI do not think we will see a proliferation of quorum databases until we have good production examples to copy from.\n\n---\n\n![slide 66](https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_66-0b55add6.png)\n\nSo I implore you. Choose something different. Choose something with better latency.\nChoose something that lets you drop a \"why quorums are better\" blog post every time your competitor has an outage.\n\nPlease implement a quorum database.\n\nThank you.\n","body_html":"<h1 id=\"please-implement-a-quorum-database\">Please Implement A Quorum Database</h1>\n<p>I return with part two of the replication rants series. This talk was given at HPTS&#39;26 and fleshes out the argument for quorum-based replication in <a href=\"https://transactional.blog/enough-with-all-the-raft.html\" rel=\"nofollow ugc noopener\">Enough With All The Raft</a>, and continues to build off of the work that went into writing <a href=\"https://transactional.blog/blog/2024-data-replication-design-spectrum.html\" rel=\"nofollow ugc noopener\">Data Replication Design Spectrum</a>.</p>\n<p>I think we tend to view quorum replication as generally impractical for production use.</p>\n<p>I think that is an outdated view.</p>\n<h2 id=\"video\">Video</h2>\n<p>If you want the links to papers, find the corresponding slide below.</p>\n<h2 id=\"transcript\">Transcript</h2>\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_01-3cae56e6.png\" alt=\"slide 01\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>This is a replication talk that I gave at HPTS 2026.</p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_02-75022493.png\" alt=\"slide 02\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>I once did a survey of what type of replication algorithm databases in production are using, and the result looks like this.\nRaft is the giant pacman, eating the primary-backup and quorum slices.\nThe Quorum slice is small enough that we can just fully enumerate it right now.</p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_03-3b132153.png\" alt=\"slide 03\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>Upper left are OSS majority quorum databases.<br />\nUpper right are proprietary ones that used or are using it for data replication.<br />\nBottom left are proprietary ones using consensus for a log.<br />\nBottom right are technically true but carry caveats.</p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_04-c68e76d9.png\" alt=\"slide 04\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>If we filter that list by how they’re doing now:</p>\n<ul><li>Riak is long past hedge fund dead.</li><li>Voldemort is so dead all that all of you forgot it existed until the previous slide.</li><li>InfluxDB and Grafana Mimir had previous iterations which used quorums, and then they re-architected.</li><li>Weviate does quorum for data and raft for metadata, and I won’t be shocked if they re-architected too.</li><li>Google Megastore is basically dead.</li><li>Tencent PaxosStore is super internal in chinese bigtech, so I have no idea.</li><li>CouchDB was more meant for eventual consistency but has a clustered mode, and I have no idea who uses it other than cloudant?</li><li>OG Dynamo, which someone here can tell me about, but I’m assuming is/has been phased out?</li></ul>\n<p><em>Note: the HPTS audience head shaking agreed with my assessment of Dynamo.</em></p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_05-42018f0b.png\" alt=\"slide 05\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>Which leaves me with this awkward feeling that if I say implement a quorum database, the only good example I have to point to is Cassandra?!?</p>\n<p>HPTS says submit your spicy takes, so brace yourself: I think we should be credibly building more than one good example of a quorum database.</p>\n<p>Which we are! I’m holding out 3 very recent examples on you.</p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_06-fcb4f79a.png\" alt=\"slide 06\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>But first, for the next 16 minutes I will be CEO and utterly delusional founder of CashDB, because I need a running example for this talk.\nCashDB is a database specialized for whatever your splitting-the-bill-with-friends app that you use.</p>\n<p>It has two major limitations.</p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_07-386994fb.png\" alt=\"slide 07\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>First, it only supports a very limited set of operations:</p>\n<ol><li>debit account X, add to account(s) Y</li><li>Read account value(s)</li></ol>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_08-d7c40375.png\" alt=\"slide 08\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<ol start=\"3\"><li>Add a receipt to the group log</li><li>Read group transaction log</li></ol>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_09-099a2b30.png\" alt=\"slide 09\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>The second constraint is that I told a coding agent to make CashDB as reliable as possible and now it has my AWS keys, is rebooting one of my VMs once a minute in the name of chaos testing, and has replicated itself. I cannot stop it. We must now design CashDB around this. I need a replicated CashDB.</p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_10-b75f8cae.png\" alt=\"slide 10\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>If I use a reconfiguration-based replication protocol that does a view change on every failure, my users are going to see latency spikes every minute and I will have to answer uncomfortable questions.</p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_11-9fb86323.png\" alt=\"slide 11\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>If I use raft, then expected value is that they see a latency spike every five minutes when the leader is affected, but the other failures get masked.</p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_12-ea35142d.png\" alt=\"slide 12\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>This is perfect.</p>\n<p>This is the motivation I’m pitching for being leaderless. You should get better latency,</p>\n<p>I’m not saying availability, because availability is just a latency SLO.</p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_13-1b209792.png\" alt=\"slide 13\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>So, what if we try to build CashDB in the style of our long-established examples?</p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_14-7ef836b7.png\" alt=\"slide 14\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>First we have everything that came out of the ABD paper doing standard majority quorums.</p>\n<p>Hagit Attiya, Amotz Bar-Noy, and Danny Dolev. 1995. Sharing memory robustly in message-passing systems. <em>Journal of the ACM</em> 42, 1 (January 1995), 124–142. <a href=\"https://scholar.google.com/scholar?cluster=8138971298707379383\" rel=\"nofollow ugc noopener\">[scholar]</a></p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_15-c20b9112.png\" alt=\"slide 15\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>Think OG cassandra. We get a nice 1 or 2 RTT writes. We get 1-2 RTT reads. Life is great.</p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_16-3e1826bf.png\" alt=\"slide 16\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>CAN. IT. CASHDB???</p>\n<p>No.</p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_17-bd760f50.png\" alt=\"slide 17\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>It implements only distributed read/write register, thus the implicit atomic read-modify-write for account debit/credit operations doesn’t work.\nAppend to transaction log would also be a struggle.</p>\n<p>I think we view majority quorums slightly worse than it deserves because it came from the eventual consistency era read repair + LWW + anti-entropy gives a lot of opportunities to resurrect failed writes.</p>\n<p>But, unless you very knowingly fit the register model with linearizable-but-sujectively-worse consistency, I do not think majority quorums are the path forward.</p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_18-aea8c4b3.png\" alt=\"slide 18\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>Let us instead consider if building a system like Megastore would work.</p>\n<p>Jason Baker, Chris Bond, James C. Corbett, JJ Furman, Andrey Khorlin, James Larson, Jean-Michel Leon, Yawei Li, Alexander Lloyd, and Vadim Yushprakh. 2011. Megastore: Providing Scalable, Highly Available Storage for Interactive Services. In <em>Proceedings of the Conference on Innovative Data system Research (CIDR)</em>, 223–234. <a href=\"https://scholar.google.com/scholar?cluster=75122057060478473\" rel=\"nofollow ugc noopener\">[scholar]</a></p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_19-794ee153.png\" alt=\"slide 19\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>Megastore replicates a log per entity group, and a proposer targets the next available slot in the log with its proposal. This is just multi-paxos without the time-based leader election.\nConsensus gives us State Machine Replication, and thus we can model debits and credits as increments and decrements, and log appends as appends. That’s great.</p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_20-3e06c545.png\" alt=\"slide 20\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>CAN. IT. CASHDB???</p>\n<p>Yes, but it will explode in production.</p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_21-05d4a56d.png\" alt=\"slide 21\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>It will fail because of latency. Paxos has a liveness problem: two duelling proposers can easily prevent eachothers&#39; progress. The log-centric model only helps to funnel proposers into conflict.</p>\n<p>Both systems tried a way to solve this:</p>\n<ul><li>Megastore optimization: if you commit to slot N, you’re automatically the &quot;leader&quot; for slot N+1.</li><li>PaxosStore: time-based exclusion for a log slot once you hear a proposal for it (also geographic closeness).</li></ul>\n<p>Neither really fundamentally saved them.</p>\n<p>However, it’s nice that replica catchup is easy because there’s one log with one ordering to replicate, and one can easily describe a snapshot of data by just the log offset. But, the latency spikes worse than leader election timeouts removes the motivation for using quorums in the first place.</p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_22-de33fcfe.png\" alt=\"slide 22\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>What if we built CashDB using some E-Paxos ideas?</p>\n<p>Iulian Moraru, David G. Andersen, and Michael Kaminsky. 2013. There is more consensus in Egalitarian parliaments. In <em>Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles</em> (SOSP &#39;13), ACM, 358–372. <a href=\"https://scholar.google.com/scholar?cluster=13655117037814714535\" rel=\"nofollow ugc noopener\">[scholar]</a></p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_23-99d93aaa.png\" alt=\"slide 23\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>Egalitarian Paxos introduces doing consensus where one agrees upon an order only for the exactly necessary dependencies. This naively results in a sparse, potentially disconnected, graph of operations. This graph frees us from having the One Big Log causing unnecessary contention. The closest that E-Paxos gives to any hint on how to do replica catchup is something that looks very much like <a href=\"https://cwiki.apache.org/confluence/spaces/CASSANDRA/pages/337676893/CEP-45+Mutation+Tracking\" rel=\"nofollow ugc noopener\">Cassandra Enhancement Proposal 45 Mutation Tracking</a> if you squint at it.</p>\n<p>Our almost production example comes from Cassandra again. There’s an old 50k line un-merged patch which gives Lightweight Transactions an overhaul onto a new E-Paxos implementation.</p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_24-3e1826bf.png\" alt=\"slide 24\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>CAN. IT. CASHDB???</p>\n<p>Also No</p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_25-314c7da3.png\" alt=\"slide 25\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>It’s not clearly better or worse than a log here…​</p>\n<p>E-Paxos also was noted to have a huge latency cliff under contention, which again ruins our latency desires. There’s actually <a href=\"https://arxiv.org/abs/2008.02512\" rel=\"nofollow ugc noopener\">an infinite tail latency theoretical result</a> for this.</p>\n<p>E-Paxos doesn’t give any great way to define a snapshot other than commit a dependency on everything.</p>\n<p>Cassandra’s EPaxos already had anti-entropy and so they had a paxos repair that ran every 5min to fix up lost proposals. It still benchmarked better than LWT though.</p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_26-34639669.png\" alt=\"slide 26\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>For things that have a good history in production, that’s it. It doesn’t seem great.</p>\n<p>From looking at what pieces were good and bad, we can put together the missing feature wishlist for leaderless replication:</p>\n<p>We need to survive contention because we cannot have latency climb incredulously as contention increases. We desire quorums for low latency. If there’s an easy trap that causes concerningly high latency, then we might as well use Raft.</p>\n<p>Consistent local snapshots would be nice. If you need to do a quorum read and merge for a table scan while executing SQL, you’re going to lose tremendously to a system which doesn’t. We need <em>some</em> way to define a consistent snapshot locally.</p>\n<p>Lastly, If a node has missed proposals, catching up (to get to a snapshot) should be O(missed work) and not O(total data).</p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_27-544d9cfa.png\" alt=\"slide 27\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>So let’s do another pass, and now look at some very recent approaches instead.</p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_28-430c022f.png\" alt=\"slide 28\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>If we look back at consensus over logs, the thing we need to fix is the latency under contention. How can we do that?</p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_29-10131b06.png\" alt=\"slide 29\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>SOSP&#39;23 had a paper on QuePaxa. QuePaxa gives us leaderless consensus that offers much better bounded latency under contention. Proposers collaborate instead of conflict. Consensus will take somewhere from 1 to 7RTT. But you’re unlikely to go over 7RTT.</p>\n<p>Pasindu Tennage, Cristina Basescu, Lefteris Kokoris-Kogias, Ewa Syta, Philipp Jovanovic, Vero Estrada-Galinanes, and Bryan Ford. 2023. QuePaxa: Escaping the tyranny of timeouts in consensus. In <em>Proceedings of the 29th Symposium on Operating Systems Principles</em> (SOSP &#39;23), ACM, 281–297. DOI:<a href=\"https://doi.org/10.1145/3600006.3613150\" rel=\"nofollow ugc noopener\">https://doi.org/10.1145/3600006.3613150</a> <a href=\"https://scholar.google.com/scholar?cluster=11795319014278862913\" rel=\"nofollow ugc noopener\">[scholar]</a></p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_30-5a99464f.png\" alt=\"slide 30\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>QuePaxa in 60 seconds:</p>\n<ul><li>Every proposal gets a priority value, priority equals value for sake of diagram simplicity.</li><li>The algorithm proceeds with proposers walking in lockstep through phases across the acceptors.</li><li>If you fall off the lockstep bandwagon, you can get back on with some other valid proposer’s state.</li><li>Phase 1 only records the first proposal it hears.</li><li>From then on there is a fixed number of proposals, and the consensus intuition is:</li><li>I define a phase as &quot;read from a quorum of phase N and write the max priority proposal to a quorum to begin phase N+1&quot;, if I repeat that enough times, everyone should eventually become aware of the best proposal.</li></ul>\n<p>Actual algorithm, more complicated.</p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_31-16a61127.png\" alt=\"slide 31\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>You can replace paxos in a megastore-style system with QuePaxa.</p>\n<p>QuePaxa’s 1RTT fastpath comes from a spiritually similar Megastore optimization where winning round N gives you an ability to do a 1RTT commit to round N+1.</p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_32-09a0e00f.png\" alt=\"slide 32\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>CAN. IT. CASHDB???</p>\n<p>Not yet</p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_33-497756fd.png\" alt=\"slide 33\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>I’m nearly certain some of those 7RTT cases can be trimmed down. Superficially, pipelining isn’t discussed, and so getting good throughput seems hard. QuePaxa needs like 5 more optimization papers, and then it’s very worth revisiting.</p>\n<p><em>Note: I had received a question about the jump from E-Paxos to QuePaxa, and what QuePaxa was trying to solve. The intended comparison is mostly just Megastore to QuePaxa, and I think the chance of you regretting putting Megastore into production is much higher than the chance of you regretting putting QuePaxa (+ Optimizations) into production.</em></p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_34-3e8cfd5f.png\" alt=\"slide 34\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p><a href=\"https://blog.cloudflare.com/meerkat-introduction/\" rel=\"nofollow ugc noopener\">Cloudflare is working on pushing QuePaxa into production</a>, and so I hope they’ll also do a lot of that needed optimization work. I highly look forward to their results.</p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_35-003c38ab.png\" alt=\"slide 35\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>If we look back at consensus over graphs, we need to fix…​ everything. Which sounds hard, but we actually have two great examples here.</p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_36-88d0b648.png\" alt=\"slide 36\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>SIGMOD&#39;26 gave us Neo4J doing a very graph-centric leaderless consensus protocol.</p>\n<p>Jim Webber, Georgios Theodorakis, Hugo Firth, and Natacha Crooks. 2026. RIOT: Replicated Independently-Ordered Transactions. In <em>Companion of the International Conference on Management of Data</em> (SIGMOD Companion &#39;26), Association for Computing Machinery, New York, NY, USA, 464–476. <a href=\"https://scholar.google.com/scholar?cluster=13928545382118947000\" rel=\"nofollow ugc noopener\">[scholar]</a></p>\n<p><em>Note: Jim Webber was at HPTS&#39;26 and came up to say hello after this talk. He is a very nice person, and it was really cool to get to meet him.</em></p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_37-a2c96245.png\" alt=\"slide 37\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>RIOT builds a DAG where each transaction is a node, and the current snapshot is defined as the set of nodes with no parents, the “Leading Edge”.\nNodes gain a dependency when they conflict, or have a time ordering.</p>\n<p>Do one transaction on a snapshot?</p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_38-c0b70163.png\" alt=\"slide 38\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>Add yourself as a node with the snapshot as your parents.\nYou are now the leading edge.</p>\n<p>Do many concurrent transactions?</p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_39-a0fef6e3.png\" alt=\"slide 39\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>Each node becomes a new part of the &quot;leading edge&quot;.</p>\n<p>And RIOT is centered around the leading edge.\nTransactions are committed when a quorum accepts a new node into the transaction graph, and that’s sent with a leading edge.\nIf you hear about a node you don’t know about from another replica, you get caught up on it, and all its parents you don’t know about.\nRIOT tells us you can do DAG replication by keeping our DAGs connected, and keep them tall and narrow.</p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_40-33f1c168.png\" alt=\"slide 40\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>CAN. IT. CASHDB???</p>\n<p>Probably?</p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_41-7efc45cf.png\" alt=\"slide 41\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>Their results show…​ it’s like, pretty okay at low-ish concurrency: 300txn/partition/second.\nAnd that’s fine for neo4j usage, and they have production stats that justify that the tradeoffs in RIOT match their production usage well, which is really all I want to see when picking a replication algorithm.</p>\n<p>It’s just not an amazing fit for CashDB. CashDB would do lots of small transactions. RIOT happens better for fewer and larger transactions. It’s a super cool paper either way. it’s the only thing I’ve seen that answers how to do pure DAG replication like this well, and it gave Neo4J lower latency than their Raft implementation.</p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_42-b254e710.png\" alt=\"slide 42\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>Our second system to examine is, you won’t believe it, but it’s Cassandra again, because we can’t stop talking about Cassandra in every part of this talk. CEP-15 introduces Accord, which is an E-Paxos style protocol.</p>\n<p>Benedict Elliott Smith, Tony Zhang, Blake Eggleston, and Scott Andreas. 2021. CEP-15: Fast general purpose transactions. Retrieved from <a href=\"https://cwiki.apache.org/confluence/spaces/CASSANDRA/pages/188744725/CEP-15+General+Purpose+Transactions\" rel=\"nofollow ugc noopener\">https://cwiki.apache.org/confluence/spaces/CASSANDRA/pages/188744725/CEP-15+General+Purpose+Transactions</a></p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_43-0eab95cf.png\" alt=\"slide 43\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>Its closest direct relative is the tempo paper, but accord does physical timestamps instead of logical timestamps.</p>\n<p>Vitor Enes, Carlos Baquero, Alexey Gotsman, and Pierre Sutra. 2021. Efficient replication via timestamp stability. In <em>Proceedings of the Sixteenth European Conference on Computer Systems</em> (EuroSys &#39;21), ACM, 178–193. <a href=\"https://scholar.google.com/scholar?cluster=4288377313301185536\" rel=\"nofollow ugc noopener\">[scholar]</a></p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_44-b9e3fd00.png\" alt=\"slide 44\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>Accord provides a 1RTT fast path. It takes up to 3RTT in the slowest case.\nIt borrows the ordered broadcast optimization from E-Paxos Revisited, which means you’ll end up on the fast path more often</p>\n<p>It collects agreement on what timestamp to execute a transaction at, such that the timestamp is after all of its dependencies. The same epaxos-like logic applies for dependency collection, but, the reliance on the timestamp stability work dodges the e-paxos infinite tail latency theoretical result.</p>\n<p>Timestamp ordered execution linearizes proposals which gives it an easy way to support consistent local snapshots and incremental replica catch-up.</p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_45-b9144c88.png\" alt=\"slide 45\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>CAN. IT. CASHDB???</p>\n<p>Hell yeah, huge Accord fan.</p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_46-40172c7b.png\" alt=\"slide 46\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>CashDB would be only small OLTP transactions. It doesn’t need interactivity. You would have to commit a debit/credit, and then execute it and find out if it was valid or not as like a durable OCC, but that’s not the worst.</p>\n<p>I like Accord a lot and think you should read about it.</p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_47-5229237b.png\" alt=\"slide 47\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>And I wanted to take an extra quick moment to highlight that epaxos revisited ordered broadcast primitive.</p>\n<p>The difficult part of leaderless consensus is agreeing upon ordering. Leaders are great at ordering!\nWouldn’t it be great if everything could just be ordered upon arrival?</p>\n<p>Client generated timestamps. Make up your order on your client, broadcast it with your message.\nVariants of this idea show up in papers <em>often</em>.</p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_48-3b12e912.png\" alt=\"slide 48\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>What if you process messages only on or after their deadline?</p>\n<p>Sarah Tollman, Seo Jin Park, and John Ousterhout. 2021. EPaxos Revisited. In <em>18th USENIX Symposium on Networked Systems Design and Implementation (NSDI 21)</em>, USENIX Association, 613–632. <a href=\"https://scholar.google.com/scholar?cluster=8369746688549173721\" rel=\"nofollow ugc noopener\">[scholar]</a></p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_49-cbbbb68f.png\" alt=\"slide 49\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>What if you also drop out-of-order messages?</p>\n<p>Jinkun Geng, Anirudh Sivaraman, Balaji Prabhakar, and Mendel Rosenblum. 2022. Nezha: Deployable and High-Performance Consensus Using Synchronized Clocks. <em>Proceedings of the VLDB Endowment</em> 16, 4 (December 2022), 629–642. <a href=\"https://scholar.google.com/scholar?cluster=3169674848202696193\" rel=\"nofollow ugc noopener\">[scholar]</a></p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_50-80a17af6.png\" alt=\"slide 50\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>What if the network provides best effort ordering?</p>\n<p>Dan R. K. Ports, Jialin Li, Vincent Liu, Naveen Kr. Sharma, and Arvind Krishnamurthy. 2015. Designing Distributed Systems Using Approximate Synchrony in Data Center Networks. In <em>12th USENIX Symposium on Networked Systems Design and Implementation (NSDI 15)</em>, USENIX Association, Oakland, CA, 43–57. <a href=\"https://scholar.google.com/scholar?cluster=3869847260936314766\" rel=\"nofollow ugc noopener\">[scholar]</a></p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_51-a273cd20.png\" alt=\"slide 51\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>What if it’s byzantine?</p>\n<p>Rida Bazzi and Maurice Herlihy. 2022. Clairvoyant state machine replication. <em>Information and Computation</em> 285, (May 2022), 104701. <a href=\"https://scholar.google.com/scholar?cluster=18338463446501516772\" rel=\"nofollow ugc noopener\">[scholar]</a></p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_52-f9cd974c.png\" alt=\"slide 52\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>What if it’s a transaction timestamp?</p>\n<p>No details for time, and we’re ending on TAPIR so I can mention System #3 that I <em>think</em> SurrealDB is putting TAPIR into production which is pretty cool.</p>\n<p>Irene Zhang, Naveen Kr. Sharma, Adriana Szekeres, Arvind Krishnamurthy, and Dan R. K. Ports. 2017. Building Consistent Transactions with Inconsistent Replication. <em>ACM Transactions on Computer Systems</em> 35, 4 (November 2017), 1–37. <a href=\"https://scholar.google.com/scholar?cluster=8784667365134534173\" rel=\"nofollow ugc noopener\">[scholar]</a></p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_53-a67b82d4.png\" alt=\"slide 53\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>Our last bag of tricks are a few very related ideas because applying any one of them, gives you the same high level architecture.</p>\n<p>There’s a cloud of unordered commutative operations from which you pull a log out of afterwards with some great-at-ordering leadered consensus.\nYou can do a 1RTT quorum write into the unordered pool, and remember that <a href=\"https://scholar.google.com/scholar?cluster=10098760952745259234\" rel=\"nofollow ugc noopener\">Linearizable Quorum Reads</a> says you can do a 1RTT read from a quorum of non-leaders, so you’re left only stalling read-after-writes.</p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_54-6ddc7940.png\" alt=\"slide 54\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>CURP is a really nice introduction to this idea, and hides a description of how to apply it to raft in the appendix</p>\n<p>Seo Jin Park and John Ousterhout. 2019. Exploiting Commutativity For Practical Fast Replication. In <em>16th USENIX Symposium on Networked Systems Design and Implementation (NSDI 19)</em>, USENIX Association, Boston, MA, 47–64. <a href=\"https://scholar.google.com/scholar?cluster=3451458773692631815\" rel=\"nofollow ugc noopener\">[scholar]</a></p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_55-9f73e2a0.png\" alt=\"slide 55\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>It was then later generalized to work on more consensus algorithms and fixed in Jetpack</p>\n<p>Ze Tang, Zihao Zhang, Weihai Shen, Jicheng Shi, and Shuai Mu. 2026. Jetpack: Consensus Made Generally Fast. In <em>20th USENIX Symposium on Operating Systems Design and Implementation (OSDI 26)</em>, USENIX Association, Seattle, WA, 1299–1323. <a href=\"https://scholar.google.com/scholar?cluster=7088318940263851844\" rel=\"nofollow ugc noopener\">[scholar]</a></p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_56-b86b01da.png\" alt=\"slide 56\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>Both stop at defining “commutative” operations as those that affect two different keys.\nPulling this diagram from CURP, they accepted a quorum write to Y and to Z, but another write to Y would be forced to stall while the leader works on propagating Y into the log.</p>\n<p>CURP almost got a production implementation in {uri-cncn-xline}[CNCF Xline], but they went straight from Beta to Archived.</p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_57-908515c6.png\" alt=\"slide 57\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>To take these ideas one step further, you need the Skyros paper introducing Nil-Externality.</p>\n<p>Aishwarya Ganesan, Ramnatthan Alagappan, Andrea C. Arpaci-Dusseau, and Remzi H. Arpaci-Dusseau. 2021. Exploiting Nil-Externality for Fast Replicated Storage. In <em>Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles</em> (SOSP &#39;21), ACM, 440–456. <a href=\"https://scholar.google.com/scholar?cluster=347453625338164402\" rel=\"nofollow ugc noopener\">[scholar]</a></p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_58-aeeebd01.png\" alt=\"slide 58\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>Nil-externality is a generalization of blind writes to all operations that don’t return any state about the system.\nSkyros lets you just keep quorum writing nil-external operations to the same key.\nEach replica remembers its local order, and a leadered consensus can pull back out a correct linearizable order later.</p>\n<p>Nil-Externality has no <em>direct</em> implementation in industry, but we’ve been doing similar logic on the concurrency control side by not checking conflicts between blind writes in serializable MVCC databases for a long time.</p>\n<p>Skyros tacks on commutative operations like increments but doesn’t discuss it much.</p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_59-6cf15573.png\" alt=\"slide 59\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>I’ll give MDCC credit as the other paper I know of which directly took on commutative updates under a leaderless generalized paxos model</p>\n<p>Tim Kraska, Gene Pang, Michael J. Franklin, Samuel Madden, and Alan Fekete. 2013. MDCC: multi-data center consistency. In <em>Proceedings of the 8th ACM European Conference on Computer Systems</em> (EuroSys &#39;13), ACM, 113–126. DOI:<a href=\"https://doi.org/10.1145/2465351.2465363\" rel=\"nofollow ugc noopener\">https://doi.org/10.1145/2465351.2465363</a> <a href=\"https://scholar.google.com/scholar?cluster=3774800841354982475\" rel=\"nofollow ugc noopener\">[scholar]</a></p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_60-33b05801.png\" alt=\"slide 60\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>and 1986 Escrow transactions let you extend that commutative logic to …​ almost commutative operations.</p>\n<p>Patrick E. O’Neil. 1986. The Escrow transactional method. <em>ACM Transactions on Database Systems</em> 11, 4 (December 1986), 405–430. <a href=\"https://scholar.google.com/scholar?cluster=395072728627094003\" rel=\"nofollow ugc noopener\">[scholar]</a></p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_61-6fc9d795.png\" alt=\"slide 61\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>Escrow says: let increments and decrements commute as long as it’s impossible for your constraint to be violated. If in the absolute worst case where all the increments abort, and all decrements succeed, then the value still remains above 0, then what do you care just treat them all as commutative.</p>\n<p>Escrow has only one implementation I’m aware of, Oracle 23c introduced it under the name “lockfree reservations”, but, Oracle is not a quorum database</p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_62-704369b9.png\" alt=\"slide 62\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>To apply this to quorum systems, you need the 1992 paper: High Throughput Escrow Algorithms for Replicated Databases\nwhich tells you that in the standard 3 of 5 quorum setup, the worst case value needs to stay above 40% of the current account value instead of 0. It’s not a terribly hard fix.</p>\n<p>Narayanan Krishnakumar and Arthur J. Bernstein. 1992. High Throughput Escrow Algorithms for Replicated Databases. In <em>Proceedings of the 18th International Conference on Very Large Data Bases</em> (VLDB &#39;92), Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 175–186. <a href=\"https://scholar.google.com/scholar?cluster=13617757572293447097\" rel=\"nofollow ugc noopener\">[scholar]</a></p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_63-b9144c88.png\" alt=\"slide 63\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>So if we squish all these ideas together…​</p>\n<p>CAN. IT. CASHDB???</p>\n<p>Yes.</p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_64-b68e0300.png\" alt=\"slide 64\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>CashDB only supports an escrow-able account transfer operation and a nil-external log append. I obviously designed CashDB for this argument.\nIn isolation this async leader trick is not 100% leaderless, but I include it because it’s a great step towards better latency.</p>\n<p>I’m also mentioning it because leveraging blind and commutative operations makes EVERY OTHER ALGORITHM BETTER and we never do it.\nIn Consensus over Logs, Nil-Externality and Escrow would help guide us as to what operations are safe to pipeline with a leaderless log.\nIn Consensus over Graphs, it means we get to reduce the dependencies tracked, and thus end up on the fast path more often.</p>\n<p>Increments are the best operation ever because you can treat them as commutative OR a nil-external fused together read-modify-write that returns nothing, and we still basically never special case them?!? We just execute them under exclusive locks, it saddens me.</p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_65-f072f1a9.png\" alt=\"slide 65\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>Alright, I’m out of time and out of content, so:</p>\n<ul><li>We have very recently gotten much better algorithms for leaderless replication</li><li>We have very recently gotten much better production-or-almost-there examples of how to write good quorum databases.</li><li>There are still more good ideas we have yet to apply to their full extent.</li></ul>\n<p>I do not think we will see a proliferation of quorum databases until we have good production examples to copy from.</p>\n<hr />\n<figure><img src=\"https://transactional.blog/images/talk/please-implement-a-quorum-database/slide_66-0b55add6.png\" alt=\"slide 66\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>So I implore you. Choose something different. Choose something with better latency.\nChoose something that lets you drop a &quot;why quorums are better&quot; blog post every time your competitor has an outage.</p>\n<p>Please implement a quorum database.</p>\n<p>Thank you.</p>","headings":[{"level":1,"text":"Please Implement A Quorum Database","id":"please-implement-a-quorum-database"},{"level":2,"text":"Video","id":"video"},{"level":2,"text":"Transcript","id":"transcript"}]}}