http://muratbuffalo.blogspot.com/2022/05/warp-lightweight-multi-key-transactions.html Skip to main content Search This Blog [ ] [Search] Metadata On distributed systems broadly defined and other curiosities. The opinions on this site are my own. Warp: Lightweight Multi-Key Transactions for Key-Value Stores * Get link * Facebook * Twitter * Pinterest * Email * Other Apps - May 04, 2022 This paper introduces a simple yet powerful idea to provide efficient multi-key transactions with ACID semantics on top of a sharded NoSQL data store. The Warp protocol prevents serializability cycles forming between concurrent transactions by forcing them to serialize via a chain communication pattern rather than using a parallel 2PC fan-out/ fan-in communication. This avoids hotspots associated with fan-out/ fan-in communication and prevents wasted parallel work from contacting multiple other servers when traversing them in serial would surface an invalidation/abortion early on in the serialization. I love the elegance of this idea. As far as I can see, this paper did not get published in any conference. The authors published a followup paper to this in NSDI 16, called "The Design and Implementation of the Warp Transactional Filesystem." But that paper does not talk about the internals of Warp protocol like this archive report, rather talks about the Warp Transactional Filesystem (WTF), a transactional, POSIX-compatible filesystem built on top of Warp. Design of the acyclic commit protocol The acyclic transactions commit protocol processes clients' transactions, and ensures that they either commit in an atomic, serializable fashion, or abort with no effect. [AVvXsEjFAbCYdUi-THqc2dkePkBIQ1Y9KSHAdRI75dF] The key insight of the acyclic transactions protocol is to arrange the servers for a transaction into a chain which processes it serially in contrast to parallel processing done by traditional commit protocols using fan-out/fan-in communication patterns. This ensures that there is at most one server actively processing each transaction at any one time. By limiting the parallelism present in a single transaction, acyclic transactions enable each server to locally make a binding decision about the fate of the transaction they are processing, and propagate that decision to the next server in the chain. Globally, though, this enables multiple transactions which modify the same data (whose execution other techniques would serialize) to execute in parallel because each pair of concurrent transactions is ordered by exactly one server that can decide their order without communicating with other servers. Any decision made by a server will be carried to, and enforced by, the remaining servers in the chain. [AVvXsEhxJtyyTQOqHdq_bqBFYLjYzQ2tzfhD3tjp-puNCuf] Figure 2 shows how transactions that read and write the same keys have overlapping chains. The first server in common between two transactions' chains can order any two overlapping transactions, and notify all subsequent servers in both chains. Inversely, when two chains do not overlap, there is no need to directly order their transactions, because they necessarily operate on disjoint data. Validation and ordering The validation step ensures that values previously read by the client remain unchanged until the transaction commits. To do this, servers check each transaction to ensure that it does not read values written by, or write values read by, previously validated transactions. Servers also check each value against the latest value in their local store to ensure that the value was not changed by a previously-committed transaction. Thus, acyclic transactions employ optimistic concurrency control. When a server determines that a transaction does not validate, the server aborts the transaction by sending an abort message backwards through the chain. Each server in the prefix aborts the transaction and forwards the abort message until the message reaches the client. These servers remove the transaction from their local state, enabling other transactions to validate in its place. [AVvXsEhiptpZ2cBFj-kvJF-OGXC84AnkrjzY8FnUE9zGDkYMghcz] A set of transactions are serializable if the dependency graph of their relative orders is free of cycles. The difficulty here lies in resolving the order across multiple pairs, because interactions between transactions can span multiple servers. As in Figure 3, it is possible that no single server would have have the requisite view to detect and prevent a cycle in the graph. To ensure that all transactions commit in a serializable order across servers, servers embed ordering information, called mediator tokens, into transactions. Mediator tokens are integer values that are assigned to transactions by the heads of chains. A simple invariant that ensures serializability is to commit conflicting pairs in the order specified by their mediator tokens. For example, if the mediator tokens for the conflicting pair (TX , TY) have the relationship mediator(TX ) < mediator(TY), then all servers order the transactions such that TX commits before TY. The acyclic transactions protocol relies on this invariant to order transactions. Upon receipt of a transaction passing forward through the chain, a server compares the transaction's mediator token to the largest mediator token across all transactions that previously read or wrote any of the current transaction's objects. If the current mediator token is larger than the previous token, the transaction is forwarded to the next server in the chain. If, however, the mediator token is less than the previous token, a *"retry"* message is sent backwards in the chain to the head, where the transaction will be retried with a larger mediator token. To recap, an invalidated transaction is aborted and cleared by communicating backwards in the chain. But a still-valid transaction, whose serialization ordering does not work with the current mediator token number, is given another chance to serialize by being sent back to the head of the chain to take a new token number to retry. During the retry it may turn out that the readset for the transaction is not valid anymore with this ordering, and the transaction may end up aborting. Or the transaction may just work with this ordering without being invalidated. There is an interesting parallel here with the CockroachDB commit protocol. CockroachDB commit uses 2PC OCC, but also performs timestamp-advancing and read-refreshing/validation. The difference is that, while those require more complicated operations and contacting more nodes in parallel in CockroachDB, the same process is handled elegantly and more efficiently (with little waste) in Warp. "Certain types of conflicts described above require advancing the commit timestamp of a transaction. To maintain serializability, the read timestamp must be advanced to match the commit timestamp. Advancing a transaction's read timestamp from ta to tb > ta is possible if we can prove that none of the data that the transaction read at ta has been updated in the interval (ta,tb]. If the data has changed, the transaction needs to be restarted. To determine whether the read timestamp can be advanced, CockroachDB maintains the set of keys in the transaction's read set (up to a memory budget). A "read refresh" request validates that the keys have not been updated in a given timestamp interval (Algorithm 1, Lines 11 to 14). This involves re-scanning the read set and checking whether any MVCC values fall in the given interval." By serializing/bottlenecking potentially conflicting transactions through chaining, Warp enforces handling/addressing of the conflicts earlier on and resolve them with little waste by either accepting them together with no serializability problems or aborting some of them. Retries are simple, and they make reordering easier. Moreover, invalidation happens earlier, with little wasted work, which also contributes to improved throughput. As such, Warp improves throughput. Implementation and evaluation They implemented Warp in 130,000 lines of code, approximately 15,000 lines of which are devoted to processing transactions. A system of virtual servers maps a small number of servers to a larger number of partitions, permitting the system to reassign partitions to servers without repartitioning the data. The implementation uses a replicated state machine as the coordinator to ensure that there are no single points of failure. The expanded API in the implementation includes support for rich data structures, multiple independent schemas, and nested transactions. (As far as I can see the implementation is not available as opensource.) In the evaluation of the paper, they also compare Warp to HyperDex, the underlying NoSQL key-value store for Warp, even though HyperDex offers no transactional guarantees. For comparison purposes, they also implemented Sinfonia's mini-transactions on top of HyperDex, and refer to this implementation as MiniDex. [AVvXsEjVxR_Z8Znx2ehxdD59iODddQBANlsCPRiJy7vv] They use TPC-C benchmark for their first set of experiments. The workload specified by TPC-C is inherently difficult to process with optimistic concurrency control, because it includes both read-heavy and update-heavy transaction profiles and the update-heavy transactions intentionally contend on a small number of hot keys. [AVvXsEicXC7PuPZC6rNUQC806T77RqhoUh1H2qE8f2j30AFxr4mkd6N4] [AVvXsEiUiaHv4xjZEb0MiDkRAz2cffvSJbMLt5Mo1qS3FhUa-zvJvDqCppjRfOnjzqHrVJp-JcddEf4O_rgL7hovtw] [AVvXsEiugp8ylqfW-f6F1VMdoKI7C0dNBYJGSN2ThFKg2EbweT6nIhMo] The experiments show that Warp achieves 4x higher throughput than Sinfonia's mini-transactions on the standard TPC-C benchmark with no aborts. Despite providing ACID guarantees, Warp also achieves 75% of the throughput of the non-transactional key-value store it builds upon. Aside from TPC-C workload, they also use targeted micro-benchmarks for experiments, where objects have 12 Byte keys and 64 Byte values, and are constructed uniformly at random. Ten million objects are preloaded onto the cluster before performing each benchmark. [AVvXsEhS4xFHr3N8Il7y-97UP_hhi6lSA8F7zj87TYG66c9wzepiRKBn] [AVvXsEjtUZBALfNk05iqpRWinOMxhbmxsUiCR8TRHx00LPWIQg6HVUH3] distributed transactions paper-review * Get link * Facebook * Twitter * Pinterest * Email * Other Apps Comments Post a Comment Popular posts from this blog Graviton2 and Graviton3 - December 04, 2021 Image What do modern cloud workloads look like? And what does that have to do with new chip designs? I found these gems in Peter DeSantis's ReInvent20 and ReInvent21 talks. These talks are very informative and educational. Me likey! The speakers at ReInvent are not just introducing new products/services, but they are also explaining the thought processes behind them. To come up with this summary, I edited the YouTube video transcripts slightly (mostly shortening it). The presentation narratives have been really well planned, so this makes a good read I think. Graviton2 This part is from the ReInvent2020 talk from Peter DeSantis. Graviton2 is the best performing general purpose processor in our cloud by a wide margin. It also offers significantly lower cost. And it's also the most power efficient processor we've ever deployed. Our plan was to build a processor that was optimized for AWS and modern cloud workloads. But, what do modern cloud workloads look like? Let's start by Read more Foundational distributed systems papers - February 27, 2021 I talked about the importance of reading foundational papers last week. To followup, here is my compilation of foundational papers in the distributed systems area. (I focused on the core distributed systems area, and did not cover networking, security, distributed ledgers, verification work etc. I even left out distributed transactions, I hope to cover them at a later date.) I classified the papers by subject, and listed them in chronological order. I also listed expository papers and blog posts at the end of each section. Time and State in Distributed Systems Time, Clocks, and the Ordering of Events in a Distributed System. Leslie Lamport, Commn. of the ACM, 1978. Distributed Snapshots: Determining Global States of a Distributed System. K. Mani Chandy Leslie Lamport, ACM Transactions on Computer Systems, 1985. Virtual Time and Global States of Distributed Systems. Mattern, F. 1988. Expository papers and blog posts There is No Now . Justin Sheehy, ACM Queue 2015 Why Logical Clock Read more FoundationDB: A Distributed Unbundled Transactional Key Value Store (Sigmod 2021) - March 10, 2022 Image This paper from Sigmod 2021 presents FoundationDB, a transactional key-value store that supports multi-key strictly serializable transactions across its entire key-space. FoundationDB (FDB, for short) is opensource. The paper says that: " FDB is the underpinning of cloud infrastructure at Apple, Snowflake and other companies, due to its consistency, robustness and availability for storing user data, system metadata and configuration, and other critical information. " The main idea in FDB is to decouple transaction processing from logging and storage. Such an unbundled architecture enables the separation and horizontal scaling of both read and write handling. The transaction system combines optimistic concurrency control (OCC) and multi-version concurrency control (MVCC) and achieves strict serializability or snapshot isolation if desired. The decoupling of logging and the determinism in transaction orders greatly simplify recovery by removing redo and undo log processing f Read more Anna: A Key-Value Store For Any Scale - April 29, 2022 Image This paper (ICDE'18) introduces Anna, a CALM / CRDT implementation of a distributed key-value system both at the data structure level as well as system architecture and transaction protocol levels. Anna is a partitioned, multi-mastered key-value system that achieves high performance and elasticity via wait-free execution and coordination-free consistency. Anna employs coordination-free actors that perform state update via merge of lattice-based composite data structures. I love the strongly opinionated introduction of this paper. This is what papers should be about: opinionated, challenging conventions, making bets, and doing hypothesis testing in the small. Conventional wisdom says that software designed for one scale point needs to be rewritten when scaling up by 10x. Anna sets out to disprove this by showing how a key-value storage (KVS) system can be architected to scale across many orders of magnitude. (Spoiler Anna can give you only upto causal consistency, but cannot pro Read more Your attitude determines your success - March 13, 2021 This may sound like a cliche your dad used to tell, but after many years of going through new areas, ventures, and careers, I find this to be the most underrated career advice. This is the number one advice I would like my kids to internalize as they grow up. This is the most important idea I would like every one undertaking a new venture to know. If you think you are not good enough, it becomes a self-fulfilling prophecy. If you think you are not enjoying something, you start to hate it. I gave examples of this several times before. Let's suffice with this one : In graduate school, I had read "Hackers: Heroes of the Computer Revolution" from Steven Levy and enjoyed it a lot. (I still keep the dog eared paper copy with affection.) So, I should have read Steven Levy's Crypto book a long time ago. But for some reason, I didn't...even though I was aware of the book. I guess that was due to a stupid quirk of mine; I had some aversion to the security/cryptography res Read more Learning a technical subject - December 18, 2021 I love learning. I wanted to write about how I learn, so I can analyze if there is a method to this madness. I will first talk about what my learning process looks like in abstract terms, and then I'll give an analogy to make things more concrete and visual. Learning is a messy process for me I know some very clear thinkers. They are very organized and methodical. I am not like that. These tidy thinkers seem to learn a new subject quickly (and effortlessly) by studying the rules of the subject and then deriving everything about that subject from that set of rules. They speak in precise statements and have clear and hard-set opinions about the subject. They seem to thrive most in theoretical subjects. In my observation those tidy learners are in the minority. Maybe the tidy thinkers are able to pull this feat off because they come from a neighboring domain/ subject and map the context there to this subject quickly. But, again from my experience, it doesn't feel like that. It s Read more Progress beats perfect - August 06, 2021 Image This is a favorite saying of mine. I use it to motivate myself when I feel disheartened about how much I have to learn and improve. If I do a little every day or every week, I will get there. If I get one percent better each day for one year, I'll end up thirty-seven times better by the end of the year. $1.01^{365}=37.78$ Years ago I had read this idea in one of John Ousterhouts life lessons, and it stuck with me. "A little bit of slope makes up for a lot of y-intercept" Recently I noticed another advantage of progress over perfect. The emotional advantage. Progress is better because it makes you feel better as you see improvement. You are getting there, you are making ... progress. Progress is growth mindset . You have an opportunity ahead of you. Perfect feels bad.. It puts you on defense. You have to defend the perfect, you have to keep the appearances. You can only go downwards from perfect, or maintain status quo. Progress gives you momentum. As long as you manag Read more Learning about distributed systems: where to start? - June 10, 2020 This is definitely not a "learn distributed systems in 21 days" post. I recommend a principled, from the foundations-up, studying of distributed systems, which will take a good three months in the first pass, and many more months to build competence after that. If you are practical and coding oriented you may not like my advice much. You may object saying, "Shouldn't I learn distributed systems with coding and hands on? Why can I not get started by deploying a Hadoop cluster, or studying the Raft code." I think that is the wrong way to go about learning distributed systems, because seeing similar code and programming language constructs will make you think this is familiar territory, and will give you a false sense of security. But, nothing can be further from the truth. Distributed systems need radically different software than centralized systems do. --A. Tannenbaum This quotation is literally the first sentence in my distributed systems syllabus. Inst Read more Cores that don't count - June 06, 2021 This paper is from Google and appeared at HotOS 2021 . There is also a very nice 10 minute video presentation for it. So Google found fail-silent Corruption Execution Errors (CEEs) at CPU/cores. This is interesting because we thought tested CPUs do not have logic errors, and if they had an error it would be a fail-stop or at least fail-noisy hardware errors triggering machine checks. Previously we had known about fail-silent storage and network errors due to bit flips, but the CEEs are new because they are computation errors. While it is easy to detect data corruption due to bit flips, it is hard to detect CEEs because they are rare and require expensive methods to detect/correct in real-time. What are the causes of CEEs? This is mostly due to ever-smaller feature sizes that push closer to the limits of CMOS scaling, coupled with ever-increasing complexity in architectural design. Together, these create new challenges for the verification methods that chip makers use to detect diverse Read more Amazon Aurora: Design Considerations + On Avoiding Distributed Consensus for I/Os, Commits, and Membership Changes - March 20, 2022 Image Amazon Aurora is a high-throughput cloud-native relational database. I will summarize its design as covered by the Sigmod 17 and Sigmod 18 papers from the Aurora team. Aurora uses MySQL or PostgreSQL for the database instance at top, and decouples the storage to a multi-tenant scale-out storage service. In this decoupled architecture, each database instance acts as a SQL endpoint and supports query processing, access methods, transactions, locking, buffer caching, and undo management. Some database functions, including redo logging, materialization of data blocks, garbage collection, and backup/ restore, are offloaded to the storage nodes. A big innovation in Aurora is to do the replication among the storage nodes by pushing the redo log; this reduces networking traffic and enables fault-tolerant storage that heals without database involvement. In contrast to CockroachDB and FoundationDB , Aurora manages not to use consensus at all. It uses a primary secondary failover at the comp Read more Powered by Blogger Theme images by Michael Elkan Murat Demirbas My photo Murat I am a principal applied scientist at AWS. On leave as a computer science and engineering professor at SUNY Buffalo. I work on distributed systems, distributed consensus, and cloud computing. You can follow me on Twitter. Visit profile Recent Posts * 2022 16 + May 3 o Why should this paper be published? o Feral Concurrency Control: An Empirical Investigat... o Warp: Lightweight Multi-Key Transactions for Key-V... + April 4 + March 3 + February 3 + January 3 * 2021 47 + December 5 + November 3 + October 6 + September 1 + August 4 + July 2 + June 12 + May 1 + April 1 + March 4 + February 4 + January 4 * 2020 76 + December 3 + November 7 + October 4 + September 1 + August 3 + July 6 + June 11 + May 9 + April 8 + March 8 + February 7 + January 9 * 2019 65 + December 10 + November 14 + October 6 + September 13 + July 3 + June 3 + May 4 + April 6 + March 2 + February 1 + January 3 * 2018 71 + December 4 + November 7 + October 2 + September 2 + August 8 + July 2 + June 4 + May 9 + April 6 + March 9 + February 5 + January 13 * 2017 77 + December 15 + November 15 + October 5 + September 8 + August 10 + July 3 + June 3 + May 3 + April 4 + February 4 + January 7 * 2016 42 + December 7 + November 9 + October 3 + September 1 + July 4 + June 5 + May 1 + April 4 + March 2 + February 2 + January 4 * 2015 34 + December 3 + November 2 + October 3 + September 2 + August 3 + June 1 + May 1 + April 6 + March 6 + February 4 + January 3 * 2014 29 + November 4 + October 4 + September 6 + August 2 + July 2 + June 3 + March 3 + February 4 + January 1 * 2013 25 + December 1 + November 2 + August 2 + July 4 + June 2 + May 5 + April 8 + January 1 * 2012 18 + December 1 + November 7 + October 1 + September 2 + August 1 + May 2 + March 1 + February 1 + January 2 * 2011 38 + December 3 + September 5 + June 1 + May 5 + April 5 + March 5 + February 9 + January 5 * 2010 31 + December 6 + November 9 + October 9 + September 7 * 2007 1 + August 1 Show more Show less Topics auditability5 automated reasoning5 Azure9 bestof5 big-data20 Blockchain39 book-review49 chaos2 cloud computing3 consistency23 Cosmos DB10 CosmosDB11 databases9 dataflow7 distributed consensus42 distributed transactions11 distSQL1 facebook14 failures16 fault-tolerance37 formal methods10 graph-processing1 humans10 indexing3 links2 mad-questions42 misc102 mlbegin7 mldl25 mobile2 my advice15 my-paper10 newsql2 paper-review141 paxos44 presenting4 programming5 reading-group23 research-advice47 research-question43 Rust3 scheduling3 seminar9 serverless1 smartphones2 sonification1 stabilization5 stream-processing10 teaching30 tensorflow11 time8 time synchronization1 tla38 trip-report20 wpaxos5 writing26 Show more Show less Pageviews