In https://gitlab.com/gitlab-org/gitlab/-/merge_requests/139519, the [Cells 1.0 proposal](https://gitlab.com/gitlab-org/gitlab/-/blob/98e2cfa07b081a527b01f01b46a70993afc2d639/doc/architecture/blueprints/cells/iterations/cells-1.0.md) handles database sequences in a way that seems subtly unsafe and is likely to cause logical data corruption under conditions that occur on average a few times per year in production. In this issue, let's explore the nature of the problem and the trade-offs among its solutions. ### Problem summary The current Cells 1.0 proposal's [first point](https://gitlab.com/gitlab-org/gitlab/-/merge_requests/139519/diffs#c66196eb5ab30c03e955d4d7ccab49c8502b4d51_0_90) under its Database Properties list is: > 1. Each primary key in the database is unique across the cluster. We use database sequences that are allocated from the Primary Cell. Using sequence values that are globally unique among all cells would simplify some aspects of the future goal of being able to migrate organizations between cells. This makes it a desirable property. However, this guarantee of global uniqueness (rather than just database-local uniqueness) makes sequences a piece of global state data that carry a stronger durability guarantee than provided. Under conditions that rewind a sequence, the same sequence value may be issued more than once. This typically happens during a database failover where a new primary can be promoted without waiting for all WAL records to be applied from the old timeline. This is essentially a CAP theorem outcome of preferring availability over consistency. Any unapplied WAL records for consumed sequence values represent values that will be reissued, and if any of those sequence values were in a range claimed by a secondary cell, that secondary cell will blindly believe those values remain uniquely claimed by it, whereas really they will be issued again to the next random clients calling `nextval()` on that sequence. #### In more detail Drawing sequence values from one database to use as keys in another database means that these sequence values straddle two independent consistency domains. Under normal conditions a sequence guarantees uniqueness -- from the perspective of the WAL stream, a sequence emits each value "at most once". However, under conditions like a patroni failover or a point-in-time recovery, some WAL records from the old timeline are lost/abandoned, and the new timeline will reissue sequence values that had previously been used on the old timeline. Within that postgres database, this is perfectly reasonable; internal data consistency and referential integrity are maintained because everything about the old timeline's lost transactions is forgotten. But outside that database, any residual external references to those lost transactions' records or associated sequence values become a data integrity liability. Concretely, consider the following two scenarios. These sketches represent how I think things would play out based on my understanding of postgres internals (about which I am fairly confident) and the Cells 1.0 design proposal (which I am still digesting, maybe missing something). ##### Case 1: Global uniqueness violation 1. A secondary cell claims a batch of sequence values from the primary cell's db. 2. Primary cell's db undergoes a database failover (typically a lossy event). The sequence reverts to its state before step 1. Crucially, the secondary cell does not know that its claim was forgotten by the primary cell's db. 3. Some of the sequence values claimed by the secondary cell are reused in the primary cell's db. In the db's new timeline, those reused values may now be used as primary keys for records in any cell (e.g. locally in the primary cell or any other secondary cell). Meanwhile, the secondary cell that originally claimed those sequence values continues to use them. Those values are likely to remain unique locally within each cell's database, but they are no longer globally unique. This global uniqueness violation will probably go unnoticed until much later when an affected organization tries to migrate between two cells that both claimed the reused sequence values. At that point, it will be practically impossible to trace the root cause of the collision back to the failover reissuing sequence values. ##### Case 2: Referential integrity violation 1. Primary cell creates a record in its global schema (e.g. a `users` record). 2. A secondary cell creates records that refer to that primary key value (e.g. `users.id`). 3. Primary cell's db undergoes a database failover (typically a lossy event). The failover loses the transaction that created that consumed that sequence value and created that record. 4. Later, the same sequence value is used to create a different record in the same table (e.g. a logically different user). Unless we have a reconciliation mechanism, the secondary cell's local (non-global) tables will continue to treat the reused sequence value to refer to the original user record, rather than the new user record. This represents a referential integrity violation. Depending on the context and implementation details, it could manifest as anything from trivial nonsense to cross-customer data exposure.