Metadata

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

Wow, what a week that was! The two days of HPTS (Monday and Tuesday this week) felt like a week to me. I learned a lot, and had a lot of good conversations, and even was able to squeeze in some beach walks in there.  HPTS has been operating since 1985, convenening mostly every two years. It has been described as Davos for database systems. Pat Helland has been running HPTS since 1989, and as usual he kicked it off with some short opening remarks 8:30am Monday morning.  Pat reminisced on the early HPTSs which discussed cutting edge work on scalable computing, punching past 100 txn on a mainframe! Then he quickly set the context of the workshop. This event is about meeting people. There are 130 people, with 20+ of them students. He said "your job is to meet everyone, HPTS is about the connections you make". The HPTS website also emphasizes this. "HPTS is about the breaks. The presentations punctuate the breaks! HPTS exists to promote community and relationships. This comm

Chapter 5 of the Designing Data Intensive Applications (DDIA) book discusses strategies and challenges in replicating data across distributed systems. I had covered the first part last week , here is the second part of leaderless replication. Leaderless replication abandons the concept of a leader node, and allows any replica to directly accept writes from clients. This method, while used in some of the earliest replicated data systems, fell out of favor during the dominance of relational databases. However, it regained popularity after Amazon implemented it in their in-house Dynamo system (not to be confused with DynamoDB). This inspired several open-source datastores like Riak, Cassandra, and Voldemort , which are often referred to as Dynamo-style databases. In leaderless replication systems, the concepts of quorums and quorum consistency are crucial. These systems use three key parameters: n: the total number of replicas w: the write quorum (number of nodes that must acknowledge a

Chapter 5 of the Designing Data Intensive Applications (DDIA) book discusses strategies and challenges in replicating data across distributed systems. Replication is critical for ensuring data availability, fault tolerance, and scalability. One of the key challenges in replication is maintaining consistency across multiple replicas. Leader-based replication, the most common method, involves a single leader node accepting all writes, while follower nodes replicate the leader's changes. While single leader replication does not guarantee consistency readily (due to leader failover cornercases), it gives us a fighting chance. One primary advantage of leader-based replication is its simplicity: all write requests are serialized through the leader, ensuring a consistent order of operations. Followers receive a stream of changes (i.e., the replication log) from the leader and apply them in sequence, ensuring eventual consistency. However, replication lag, the delay between when a write i

This paper appeared in CIDR23 and is from Meta (wow, this is the first time I used the new name without needing to mention it is in fact Facebook... wait.. goddammit). The paper talks about how they applied Raft to MySQL replication, and used the flexible quorums in the process. This is not a technically deep paper, but it was interesting to see a practical application of flexible quorums idea to Raft rather than Paxos. The most technically interesting part is the adoption of flexible quorums to Raft rather than Paxos. What is the difference? Flexible quorums idea was developed for Paxos's two phases. But, Raft needs to impose an extra requirement on quorums in order to guarantee Leader Completeness: "the new leader must already have all log entries replicated by a majority of nodes in the previous term." The paper does not call this explicitly. This is what the paper says: "For state machine safety, every data commit quorum needs to intersect with every leader elec

This second part of Chapter 4 of the Designing Data Intensive Applications (DDIA) book discusses methods of data flow in distributed systems, covering dataflow through databases, service calls, and asynchronous message passing. For databases, the process writing to the database encodes the data, and the reading process decodes it. We need both backward and forward compatibility, as older and newer versions of code may coexist during rolling upgrades. The book emphasizes that *data often outlives code*, hence this makes schema evolution crucial. The techniques we discussed in the first part of the chapter for encoding/decoding and backward/forward compatibility of schemas apply here. Most databases avoid rewriting large datasets when schema changes occur, instead opting for simple changes like adding nullable columns. For service calls, the chapter primarily discusses web services, which use HTTP as the underlying protocol. Web services are used not only for client-server communicatio