I want to tell you a story about a problem I spent an embarrassingly long time debugging.

The project I'm working on now is by far the most technically ambitious thing I've ever built myself. I have contributed to more technically ambitious problems, but I've never been the primary developer, or had to make as many foundational design decisions.

One of the most complicated parts of the project has been managing ordered lists. It allows multiple clients to connect to a particular list and make ordering changes. It uses Sortable.js to manage changes to the order on the client, and then a Phoenix LiveView to persist those changes to other clients, and store them off in a database. I'm now on my third design for the "store in the database" part, and it took me over a year to get here.

The Naive Approach

I started out implementing this with what seemed like a simple, straightforward implementation: Each item in the list gets a "position" field, and that position is an integer. The "move" operation changed the position of the item being moved, and then incremented the position of any element beneath it. This worked okay– at first, and for small lists.

The first sign of trouble was I started getting duplicate positions– when two clients tried to make a move to the same spot on the list, they would give both elements the same position value. I tried to fix the issue by having Postgres enforce uniqueness on the position field, but that interfered with "and now move all the other elements" part of the operation. I ended up moving all the elements that were getting moved out of the way to negative indices, and then back to their final positions. This was slow, got slower as the lists got longer, and made the "sometimes clients make moves based on stale data" problem even worse.

I spent some time thinking it through and looking at similar projects handle this problem, and thought I'd come up with a clean solution: Linked lists! Sure, this would make reading the list slower, but actually moving the elements would stay snappy. Right?

Linked Lists

The big problem with using linked lists is that if you make changes to a linked list badly, you can suddenly lose a huge chunk of the list. A linked list does not "degrade gracefully." If you accidentally set the "next" pointer on an item in the middle of the list to nil, or to an item that's not in the list, you can make the rest of the list inaccessible.

And remember: This is a system where multiple clients sometimes try to make moves simultaneously, which causes bugs where the one of the moves makes the other somewhat nonsensical. With position-based indices, this led to issues where items would have the same position. But with linked lists, this led to issues where half the list would appear to disappear from the application entirely.

The usual way that you avoid these kinds of problems is you do you read and your write inside of a transaction and enforce transaction serialization such that once state has been read for a move, it can't be referenced by other operations until the move it was read for is complete. I knew about the potential failure state here so I cleverly and diligently wrote a bunch of validations inside the transaction, which I assumed would roll back any "bad" moves that got us into invalid states.

Unfortunately for me, the default transaction isolation level for Postgres is READ COMMITTED, not SERIALIZABLE. This wouldn't have been a problem (the validations would have caught and stopped bad state from being committed) except that my validations didn't actually throw the errors I thought they would throw, so they didn't actually do anything (except add read load to the database).

It took me weeks to figure out what was going on here. I could reliably replicate the problem by running a lot of moves at the same time in a test, but because I believed that I was using transaction isolation correctly, I thought that of course the problem must be replicable with a linear, deterministic sequence. I spent a long time trying to extract that linear sequence out of the logs from tests that did replicate the error and then write a "simpler" test that produced the problem sequentially.

What got me out of the problem was sitting down and reading the code carefully with another person, and then diagramming all of the valid moves on paper.

As we read through the code together line by line, my partner eventually asked me, "Do you know what the transaction isolation level in this project?" I was pretty sure it was SERIALIZABLE, but since a lot of experience in being an engineer is remembering to check stuff that you're pretty sure about, we went and checked. And, it, uh, wasn't.

Once we realized that the transactions weren't SERIALIZABLE (and that the verifications weren't actually verifying) solving the problem was fairly straightforward.

This whole saga, though, took months, and left me pretty dissatisfied with linked lists as a solution, especially since about halfway through I encountered a much better solution: Fractional indexing.

Fractional Indexing

Fractional indexing is a lot like integer positions, except that you don't use an integer, you use something that can be divided indefinitely into finer and finer distinctions, but that's still sortable. Often you'll see this described with strings. You might start with this:

a
b
c

and then if you want to add a few records in between you end up with this

a
aa
b
ba
c

and then if you add a few more you might end up with this

a
aa
b
ba
baa
bab
c

You always have a consistent sort order, but you can always add a record in between any other record in a fixed time.

Since Postgres provides a Decimal type, I use a Decimal, just because I find it a little bit easier to read the order of Decimals. My understanding is that this is slightly less performant than strings, but I'm never dealing with enough records that this has felt like a problem.

Bugs are architecture problems

There are a few lessons you could take from this story.

It's generally been my experience, for instance, that any complex design problem takes about three tries to get right. The most complex part of most systems I've worked on ended up getting redesigned multiple times. This isn't (necessarily) a failure, it just sometimes takes a while to get a good enough handle on the problem to actually understand the design tradeoffs. A lot of long-term architecture is building the system and the organization around it such that it's possible to redesign a part of the system without having to rewrite the whole thing.

"Complex design problem" is relative. I have over ten years of experience in software development. I've worked on systems that were much more complex than this one, and technical problems that were much harder. But I'd never encountered this particular problem, so it was hard for me.

But if you take anything away from this story I think it should be this: When there's a part of your system that's "buggy," it's not a testing problem. The solution isn't more validation. The problem is with the design.

When I joined Cloud Foundry, they were in the final stages of replacing the core of the system, the container scheduler itself, with a new system written in Golang. The old version of it had been written in Ruby (and was itself a rewrite of an even older version). We had some pretty neat tooling for setting up scenarios to find bugs in that containerization system— ways that a misbehaving app could interfere with other applications running on the system. By the time I joined, though, we only used that tooling occasionally, and we only used a handful of its features.

At first I thought it must be because we weren't doing enough testing. Then I looked carefully at what that tooling was doing, and I realized, I "Most of these failure modes aren't possible with the new system." That test tool was a detailed record of all the problems with the Ruby version of the system — that were mostly with the home grown containerization engine, written in Ruby, before Docker. It had been replaced with a more "standard" system.

I started my career in testing, and specifically in exploratory testing. I spent a lot of time learning skills for finding and precisely characterizing bugs, especially subtle, weird bugs, the kinds of things that slip out underneath you as you're studying them. It's not that I don't find that skillset useful— I really do.

But the more experience I get in software, the more I start to get suspicious when I break out that skillset. If I'm encounter a lot of bugs, and especially a lot of similar bugs, and bugs that keep coming back, I start asking, "What is it about this architecture, these design decisions, that are making these bugs so common? Why is it so hard to do the 'right thing' consistently? Why are errors in this system so noticeable?" I find that much more productive than treating problems like this as testing problems.