On Mar 2, 1:25 pm, Henrik Schröder <[email protected]> wrote:
> 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?
http://cvs.php.net/viewvc.cgi/pecl/memcache/memcache_consistent_hash.c?revision=1.7&view=markup
80 static mmc_t *mmc_consistent_find(mmc_consistent_state_t *state,
unsigned int point) /* {{{ */
81 {
82 int lo = 0, hi = state->num_points - 1, mid;
83
84 while (1) {
85 /* point is outside interval or lo >= hi, wrap-around */
86 if (point <= state->points[lo].point || point >
state->points
[hi].point) {
87 return state->points[lo].server;
88 }
89
90 /* test middle point */
91 mid = lo + (hi - lo) / 2;
92 MMC_DEBUG(("mmc_consistent_find: lo %d, hi %d, mid %d,
point %u,
midpoint %u", lo, hi, mid, point, state->points[mid].point));
93
94 /* perfect match */
95 if (point <= state->points[mid].point && point > (mid ?
state-
>points[mid-1].point : 0)) {
96 return state->points[mid].server;
97 }
98
99 /* too low, go up */
100 if (state->points[mid].point < point) {
101 lo = mid + 1;
102 }
103 else {
104 hi = mid - 1;
105 }
106 }
107 }
108 /* }}} */
109
110 static void mmc_consistent_populate_buckets(mmc_consistent_state_t
*state) /* {{{ */
111 {
112 unsigned int i, step = 0xffffffff / MMC_CONSISTENT_BUCKETS;
113
114 qsort((void *)state->points, state->num_points, sizeof
(mmc_consistent_point_t), mmc_consistent_compare);
115 for (i=0; i<MMC_CONSISTENT_BUCKETS; i++) {
116 state->buckets[i] = mmc_consistent_find(state, step *
i);
117 }
118
119 state->buckets_populated = 1;
120 }
> 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! :-)
I hope you see that "while (1)" cycle and realise that it is not
insignificant, since you always start the search from point 0 so you
are doing at least 1023 unneeded cycles -> unneeded cpu usage :) It
would be better if that 'lo' variable is static, so that it's value is
preserved upon next excution, you don't really need to start from 0
every time. Moreover a large number of hashes are being computed every
time, which adds to the total CPU usage, and network I/O is irrelevant
here, since the OPs problem is CPU usage, not latency.
