Table of Contents

• Introduction
• Switching the Course Projects
• What Did We Change in Fall 2023
• The HyPer MVCC Project
  • Deciding on the Base Implementation
  • Now It’s Meeting Time…
• Balancing the Difficulty
• Calcite on BusTub
• What’s next

Introduction

It has been a busy semester and also my last semester at CMU. I have finally retired from the 15-445/645 teaching assistant position. Thanks to the whole TA team and Andy/Jignesh, the BusTub project evolved significantly and saw exciting changes over the past semester. In this blog post, I will go over all these changes and the outlook for the BusTub project.

This is part of a series of blog posts about the design choices and goals of the BusTub project during my time as a TA for the Database Systems course. Previously, we had…

• A Year in BusTub
• Query Processing in BusTub

Switching the Course Projects

In previous semesters, the course projects were composed of:

Overall, the course staff tries to rotate something every semester, while the structure of the course projects has largely stabilized—students build the BusTub system from the bottom up. They first build a buffer pool manager to learn how other parts of the system interact with the storage pool; then, some kind of index to learn how to use the buffer pool; next, query executors over the storage components they built in the previous two projects; and finally, concurrency control.

Because 80% of the course projects stay the same across semesters and people outside CMU post solutions online, things are getting a little trickier. Students read source code and walkthrough articles from other students on the Internet without thinking through systems programming problems on their own. Some start the course projects before the semester begins rather than on the intended dates because most of the content stays the same.

Apart from the public solution and early start problems above, we also want to improve the quality of the course projects to help students learn more and achieve their learning goals. We want to balance the difficulty of the projects so that students can have a progressive and smooth experience during the semester. I redesigned the C++ Primer project to incorporate the C++ features that students will use throughout the semester so that students can learn these features early in the semester and have a solid foundation in C++ programming. The B+ tree project has been revamped several times by adding more guides and helper functions to ensure its difficulty fits well as the second project in the course. During this semester, we introduced a new MVCC project to better balance the difficulties.

Besides balancing project difficulty, we also want to ensure that the functionality students implement is correct by adding more test cases and improving their completeness. Every semester, when we revisit the test cases and student feedback from previous semesters, we find bugs and design flaws in the reference solution and fix them before releasing the projects.

In summary, we want students to get something out of the course, think on their own, practice systems programming, and have a smooth learning experience. At the end of the semester, students should feel a sense of achievement from building a database system, understand the core ideas behind database system implementation, and have stronger systems programming skills. Therefore, we made some big changes to the course project composition this semester.

What Did We Change in Fall 2023

• In Project 0, Abi introduced a C++ bootcamp composed of snippets that use different C++ features. We saw far fewer students during office hours for Project 0 than in previous semesters.
• We added a disk scheduler in Project 1 so that the project has a more reasonable workload and students can implement I/O workers to exploit disk parallelism.
• We switched from the B+ tree index to the hash index to lower the difficulty of the second project.
• We put more emphasis on query optimization in Project 3: point index lookup optimization, window functions, and group top-N optimization.
• In Project 4, students implement HyPer-style multi-version concurrency control. This project requires a good understanding of everything they implemented before—it involves MVCC indexes (Project 2) and new access method executors (Project 3). It is also a super flexible project: we guided students through the algorithm they needed to implement without giving them any pseudocode, and we used behavioral tests (which I will discuss later in this post). I feel this project is truly challenging.

This creates a natural progression of difficulty throughout the semester—simply following and implementing pseudocode (Project 1), reading pseudocode and debugging concurrency issues (Project 2), reading the code of existing components and seeking ways to achieve a programming goal (Project 3), and making their own design choices based on what they implemented before (Project 4).

The HyPer MVCC Project

Deciding on the Base Implementation

One of the most significant changes this semester is the newly designed Project 4—multi-version concurrency control. This is super challenging and interesting to work on.

