4 ms·

Are there are any other approaches for this problem? Seems like there should be.

smlacy 2y ago
Usually for this kind of use case you want both INCREMENT and DECREMENT. Using a random number for the "Slot" (AKA "Shard") seems like an anti-pattern. If the Slot were derived from a hash of the data itself, then DECREMENT would be much more straightforward.
- roywiggins 2y ago
  Hm, why wouldn't decrements work with random slots, if you're always just summing up all the slots to get the final tally?
immibis 2y ago
Yes: use a different tool, such as Redis. Updating a SQL database row can be expensive because of the transaction overhead. Once you increment this counter, the row with the counter remains locked until the transaction is committed. But the actual useful work of incrementing a number is already quicker than selecting a random slot. If the increment can be a simple ADD instruction, without transactional semantics, then this random-slot-based approach is slower than just incrementing it. Especially if you don't care about missing a few increments and therefore don't need a mutex. For even more scale, don't use Redis but have a shared memory block containing your integer. For even more scale, you can have one such slot per CPU. Make sure they're in different cache lines, to avoid false sharing. Now you have slots again, but they're per-CPU and so you still avoid all the SQL database overhead. Performance is all about structuring the task as close to the machine as possible.
- jeffrallen 2y ago
  Some people, when they have the problem of incrementing integers think, "I'll use Redis." Now they have two problems.
  - esafak 2y ago
    Can you go into more detail? Redis supports counters: https://redis.io/glossary/storing-counters-in-redis/ https://redis.io/glossary/storing-counters-in-redis/
    - jeffrallen 2y ago
      https://regex.info/blog/2006-09-15/247 https://regex.info/blog/2006-09-15/247
      - immibis 2y ago
        so... what's the problem with using Redis to store a shared counter?
        jeffrallen 2y ago
        It's a joke about answering complexity with additional complexity. Laugh, it's ok. :)
        immibis 2y ago
        Redis is a data structure server, for a limited set of data structures. If that's what you want, then use Redis.
aqueueaqueue 2y ago
Outside of the DB: some kind of queue. Could be a SQS or an in memory queue in your app (hand waves about mutiple nodes but that can be dealt with or use redis). Have a single processor that aggregates and does writes. You can use DLQ if something goes wrong to avoid data loss. Inside the DB maybe just append rows for each add to a table without indexes. That way the engine probably just needs to write out a journal record and append but doesn't spend time on updating indexes. Then periodically read all from the table and aggregate into another. You could cycle between 2 tables. These is eventually consistent in aggregations but transactional in source of truth. I.e. if you write you can be sure the data is stored, but may take time to aggregate. Or Use a more exotic DB. That is distributed but still supports transactions.
Squid_Tamer 2y ago
I think probabilistic counters are really interesting for this situation, as long as you don't need exact numbers. if random.randint(1, 100) == 1: db.increment(row) Then, looking at the database, you can know that the actual count is approximately 100x the number of times the row was incremented. There's an even more aggressive version that I've seen called a 'Morris Counter' which uses just a few bits to build an order-of-magnitude estimate of the number of events: https://en.wikipedia.org/wiki/Approximate_counting_algorithm https://en.wikipedia.org/wiki/Approximate_counting_algorithm
coolhand2120 2y ago
You could add a row for each count. You could add more associated information with the count too, like date, why, etc.. Then that insert would trigger a debounced method that would query the event stack to give you a count. You can make periodic snapshots of the total to avoid O(n) table scans. This allows scale without row locking and a much more accurate accounting of when the counts happen. You rewind/fast forward, get a time series, whatever with the event stack. This is all part of the CQRS pattern. https://martinfowler.com/bliki/CQRS.html https://martinfowler.com/bliki/CQRS.html

Usually for this kind of use case you want both INCREMENT and DECREMENT. Using a random number for the "Slot" (AKA "Shard") seems like an anti-pattern. If the Slot were derived from a hash of the data itself, then DECREMENT would be much more straightforward.

roywiggins 2y ago
Hm, why wouldn't decrements work with random slots, if you're always just summing up all the slots to get the final tally?

immibis 2y ago

Yes: use a different tool, such as Redis. Updating a SQL database row can be expensive because of the transaction overhead. Once you increment this counter, the row with the counter remains locked until the transaction is committed. But the actual useful work of incrementing a number is already quicker than selecting a random slot. If the increment can be a simple ADD instruction, without transactional semantics, then this random-slot-based approach is slower than just incrementing it. Especially if you don't care about missing a few increments and therefore don't need a mutex. For even more scale, don't use Redis but have a shared memory block containing your integer. For even more scale, you can have one such slot per CPU. Make sure they're in different cache lines, to avoid false sharing. Now you have slots again, but they're per-CPU and so you still avoid all the SQL database overhead. Performance is all about structuring the task as close to the machine as possible.

jeffrallen 2y ago
Some people, when they have the problem of incrementing integers think, "I'll use Redis." Now they have two problems.
- esafak 2y ago
  Can you go into more detail? Redis supports counters: https://redis.io/glossary/storing-counters-in-redis/ https://redis.io/glossary/storing-counters-in-redis/
  - jeffrallen 2y ago
    https://regex.info/blog/2006-09-15/247 https://regex.info/blog/2006-09-15/247
    - immibis 2y ago
      so... what's the problem with using Redis to store a shared counter?
      - jeffrallen 2y ago
        It's a joke about answering complexity with additional complexity. Laugh, it's ok. :)
        immibis 2y ago
        Redis is a data structure server, for a limited set of data structures. If that's what you want, then use Redis.

aqueueaqueue 2y ago

Outside of the DB: some kind of queue. Could be a SQS or an in memory queue in your app (hand waves about mutiple nodes but that can be dealt with or use redis). Have a single processor that aggregates and does writes. You can use DLQ if something goes wrong to avoid data loss. Inside the DB maybe just append rows for each add to a table without indexes. That way the engine probably just needs to write out a journal record and append but doesn't spend time on updating indexes. Then periodically read all from the table and aggregate into another. You could cycle between 2 tables. These is eventually consistent in aggregations but transactional in source of truth. I.e. if you write you can be sure the data is stored, but may take time to aggregate. Or Use a more exotic DB. That is distributed but still supports transactions.

Squid_Tamer 2y ago

I think probabilistic counters are really interesting for this situation, as long as you don't need exact numbers. if random.randint(1, 100) == 1: db.increment(row) Then, looking at the database, you can know that the actual count is approximately 100x the number of times the row was incremented. There's an even more aggressive version that I've seen called a 'Morris Counter' which uses just a few bits to build an order-of-magnitude estimate of the number of events: https://en.wikipedia.org/wiki/Approximate_counting_algorithm https://en.wikipedia.org/wiki/Approximate_counting_algorithm

coolhand2120 2y ago

You could add a row for each count. You could add more associated information with the count too, like date, why, etc.. Then that insert would trigger a debounced method that would query the event stack to give you a count. You can make periodic snapshots of the total to avoid O(n) table scans. This allows scale without row locking and a much more accurate accounting of when the counts happen. You rewind/fast forward, get a time series, whatever with the event stack. This is all part of the CQRS pattern. https://martinfowler.com/bliki/CQRS.html https://martinfowler.com/bliki/CQRS.html