Writing git from scratch

Git is a version control system used by the most of the world's software developers. What's under the hood? Let's get a glimpse into the workings of the .git folder, featuring content-addressed storage and hash trees.

Commits are snapshots, not diffs •Git's database internals I •Write yourself a Git

Compiling mlc, the course

Compilers in machine learning are the silent toolchains that make compute possible at massive scale, on CPUs and on hardware accelerators like GPUs. How do they work? And what really goes into doing matrix multiplication fast?

Halide •PyTorch •Introduction to ML compilers •mlc.ai

Perspectives on async

Cooperative and preemptive multitasking, schedulers, concurrency vs parallelism models, and how they influence language features. Case studies in Go and Rust internals, and mentions of Python, JavaScript, C#, Dart, and Lua.

What Color is Your Function? •Goroutines •Async/Await •Structured concurrency

The database storage layer

Host: Mufeez Amjad and Rama Tadepalli

Storage is at the heart of databases, lying below execution and query planning, but above the file system, OS, and hardware. Let's learn about them and get started with our own.

Disk-Oriented DBMS Overview •mmap •LSM Trees •Database Internals

Web browser security

Host: Raghav Anand

Security is hard, and browsers are incredibly complex artifacts with tens of millions of lines of code. What could go wrong? From distributed systems security to process sandboxing, and from type confusion to Spectre.

Understanding The Web Security Model •Spectre.js •Site Isolation •CVE-2023-3420

Build systems

Host: Val Kharitonov and Fang Shuo Deng

Build processes are complex and computationally intensive. How can we make builds fast, reproducible, and flexible, all while retaining simplicity? Maybe studying their underpinnings and reimplementing them can teach us a bit about computing.

Build Basics (Bazel) •Build Systems à la Carte

Virtualization with KVM

Complex systems tend to produce more copies of themselves, and computers are no exception to this self-referential behavior. Let's see how virtualization and emulation work on the OS and machine levels.

JSLinux •Virtio •kvm-ioctls •Book of crosvm •KVM/ARM

Structured data encoding

Schema-based binary formats, and their associated languages, for specifying and serializing structured data. Design tradeoffs for RPCs, data archiving, OLAP, and embedded.

Protocol Buffers •Cap'n Proto •rkyv •Apache Arrow •Cornflakes

What the k8s!

Kubernetes is, undeniably, tech's favorite system for deploying code. It's also crazy complex. Let's look at it (a healthy serving of YAML!), then at Slurm (a scheduler for supercomputers from the 2000s), so we can discuss what the essential complexity is.

Kubernetes (O'Reilly) •R with k8s •Cluster Architecture •CRI Spec •SLURM

Time series databases

Time-series databases index massive amounts of data. They're the tools that let engineers understand and do more with systems. How do they work, and what are the key data structures and ideas in balancing their speed, storage, and cost?

InfluxDB •Prometheus •Gorilla (VLDB '15) •Monarch (VLDB '20)

Make a plasmid viewer

You may have no idea what a plasmid is, me neither! It's a circular DNA sequence. But treat this as a complex data visualization and UI exercise. We'll each try to write an interactive SVG viewer, learning about libraries and reactive programming models.

SeqViz •Teselagen's Vector Editor

The JVM specification

We'll read the specification for the Java Virtual Machine, with a focus on Chapter 3 (compilation). Java is the most successful cross-platform compiled bytecode in the world.

The Java Virtual Machine Specification (Java SE 21)

Compilers compiling compilers

Compilers compile code. But compilers are also code themselves. It's 2024, and as we reflect on our past and present, let's also reflect on some of the classic and modern takes on self-referentiality of compilers and staging.

Reflections on Trusting Trust •Futamura •Essence of Incremental Computation

Compression with zstd

Exploring state-of-the-art lossless data compression. How do you pack big things in a small package, fast? (Note: This is a hard algorithm and we probably won't make it all the way through in one sitting.)

LZ77 •Asymmetric Numeral Systems •Zstd blog post •Zstd spec •Brotli

Media codecs

Still talking about compression like last week, but lossy codecs come with spicy cosine transforms, color spaces, and legal trickery. Video encoding is also absurdly complicated; who knew an algorithm could be broken up into 5000+ patents!

Web audio codec guide •Web video codec guide •PNG •JPEG •MP3 •VP8

zstd spec, revisited

We'll continue where we left off in Week 14 by understanding finite-state entropy in depth. Then, buckle down to read the actual zstd spec, followed by Brotli.

Finite State Entropy (series) •RFC 8878 (Zstd) •RFC 7932 (Brotli)

Linux executables

What goes into executables and dynamic linking? How do they work, and how much of their functionality is engineered versus operating system magic? We'll start reading a series by Amos Wenger.

Making our own executable packer (series)

Zig compiler internals

A blog post by Mitchell Hashimoto, dissecting the Zig compiler. Zig is a self-hosted, low-level compiled systems programming language.

A half-hour to learn Zig •Zig compiler internals

The WireGuard protocol

Host: Abel Matthew

The working operations of a secure VPN tunnel. Public-key cryptography and forward secrecy, parallelism techniques, and kernel networking.

WireGuard •Black Hat USA 2018

String indexing algorithms

What ties together FASTA, ripgrep, bzip2, Prometheus, and Sublime Text? Algorithms and data structures for practical string indexing and search, with a healthy dose of practical automata theory.

Skew Algorithm (2003) •Index 1,600,000,000 Keys with Automata and Rust

Distributed training

Training big ML models is the elephant in the room. So everyone starts by talking about compute, but it ends up being mostly about networking. Hello, data movement!

Allreduce (2017) •How to Train Really Large Models on Many GPUs? (2021) •Everything about Distributed Training and Efficient Finetuning (2024) •Tensor Parallelism with jax.pjit (2022)

Linux kernel programming

We'll read through a recent guide on Linux kernel module programming in C. (Before the meeting, get an x86-64 cloud VM with a fresh install of Ubuntu 22.04.)

The Linux Kernel Module Programming Guide

io_uring

Reading about an up-and-coming Linux subsystem for high-performance async I/O. Thinking about memory access models, buffer ownership, and fault-tolerant parallelism.

Is there really no asynchronous block I/O on Linux? •Lord of the io_uring •Notes on io-uring •tokio-rs/io-uring

Memory allocators

A discussion of general-purpose memory allocators. We'll focus on the successful jemalloc, and the newer but promising mimalloc. Let's peruse some source code if time permits.

jemalloc (2006) •mimalloc (2019) •std.heap.general_purpose_allocator

AOSA Volume 1

Selected readings from The Architecture of Open Source Applications, Volume 1. How the software we know and love was designed, redesigned, and built.

Audacity •Bash •CMake •HDFS •LLVM •Riak and Erlang/OTP

AOSA Volume 2, part 1

Selected readings from The Architecture of Open Source Applications, Volume 2.

matplotlib •PyPy •processing.js •The Glasgow Haskell Compiler

The Ceph trilogy, parts 1+2

Host: Ori Bernstein

A trio of classic papers on building a distributed file system from the ground up for exabyte-scale storage. How the biggest organizations in the world keep track of data. Let's start with the first two papers: CRUSH and RADOS.

CRUSH (2006) •RADOS (2007)

The Ceph trilogy, part 3

Host: Ori Bernstein

We'll continue where we left off from last week, reading the Ceph distributed file system paper from OSDI '06. Ceph is a near-POSIX file system built on CRUSH and RADOS.

Ceph (2006)