What's the Hi/Lo algorithm?

views:

8417

answers:

+69 Q:

What's the Hi/Lo algorithm?

I've found this in the NHibernate documentation (it's one method to generate unique keys, section 5.1.4.2), but I haven't found any good explanation of how does it work.

I know that Nhibernate handles it, and I don't need to know the inside, but I'm just curious.

+108 A:

The basic idea is that you have two numbers to make up a primary key- a "high" number and a "low" number. A client can basically increment the "high" sequence, knowing that it can then safely generate keys from the entire range of the previous "high" value with the variety of "low" values.

For instance, supposing you have a "high" sequence with a current value of 35, and the "low" number is in the range 0-1023. Then the client can increment the sequence to 36 (for other clients to be able to generate keys while it's using 35) and know that keys 35/0, 35/1, 35/2, 35/3... 35/1023 are all available.

It can be very useful (particularly with ORMs) to be able to set the primary keys on the client side, instead of inserting values without primary keys and then fetching them back onto the client. Aside from anything else, it means you can easily make parent/child relationships and have the keys all in place before you do any inserts, which makes batching them simpler.

Jon Skeet 2008-11-11 20:57:35

Are you saying that "low ranges" are coordinated within the client, while the "high sequence" corresponds to a DB sequence?

Chris Noe 2009-06-30 13:15:39

Yup, that's basically it.

Jon Skeet 2009-06-30 13:38:31

Chris Noe 2009-06-30 15:48:09

like an IP address then - ICANN gives you a high 'network' number, you then have as many low 'host' numbers as you like, within the limit of the CIDR range you're given.

gbjbaanb 2009-08-07 14:19:06

What is the advantage of the hi/lo algorithm over simply having clients draw *batches* of keys from the central sequence in bulk?

Adam Paynter 2010-08-09 10:57:25

@Adam: Fundamentally, nothing - it's just potentially cheaper to increment one value (the "high" part) than to generate a bunch of keys. (It's potentially *much* cheaper in terms of data transfer - you can "reserve" a huge number of keys with minimal bandwidth.)

Jon Skeet 2010-08-09 11:15:36

@Jon: True. Though in practice, clients need not *transfer* the batch of keys. The central sequence could merely be incremented by a larger quantity, effectively reserving those keys for the client.

Adam Paynter 2010-08-09 11:31:10

@Adam: That's true if the keys are just numbers. Not so much for GUIDs :) But yes, in the case of simple numbers, any atomic "increment by a fixed amount" will do. That's effectively what hi-lo is doing, if you think of it as one number split into two sections.

Jon Skeet 2010-08-09 11:36:17

@Jon: Yes, that's effective what hi-lo is doing. You're point about non-numeric keys finally made things click for me. How naive of me, assuming keys are numbers. :)

Adam Paynter 2010-08-09 11:52:35

So it's just a particular way to assign the client a range of primary keys instead of a single primary key, which is desirable for performance reasons?

Strilanc 2010-10-12 17:27:30

@Strilanc: That's my understanding, yes. Of course, there could well be subtleties that I'm missing :)

Jon Skeet 2010-10-13 06:12:19

+27 A:

In addition to Jon's answer:

It is used to be able to work disconnected. A client can then ask the server for a hi number and create objects increasing the lo number itself. It does not need to contact the server until the lo range is used up.

Stephan Eggermont 2008-11-11 22:08:43

ansaurus

tags:

views:

answers:

What's the Hi/Lo algorithm?

related questions