See all blog posts

Can AI Write Database Internals?

A new cache policy in days, weeks stuck with no measurable gain, and an MVCC invariant Claude overlooked

I’ve been intrigued by the W-TinyLFU caching algorithm for over a decade now. Back in 2015, my former CS professor Roy Friedman co-authored a paper on TinyLFU: A Highly Efficient Cache Admission Policy. I stumbled upon it by accident in 2016, when it was referenced in a Cassandra pull request for Caffeine (a TinyLFU implementation in Java). It’s good stuff, and it’s used in projects like Kafka and HBase as well as Cassandra.

I figured we could/should just switch ScyllaDB to W-TinyLFU too, and back in 2018 I added a GitHub issue. It seemed likely to provide better performance than our LRU approach, so why not? Well, it wasn’t so simple after all. We didn’t really start coding it for 8 years and it’s still not merged. The ScyllaDB Engineering team was busy with other priorities, and coding – plus extensive performance testing and regression testing – was going to require a substantial amount of work.

So like hundreds of other enhancement ideas, W-TinyLFU was dormant, like Sleeping Beauty waiting to be kissed.

AI to the rescue!

As CEO, I mostly read commit messages nowadays (well, to be frank, I only read new key PR titles – and I read the pull request full message only if the title is attractive enough). Gladly, I couldn’t resist getting my hands dirty again on my Linux laptop with Claude. My first adventure in vibe coding was something I call “Deal Chat.” ScyllaDB sells thousands of SKUs across server types and configurations, and our quoting tool was just miserable to configure. I rebuilt it with AI in two weeks, using about 5% of my capacity between meetings and after midnight. I got it into production, then the sales team started asking for features like DocuSign support, WalkMe-style help captions, a bug tracker for people without Jira access. Each of those took about a day, and adding an AI chatbot took two prompts. Look ma, I can ‘code’ again!

I was hooked, so I thought: Let’s get back to database coding. An obvious choice was the good old W-TinyLFU that was waiting for a prince. It’s not in the R&D main path and it can be a wonderful playground. AI had already proven it could build applications, fix bugs, even “rewrite it in Rust.” But what about implementing high-performance infrastructure? This post covers my experience. (Spoiler: AI was quite helpful.)

Background: Why replace LRU?

First, more background on why I was interested in W-TinyLFU to the point that I remembered filing that issue ~8 years later.

Least Recently Used (LRU) is a good and convenient cache algorithm, but it has a major problem. If you have “hot” (frequently used) data and “cold” (rarely used) data, a background scan attack of cold data can push the hot data out and pollute the cache. That causes you to lose your hot data for a while, which isn’t great for performance. (ScyllaDB added a “bypass cache” command to help in these situations).

A better approach to caching would track not just recency, but also the frequency of usage.

The problem is that if you track the usage frequency of every item, your RAM will max out. (For most databases, ScyllaDB included, the working set size is much smaller than the entire database). TinyLFU avoids that with an approximation technique called Count-Min Sketch, which uses far less memory per cache entry.

Additionally, W-TinyLFU uses three different connected caches:

  • Admission Window: A tiny LRU cache. New entries land here first, so a scan churns through the window and never touches the main cache.
  • Probation Area: A place where new items from the window compete against existing entries using frequency.
  • Main Cache: The final area where frequently used items are kept. Items are promoted and demoted between these areas based on their frequency and LRU order.

The cost of the W-TinyLFU algorithm is pretty good compared to LRU, exact LFU, and ARC. W-TinyLFU has the lowest memory overhead, a high hit rate, no ghost entries, and it tracks the optimal hit rate better.

The paper says the implementation complexity is “low,” but I’m not convinced. It’s more complex than LRU. Each cache is simple, but the combined implementation is not.

Vibe coding W-TinyLFU for ScyllaDB

To implement W-TinyLFU for ScyllaDB, I started a loop of coding with AI, testing, performance testing, and optimization. It was refreshingly fast to generate the first version. It was so easy to ask the AI for changes (for example, switching from partition-level to row-level caching granularity) as well as adding metrics, analyzing cache hit rates, and writing tests. I was coding and contributing at a pace I never did before.

However, I hit a wall. It worked, but I couldn’t show any actual performance gains.

Many entries were hitting the initial window, but very few were reaching the protected area where the hot keys are supposed to live during parallel scan attacks. The above graphs compare the 1% window vs. the 50% window vs. the 99% window (which basically acts like regular LRU). I was stuck here for weeks.

To battle this, I asked AI to do a thorough code review, compare my implementation to Caffeine, and explain the architecture differences so I could find the problem. I also had Claude write a simulator – first in Python, then translated into JavaScript, so it will live as a static page. That was so easy with AI! Now I could test hot keys, run scan attacks, and visualize how different window sizes promote entries over time. See the simulator for yourself. This made it much easier to test configurations and find the right use cases.

Finally, success

Using those techniques, I eventually hit success! In my test comparisons between W-TinyLFU and LRU, I finally saw a significant improvement in hit rates. Items were properly promoted to the main cache, and LRU ended up having 1.4x more evictions than my implementation. Things were running much better with W-TinyLFU.