I had been thinking about redesigning the concurrency control project since my first semester there. At that time, we asked students to implement a lock manager and deadlock detection and to add 2PL to query executors in the concurrency control project (the fourth one). However, the implementation was somewhat problematic when it came to 2PL query executors. There were no concurrent test cases, and the reference solution itself did not seem correct. Implementing 2PL in a single-versioned database also did not seem common in industry database systems, as most products use more efficient MVCC implementations. In the spring semester, because Andy was not teaching the course (Charlie was), he asked me not to change the projects too much and risk creating problems. Therefore, I worked on enhancing the test cases and better integrating the lock manager with the executors. At that time, I realized that MVCC was the only viable path if we wanted to integrate indexes and isolation levels into the system. In the fall semester, I therefore started refactoring the codebase and adding MVCC support.

There are many MVCC implementations we could take from existing database systems. I compared them and ultimately chose the HyPer approach. The HyPer implementation is simple and elegant. It stores the latest tuple in the main table, while all old-version data is stored in transaction-local buffers. Serializable verification is based on traditional backward OCC with precision-locking optimization. Because most operations happen in memory, students do not need to interact with the buffer pool manager and can focus on implementing the algorithm itself. Reducing contention on disk also makes it possible for students to optimize performance and reason about concurrency issues.

HyPer is an in-memory database, while BusTub needs to persist data to disk. A later Umbra paper ports the HyPer MVCC implementation to a disk-based database system. Neither paper provides implementation details down to the pseudocode level, so I had to figure out many things myself. While the papers mainly explain how to construct the in-memory format for undo logs and perform precision locking, many implementation details remain unspecified: the procedures for insertions, deletions, and updates; what to store in the index; how to store the version chain in a disk-based system; and so on. Therefore, I made several design choices in BusTub to adapt the algorithm to our educational system while simplifying the project. The figure below visualizes the BusTub system.

1. In HyPer, there is a version vector that stores the pointer to the first undo log in the main table. In Umbra, the version vector is part of the buffer pool manager that is fetched along with the page. In BusTub, we store the link to the first undo log in the transaction manager. This turned out to be a bad design choice because we can never atomically insert the latest version into the version chain, and Avery will fix this in future semesters.
2. The HyPer implementation uses a doubly linked list so that it is easy to traverse backward through the version chain and perform garbage collection while transactions are running. In BusTub, we use a singly linked list for the version chain to make it simpler to add entries to the head.
3. And because of the version chain linked list direction choice, we have to implement stop-the-world garbage collection instead of transaction-level garbage collection.
4. We store exactly one undo log for a tuple in a single transaction to avoid the complexity of having multiple undo logs with the same timestamp in the version chain when a transaction completes.
5. We do not garbage-collect the index or table heap, which means that the index always grows and unused slots in the table heap are never reused. This also greatly simplifies the implementation.
6. (Not shown in the figure) To simplify the serializable verification, we did not implement the precision locking algorithm. Instead, we simply have a write set and a read predicate set to do backward OCC verification.

Things worked well, and I spent half of my fall break working on the reference solution for the new project. By the end of the break, we had everything ready—version chains, indexes, aborts, and serializable verification. I spent another week on the write-up and yet another week designing the test cases. I broke my own implementation twice and spent some hours fixing it.

Now It’s Meeting Time…

At the first meeting about this project, I presented it as 10 tasks, each of which I expected to take students 2–3 hours to complete. Abi was like, NOOOOO YOU CANNOT ASK STUDENTS TO IMPLEMENT HYPER. Yuchen was like, okay… I partially understand the algorithm. Avery was like, THIS IS SO CLEVER, but I have a few more questions. Andy was kind of, well, it’s exciting to have MVCC in the course project, but we need to cut down the workload. Jignesh then followed: this is exciting, and I really want to have that… but you need to think about the students—if everything is hard, it will be a disaster; if we have three things that challenge students, such as version chain maintenance, garbage collection, and index insertion concurrency, it will be good. Anyway, the course staff felt that the whole thing was too hard for students to implement.

