Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Slotted Counter Pattern

planetscale.com

Post reply on HN
Print view View original

21–30 of 34 posts

Re: The Slotted Counter Pattern

#21

Post by _vvhw »

Balance tracking seems to be the Achilles' heel of SQL databases.

For example, my experience has been that in the world of payments, the nature of money transactions is to debit perhaps many different accounts on the one side, but credit only a handful of accounts on the other, so that group commit can't fully amortize fsync.

Performance panaceas mostly come down to sharding, but sharding doesn't work well where you need strict updates to balances.

At work, we saw this play out several times in different systems, and decided to do something about it. We took the ledger of an open-source payments switch called Mojaloop, and extracted it as a distributed financial accounting database called TigerBeetle, designed to track financial transactions at scale.

The key performance insight was to dial up group commit. We batch up balance updates so that a single DB query can do on the order of 10k balance updates. We then fsync the batch with a single write before commit, moving the performance needle out from 1k-10k TPS to 1m TPS.

This is the advantage of a purpose-built database that's designed for counting at scale.

More information, including our design decisions are in the repo here: https://github.com/coilhq/tigerbeetle

Re: The Slotted Counter Pattern

#23

Post by idk1 »

I accidentally ended up at a similar solution once.

I has the same issue, and I fixed it by adding an associated 'count_table' row for each hit, and deleting the row once it had been added later on to the final count. Which actually fixed the issue. Then refactored it so each user or ip had it's own 'count_table' row. It meant the final total count lagged a bit, by 60 seconds or so once the count_table rows had been counted up and deleted, that was the downside but it was totally acceptable.

I wish I'd have thought of this, it's much better and simpler I think haha.

Re: The Slotted Counter Pattern

#24

Post by tantalor »

zimpenfish wrote: post #18
ris wrote: post #10

Earlier quoted context omitted.

Was going to post this. "Sharding" seems like a better term for communicating the idea.

I dunno - "sharding" would generally imply (to me, at least) that you're spreading the counters amongst different databases (or tables in a smaller context.) All the counters are in the same table here which is counterintuitive to "sharding".

Semantics

Re: The Slotted Counter Pattern

#27

Post by tantalor »

iv42 wrote: post #14
tantalor wrote: post #9

Basically same as "Sharding counters" (2008) https://download.huihoo.com/google/gdgdevkit/DVD1/developers... Also in Brett Slatkin's "Building Scalable Web Apps with App Engine" (2008) https://youtu.be/Oh9_t5W6MTE?t=1181

Also, it's basically identical to the pattern described as Counter Tables in "High Performance MySQL" (3rd edition), published in 2012.

Indeed, it also calls them "slots":

> You can get higher concurrency by keeping more than one row and updating a random row... just choose a random slot and update it

https://www.oreilly.com/library/view/high-performance-mysql/...

Re: The Slotted Counter Pattern

#29

Post by hiptobecubic »

ukd1 wrote: post #16

Cool, but this method will still get locks in whatever percent of cases, regardless of if there are slots not in transactions. In Postgres you can probably do this with slots using SKIP LOCKED; though in practice I belive you have to deal with the case where everything is locked, by falling back to waiting for a lock. UPDATE counters SET count = count + 1 WHERE name = ? AND slot = (SELECT slot FROM counters FOR UPDAT…

I would definitely complain about this in code review without some performance testing showing that 1) it's actually faster than waiting for a lock and 2) it's better than just increasing the number of slots.

Re: The Slotted Counter Pattern

#30

Post by wcarss »

teej wrote: post #11
wcarss wrote: post #7

At the extreme end of this, you could also append a new row for every event and count them. If the number of rows would be too big over some period of time, you could similarly aggregate them occasionally and clear the "scratch" table.

This "Slotted Counter" approach optimizes for a write-contention constraint, specifically row locks. From 10 seconds of Googling it seems InnoDB has other locks it uses on INSERT, I'd first check if moving the write contention to gap locks actually helps or not. One side benefit of this approach is that getting the final aggregate is cheap, where compacting an append-only log table might not be.

Thanks for taking the time to look into it, that's an interesting point. According to the manual [1], InnoDB's insert locking should not prevent other inserts from executing, it only takes an exclusive row lock on the inserted row. I agree that measuring would likely be smart.

This makes some intuitive sense, though: general purpose databases are expected to be _pretty good_ at handling the case of "add new data" with no other specific conditions, e.g. on other rows or tables' existing data.

I also agree with your last point. Running count() all day on this wouldn't be great, and compaction would take real time. I assumed that most high throughput write scenarios for something like an event count or view count can be a few minutes (or hours, or days) out of date, at which point read caching would be my first stop before clever summation algorithms, which are still pretty cool.

1 - https://dev.mysql.com/doc/refman/8.0/en/insert.html

Post reply on HN