[HN Gopher] The Slotted Counter Pattern
___________________________________________________________________
The Slotted Counter Pattern
Author : hollylawly
Score : 67 points
Date : 2022-08-01 15:58 UTC (7 hours ago)
(HTM) web link (planetscale.com)
(TXT) w3m dump (planetscale.com)
| ukd1 wrote:
| 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 UPDATE SKIP LOCKED LIMIT 1) LIMIT
| 1
| robocat wrote:
| How does that avoid race conditions?
|
| SKIP LOCKED doesn't seem to be designed for that purpose:
| https://www.enterprisedb.com/blog/what-skip-locked-postgresq...
| sonicgear1 wrote:
| Wouldn't querying the count be slow using a WHERE clause?
| LesZedCB wrote:
| it was indexed which should help, but i assume that the reads
| are far less common than the inserts. reads could even be
| scheduled/automated and stored in a cache table if they need to
| be faster and ok being a little stale
| jorangreef wrote:
| 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
| asadawadia wrote:
| the fundamental problem with counters is that it does a read-
| modify-write cycle which is quite harsh on the DB - a better
| approach is to take advantage that counters are cumulative and we
| can keep the delta events only and 'merge' them on reads
|
| or just buffer the counters in redis and then flush them out
|
| I have a counters API that does precisely this
|
| Docs are here: cmd+f: 'Counters API now live'
|
| https://blog.aawadia.dev/api/
| [deleted]
| elsurudo wrote:
| Makes sense, but I can't help but feel it's a solution at the
| wrong abstraction level. It's a shame the DB can't figure this
| out for you.
| yccs27 wrote:
| Yeah, it seems like it would be possible for the DB engine to
| aggregate all these increments into one update. If you have two
| increments by one each in the queue, why not make it a single
| increment by two? I'm not sure though how much computing power
| it would need to figure that out...
| LesZedCB wrote:
| wouldn't that break the atomic and isolated rule of ACID?
| MauranKilom wrote:
| Not any more than the slotted counter pattern...
| samatman wrote:
| Not necessarily. If both updates are in a single
| transaction then it's valid for the query planner to batch
| them, although that seems unlikely in the use case this
| table layout is designed for.
| [deleted]
| cryptonector wrote:
| The DB could figure it out IF it had monoid counter type to use
| as the column's type.
| tantalor wrote:
| 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
| ris wrote:
| Was going to post this. "Sharding" seems like a better term for
| communicating the idea.
| zimpenfish wrote:
| 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".
| iv42 wrote:
| Also, it's basically identical to the pattern described as
| Counter Tables in "High Performance MySQL" (3rd edition),
| published in 2012.
| yccs27 wrote:
| Interesting. This basically implements a parallel algorithm for
| summation/counting, by calculating a partial sum in each slot,
| and then merging the results with every read. This approach could
| be applied more generally to values in a commutative monoid, and
| there are probably other parallel algorithms that could be
| implemented in a database a similar way.
| idk1 wrote:
| 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.
| wcarss wrote:
| 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.
| teej wrote:
| 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.
___________________________________________________________________
(page generated 2022-08-01 23:01 UTC)