...

Exploring Relaxed Consistency

If we're OK with indexes possibly containing "extra" key/OID pairs for short periods of time, we can get away with cheaper algorithms to deal with updating multiple unique indexes.

For example, suppose we want to insert an employee with a unique SSN and a unique username where the table and each index are on separate machines.

If all goes well:

1. Client sends insert-object request to master
2. Master sends insert-index-entry-if-unique request to SSN index. Assume this succeeds.
3. Master sends insert-index-entry-if-unique request to username index. Assume this succeeds.
4. Master writes object to table.
5. Master returns OK to client.

If the second index entry can not be inserted:

1. Client sends insert-object request to master
2. Master sends insert-index-entry-if-unique request to SSN index. Assume this succeeds.
3. Master sends insert-index-entry-if-unique request to username index. Assume this one is taken.
4. Master sends delete-index-entry request to SSN index to roll back step 2.
5. Master returns error to client.

Insert in the unique case throws an error if there's a concurrent transaction with the same key

...