While SQL & Hibernate are mostly portable, one crucial area remains subject to incompatibility. Primary keying is the foundation of our tables, but key allocation is non-standard.

Most other SQL elements are standard & compatible, especially with the help of Hibernate. Joins, columns, mappings & queries will generally port without a hitch.

But when we get to identifier generation, the picture falls apart. Some databases use auto-increment/  identity columns, others sequences. Syntaxes differ, retrieving generated keys is variable at best. With such divergence, how can we possibly allocate keys portably?

Well, it turns out if we’re using Hibernate or Java we can — and it can even perform better than proprietary options such as SEQUENCES (Oracle).

We’re going to look at one fundamentally optimal design — a mathematically direct approach, using a table to allocate keys in blocks.

Efficiency is achieved by allocating in bulk, then caching & using the keys from memory. This can be implemented using only standard portable SQL.

We’ll also compare the design of this approach with the design of HiLo, an early & widely promoted allocation scheme, and see where that went wrong.

Hi-Lo: a design and it’s drawbacks

Back in 1997, Scott Ambler released a series of papers on persistence layers & object-relational mapping (ORM). Among useful ideas, he included a method for key allocation.

Amazed & awed by the magic of CPU words, Scott envisaged a new approach to primary keying – the Hi-Lo strategy. Entities would be keyed with a composite key, comprising one word allocated from a database counter & one word incremented internally.

This sounds great, if you’re a CPU. For humans, not so much! The generated keys are ugly, and restarting your server 65,536 times runs out of keyspace. And if you change the block-size, Hi-Lo loses integrity & starts re-issuing duplicate keys..

While this initial form of HiLo did work, having composite keys everywhere was painful & inefficient. Eventually, everyone dropped that part.

But meanwhile, I wrote to Scott..

An Information-theoretic Analysis

I had kept thinking about this problem — whether we’re allocating integer (32-bit) or larger keys, it just seemed obvious. In my young & obnoxious way, I found some points profoundly self-evident:

• Dividing a keyspace into separate words is more complex than treating it, as a simple range of numbers.
• Blocks of any convenient size can be allocated, simply by adding to a NEXT_ VAL counter. If we need a block of 20, we just read the counter & advance it 20.
• Our allocator state (NEXT_VAL) is simpler — and definitively better — if it directly corresponds to key values in the table.
• Allocator state should ideally be of the same type & same magnitude, as the keys it represents!

Logically, it is simpler to treat our keyspace as a simple number line on which we perform addition, than to split it into separate words (a two-dimensional space) which require multiplication.

For bulk inserts or database maintenance, being able to compare NEXT_VAL directly with existing keys is absolutely better than having to factor in some hidden multiplication by block/word sizes etc.

Mathematically, there’s a principle here. Integer keyspace is a fundamentally a number-line, and inherently one dimensional. Splitting keyspace into two separate words makes a two-dimensional space, which is not only unnecessarily complex but no longer directly corresponds to our actual keys.

And there is just no intellectual reason or excuse to justify the added contortion of making NEXT_HI_WORD differ, in type & magnitude, from the keys it is allocating. Changing types or multiplying values in Hi-Lo is just needless & complicated. And Occam’s razor is pretty harsh against details like that.

Ambler tries to justify this on the grounds of efficiency. But efficiency is achieved by allocating keys in blocks, not by whether the allocator state stores NEXT_VAL directly or not. Both designs are similarly efficient, especially considering that allocation cost is only a part of overall row ‘INSERT’ cost.

Most times, a block-size of 20 or 100 would be ideal; giving friendlier keys for humans & delivering similar performance. But, if we really wanted to, we could set a block-size of 65536 to exactly replicate Hi-Lo’s characteristics.

Thus, we can conclude that linear block allocation is mathematically simpler & more correct. It represents allocator state (NEXT_VAL) directly, without introducing superfluous complications or extra dimensions to the keyspace.

Linear block allocation supersedes Hi-Lo’s capabilities by enabling configuration of block size, and by allowing block-size adjustment without loss of integrity.

I wrote all this to Scott Ambler. But needless to say, it was the “not invented here” syndrome. He grudgingly accepted my optimal & ideal design as being “vaguely in compliance” with his idea, but dodged the question as to it being preferable.

Table Block Allocator

But back to our original goals. If we wanted a perfect portable key allocator, our requirements would be:

1. absolutely portable using standard SQL,
2. high performance,
3. tuneable without affecting integrity
4. represent allocator state directly, for easy maintenance.

This seems like quite a wishlist. But it turns out we can achieve it quite easily..

Allocation using the “Linear Block Allocator” can be understood as allocating blocks, from a linear number-line. We store a counter (NEXT_VAL) as to the start of the next block in a row in an allocator table.

Allocating a block (of say, 20) for a given entity is simply a matter of reading NEXT_VAL from the desired row, then adding 20 to it.

Blocks are cached in memory and keys issued as required. When the current block is exhausted, another block is allocated from the database.

Sounds pretty simple so far! The only matters that remain, are to ensure that database allocation & in-memory caching are handled in a multi-user & concurrency-safe manner.

For the database read & update, we can apply locking if possible, but that depends on the specific database. Our best course is to wrap the entire operation in an “optimistic locking” retry pattern — looping until rowsAffected == 1 — thus guaranteeing reliability, regardless of database.

The in-memory cache is simple & “synchronized” for thread-safety. We maintain allocNext & allocHi variables, indicating the next value to allocate & the end of the block (exclusive). If allocNext >= allocHi the block is exhausted & we must obtain a new one before allocating our key.

Conclusion

Database portability is an excellent attribute for our applications. It increases saleability, as customers can use their existing database, and enables us to escape lockin for vendor pricing or technical issues.

Key allocation is the critical area for database portability. Hibernate abstracts other areas of difference between SQL dialects, but primary keys are crucial and “native” approaches not portable.

Linear block allocation offers an efficient approach to key allocation from within the application server. It utilizes a block-based cache for performance, and requires only standard SQL — giving excellent portability.

Crucial to linear block allocation’s benefits over the (older) Hi-Lo approach, is the clean & direct representation of allocation state. NEXT_VAL directly corresponds to upcoming keys, and is always greater than existing keys.

This clarity is mathematically based, and offers fundamental advantages. Performance tuning is easy; unlike Hi-Lo, where changing the multiplier changes position in the sequence & causes loss of integrity.

Merges, bulk inserts & database maintenance are also made easy, by a direct correspondence of keys to allocation state. NEXT_VAL can easily be advanced after adding records, and correctness is trivial to check.

Having worked with Hibernate & SQL for many years, I now build all my green-fields projects to be database portable; this key-allocation method is the crucial building block to do so.

LinearBlockAlloc now available via Maven & GitHub

Latest news: LinearBlockAllocator is now available as a Maven dependency, as well as on GitHub. Releases for Hibernate 4, Hibernate 5 beta and 3.6.10 versions are available.

• LinearBlockAlloc project page & docs
• Release for Hibernate 4
• Release for Hibernate 5.0.0.Beta1
• Release for Hibernate 3.6.10

Add a comment if you’re interested to know more!

Preliminary:  for Hibernate 5.0.0.Beta1