However, when I checked the P99 latency, it was almost the same. This felt weird; how could the hit rate improve so much without any real improvement in latency?

The main reason was that I was running tests on a large machine using just a single vCPU, so the disk wasn’t under heavy load. The better cache hit rate didn’t really help latency because disk access wasn’t the bottleneck.

To isolate the impact of cache misses, we (Claude and I) used FUSE to create artificial delays for disk access. With that diagnostic setup, P99 latency fell from 27 ms with LRU to 6.7 ms with W-TinyLFU. That’s roughly a 4x improvement.

(Later, I ran more extensive tests with a real 3-node cluster and multiple vCPUs per node.)

Still, I wanted to optimize the performance even more. I felt there were far too many parameters. Why 1% for the window? Why not 50% or 3%? Going back to the paper together with Claude, I discovered “Hill Climbing” was already covered by Ben Manes, Caffeine maintainer. It automatically changes the window size over time instead of staying stuck on a static setting. It was simple to implement with basically just one prompt, and easy to instrument with Grafana. You can just watch the hill climber converge towards better performance.

But database code is tricky

Before merging, I had Claude generate tests for me. You can set a very specific hot key at the exact temperature you need without dealing with tens of thousands of keys. Bisecting test failures was just one prompt away; often I’d give a command before going to sleep and check the results in the morning.

However, database code is tricky. Databases have MVCC (Multi-Version Concurrency Control), which is one of the most difficult and intricate areas of the code.

ScyllaDB’s MVCC implementation has an invariant: when multiple versions of the same partition are cached, the older version (V1) must be evicted before the newer one (V2). LRU preserves this ordering. But with W-TinyLFU, entries can be promoted/demoted between cache regions, and that could disrupt the order MVCC relies on. The result is a correctness risk, even if the cache algorithm is working as designed.

Neither Claude nor I accounted for this invariant when we started, and Claude missed it during its reviews. Two of our leading developers who were familiar with the code rejected the pull request. We considered changing the MVCC code, but it’s too risky. Instead, we opted for a less intrusive change: bypass MVCC for partitions without clustering keys. My pull request is currently waiting on another PR that bypasses MVCC. Along the way, I also got rid of special handling for the index page cache. That’s a small nice gain. The index page cache carved out an isolated 20% cache pool which was static; now, it’s possible to use one large pool and the code is simpler. Overall, I consider the experiment to be a success, even though merging is pending that prerequisite PR.

Looking back, there were definitely issues with AI. For weeks, Claude fed me plenty of false positives and stories about 1% performance gains. 1%?! I was aiming for 4x. It also completely missed the MVCC design flaw. AI struggled, but after 8 years of no movement on this algorithm, it is finally committable this year.

Adding Parquet support

I didn’t want to stop there. Next, I tried adding the Parquet file format to ScyllaDB. Parquet keeps data column-by-column rather than row-by-row, so compression can be dramatically better—up to three times better than our best existing dictionary compression with ZSTD. For time series, Parquet saved 93% of the dataset, leaving only 7% of the original size vs 21% for ZSTD.

Parquet is a complicated format with lots of internal structures I knew nothing about. Together with AI, I generated design guides to understand the structure, where metadata fields are kept relative to row groups, and the trade-offs between point reads and scans across different row and page sizes.

For latency, there’s a clear trade-off: if you have nine columns, Parquet has to open compression column-by-column, so a nine-column search costs nine times more than a single column. AI was super helpful for representing these trade-offs and generating HTML guides for code reviewers to walk through top focus areas.

Parquet is about to be merged into the main database in a couple of weeks with great results, including encryption at rest. It took seven straight 24-hour days of Claude running agent work to complete and test everything.

The verdict

So, going back to the question: Can AI write database internals? Hell yeah, it can. Can it write fast database internals? The hit-rate and latency numbers indicate that it can. Can it write fast, stable, and consistent database internals? Remember the MVCC problem? Well, it depends.

Even if AI has a 5-nines accuracy factor, a database tracks trillions of objects with complex parallel interactions: locking, sorting, indexing, page sizes, MVCC, and caching. Multiplying those decisions across parallel states leads to errors. When I asked AI to model its error ratio, it tracked 57 defects caught by other AI review models and classified them by severity and type.

Now, let’s compare the imperfect AI to a human. The average developer cannot write a database. Great developers can write databases; some of them can even write fast and stable databases. But a single developer, even today, even at ScyllaDB, cannot understand and cannot be an expert on the entire codebase. So I find AI the best tool we’ve got to code databases. It can accelerate your results, massively. But it cannot be run completely alone…at least not today, maybe in the future.

Overall, I had a fantastic experience, and I’m just dying to do more with AI.

About Dor Laor

Dor Laor is co-founder and CEO of ScyllaDB. Previously, Dor was part of the founding team of the KVM hypervisor under Qumranet that was acquired by Red Hat. At Red Hat Dor was managing the KVM and Xen development for several years. Dor holds an MSc from the Technion and a PhD in snowboarding.