HPTS'24 day 1, part 2

-

This is part 2 of day 1 of HPTS'24. (You can tell I did some lisp programming back in the day, huh?) Here is the first part of day 1, you should check that out as well. 

There were 2 sessions each with 4 talks in the afternoon of day 2. After dinner, we had a gong show presentation on miscellaneous topics as well. 


Session 3: DBOS

Virtual Memory: a Huge Step Backwards- Daniel Bittman (Elephance)

Daniel argued that virtual memory, despite its widespread use, is fundamentally flawed. He contends that virtual memory presents an abstraction of memory as  flat, uniform, contiguous, infinite, isolated, and fast - all of which are untrue. 

He pointed to significant performance issues with virtual memory, noting that virtual memory adds substantial overhead to every memory access. Every memory access costs 4 extra memory accesses and 100s of nanoseconds of wasted CPU time, which is an eternity in CPU world. He criticized the Transaction Look-Aside Buffer (TLB) for its complexity and lack of coherence, especially in multi-threaded systems.

Security is another major concern. The large codebase required for TLB management and the hardware itself present significant attack surfaces. Why do threaded systems have all threads in same address space? The process model is much more precise with OS about its isolation boundaries.

He also pointed out the dangers of overcommitting memory and the unpredictability of memory allocation failures through malloc. He did an experiment fuzzing malloc failures, and showed that almost all databases had problems.

Daniel argued that very early segmentation model was a superior memory model and proposes CHERI as a potential improvement. He's working on a new OS called Twizzler, written in Rust, which aims to address these issues by being more precise about memory management. See https://dbittman.com.

He concluded "Just run SPDK on bare metal, man. Peace out dude!".

Daniel is a natural presenter. He is very comfortable in front of crowds with great delivery. I guess he took after his advisor Peter Alvaro. What is your secret guys? Inquiring minds want to know.


Portable Compiler-Centric SIMD Code in Databases - Lawrence Benson (TU Munich)

Lawrence discussed the importance of SIMD (Single Instruction Multiple Data) in database operations. A simple example of SIMD is doing 4 additions in one instruction. SIMD allows for parallel processing, significantly improving performance in tasks like table scans, hash tables, and sorting.

However, he pointed out that SIMD code is challenging to develop, test, and benchmark due to its CPU-specific nature. This is particularly relevant given the increasing presence of ARM processors in cloud environments.

He questioned the need for hand-written SIMD code, suggesting that compilers should handle this optimization. He critiqued the current approach of using multiple layers of abstractions, such as platform intrinsics built on compiler intrinsics.

Instead, he proposes a more direct approach: using compiler intrinsics exclusively. His method aims to simplify SIMD implementation while maintaining portability and performance across different CPU architectures. He has code to back up his proposal. 


Making Peace Between Mortal Enemies: Running a Database Management System in the Linux Kernel - Matt Butrovich (Carnegie Mellon University)

Matt proposed a radical approach to database management systems (DBMS): running them in the Linux kernel. Why? Because the operating system is often an impediment to database performance. 

Instead of conventional user-space operations, Matt suggests pushing DBMS logic into kernel-space using eBPF (extended Berkeley Packet Filter). eBPF allows safe execution of event-driven programs in kernel space, supporting languages like C, Go, and Rust.

He introduced BPF-DB, an embedded transactional database for eBPF. However, implementing this faces challenges due to the eBPF verifier's strict limitations, including instruction limits and restrictions on branches and recursion. To overcome these obstacles, BPF-DB employed continuation passing style and uses kernel-resident thread-safe data structures for storage management. Transaction management used strict multi-version two-phase locking (MV2PL) to ensure ACID properties. A key innovation was the use of a ring buffer to communicate with user space for write-ahead logging, as eBPF can't directly access the disk.

While this was impressive, an expert (Margo) comments that this project is notable more for its audacity than its practicality, likening it to a "dancing bear" - remarkable not for how well it performs, but for the fact that it works at all. 


DBOS 2.0: Practical DB-OS Co-Design with Process Virtualization - Xinjing Zhou (MIT)

First, here is some background about the DBOS project and its goals. Now there is a company around the project making some leeway. 

Xinjing's talk focused on database-operating system co-design. This middle-ground solution aims to integrate some database functionalities into the OS without completely bypassing the kernel.

The talk brought up issues like virtual memory snapshotting, where operations like fork() can be blocking. To minimize security risks associated with kernel-level modifications, Xinjing proposed a "privileged kernel bypass" approach using virtualization. This method elevates the privilege level of the database process through a hypervisor, allowing it to access privileged information and use features like paging, interrupts, and protection rings.

A case study on the fork problem demonstrates a 20x reduction in copy operations using this approach. The privileged database remains a process, preserving compatibility with Linux tools and ecosystem. Xinjing argues that this evolutionary approach is preferable to a unikernel solution, as it doesn't require abandoning the Linux ecosystem.

