hit9

Reasons to create it:

- Most redis client implementations don't support redis cluster.

- It's hard to provide redis client libraries for multiple languages without breaking compatibilities.

- twemproxy requires restarting to add/remove redis nodes.

- twemproxy is single-threaded.

Hope you like it!

Hmm.. The 2 * 3 ... 29 can be larger, if we want a larger tree.

Comment 1: O(2 * 3 ... 29) is indeed constant level, but we don't like it. The put/get/delete operations on this tree are all constant level, but at most Sum(lg2~lg29) checks.

Comment 2: Yes, we can use fixed-size arrays and build an open-addressing hash table with no space overhead (load factor is 1), this makes 100% table space utilization, but any insertions would cause table to resize, which is an O(N) copy (where N is the table size). However, insertions on a tree node can be done locally, without moving the whole tree.

The page dosen't say words like "faster than a hash table".

The hash table has time complexity O(1) on get/set operations. And this tree has a constant-level time complexity, and should be a bit slower than hash table.

Besides the redundancy of the golang array auto-expanding, this tree is more space-efficient than a hash table, If you implement it in C without the auto-expanding feature, the space utilization can be better.

Sorry but I have typo in the documentation, the " Goroutine Safety." is the headline of following paragraph.

HTree dose not guarantee the goroutine safety:

> "Lock granularity depends on the use case."

The docs page updated.

And the origin string keys are stored in the htree item only if there is collision. So the string key distinguishing checks are at most once.