The other day, after the DB lab meeting, I pitched the new MVCC project to Wan. As a former CMU undergrad who took 15-445 (well, I did not take the course because I TAed in my first semester), Wan provided a good estimate of how a typical student would fare when working on the project. In the end, the course staff agreed on an easy 80 points for the MVCC implementation and a hard 20 points for concurrency and index work, with an extra 20 bonus points for aborts and serializable verification. I assumed that getting 100 points would be as hard as the previous B+ tree project.

I also designed the project to have two leaderboard rankings: one for speed and the other for space utilization. Students can get the full leaderboard bonus only if their implementation is both fast and space-efficient. By optimizing for multiple, somewhat competing goals, students can learn about the tradeoffs involved in designing a system.

Balancing the Difficulty

So far, I have described how we designed the point distribution to make the first 80 points easy to earn and the remaining points difficult. I also employed multiple ways to balance the difficulty of each part of the project.

I see the MVCC project as a system design problem: we provide the specifications and interfaces in the write-up and perform minimal checks on internal structures (mostly behavioral tests using SQL), while students make their own design choices in a variety of areas. These are the design goals I have in mind:

• Understand existing code. Students will need to understand the structure of the current codebase and know which parts they can use to achieve a design goal.
• Understand design specifications. Students will need to read the write-up and understand how HyPer MVCC works.
• Implement the MVCC algorithm. Based on the code we have and the specification in the write-up, students will need to know how to leverage existing BusTub interfaces to implement the specification.
• Make design choices for parts of the MVCC algorithm. Specifically, students will need to consider edge cases and establish the correct order of operations for index modifications, aborts, and serializable verification.
• Debug and fix system code. We have some super hard concurrent behavioral SQL tests to ensure the system works correctly in a multi-threaded environment.
• Optimize for performance and efficiency. As part of the leaderboard tasks.

To achieve these design goals, I applied a variety of strategies across the project.

Write-up. We explained all the edge cases for insertion, deletion, and updates without indexes in the write-up. For the concurrent portion and index operations, however, we provided only a general approach to modifying the version chain. This creates a natural progression in the project’s difficulty. Students who fully understand how to interpret the version chain can easily pass all single-threaded tests. They will then need to reason about race conditions themselves when implementing later parts. I used many figures to illustrate how to perform an operation step by step. Anyone who has worked with me at a company will find that the MVCC project write-up is basically a Chi-style design doc…

Refactors / Design Choices. It is easy to handle things when there is only one thread and the test cases are simple. However, when MVCC indexes and more concurrent tests arrive, students need to make design choices and perform some refactors. For example, all DML executors—insert into an unused slot, delete, and update without changing the primary key—do the same thing: update a tuple. They can update a tuple to either a deletion marker or a new value. At this point, students should realize that they need to extract the common logic into a helper function. For the storage format, we tested only the minimum requirement (i.e., one undo log for one tuple in one transaction, plus replaying the undo logs). Many decisions are left to the students, such as whether to store data with the deletion marker. When it comes to the bonus tasks, students will likely need another refactor because the sequential scan code is reused across sequential scans, index scans, garbage collection, aborts, and serializable verification. Having one helper function for all these operations can help them organize the code and fix bugs in one place.

Testing

• Hidden test cases vs. public test cases. We make all concurrent test cases available to students so that they can debug them on their own. For single-threaded test cases, we hide only those after the 80-point boundary, which encourages students to design their own test cases and think about edge cases in a later stage of the project.
• Concurrent tests vs. single-threaded tests. We have hard concurrent tests only after the 80-point boundary. Single-threaded tests can detect logic problems in the implementation, while concurrent tests can exercise the system comprehensively. A good combination helps students detect logic errors early so that they struggle less when debugging concurrency issues.
• Debug information. We asked students to implement a debug helper function to dump the version chain to stdout. I remember a student came to my office hours asking for garbage collection problems without implementing that helper function. I asked him to do that before I could help. After he dumped the table heap and version chain out, he immediately realized the timestamp written to the table heap was wrong.
• Large vs. small test cases. Most of our test cases contain fewer than 50 lines of SQL, making it easier for students to understand what is going wrong in their systems.
• Behavioral tests vs. tests of internal structures. We employed minimal checks on the internal structures of the version chain. Only the test cases for the first 30 points directly manipulated the table heap and version chain. All the remaining test cases create transactions and use SQL queries to verify whether the result received by the user is as expected. This helps students see the connection between their MVCC structures and the end-user experience: when a user requests a SQL query with snapshot isolation, how does the system satisfy that isolation level internally? I remember that, in the query executor project before I came to CMU, after students implemented the executors, the test cases simply set up the executors programmatically and verified their output. TAs who had taken the course before complained that they did not understand how SQL mapped to these executors. After I added the SQL layer, they saw the connection between what they implemented and the SQL user interface, and they understood the full lifecycle of a SQL query. Understanding a system from its top-level user interface down to its internal implementation can help students gain a complete view of the system, which is an exciting learning experience.

