1 /* vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
5 * Copyright (C) 2011-2012 Data Differential, http://datadifferential.com/
6 * Copyright (C) 2006-2009 Brian Aker All rights reserved.
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions are
12 * * Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
15 * * Redistributions in binary form must reproduce the above
16 * copyright notice, this list of conditions and the following disclaimer
17 * in the documentation and/or other materials provided with the
20 * * The names of its contributors may not be used to endorse or
21 * promote products derived from this software without specific prior
24 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
25 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
26 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
27 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
28 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
29 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
30 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
31 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
32 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
33 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
34 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
39 #include <libhashkit/common.h>
43 static uint32_t ketama_server_hash(const char *key
, unsigned int key_length
, int alignment
)
45 unsigned char results
[16];
47 md5_signature((unsigned char*)key
, key_length
, results
);
48 return ((uint32_t) (results
[3 + alignment
* 4] & 0xFF) << 24)
49 | ((uint32_t) (results
[2 + alignment
* 4] & 0xFF) << 16)
50 | ((uint32_t) (results
[1 + alignment
* 4] & 0xFF) << 8)
51 | (results
[0 + alignment
* 4] & 0xFF);
54 static int continuum_points_cmp(const void *t1
, const void *t2
)
56 hashkit_continuum_point_st
*ct1
= (hashkit_continuum_point_st
*)t1
;
57 hashkit_continuum_point_st
*ct2
= (hashkit_continuum_point_st
*)t2
;
59 if (ct1
->value
== ct2
->value
)
61 else if (ct1
->value
> ct2
->value
)
67 int update_continuum(hashkit_st
*hashkit
)
70 uint32_t continuum_index
= 0;
72 uint32_t points_index
;
73 uint32_t points_count
= 0;
74 uint32_t points_per_server
;
75 uint32_t points_per_hash
;
76 uint64_t total_weight
= 0;
77 uint32_t live_servers
;
80 if (hashkit
->active_fn
!= NULL
|| hashkit
->weight_fn
!= NULL
)
84 for (count
= 0, context
= hashkit
->list
; count
< hashkit
->list_size
;
85 count
++, context
+= hashkit
->context_size
)
87 if (hashkit
->active_fn
!= NULL
)
89 if (hashkit
->active_fn(context
))
95 if (hashkit
->weight_fn
!= NULL
)
96 total_weight
+= hashkit
->weight_fn(context
);
100 if (hashkit
->active_fn
== NULL
)
101 live_servers
= (uint32_t)hashkit
->list_size
;
103 if (live_servers
== 0)
106 if (hashkit
->weight_fn
== NULL
)
108 points_per_server
= HASHKIT_POINTS_PER_NODE
;
113 points_per_server
= HASHKIT_POINTS_PER_NODE_WEIGHTED
;
117 if (live_servers
> hashkit
->continuum_count
)
119 hashkit_continuum_point_st
*new_continuum
;
121 new_continuum
= realloc(hashkit
->continuum
,
122 sizeof(hashkit_continuum_point_st
) *
123 (live_servers
+ HASHKIT_CONTINUUM_ADDITION
) *
126 if (new_continuum
== NULL
)
129 hashkit
->continuum
= new_continuum
;
130 hashkit
->continuum_count
= live_servers
+ HASHKIT_CONTINUUM_ADDITION
;
133 for (count
= 0, context
= hashkit
->list
; count
< hashkit
->list_size
;
134 count
++, context
+= hashkit
->context_size
)
136 if (hashkit
->active_fn
!= NULL
&& hashkit
->active_fn(context
) == false)
139 if (hashkit
->weight_fn
!= NULL
)
141 float pct
= (float)hashkit
->weight_fn(context
) / (float)total_weight
;
142 points_per_server
= (uint32_t) ((floorf((float) (pct
* HASHKIT_POINTS_PER_NODE_WEIGHTED
/ 4 * (float)live_servers
+ 0.0000000001))) * 4);
145 for (points_index
= 0;
146 points_index
< points_per_server
/ points_per_hash
;
149 char sort_host
[HASHKIT_CONTINUUM_KEY_SIZE
]= "";
150 size_t sort_host_length
;
152 if (hashkit
->continuum_key_fn
== NULL
)
154 sort_host_length
= (size_t) snprintf(sort_host
, HASHKIT_CONTINUUM_KEY_SIZE
, "%u",
159 sort_host_length
= hashkit
->continuum_key_fn(sort_host
, HASHKIT_CONTINUUM_KEY_SIZE
,
160 points_index
, context
);
163 if (hashkit
->weight_fn
== NULL
)
165 if (hashkit
->continuum_hash_fn
== NULL
)
166 value
= hashkit_default(sort_host
, sort_host_length
);
168 value
= hashkit
->continuum_hash_fn(sort_host
, sort_host_length
);
170 hashkit
->continuum
[continuum_index
].index
= count
;
171 hashkit
->continuum
[continuum_index
++].value
= value
;
176 for (i
= 0; i
< points_per_hash
; i
++)
178 value
= ketama_server_hash(sort_host
, (uint32_t) sort_host_length
, (int) i
);
179 hashkit
->continuum
[continuum_index
].index
= count
;
180 hashkit
->continuum
[continuum_index
++].value
= value
;
185 points_count
+= points_per_server
;
188 hashkit
->continuum_points_count
= points_count
;
189 qsort(hashkit
->continuum
, hashkit
->continuum_points_count
, sizeof(hashkit_continuum_point_st
),
190 continuum_points_cmp
);