http://muratbuffalo.blogspot.com/2024/01/scalable-oltp-in-cloud-whats-big-deal.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. Scalable OLTP in the Cloud: What's the BIG DEAL? * Get link * Facebook * X * Pinterest * Email * Other Apps - January 17, 2024 This paper is from Pat Helland, the apostate philosopher of database systems, overall a superb person, and a good friend of mine. The paper appeared this week at CIDR'24. (Check out the program for other interesting papers). The motivating question behind this work is: " What are the asymptotic limits to scale for cloud OLTP (OnLine Transaction Processing) systems?" Pat says that the CIDR 2023 paper "Is Scalable OLTP in the Cloud a Solved Problem?" prompted this question. The answer to the question? Pat says that the answer lies in the joint responsibility of database and the application. If you know of Pat's work, which I have summarized several in this blog, you would know that Pat has been advocating along these lines before. But this paper provides a very crisp, specific, concrete answer. Read on for my summary of the paper. Disclaimer: This is a wisdom and technical information/detail packed 13-page paper, so I will try my best to summarize the salient points. I will be using text from the paper to explain/summarize it. (Don't taze me bro!) Snapshot Isolation (SI) is a BIG DEAL The database and the application have a BIG DEAL: their isolation semantics! In particular, snapshot isolation (SI) is the sweet spot. At this point, I got a nice database history lesson on how the isolation semantics evolved. I would have guessed the semantics had become more strict over time. No, on the contrary, they evolved to be more relaxed to meet performance and scalability expectations. And SI does hit a sweet point in that it still provides the user good isolation guarantees without jeopardizing the scaling behavior of the database by requiring it to serialize everything. [AVvXsEixuW5RhqakvtCihi8JM91NYzNa7Ud6z3G2SM7D2fS4z1B6] In the rest of the paper, keep in mind that, an OLTP system is defined as a domain-specific application using a RCSI (READ COMMITTED SNAPSHOT ISOLATION) SQL database to provide transactions across many concurrent users. The BIG DEAL splits the scaling responsibilities between the database and the application. * Scalable DBs don't coordinate across disjoint TXs updating different keys. * Scalable apps don't concurrently update the same key. The big deal provides guarantees from the DB to the App. A scalable application can read all it wants. Updates to disjoint records don't coordinate across TXs. Row-locks on disjoint records don't coordinate across TXs. Applications must tolerate these big deal disclaimers. Reads return snapshots: Records have no "current" value. There is no NOW in a BIG DEAL database! Transactions may abort any time but not too often. SELECT with SKIP LOCKED may subset the set of qualifying records as it returns results. This means applications should change business behavior in order to scale. They can only provide a fuzzy/blurry view of the "current" state/changes. So, apps introduce ambiguity in biz domain specific ways: online retail makes ambiguous promises such as "Usually ships in 24 hours". And apps provide delayed truth: finances of a large company may take days to summarize. Many OLTP apps aggregate values synchronously as they interact with humans. Public TPC benchmarks (e.g., TPC-A, TPC-B, and TPC-C) mandated synchronous aggregations. But, as applications scale they should rethink concentrating the aggregated values of business state in dedicated records. By slowly and asynchronously aggregating these business state, the application can scale in a domain-specific manner. Today's OLTP databases don't scale Before suggesting a hypothetical scalable database that satisfies the database side of the big deal, Pat shows us why today's databases don't scale! [AVvXsEha3L] In today's MVCC databases, reads & writes fight to access the "current" value of a record. The current version has a home location (a partition, server, or a B+ tree) holding the most recently committed version of the record or perhaps an uncommitted version. To update a record, exclusive access to the record's home is required. This causes infighting, contention, and coordination between the updating TX and any concurrent reading TXs. Even reads contend with each other, since these implementations force MVCC readers to start out looking at the latest version of a key first. Coordination may also be needed to access neighboring records. Accessing key-ranges in B+Trees or similar data structures that may be changing needs cross-transaction coordination. Readers coordinate with writers. Writers coordinate with readers. Readers coordinate with other readers! Having a home for a record also makes online repartitioning/sharding (which is required for scalability) very difficult. Moving record keys from one partition to another is complex and impacts application availability. To address these challenges, Pat proposes a prototype design. The database is structured so that there is no pre-assigned home for a record per key. Unlike partitioned DBs, this allows the database to seamlessly adapt to workload changes. I liken this to the miscellaneous manifesto or how instead of neatly organizing/allocating everything a place (which inevitably fails, requiring incessant re-orgs), embracing the messiness and using a search engine to get to information quickly. Rethinking OLTP databases The architecture is based on a design Pat explored in a previous work . The work is very technical, and I missed the nuance and contributions of it because I didn't read through the appendix about details. [AVvXsEgBme] Owner servers verify that concurrent transactions have not created any conflicting updates for each key row-locked or updated by the TX that optimistically hopes to commit. Owner servers partitioned by both key-range and time-range. Repartitioning happens dynamically to accommodate scale. Worker servers are also horizontally scalable, and each have their own transaction log. As TX load increases, workers are added. Each TX happens at a single worker server. The worker servers accept connections from app servers, perform transactions & their queries, commit transactions to their per-worker log, and periodically flush committed new record-versions to the LSM (log structured merge tree). LSM servers accept flushes from workers and incorporate them into the orderly past stored in the LSM. Record-versions are organized first by time, second by key. Each LSM layer contains record-versions for a band of time. With an LSM, the past scales without coordinating across disjoint transactions reading and updating! [AVvXsEhyhoxQSRPZsc1QWeYCex7Gm209SlW0kQMH53tGgHyt5YwnwXwO] Transaction execution and commit We now deep dive to workers and owners as they are the most significant components in this OLTP architecture. The owners do the concurrency control (the adjudication of transactions with respect to other concurrent transactions), but the workers do the actual work of the transaction. The transaction is centralized in the worker's log. The workers' logs are ingested by LSM servers for later consumption and durability. The worker will accept incoming connections from application servers, and plan/execute SQL statements: Reading with snapshots by key or key-range, acquiring row-locks using their unique record key, and updating records by their unique key. The worker will guess a future time to hopefully commit after being verified that updates and row-locks don't conflict with concurrent TXs. The worker will then log the transaction's updates & commit record in its local transaction log, which will then be fed into LSM servers. As a commit-time for a transaction is guessed by the worker, every update and row-lock must be verified for no conflicting updates from snapshot to commit by the owner servers. As incoming proposed-updates and verify-locks arrive, they include a proposed-commit-time. Owner-servers align commit-time for records & workers. An incoming request from a worker hopefully arrives at the owner-server before its local clock has reached the proposed-commit-time. If it arrives after commit-time, owner-server returns an error and the TX aborts. If it arrives before commit-time, the owner-server waits until its local clock reaches commit-time. What are row-locks you ask? Row-locks allow the application to ask the database for help with concurrency across transactions. Traffic cops provide pessimistic concurrency control. They will stall later transactions if they acquire a row-lock held by an earlier transaction. This pessimistic ordering of transactions may be violated when failures happen. Competing transactions usually wait to allow the lock holder to go first but that may be flawed. So correctness will be enforced by OCC prior to commit. Of course, row-locks are moot when scalable apps avoid concurrent updates to the same records. But if the app experience concurrent updates to the same records, row-locks can help with the liveness of transactions when the DB uses them to function as a traffic cop. Ok, let's wrap up the transaction execution discussion by talking about how owners can be horizontally scaled. Owners can close for new business and direct new proposed-updates elsewhere. An owner closed for new business only accept worker requests for snapshot reads in their rectangle of key & time ranges, proposed updates, and notifications of transaction outcome. In contrast an owner open for new business also allow new proposed-updates, and new verify-locks. Massive Scale: It's About Time! As we have seen, the DB leverages time to provide snapshots, commits, and external consistency. External Consistency ensures new incoming requests see all previously exposed data, even by other database connections. That means, snapshot reads from new incoming work must be after all committed work previously visible outside the database. By using current time, T-now, as the snapshot time, this is easy. But this would get trickier and more complex as the geographic scope of a DB grows past a single datacenter. Overall, this prototype database architecture is a big vindication for using time in systems. (Some of these ideas have been explored in Pat's earlier paper, under seniority and retirement.) Everything in the database is versioned by the record-version commit time. The database organizes data by its creation time to achieve scaling. Reads are old record-versions as of a past snapshot. Row-locks ensure locked records unchanged until commit time. And updates materialize as new record-versions for later snapshots. databases distributed transactions distSQL newsql OLTP paper-review SQL * Get link * Facebook * X * Pinterest * Email * Other Apps Comments [IMG] Franck Pachot said... This article is based on the claim that MVCC reads have to compete with concurrent writes, but that is incorrect. In fact, it's the opposite. Non-MVCC databases had to acquire a lock to read because they only have access to the current version. In contrast, MVCC databases can read from a past state. The past doesn't change because nobody can modify the past version of anything (except for Terminator). That's why in MVCC you can read the past versions without acquiring any lock on them. MVCC databases can even read from the read-only standby replica to scale out the reads, ignoring concurrent reads on the primary. January 18, 2024 at 1:20 PM [icon_delet] [hac] Murat said... Yes, MVCC helps. But, as Pat shows in the paper, and outlines in Table 1, in the existing MVCC implementations, since the current record is in the path of reaching the snapshot reads, there is infighting and contention. January 18, 2024 at 2:11 PM [icon_delet] [IMG] Franck Pachot said... The problem is that the author doesn't show it but claims, maybe from SQL Server implementation (which I don't know in detail but all terms used are SQL Server ones to it, and he ignores that Oracle and PostgreSQL store rows in Heap Tables, not in the primary key). He claims that the current row must have the location of the previous one. It is the opposite in PostgreSQL: https://postgrespro.com/blog/ pgsql/5967892#:~:text=ctid. When the current version is updated, it adds a pointer in the previous one. This is additional work for the writers, but readers do not have to go to the current version except if their read time is higher than the past version. In Oracle, the current row points to the transaction log to build a previous image but only needs a short shared latch. Then, the buffer clone can be used by many other consistent reads. The buffer cache holds 5 versions by default, which covers most of the queries read times without rereading the current buffer. I've seen contention on rollback segments but never on the current buffer (XCUR in V$BH). Good explanation here: http://oracleinaction.com/ consistent-reads-in-oracle-part-i/ January 19, 2024 at 3:17 AM [icon_delet] [bla] bad.engineer said... I believe I understand what you are saying, and I entirely agree the subtly of implementation matters here since the author's point is itself subtle. My charitable interpretation would be the following. If we consider a record to include both an index entry & heap tuple, it is correct to state new index entries are replaced in Oracle & placed next to older versions in Postgres. These would be the mechanisms of contention in Table 1. Not all varieties of reads will contend via this mechanism. That being said, I can understand why this point was omitted from the paper since any read that doesn't use an index will result in a larger scope of access and more necessary coordination. January 19, 2024 at 12:55 PM [icon_delet] [blo] sb said... Getting cooperation from the OLTP app side is interestingly nothing mentioned (atleast in your summary), now that becomes relevant when you think of the key, is it stock itself or the trade/order IDs? A basket of NiFTY 500 order processing will swarm the workers to grow rapidly, while owners adjusting its key ranges to the workers? I suppose splitting the whole transaction work into multiple dedicated servers is ignoring the network chatter required (imagine just clock sync overhead for a nanosecond future commit timestamp in your summary) to scale. MVCC and realtime read/write with trade guarantees is hard, really hard, I mean will you place another million dollar without knowing the previous one really went through or not? No overlapping key updates (single trades) days are ancient, TPCC is just primary exam in terms of today's basket trading and search for sub-nanosecond latency. Having developed such apps/ similar databases and now reinventing myself for low latency programming, I've few ideas that be worth something that sees through both sides of the aforementioned "coordination required to scale". January 22, 2024 at 7:45 AM [icon_delet] Post a Comment Popular posts from this blog Hints for Distributed Systems Design - October 02, 2023 This is with apologies to Butler Lampson, who published the " Hints for computer system design " paper 40 years ago in SOSP'83. I don't claim to match that work of course. I just thought I could draft this post to organize my thinking about designing distributed systems and get feedback from others. I start with the same disclaimer Lampson gave. These hints are not novel, not foolproof recipes, not laws of design, not precisely formulated, and not always appropriate. They are just hints. They are context dependent, and some of them may be controversial. That being said, I have seen these hints successfully applied in distributed systems design throughout my 25 years in the field, starting from the theory of distributed systems (98-01), immersing into the practice of wireless sensor networks (01-11), and working on cloud computing systems both in the academia and industry ever since. These heuristic principles have been applied knowingly or unknowingly and has proven... 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 >> Making database systems usable - August 19, 2024 Image C. J. Date's Sigmod 1983 keynote, "Database Usability", was prescient. Usability is the most important thing to the customers. They care less about impressive benchmarks or clever algorithms, and more about whether they can operate and use a database efficiently to query, update, analyze, and persist their data with minimal headache. (BTW, does anyone have a link to the contents of this Sigmod'83 talk? There is no transcript around, except for this short abstract .) The paper we cover today is from Sigmod 2007. It takes on the database usability problem raised in that 1983 keynote head-on, and calls out that the king is still naked. Let's give some context for the year 2007. Yes, XML format was still popular then. The use-case in the paper is XQuery. The paper does not contain any reference to json. MongoDB would be released in 2009 with the document model; and that seems to be great timing for some of the usability pains mentioned in the paper! Web 2.0 was in ... Read more >> Looming Liability Machines (LLMs) - August 24, 2024 As part of our zoom reading group ( wow, 4.5 years old now ), we discussed a paper that uses LLMs for automatic root cause analysis (RCA) for cloud incidents. This was a pretty straightforward application of LLMs. The proposed system employs an LLM to match incoming incidents to incident handlers based on their alert types, predicts the incident's root cause category, and provides an explanatory narrative. The only customization is through prompt-engineering. Since this is a custom domain, I think a more principled and custom-designed machine learning system would be more appropriate rather than adopting LLMs. Anyways, the use of LLMs for RCAs spooked me vicerally. I couldn't find the exact words during the paper discussion, but I can articulate this better now. Let me explain. RCA is serious business Root cause analysis (RCA) is the process of identifying the underlying causes of a problem/incident, rather than just addressing its symptoms. One RCA heuristic is asking 5 Why... Read more >> Advice to the young - July 30, 2024 Image I notice I haven't written any advice posts recently. Here is a collection of my advice posts pre 2020. I've been feeling all this elderly wisdom pent up in me, ready to pour at any moment. So here it goes. Get ready to quench your thirst from my fount of wisdom. No man, think for yourself, only get what works for you. It is called foundations, not theory Foundations of computer science (or rather any field of study) are the most important topics you can learn. These lay down the frame of thinking/perspective for that area of study. Yet, I am saddened to hear these called as "theory", and labeled as "unpractical". This couldn't be farther from the truth. Take a look at how I recommend studying distributed systems . Don't you dare call this "theory" and "unpractical". This lays the bedrock that you build your practice on. Don't skimp on the foundations. Don't build your home on quicksand. Keep your hands dirty, your mind cl... 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. Practical uses of synchronized clocks in distributed systems. B. Liskov, 1991. Exp... Read more >> Distributed Transactions at Scale in Amazon DynamoDB - August 17, 2023 Image This paper appeared in July at USENIX ATC 2023. If you haven't read about the architecture and operation of DynamoDB, please first read my summary of the DynamoDB ATC 2022 paper . The big omission in that paper was discussion about transactions. This paper amends that. It is great to see DynamoDB, and AWS in general, is publishing/sharing more widely than before. Overview A killer feature of DynamoDB is predictability at any scale. Do read Marc Brooker's post to fully appreciate this feature. Aligned with this predictability tenet, when adding transactions to DynamoDB, the first and primary constraint was to preserve the predictable high performance of single-key reads/ writes at any scale. The second big constraint was to implement transactions using update in-place operation without multi-version concurrency control. The reason for this was they didn't want to mock with the storage layer which did not support multi-versioning. Satisfying both of the above constraints may s... Read more >> Linearizability: A Correctness Condition for Concurrent Objects - August 09, 2024 Image This paper is from Herlihy and Wing appeared in ACM Transactions on Programming Languages and Systems 1990. This is the canonical reference for the linearizability definition. I had not read this paper in detail before, so I thought it would be good to go to the source to see if there are additional delightful surprises in the original text. Hence, this post. I will dive into a technical analysis of the paper first, and then discuss some of my takes toward the end. I had written an accessible explanation of linearizability earlier; you may want to read that first. I will assume an understanding of linearizability to keep this review at reasonable length. Introduction I love how the old papers just barge in with the model, without bothered by pleasantries such as motivation of the problem. These are the first two sentences of the introduction. "A concurrent system consists of a collection of sequential processes that communicate through shared typed objects . This model encompass... Read more >> Understanding the Performance Implications of Storage-Disaggregated Databases - July 23, 2024 Image Storage-compute disaggregation in databases has emerged as a pivotal architecture in cloud environments, as evidenced by Amazon ( Aurora ), Microsoft ( Socrates ), Google (AlloyDB), Alibaba ( PolarDB ), and Huawei (Taurus). This approach decouples compute from storage, allowing for independent and elastic scaling of compute and storage resources. It provides fault-tolerance at the storage level. You can then share the storage for other services, such as adding read-only replicas for the databases. You can even use the storage level for easier sharding of your database. Finally, you can also use this for exporting a changelog asynchronously to feed into peripheral cloud services, such as analytics. Disaggregated architecture was the topic of Sigmod 23 panel . I think this quote summarizes the industry's thinking on the topic. "Disaggregated architecture is here, and is not going anywhere. In a disaggregated architecture, storage is fungible, and computing scales independently. ... Read more >> Powered by Blogger Theme images by Michael Elkan Murat Demirbas My photo Murat I am a principal research scientist at MongoDB Research. Ex-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 Mastodon or Twitter. Visit profile Pageviews Recent Posts * January4 * December8 * November5 * October8 * September10 * August9 * July3 * June5 * May2 * April6 * March6 * February9 * January7 * December3 * November4 * October4 * September4 * August4 * July5 * June2 * May3 * April3 * March3 * February5 * January3 * December4 * November4 * October1 * September4 * August5 * July6 * June3 * May3 * April4 * March3 * February3 * January3 * December5 * November3 * October6 * September1 * August4 * July2 * June12 * May1 * April1 * March4 * February4 * January4 * December3 * November7 * October4 * September1 * August3 * July6 * June11 * May9 * April8 * March8 * February7 * January9 * December10 * November14 * October6 * September13 * July3 * June3 * May4 * April6 * March2 * February1 * January3 * December4 * November7 * October2 * September2 * August8 * July2 * June4 * May9 * April6 * March9 * February5 * January13 * December15 * November15 * October5 * September8 * August10 * July3 * June3 * May3 * April4 * February4 * January7 * December7 * November9 * October3 * September1 * July4 * June5 * May1 * April4 * March2 * February2 * January4 * December3 * November2 * October3 * September2 * August3 * June1 * May1 * April6 * March6 * February4 * January3 * November4 * October4 * September6 * August2 * July2 * June3 * March3 * February4 * January1 * December1 * November2 * August2 * July4 * June2 * May5 * April8 * January1 * December1 * November7 * October1 * September2 * August1 * May2 * March1 * February1 * January2 * December3 * September5 * June1 * May5 * April5 * March5 * February9 * January5 * December6 * November9 * October9 * September7 * August1 Show more Show less Topics 2PC1 abstraction4 AI4 analytics3 atomic storage2 auditability5 automated reasoning9 aws5 Azure11 benchmarks4 bestof8 big-data30 Blockchain39 book-review54 calm5 chaos2 cloud computing17 consistency32 Cosmos DB11 CosmosDB12 crdts2 data warehouse2 databases56 datacenter networking1 dataflow11 dbos1 DDIA15 disaggregation2 distributed consensus49 distributed transactions36 distSQL8 facebook16 failures18 fault-tolerance46 formal methods12 graph-processing1 hpts3 htap3 humans10 indexing3 isolation levels4 links2 mad-questions42 main-memory1 measuring1 metastability2 microservices2 misc113 ML1 mlbegin7 mldl26 mobile2 mongodb8 MVCC1 my advice17 my-paper10 networking1 newsql3 NoSQL2 OLAP2 OLTP7 paper-review149 paxos51 postgres1 presenting4 privacy1 programming7 query-processing2 raft1 RDMA2 reading-group23 reconfiguration4 research-advice50 research-question44 Rust3 scheduling3 security1 seminar9 serializability1 serverless1 smartphones2 snapshot isolation 5 sonification1 SQL6 stabilization6 statistics3 stream-processing12 teaching31 tensorflow11 time19 time synchronization5 timeDB7 tla51 tpbook1 transactions30 trip-report31 wpaxos6 writing30 Show more Show less