Grading

• Point distribution. 80 easy points, 20 hard points, and 20 bonus points ensure students worry less about their grades and challenge themselves.
• Two Leaderboard Rankings. Students can learn about tradeoffs in a real system when they optimize for two competing goals. With a vanilla implementation, students who achieve higher throughput will have more garbage in their systems, and vice versa. However, performing garbage collection too frequently will also affect the system’s performance. A good implementation should balance these two goals.

With my approach to balancing the project’s difficulty, the grade distribution was as expected. About 10 students finished all tasks, including the bonus tasks, and 20% of the students earned 100 points. About 50% tried to reach 100 points but did not, while nearly all students earned 80 points on this project.

Calcite on BusTub

As part of my optimizer research with Andy, I studied some optimizer frameworks. Apache Calcite is the one that particularly interests me, and I tried building something on top of it.

I plugged Calcite into BusTub’s query frontend. BusTub runs an HTTP service that listens for JSON query plans and serves the catalog. Calcite parses the SQL, generates a query plan for BusTub, and sends it to the BusTub HTTP service.

The Calcite frontend opens up a lot of opportunities for BusTub — for example, students can implement semi join executors. With that, Calcite can unnest correlated subqueries and execute them on BusTub. We could have a semester focusing on execution (implementing a lot of different query executors) if we use Calcite as the frontend, and alternatively, a semester focusing on optimization (implementing a lot of rules in BusTub).

What’s next

• Recovery. This is a missing part of BusTub, and we could probably have a short recovery project as an additional final project in future semesters. The catalog should be persisted, and transition operations should be written to a redo log.
• LSM index. Most database systems using an LSM index store all data in the LSM tree rather than in a table heap. If we use an LSM index for Project 2, Project 3 will also need to support it in access method executors with primary keys, and Project 4 will need to implement MVCC over it (i.e., by adding a timestamp to the LSM key). LSM indexes also make it easier to support variable-size data because we do not update key-value pairs in place, which opens many possibilities for the BusTub project.
• Alternating between optimization and execution with the Calcite frontend.

By the way, here is my personal ranking of my favorite BusTub course projects…

• Top 1: Multi-Version Concurrency Control
• Top 2: Query Execution + Optimization
• Top 3: B+ Tree Index

Being part of an educational database project has been a fascinating experience for me. Instead of applying fancy optimizations to the system, we focus more on its readability. We want to add new features without creating learning barriers. We redesign ideas from industry and academia in the simplest possible way so that students can quickly understand the core concepts and gain hands-on experience with new technologies. We also want to create opportunities for students pursuing advanced studies in database systems to try whatever they want by keeping the design flexible, so that they can optimize their implementations however they choose. The different design goals of educational and industry systems, along with my communication with students, have shaped me into a better engineer—one who can explain complex ideas simply, help people understand my work, and deliver challenging features in a system.

Well, this is my last semester at CMU, and I have finally retired from being a teaching assistant for the Database Systems course. An exciting journey as a full-time systems software engineer lies ahead, and I am looking forward to my full-time job at Neon.

Thanks for reading, and feel free to leave your comments on GitHub.