lshift/diffa — pull request #260 by 0x6e6562 (2012-09-02 23:12:01+00:00)
Title: WIP: Introduce Extents

An extent is a level of indirection between a row in the `DIFFS` table and entries in the `PAIRS` table. The motivation behind introducing extents is to be able to implement fast pair removal (and truncation), without having to partition the `DIFFS` table. As such, an extent is merely a pointer that allows a pair to be semantically removed without having to synchronously delete all of the `DIFFS` records that reference it in the same transaction. When a pair is deleted, it assumes an new upgraded extent, and the old extent that it previously referenced remains as an orphan. The advantage of this approach is that referential integrity between live diffs and pairs can be enforced, without having to pay the penalty of deleting the diffs in the same transaction as the pair. Diffs that are linked to orphaned extents are in themselves orphans, and will be removed as part of a background process.

The one (minor) complication with this approach is that the `DIFFS` table has a FK back to the `ESCALATIONS` table, which in turn has a FK back to the `PAIRS` table. To circumvent this, an extra pointer table (`PENDING_ESCALATIONS`) has been introduced between the escalations and the diffs tables. When a pair is removed, the back pointer that `PENDING_ESCALATIONS` holds to the `ESCALATIONS` table is removed and hence `DIFFS` records that previously held an FK back to `ESCALATIONS` can remain as orphans after the master escalation has been deleted.