Asked  7 Months ago    Answers:  5   Viewed   35 times

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 a good explanation of how it works.

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

 Answers

87

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.

Tuesday, June 1, 2021
 
RenegadeAndy
answered 7 Months ago
32

Create the strings <providername>000001, <providername>000002, etc. or whatever and encrypt them with a public key, and that's your "CD-KEY" that the user enters. Decrypt the CD-KEY with the private key and validate that when decrypted you get a valid string with a valid provider name.

Wednesday, August 11, 2021
 
jwegner
answered 4 Months ago
93

There are 2 reasons I would always add an ID number to a lookup / ENUM table:

  1. If you are referencing a single column table with the name then you may be better served by using a constraint
  2. What happens if you wanted to rename one of the client_status entries? e.g. if you wanted to change the name from 'affiliate' to 'affiliate user' you would need to update the client table which should not be necessary. The ID number serves as the reference and the name is the description.

In the website table, if you are confident that the name will be unique then it is fine to use as a primary key. Personally I would still assign a numeric ID as it reduces the space used in foreign key tables and I find it easier to manage.

EDIT: As stated above, you will run into problems if the website name is renamed. By making this the primary key you will be making it very difficult if not impossible for this to be changed at a later date.

Thursday, August 12, 2021
 
Thomas Weller
answered 4 Months ago
11

Paxos is non-trivial to implement, and expensive enough that many systems using it use hints as well, or use it only for leader election, or something. However, it does provide guaranteed consistency in the presence of failures - subject of course to the limits of its particular failure model.

The first quorum based systems I saw assumed some sort of leader or transaction infrastructure that would ensure enough consistency that you could trust that the quorum mechanism worked. This infrastructure might well be Paxos-based.

Looking at descriptions such as https://cloudant.com/blog/dynamo-and-couchdb-clusters/, it would appear that Dynamo is not based on an infrastructure that guarantees consistency for its quorum system - so is it being very clever or cutting corners? According to http://muratbuffalo.blogspot.co.uk/2010/11/dynamo-amazons-highly-available-key.html, "The Dynamo system emphasizes availability to the extent of sacrificing consistency. The abstract reads "Dynamo sacrifices consistency under certain failure scenarios". Actually, later it becomes clear that Dynamo sacrifices consistency even in the absence of failures: Dynamo may become inconsistent in the presence of multiple concurrent write requests since the replicas may diverge due to multiple coordinators." (end quote)

So, it would appear that in the case of quorums as implemented in Dynamo, Paxos provides stronger reliability guarantees.

Friday, September 3, 2021
 
BlueNile
answered 3 Months ago
47

Building a suffix tree will allow you to do a substring search on all your strings in parallel in O(1). The pedantic in me can't help but note that it's really O(n + m) where n is the number of strings that match your substring and m is the size of the substring being queried.

So what's a suffix tree you ask? In its most basic implementation, it's a trie with a fancier insert method: in addition to adding a string, it also adds every possible suffix of that string to the trie. On this data structure, a substring search becomes a prefix search of all possible suffixes. Since you also want to do prefix searches, you'll want to add a special character in front of each inserted string and the query substrings. The special character will allow you to differentiate between a suffix and a full string.

While this implementation of a suffix tree is remarkably simple, it's also very inefficient (O(n^2) space and build time). Fortunately, there are other more efficient implementations which can greatly reduce the space and time bounds. One of these, Ukkonen's algorithm, is very well explained in this SO answer and brings the space bound down to O(n). You may also want to look into suffix arrays which are an equivalent but more efficient representation of suffix trees.

While I know there are many many more implementations of suffix trees out there (one of which would probably hit the sweet spot for your use case) I just don't know them. I recommend you do some research on the subject before you settle on an implementation.

Sunday, October 10, 2021
 
Naveed S
answered 2 Months ago
Only authorized users can answer the question. Please sign in first, or register a free account.
Not the answer you're looking for? Browse other questions tagged :  
Share