Links for Feb and March

Sat Apr 13 2024E.W.Ayers

• Distributed Systems: Time and Order

• capn proto is fantastic docs and led down a rabbit hole.

• Cresta guy: Every infra decision I endorse or regret . The amount of bloat in infra is insane and everyone just thinks its normal.

• Signals for JavaScript. A Signal is a value that changes over time. You can write signals that are derived from other signals. Signals are cached and invalidated by a 'dirty' flag that is set whenever an upstream signal changes value. Seems ok.

• TigerBeetle talk

  • Tiger Style

• I got completely nerdsniped by an old programming language called E. They have an abandoned book brimming with exciting ideas about distrubuted / trusted computing that predates our current cryptobro nonsense.

• The Generics dilemma

• Files are Hard

• NASA powers of ten

1. PostgreSQL

I read PostgreSQL Internals. Very well written. I have mad respect for Postgres. It is a good supplement to Pavlo's database course. Some features that are worth knowing about:

• [RLS](https://www.postgresql.org/docs/current/ddl-rowsecurity.html; you can CREATE POLICY and do access control at the level of individual rows;

• GRANT command for doing RBAC.

• You can write queries in Python (!)

• Not strictly part of postgres but there is a webserver called PostgREST which automatically creates a webserver + auth for your postgres instance. I consider this the solution to Databases have failed the web.

• NOTIFY

• It is super-customisable (at least in principle). You can bring your own indexes, functions, table layouts. You can write custom query-planner rewrite rules.

1.1. Techdebt in Postgres

However, there were lots of points reading it where you can see the pain from keeping decisions made in the 80s piling up:

• TOAST is bonkers ratsnest.

• The logic required to get MVCC working is kinda nuts. Most fun chapter to read.

• The WAL seems like an afterthought, afaict lots of the more advanced features and extensibility doesn't work with the WAL.

• Query planner is cool, but also feels overabstracted and lots of complicated edge cases and ad-hoc heuristics. Particularly around choosing indexes. Sufficiently powerful planning engines like this and Prolog scare me because they become unpredictable and hard to debug when the query becomes slow. You are at the mercy of the person who designed the heuristics for the planner. This can easily become critical in real-world systems.

The problem is you have N complicated components, which are tightly coupled. Then some fundamental issue is found with component i (eg row size limit), so a solution is duct-taped on in a backwards compatible manner. But then there are N² interactions from adding this duct-tape, so you have a cascade of mess throughout the entire architecture.

1.2. Postgres dreams

The main thing that frustrates me about PostgreSQL is there is almost a full-featured programming environment in there, but then people just write their business logic in Python, Javascript, Java and stick an API on the front. If Postgres had gone a bit further (support HTTP, better auth, better DX, maybe even html templating), you could stick it directly on the internet and have it as your backend without needing to wrap it in nonsense backend layer. The reasons why this isn't done seem to be:

• Postgres' user management and RBAC isn't really suitable for application-level auth. There are workarounds as you can find in Supabase, but it seems like duct-tape.

• API versioning. Auto-genning REST endpoints directly from the tables is fine until you have some legacy downstream code that assumes a particular table. Again you can workaround with views but migrations are hard enough. Having an API written in a general purpose PL lets you have complete control over versions.

• you often need to interact with other external services

• SQL is not a great language to develop in, developer tooling is stuck in the stone age compared to modern PLs. Where is our 'TypeScript for SQL'?

• culturally, if you say your company does all application logic in postgres people are going to think you are crazy because that's not how it is done.

I think that most of these bullet points could be addressed with a carefully designed extension to Postgres, but the reality is that making postgres extensions is extremely hard for all of the tech-debt reasons discussed above. There are loads of startups (see [/blog/dbs](my database roundup)) trying to solve this but they are all doing it by adding overcomplicated application-layer cruft on top of Postgres so they can sell it as a service.

There is a Figma blog post on 'scaling postgres'. It just feels like they are bending over backwards to keep using Postgres but it's not fit for purpose.

2. RocksDB

It's a key-value (KV) store database. Keys and values are just byte arrays. It is really cool. Reading about the internals feels lovely compared to Postgres. Basically all the hot new databases cash out as a fancy frontend on a KV store. Then they choose RocksDB for the store and it is fast.

• Artem Krylysov -- How RocksDB Works

• some cool CS datastructures:

  • Log structured merge tree paper

  • Skip lists

  • Bloom filters

  • k-way merge

  • variable-width integers, similar to how utf-8 is encoded.

• The main place to learn more is the wiki. Of these the good pages are:

  • RocksDB Overview

  • Leveled Compaction

• I love all the extra features that just drop out because they chose the right way of representing data:

  • Large binary object storage. Plus a cool paper about it.

  • Merge operator

  • backups, snapshots and checkpoints, since SSTs are immutable, this amounts to not deleting SST-files and keeping track of which files were 'alive' at the given checkpoint. (afaict snapshots are in-mem checkpoints where we just keep a sequence number and prevent compaction before the snapshot horizon)

  • Write your own SST file format. Write your own Compaction system. Write your own MemTable. If you can have this much separation of concerns you are doing it right.

  • transactions with locking

• retrospective paper on RocksDB

Something about the levelled compaction mechanism captures my imagination. The way I see it: you can either store state as logs, where it's an append-only stream of actions (fast write, easy to version), or you can store it as a mutating table or state (fast query, hard to version). LST seems enlightened in that there is not a hard switch between logs and state, the logs are gradually converted to a sorted KV store through compaction. Since the blocks are immutable we can also keep snapshots without a lot of trouble.

Part of me still wants a 'time-travelling' DB where you can rewind and replay transactions to arbitrary points in time. However there is a performance cost to this which is unacceptable in real-world systems. You usually only want this for certain user-facing tables, and it's probably better to have the time-travel auditing managed at the application layer.

I like how explicit the docs are about the tradeoffs between read/write space/time. Compare with Postgres, where figuring out what the performance tradeoffs are is difficult because everything is wrapped in a query planner abstraction.

Oh yeah, also rocksdb is embedded, so you can just import it as a library rather than needing a ratsnest of dedicated processes like postgres.

Conclusion: next time I need a low-level persistence layer I'm choosing RocksDB.

3. Zig

I have been writing a GLR parser in Zig. It's just for fun. I was inspired to do so by this video about TreeSitter.

I'm starting to get into the flow of Zig. But there are still some things that I really miss:

• tooling, I want to see all diagnostics but Zig will drip-feed me the errors and I have to whack-a-mole fix them before I see the next error. I want all the diagnostics to show up in my code as red squigglies in one go. I think my vscode extension is supposed to do this but it doesn't work for me.

• goto-def can be flakey, particularly for aliases like const NodeList = TailQueue(int). Then the methods on NodeList will not gotodef in std.

• Copilot is bad at Zig and makes terrible suggestions. Coding without copilot feels like losing a limb. The fact is that most code is boilerplate or setup, and copilot instantly fills in that if it knows the language.

• Accidentally making a pointer to something in your stack frame is hard to debug. You just get wacky mutating behaviour in your stack vars and then need to hunt through for a naughty &. This is mostly due to my inexperience but it's annoying. The problem is sometimes the reference is inside some other method like an init() call. I think there is an unwritten convention that init() should always come with a defer deinit() call to enforce its lifetime to the current frame. It feels like the compiler should have enough information at least in easy cases for detecting when you are returning a structure with a pointer to something on the stack. It should be possible without descending into a full lifetime management thing.

good things:

• memory leak detection on test allocator is fantastic

• it's so fast to compile. Unbelievable.

• It's so simple and unbloated. comptime is a revelation.