Drag-to-reorder looks like a drag problem. The algorithm is entirely in the save. If a card's place in the list is an integer index, moving one card rewrites the index of every card below it — on every client, over a network, while somebody else is dragging. So give each card a key instead and require only that the keys sort into the right order. Then one move writes exactly one row.
// a base-62 string read as a fraction: between any two keys there is always another
const k = keyBetween(above, below); // one UPDATE, whatever the column length
Integers cannot do it, because between 3 and 4 there is nothing. Floats can do it a bounded number of times. A string always can, because a string has no last digit. Eight implementations on one board, live: https://dev48.infy.uk/design/day70-order-keys.html
The property everybody tests separates almost nothing
"After the drop, every card is where you put it" is the right property, and it is checked here against an order held as a bare array of ids that has never seen a key. It is satisfied by 5 of 8 implementations on 100.0% of 6,000 random moves and 100.0% of 6,000 moves shaped like a real board.
Two of those five are wrong in ways the property cannot express. Renumbering the whole column is never wrong and writes 6.48 rows per move. Integer gaps of 1,000 renumbered 2 times in 6,000 realistic moves — the reason to reject them is the tail, not the mean. The other two are correct until they are not, and the budget they spend is not a constant you can look up:
| the two positions | float64 insertions before a collision | integer insertions before a renumber | base-62 key |
|---|---|---|---|
| a brand new list, 0 and 1 | 1,074 | 0 | unbounded |
| a 1-based position column, 1 and 2 | 52 | 0 | unbounded |
| positions in steps of 1,000 | 53 | 9 | unbounded |
| a million rows in, 1 apart | 33 | 0 | unbounded |
| a timestamp used as a position | 23 | 0 | unbounded |
The float budget is the distance between the exponent of the gap and the exponent of the numbers, not a constant 52. Same code, 1,074 insertions at the head of a fresh list and 23 beside a timestamp.
What the measurement contradicted
The plan was to bake the breaking structure into the realistic corpus and let it do the work. It does not work. 20,000 realistic moves never exhaust a float64 position, even though a quarter of them are exactly the killing habit — a pinned card at the top of the column with everything urgent dropped directly underneath it — because between two of them something else lands in the gap and resets it. Realistic is not concentrated, and a defect with a budget is only visible to a corpus that spends the budget in one place. The habit in isolation kills the float on move 55, and the key decoded back to a double on move 45.
The defect I drafted as the subtle one turned out to be the loudest thing on the page, and it is not in any of the code. Byte order puts every uppercase letter before every lowercase one; a case-insensitive collation — MySQL's default — interleaves them, and base-62 crosses the case boundary on the second key it ever mints. The board is wrong on 100.0% of boards before a card has moved. Its visibility then inverts: a workload that only ever inserts at the top drives the keys down into the digits, where the two collations agree, and the same defect shows up on 5.6% of sessions.
Two clients inserting into one gap from the same snapshot mint the identical key 100% of the time, by construction rather than by accident, and neither is wrong. Sorting by key alone diverges on 100.0% of sessions; (key, id) diverges on 0.
3,974,372 assertions on load, and 88 in the verifier against four independently written oracles. One file, inline CSS, no external asset of any kind.
Part of a from-scratch series — one component a day, vanilla JS, one file, dependency-free engine: https://dev48.infy.uk/designfromzero.php
Top comments (0)