sql: support for a globally unique monotonically increasing logical timestamp

[csdigi]

As discussed previously on the Gitter room, we currently have the need for a globally (within a table) unique identifier that is monotonically increasing. One of the motivating use-cases for this is pagination, where we want to have a consistent cursor into the table, as well as showing the user a consistent snapshot of the table contents (so that it is not updating and reordering while they page through). Although there are plenty of motivating cases for being able to totally order writes into a table.

The current solution we are using to work-around this is a combination of the cluster_logical_timestamp (which is monotonically increasing in a global sense but for rows written inside a transaction will have duplicate values), and the unique_row_id() which is globally unique and monotonically increasing locally (inside a transaction, except for local clock jumps).

This solution requires two columns in a table and complicates the queries (and indexes) to get a cursor on the table as we must do something like (for a cursor of 123.0:456):

select * from table where ((logical_timestamp = 123.0 and id > 456)
    or logical_timestamp > 123.0) order by logical_timestamp, id ;

Obviously the above query gets more complex when we also want to freeze the table updates to a max logical timestamp as we would need to add logical_timestamp < max_timestamp or (logical_timestamp = max_timestamp and id < max_id) too.

Having this combined into a single column would allow much simpler querying (and would allow for fewer indexes) and would provide a neat way to keep a logical cursor into tables.

[petermattis]

@csdigi A monotonically increasing value is difficult (impossible?) to achieve in a distributed system without some central coordination. Even with such a service we would need special consideration for how to use such sequences in SQL given that you want a total ordering of writes to a table.

I'm curious what you would do if you were implementing your system on MySQL or PostgreSQL. Be aware that auto-increment is not always sequential also means that auto-increment/serial is not monotonically increasing with respect to transaction order. That is, a later transaction can commit with a smaller auto-increment/serial value than an earlier transaction.

[bdarnell]

The current solution we are using to work-around this is a combination of the cluster_logical_timestamp (which is monotonically increasing in a global sense but for rows written inside a transaction will have duplicate values), and the unique_row_id() which is globally unique and monotonically increasing locally (inside a transaction, except for local clock jumps).

The properties of these two functions are weaker than that. cluster_logical_timestamp() is only guaranteed to be monotonic for transactions that interact with each other (so non-interacting transactions may see lower values inserted after higher ones). unique_rowid() doesn't guarantee monotonicity, even inside a transaction (the issue is not clock jumps, it's whether the rows live on the same node). I don't think combining these two columns is any better than using one or the other separately.

It's fairly simple to have a strictly monotonic counter, it's just expensive. All you need to do is read the previous maximum value in the same transaction where you insert the new row: INSERT INTO tbl (id, ...) VALUES ((SELECT MAX(id) FROM tbl), ...). This will cause all your insert transactions to conflict with each other and effectively limit you to one insert at a time, but it will guarantee that your ids are strictly increasing. CockroachDB's optimistic transactions don't perform very well under this level of contention so you could probably do better than just throwing these conflicting transactions at the database, but the need to limit yourself to one insert at a time is unavoidable if you need strict monotonicity.

In practice, people seem to get by without strict monotonicity (as @petermattis said, the auto-increment features of MySQL and PostgreSQL don't guarantee this level of strictness). For pagination, one common strategy is to fetch several pages of data initially and store it in memcache, so you can send subsequent pages to the client from this cache instead of going back to the database (or cache metadata for several pages and fill in the rest of the data on subsequent requests). Or you can make your pagination more stateful, fetching more than a page each time and throwing away records you've already seen.

[danhhz]

@bdarnell Can't you also use AS OF SYSTEM TIME for pagination?

[bdarnell]

Ah, yes you could. Just pick a timestamp when querying the first page, and use the same timestamp for subsequent pages and you'll get stable results. That doesn't solve all the reasons one might want strictly increasing IDs (it doesn't help if you want to tail a table, for example), but it does give you pagination that won't change out from under you.

[dynajoe]

A transaction could still be open with a time earlier than the one you're using for pagination. Therefore, your results would not be stable.

[tbg]

@joeandaverde no, that does not happen. A read forces a conflict with pending values at lower timestamps which results in serializing behind that transaction or aborting it (and prevents creation of conflicting values at lower timestamps).

[dynajoe]

Good to know! My bad on making the assumption that the problem being discussed here had similar semantics to that of Postgres.

I found this via Google search for stable pagination and was hoping to ensure that those who come across this wouldn't be misinformed.

[knz]

@csdigi CockroachDB supports SQL sequences now. Would this help?

[knz]

We are documenting the spectrum of solutions to this use case here: cockroachdb/docs#3104

Please contact us if you have any additional question, comment, concern or suggestion.