During the time of my previous post, the version of Informix on the Amdahl mainframe was upgraded to a new version that included row level locking. Common now, at the time, database vendors were busy figuring out the best ways to perform row level locking.
The method that Informix chose had an interesting unexpected feature. If you had a unique index on a table and you inserted a row, the database implemented a row level lock on the yet to be committed index row by locking the next row in the table. If there was no index key larger than that, it would lock to the end of the index.
This meant that inserting sequential values at the end of the table, a very common occurrence for our system, would in effect behave like a full table lock. A clean solution to this problem would have been to apply the CQRS pattern so that the inserts into the database could be queued without affecting the user. But that would have required a complete refactoring of the linkages between the database interface and the custom screen processing library in an age where C code didn't have unit tests.
The solution/hack was to assign the index numbers non-sequentially. I created an RPC program that would hand out index values based on a tree based representation of the key numbers. For example, let's say you had 8 buckets (2^3) of numbers:
If you started with 8 already inserted rows as a preset base case, then an insert would lock only up to the end of the bucket, allowing 8 concurrent inserts at a time. If you need more concurrency, then you could increase the number of buckets.
Now for 8 of those inserts, regardless of the size of the buckets, we need to not insert the pre-inserted values. Instead we need to insert into the next set of bucket dividers. The simple way I decided to do that was to make the size of the buckets 2^8. That way I could use bit manipulation as follows:
By arraigning the counter this way, I could use a normal counter with simple math to generate the resulting index when it wasn't a special case. I could also get exponential back-off behavior by decrementing the counter and doing the inserts into the next range when the counter ended in all 1's (the first insert would happen right away, the second would be 1/2 of the way through the counter, etc.). The remaining "fix" was map the 8 overlapping counter values to the missed inserts into the last bucket (which would always be 111 when inserting into the next set of ranges).
The major boundary change in this solution, assigning sequence or identity values outside of a transaction, is behavior that many (most?) database systems now do: Oracle sequences, SQL Server identity columns, PostgresSQL sequences, etc.
Looking outside of your boundaries expands the solution space available to you.
The method that Informix chose had an interesting unexpected feature. If you had a unique index on a table and you inserted a row, the database implemented a row level lock on the yet to be committed index row by locking the next row in the table. If there was no index key larger than that, it would lock to the end of the index.
This meant that inserting sequential values at the end of the table, a very common occurrence for our system, would in effect behave like a full table lock. A clean solution to this problem would have been to apply the CQRS pattern so that the inserts into the database could be queued without affecting the user. But that would have required a complete refactoring of the linkages between the database interface and the custom screen processing library in an age where C code didn't have unit tests.
The solution/hack was to assign the index numbers non-sequentially. I created an RPC program that would hand out index values based on a tree based representation of the key numbers. For example, let's say you had 8 buckets (2^3) of numbers:
If you started with 8 already inserted rows as a preset base case, then an insert would lock only up to the end of the bucket, allowing 8 concurrent inserts at a time. If you need more concurrency, then you could increase the number of buckets.
Now for 8 of those inserts, regardless of the size of the buckets, we need to not insert the pre-inserted values. Instead we need to insert into the next set of bucket dividers. The simple way I decided to do that was to make the size of the buckets 2^8. That way I could use bit manipulation as follows:
The major boundary change in this solution, assigning sequence or identity values outside of a transaction, is behavior that many (most?) database systems now do: Oracle sequences, SQL Server identity columns, PostgresSQL sequences, etc.
Looking outside of your boundaries expands the solution space available to you.
Comments
Post a Comment