Counter CRDT

[tantaman]

Allow columns to be defined as counters rather than LWW.

Some basic background: https://www.cs.utexas.edu/~rossbach/cs380p/papers/Counters.html

API ideas:

We could use special functions to interact with count columns. E.g.,

UPDATE foo SET counter = crsql_incr(counter, amount)

where crsql_incr takes a counter crdt instance.

@ivertom -- I remember you sketching out ideas for a counter but can't seem to track them down.

Implementation Ideas

Ideally we'll start with the most generic counter -- one that increments and decrements.

We'll need to track two lists of tuples:

// increments
type Increments = [SiteId, count][];
type Decrements = [SiteId, count][];

and the "final" count is simply the sum of increments minus sum of decrements:

increments.reduce((l, r) => l + r[1], 0) - decrements.reduce((l, r) => l + r[1], 0)

https://www.cs.utexas.edu/~rossbach/cs380p/papers/Counters.html#cvrdt-state-based-design-1

The final value is what should always be stored in the column. Backing data (e.g., sites and their counts) should be stored in some auxiliary table.

The auxiliary table could be something as simple as a table called crsql_counters which tracks state for all counters in the system:

CREATE TABLE crsql_counters(
  counter_id INTEGER,
  site_ordinal INTEGER,
  val ANY_NUMBER_TYPE,
  type INCREMENT | DECREMENT
);

Issues

• Continuous growth of rows to track a count increment / decrement

Workarounds

• Compact out these rows when all sites are > a given db version
  • Save a snapshot of the state at the compaction point

Compacting out history will be a later exercise.

[jeromegn]

I'm wondering if it could allow a more generic function name like incr instead of crsql_incr? I'd like to hide the cr-sqlite details as much as possible from our users, but I'd also like to have this functionality when it's ready :)

Maybe as an option somehow? Ideally not at compile-time because that seems like a bit of pain. I assume you can register a function from another function?

[tantaman]

more generic function name like incr instead of crsql_incr

We could. I'm worried about name collisions though. Wouldn't there be a chance that some other extension includes an incr?

I assume you can register a function from another function?

Maybe 😅 Like register a function from within a function extension?

[jeromegn]

I assume you can register a function from another function?

Maybe 😅 Like register a function from within a function extension?

I probably should've said a bit more... I was wondering if a function could be created to alias or deregister + re-register the crsql_incr function and rename it to incr. That would make it opt-in.