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)

JAX from scratch

JAX is a differentiable programming language embedded in Python, which implements forward and reverse-mode automatic differentiation via functors and a tracing JIT. Come for a unique mix of vector calculus + category theory + compilers, as we make our own JAX.

JAX Quickstart •Pushforward and pullback •Autodidax: JAX core from scratch

code reading: Wasmi

What does it take to write a fast interpreter in 2024? We'll read the source code of a recent and relatively small (~50,000 LoC) runtime for WebAssembly, with interesting tradeoffs between startup speed and performance.

Wasmi's new execution engine •Wasmi source •Wasmtime source

disaggregated databases

Disaggregation is a technique to separate compute, storage, and memory needs in warehouse-scale computing. We'll read about how people balance these features with the limitations of networked systems.

Tutorial: Disaggregated Database Systems (SIGMOD '23) •Aurora (SIGMOD '17) •Snowflake (NSDI '20)

FoundationDB

FoundationDB is a distributed, transactional key-value store that underpins several new database systems. It claims to be strict serializable and lock-free, while having very strong failure tolerance. We'll read the FoundationDB paper and some docs.

Blog Post •FoundationDB (SIGMOD '21) •Technical Overview

Memory models

A series of three posts on how memory consistency is preserved by multicore processors: in hardware, in programming languages, and in specifically the Go programming language.

Memory Models (rsc)

New sorting implementations

Sorting is one of the most common problems in computing. It's also heavily optimized. Let's look at research into two hand-tuned sorting implementations that are tailored for performance, which were recently merged into the Rust standard library.

driftsort •ipnsort •Sort safety •Branchless partitions

code reading: Redis

We'll read the source code of Redis 1.3.6, the oldest tagged release (March 18, 2010). Redis is a cornerstone of modern systems, and its data structures power much of the Internet. But in 2010, Redis was mostly a single 9000-line C file written by one developer.

Redis 1.3.6

kernel instrumentation

The foundations of dynamic instrumentation in kernels. Case studies on DTrace (Solaris) and eBPF (Linux, Windows). Note that eBPF has a very large scope, we'll discuss the groundwork rather than applications in this meeting.

Dynamic Instrumentation of Production Systems (2004) •What is eBPF? •PREVAIL: Understanding the Windows eBPF Verifier (2023)

Intel SGX

Trusted computing: how can you possibly run sensitive code on a computer that's been completely compromised? Obviously homomorphic encryption isn't practical in 2024, so let's try to learn a bit about how SGX promises this.

Intel SGX Explained

code reading: Solid.js

A study on reactive programming. Solid is a popular frontend framework for user interfaces. It's known for fine-grained reactivity and minimal runtime overhead, being faster than React and Svelte. We'll read the source code to see how it works (~6000 lines).

Solid Tutorial •Solid

Garbage collection

We'll read the literature about garbage collection algorithms for Java. While the JVM's heap allocation interfaces have been largely the same for decades, its garbage collection algorithms have evolved to reflect changing needs.

Garbage-First Garbage Collection (2004) •Shenandoah GC (2016) •LXR (2022)

code reading: MoonRay

We'll explore DreamWorks' 3D renderer, used in films like How to Train Your Dragon. MoonRay (~650,000 LoC) is a state-of-the-art system with GPU-accelerated ray tracing, real-time distributed computation, denoising, and a huge number of materials and simulations.

MoonRay (SIGGRAPH '17) •Vectorized Production Path Tracing (HPG '17) •dreamworksanimation/openmoonray

Embedded Rust

We will read about writing embedded firmware and drivers in Rust. I bought one STM32F3DISCOVERY kit (STM32F303VC MCU) for us to share, but feel free to bring your own hardware.

The Embedded Rust Book •Embassy •RTIC •Drivers in Rust

Amazon's distributed storage

We'll read some reflections from scientists on AWS S3, the oldest service of the world's largest cloud provider. As of 2024, S3 stores over 350,000,000,000,000 objects (~100,000,000,000,000,000,000 bytes) with 99.999999999% durability.

Building and operating a pretty big storage system called S3 (2023) •Using Lightweight Formal Methods to Validate a Key-Value Storage Node in Amazon S3 (SOSP '21)

TAPL speedrun week 1

We'll read Parts I–II of Types and Programming Languages by Benjamin Pierce, a classic book on type theory. If you're like me and never formally studied this, let's speedrun through it together. Feel free to start before the meeting if you want!

Types and Programming Languages

TAPL speedrun week 2

We'll read Parts III–IV (Recursive Types, Polymorphism) of Types and Programming Languages. Try to catch up to Chapter 14 before coming!

Types and Programming Languages

TAPL speedrun week 3

We'll read Parts V–VI (Polymorphism, Higher-Order Systems) of Types and Programming Languages, completing the book. Try to catch up to Chapter 28 before coming!

Types and Programming Languages