Hi, This fixed-length array, how do you calculate it? It could be interesting to implement, but I couldn't find anything in the links provided so far in this discussion. I guess you could do a binary search for 1024 evenly spaced values, that should give you the properties of the array that you want, or does it do something even more clever?
About the complexity, yes, a single modulo operation is faster than a binary search, but if you look at the whole thing, network I/O is surely much, much slower, such that the difference in server selection algorithm becomes insignificant. It's clever though, I like that! :-) /Henrik On Sun, Mar 1, 2009 at 17:32, Mikael Johansson <[email protected]> wrote: > Hi, > > The server selection isn't done in an external library, it's just that the > algorithm used is the same as the one in Set-ConsistentHash, though it uses > crc32 or fnv1a instead of sha1 (versus md5 for ketama). > > The big difference is that pecl/memcache and Set-ConsistentHash after > having built and sorted the continuum precomputes an array of 1024 buckets, > which can then be used by hashing the key and using a modulo operation on > the array. It's computing this array that takes most of the time. What can > be done is, as you say, caching it in shared memory alongside the persistent > connection sockets. I'll have a look at this. > > Consistent hashing takes O(log n*w*m) to find a server, not counting the > hash function itself, where n is the number of servers, w is the average > weight of a server (usually 1) and m is number of points per server (usually > 100 or 160). Standard modulo hashing is O(1), so it's inherently faster. > > //Mikael > >