Margo found the work interesting but questioned how it would be avle avoid past issues with kernel extensions work in the 1990s. Bruce Lindsay argued that fork isn't a significant problem for databases and that checkpoints don't necessarily require it. He said "we don't need much but we complain about what we get."


Session 4: Testing, Faults, and Privacy 

Also known as, the "Oh shit!" session.  

FoundationDB Testing? Not Very Good, Actually!- Ben Collins (Antithesis)

Ben, formerly of FoundationDB and now with Antithesis, talked about the limitations of deterministic simulation testing (DST) and discussed the extended approach Antithesis takes to system testing.

Ben acknowledges the benefits of DST, such as replayability and time machine capabilities, but highlights significant drawbacks: High implementation costs, Deep integration requirements, Design limitations due to determinism constraints, and Prohibitive computational costs for bug search.

To address these issues, Antithesis developed a more generalized DST approach over the past six years. Key features include:

  • Simulating at the computer level rather than system components
  • Focusing on blackbox bug finding and correctness testing
  • Combining multiple signal types: direct feedback, code coverage, and anomaly detection
  • Addressing search challenges like local maxima and sparse signals

He said that with FoundationDB we were trying to get lucky with search, but here we bias the search strategy to find the bugs. The customers ask Antithesis to find violations of certain types of exceptions and panic statements, and Antithesis nudges things to explore these violations efficiently and effectively. To tackle workload issues, they use once-seeded PRNGs and batched validations. I got the impression that determinism is there to cope with not having infinite memory or time, as sort of a compressing mechanism.

Antithesis offers SDK support for various languages, integration with development tools, and actions on CI platforms. An example test demonstrated the ability to find exceptions under heavy loads within 2 hours of wall clock time (96 test hours including parallelization).

When questioned about non-deterministic bugs, Ben explained that their system wraps tests in a deterministic hypervisor. He also noted that fault-injection and thread pausing techniques are employed to quickly identify bugs before applying more complex search strategies.

I know that MongoDB is a satisfied customer of Antithesis. I think they do a good job of balancing between comprehensive coverage and practical exploration of implementation for large scale systems. 


When Bad Hardware Happens to Good Databases- Scott Andreas (Apple)

Scott, an engineering leader at Apple working on Cassandra, discussed the challenges of building reliable database systems on unreliable hardware. He emphasized that bit flips, seemingly minor errors, can have severe consequences, particularly when they affect critical operations like distinguishing between enum operation types of "update" and "drop_table" commands.

He outlined various hardware issues affecting different components. DRAM faces challenges with socket connectivity, thermals, and signal integrity. Flash memory suffers from voltage degradation and wear, while CPUs can have manufacturing defects, thermal issues, and cache faults. While protection mechanisms like ECC and page offlining exist for DRAM, they aren't comprehensive solutions.

Flash memory presents other unpleasant surprises, with increasing density leading to higher error rates. With high write rates, and write amplication, they get more prone. PCIe-related issues in storage and network interface cards also require attention. Scott stressed the importance of enabling advanced error reporting for these components.

As we found out from Google and Facebook reports, CPUs are prone to silent Corruption Execution Errors (CEEs), and these necessitate burn tests and ongoing tracking of hardware performance over time.

A significant portion of the talk focused on checksumming as a crucial strategy for maintaining data integrity. Scott recommended Cyclic Redundancy Check (CRC) for its balance of efficiency and effectiveness, highlighting the textbook by Koopman on CRC polynomials.

In the Q&A, Brooker suggested that modern systems should use GMAC or cryptographic MACs, which are hardware-accelerated and can address potential spoofing attacks on CRCs.

These are scary problems indeed. For maintaining data integrity we cannot take hardware including CPU reliability for granted. We should ponder on the overhead involved in addressing computational CPU problems in particular.


Hyper-reliability for Hyper-scale Databases - David Bacon (Google)

David discussed the challenges of maintaining hyper-reliability in hyper-scale databases like Spanner, which manages over 15 exabytes of data. Spanner underlies most of Google's external-facing products and is scaling towards zettabyte levels.

This is another doom talk. It could be depressing to hear about these, but we need to face up to the reality and ruggedize our systems. 

David highlights the issue of Corrupt Execution Errors (CEE), which can lead to silent data corruption or worse corrupted program states. To combat this, Google employs various protection techniques, including checksumming for 32K blocks with 32-bit checksums before encryption, validated on write and read operations.

They implemented a corruption monitoring pipeline, processing debug reports and evicting compromised machines. David calls this their sensor array. This system caught a device driver corruption bug, though it took 18 months to debug fully.

Google also developed the Tinfoil library, featuring "paranoid variables" for high-impact values (e.g., # records in file). This approach has a 90% conviction rate and only costs 0.1% in performance overhead.

David concludes that silent data corruption will worsen with advancing technology nodes and growing database sizes. While safe languages can help, they're not sufficient for lower abstraction levels. The sensor array approach shows promise, and interestingly, memory corruption is rarer compared to CPU corruption.


Privacy-Preserving Databases: What will you favour? Serializability or scalability? (Cuz you aren’t getting both) - Natacha Crooks (UC Berkeley)

Natacha discussed the challenges of creating privacy-preserving databases, focusing on the trade-offs between serializability and scalability while ensuring privacy. She used electronic health records (EHR) in the cloud as a motivating example, emphasizing that encryption alone is not sufficient for privacy, as access patterns by specific type of doctors can reveal sensitive information.

To set the problem up, Natacha talked about their previous work on two systems: Obladi and Snoopy. Obladi achieves serializability and privacy but at the cost of performance, being 10X slower than MySQL on TPC-C benchmarks. It uses a trusted centralized proxy and Oblivious RAM (ORAM) to hide workload patterns (making storage look completely random) by employing techniques like delayed commit notifications (because serializability only needs to hold at commit time) and epoch-based processing to amortize costs.

Snoopy, on the other hand, prioritizes scalability and privacy, performing 13X better than Obladi. However, it sacrifices transaction support. Snoopy replaces the central proxy with multiple load balancers, each with a trusted enclave, and uses techniques like deduplicating writes at the load balancers and arranging reads before writes to improve performance.

Natacha concluded that while both serializability and scalability can be achieved with privacy, combining all three remains a challenge. The choice between Obladi and Snoopy represents a trade-off between transactional consistency and performance in privacy-preserving database systems. She is trying to deal with this problem in her research. It is really an interesting research question. 


Gong show

After the dinner, we had a gong show session.  These are quick 5 minutes talks each on miscellaneous topics. Here are the titles:

  • Kyle in Absentia - Jepsen test of Datomic, and unusual Intra-Transaction Semantics - Adrian Cockcroft (OrionX)
  • Metadata is underrated - Danica Porobic (Oracle)
  • BigQuery Omni: Shipping and supporting the monorepo on AWS/Azure - Jeff Johnson (Google)
  • Vector-Relational Databases (and how to avoid historic recurrence) - Viktor Sanca (EPFL)
  • Using SmartNICs for Database Management - Phil Bernstein (Microsoft)
  • Leaky Memory Abstractions: Hidden Performance Loss on Modern Hardware - Hamish Nicholson (EPFL)
  • Shipping up to Space - Robert Bayer (ITU Copenhagen)
  • Plus ça change - Sailesh Krisnamurthy (Google)
  • Missing the Metaphor for Self-Driving Databases - Johann Schleier-Smith (CrystalDB)
  • Sharing Data Loading - Titus Theodorus (Ties) Robroek (ITU Copenhagen)
  • Make DBs (for GenAI) Declarative Again - Yannis Papakonstantinou (Google)
  • Text2SQL is Not Enough: Unifying AI and Databases with TAG - Liana Patel (Stanford)
  • Optimizing Distributed Protocols with Query Rewrites - David Chu (UC Berkeley)
  • Fixing Distributed Consensus to achieve scalability - Chuck Carman (Amazon)

David Chu won the best presentation award. This is top-notch story telling. He took a bold approach, using 4 of 5 minutes on the build up, and the last minute for pay-off. I was lost at the end of the 4 minutes about what even the title was, and what point he could possibly make after all this built up about Yugi-Oh playing cards. But then boom, boom, boom, came the pay-off! It was great, I won't ruin it for you. Please watch it yourself. 


Comments

Post a Comment

Popular posts from this blog

Hints for Distributed Systems Design

-
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?

-
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

-
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)

-
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 >>

Foundational distributed systems papers

-
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. Expository papers
Read more >>

Advice to the young

-
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 >>

Linearizability: A Correctness Condition for Concurrent Objects

-
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 >>

Scalable OLTP in the Cloud: What’s the BIG DEAL?

-
Image
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 sa
Read more >>

Understanding the Performance Implications of Storage-Disaggregated Databases

-
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 >>

Designing Data Intensive Applications (DDIA) Book

-
Image
We started reading this book as part of Alex Petrov's book club . We just got started, so you can join us, by joining the discord channel above. We meet Wednesday's 11am Eastern Time.  Previously we had read transaction processing book by Grey and Reuters. This page links to my summaries of that book. Chp 1. Reliable, Scalable, and Maintainable Applications I love the diagrams opening each chapter. Beautiful! The first chapter consists of warm up stuff. It talks about the definitions of reliabilty, scalability, and maintainability. It is still engaging, because  it is written with an educator and technical blogger voice, rather than a dry academic voice. This book came out on 2017. Martin is working on the new version. So if you have comments for things to focus on for the new version, it would be helpful to collect them in a document and email it to Martin. For example, I am curious about how the below paragraph from the Preface will get revised with 8 more years of hindsight:
Read more >>