Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
branch: master
Fetching contributors…

Cannot retrieve contributors at this time

332 lines (261 sloc) 10.632 kb
/**
* Copyright 2011 LiveProfile
*
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <stdlib.h>
#include "hash_ring.h"
#include <mach/mach_time.h>
static uint64_t opStartTime = 0;
void testAddMultipleTimes();
void testRemoveNode();
void testEmptyRingItemSearchReturnsNull();
void testEmptyRingSearchReturnsNull();
void testKnownNextHighestItemOnRing();
void testKnownSlotsOnRing();
void testRingSorted();
void runBenchmark();
void startTiming();
uint64_t endTiming();
int main(int argc, char **argv) {
testAddMultipleTimes();
testRemoveNode();
testRingSorted();
testKnownNextHighestItemOnRing();
testEmptyRingItemSearchReturnsNull();
testEmptyRingSearchReturnsNull();
testKnownSlotsOnRing();
runBenchmark();
return 0;
}
void startTiming() {
#ifdef __APPLE__
opStartTime = mach_absolute_time();
#endif
}
uint64_t endTiming() {
#ifdef __APPLE__
uint64_t duration = mach_absolute_time() - opStartTime;
/* Get the timebase info */
mach_timebase_info_data_t info;
mach_timebase_info(&info);
/* Convert to nanoseconds */
duration *= info.numer;
duration /= info.denom;
return duration;
#else
return 0;
#endif
}
void fillRandomBytes(uint8_t *bytes, uint32_t num) {
int x;
for(x = 0; x < num; x++) {
bytes[x] = (rand() % 25) + 97;
}
}
void addNodes(hash_ring_t *ring, int numNodes) {
int x;
uint8_t nodeName[16];
printf("generating and sorting %d nodes...", numNodes);
fflush(stdout);
for(x = 0; x < numNodes; x++) {
fillRandomBytes(nodeName, sizeof(nodeName));
hash_ring_add_node(ring, nodeName, sizeof(nodeName));
}
printf("done\n");
}
void generateKeys(uint8_t *keys, int numKeys, int keySize) {
printf("generating keys...");
fflush(stdout);
int x;
for(x = 0; x < numKeys; x++) {
fillRandomBytes(&keys[x], keySize);
}
printf("done\n");
}
void runBench(HASH_FUNCTION hash_fn, int numReplicas, int numNodes, int numKeys, int keySize) {
char *hash = NULL;
if(hash_fn == HASH_FUNCTION_MD5) hash = "MD5";
else if(hash_fn == HASH_FUNCTION_SHA1) hash = "SHA1";
printf("----------------------------------------------------\n");
printf("bench (%s): replicas = %d, nodes = %d, keys: %d, ring size: %d\n", hash, numReplicas, numNodes, numKeys, numReplicas * numNodes);
printf("----------------------------------------------------\n");
hash_ring_t *ring = hash_ring_create(numReplicas, hash_fn);
addNodes(ring, numNodes);
uint8_t *keys = (uint8_t*)malloc(keySize * numKeys);
generateKeys(keys, numKeys, keySize);
printf("running...\r");
uint64_t min = 0;
uint64_t max = 0;
uint64_t total = 0;
int times = 100;
int x, y;
for(y = 0; y < times; y++) {
startTiming();
for(x = 0; x < numKeys; x++) {
assert(hash_ring_find_node(ring, keys + (keySize * x), keySize) != NULL);
}
uint64_t result = endTiming();
if(result > max) max = result;
if(min == 0 || result < min) min = result;
total += result;
}
printf("stats: total = %.5fs, avg/lookup: %.5fus, min: %.5fus, max: %.5fus, ops/sec: %.0f\n",
(double)total / 1000000000,
(((double)(total / numKeys)) / 1000) / times,
(double)min / numKeys / 1000,
(double)max / numKeys / 1000,
1000000000 / ((double)(total / (numKeys * times))));
free(keys);
hash_ring_free(ring);
}
void runBenchmark() {
printf("Starting benchmarks...\n");
HASH_FUNCTION hash_fn = HASH_FUNCTION_SHA1;
runBench(hash_fn, 1, 1, 1000, 16);
runBench(hash_fn, 1, 8, 1000, 16);
runBench(hash_fn, 1, 256, 1000, 16);
runBench(hash_fn, 8, 1, 1000, 16);
runBench(hash_fn, 8, 32, 1000, 16);
runBench(hash_fn, 8, 512, 1000, 16);
runBench(hash_fn, 512, 8, 1000, 16);
runBench(hash_fn, 512, 16, 1000, 16);
runBench(hash_fn, 512, 32, 100000, 16);
runBench(hash_fn, 512, 128, 10000, 16);
runBench(hash_fn, 16, 1024, 1000, 16);
hash_fn = HASH_FUNCTION_MD5;
runBench(hash_fn, 1, 1, 1000, 16);
runBench(hash_fn, 1, 8, 1000, 16);
runBench(hash_fn, 1, 256, 1000, 16);
runBench(hash_fn, 8, 1, 1000, 16);
runBench(hash_fn, 8, 32, 1000, 16);
runBench(hash_fn, 8, 512, 1000, 16);
runBench(hash_fn, 512, 8, 1000, 16);
runBench(hash_fn, 512, 16, 1000, 16);
runBench(hash_fn, 512, 32, 100000, 16);
runBench(hash_fn, 512, 128, 10000, 16);
runBench(hash_fn, 16, 1024, 1000, 16);
}
void testRingSorting(int num) {
printf("Test that the ring is sorted [%d item(s)]...\n", num);
hash_ring_t *ring = hash_ring_create(num, HASH_FUNCTION_SHA1);
char *slotA = "slotA";
assert(hash_ring_add_node(ring, (uint8_t*)slotA, strlen(slotA)) == HASH_RING_OK);
int x;
uint64_t cur = 0;
for(x = 0; x < ring->numItems; x++) {
assert(ring->items[x]->number > cur);
cur = ring->items[x]->number;
}
hash_ring_free(ring);
}
void testRingSorted() {
testRingSorting(1);
testRingSorting(2);
testRingSorting(3);
testRingSorting(5);
testRingSorting(64);
testRingSorting(256);
testRingSorting(1024);
testRingSorting(10000);
testRingSorting(100000);
testRingSorting(1000000);
}
void testEmptyRingItemSearchReturnsNull() {
printf("Test empty ring search returns null item...\n");
hash_ring_t *ring = hash_ring_create(8, HASH_FUNCTION_SHA1);
assert(hash_ring_find_next_highest_item(ring, 0) == NULL);
hash_ring_free(ring);
}
void testEmptyRingSearchReturnsNull() {
printf("Test empty ring search returns null node...\n");
hash_ring_t *ring = hash_ring_create(8, HASH_FUNCTION_SHA1);
char *key = "key";
assert(hash_ring_find_node(ring, (uint8_t*)key, strlen(key)) == NULL);
hash_ring_free(ring);
}
void testKnownSlotsOnRing() {
printf("Test getting known nodes on ring...\n");
hash_ring_t *ring = hash_ring_create(8, HASH_FUNCTION_SHA1);
char *slotA = "slotA";
char *slotB = "slotB";
char *keyA = "keyA";
char *keyB = "keyBBBB";
char *keyC = "keyB_";
hash_ring_node_t *node;
assert(hash_ring_add_node(ring, (uint8_t*)slotA, strlen(slotA)) == HASH_RING_OK);
assert(hash_ring_add_node(ring, (uint8_t*)slotB, strlen(slotB)) == HASH_RING_OK);
node = hash_ring_find_node(ring, (uint8_t*)keyA, strlen(keyA));
assert(node != NULL && node->nameLen == strlen(slotA) && memcmp(node->name, slotA, strlen(slotA)) == 0);
node = hash_ring_find_node(ring, (uint8_t*)keyB, strlen(keyB));
assert(node != NULL && node->nameLen == strlen(slotA) && memcmp(node->name, slotA, strlen(slotA)) == 0);
node = hash_ring_find_node(ring, (uint8_t*)keyC, strlen(keyC));
assert(node != NULL && node->nameLen == strlen(slotB) && memcmp(node->name, slotB, strlen(slotB)) == 0);
hash_ring_free(ring);
}
void testKnownNextHighestItemOnRing() {
printf("Test getting next highest item on ring...\n");
hash_ring_t *ring = hash_ring_create(8, HASH_FUNCTION_SHA1);
char *slotA = "slotA";
char *slotB = "slotB";
assert(hash_ring_add_node(ring, (uint8_t*)slotA, strlen(slotA)) == HASH_RING_OK);
assert(hash_ring_add_node(ring, (uint8_t*)slotB, strlen(slotB)) == HASH_RING_OK);
// next highest for first item should yield the second
assert(hash_ring_find_next_highest_item(ring, 2351641940735260693u)->number == 2584980261350711786u);
// number less than the first should yield the first
assert(hash_ring_find_next_highest_item(ring, 2351641940735260692u)->number == 2351641940735260693u);
// number in the middle should yield the next
assert(hash_ring_find_next_highest_item(ring, 5908063426886290069u)->number == 6065789416862870789u);
// number equal to the last should wrap around to the first
assert(hash_ring_find_next_highest_item(ring, 17675051572751928939u)->number == 2351641940735260693u);
hash_ring_free(ring);
}
void testRemoveNode() {
printf("Test removing a node...\n");
hash_ring_t *ring = hash_ring_create(1, HASH_FUNCTION_SHA1);
hash_ring_node_t *node;
char *mynode = "mynode";
char *mynode1 = "mynode1";
char *mynode2 = "mynode2";
char *mykey = "mykey";
assert(hash_ring_add_node(ring, (uint8_t*)mynode, strlen(mynode)) == HASH_RING_OK);
assert(hash_ring_add_node(ring, (uint8_t*)mynode1, strlen(mynode2)) == HASH_RING_OK);
assert(hash_ring_add_node(ring, (uint8_t*)mynode2, strlen(mynode2)) == HASH_RING_OK);
assert(ring->numNodes == 3);
node = hash_ring_find_node(ring, (uint8_t*)mykey, strlen(mykey));
assert(node != NULL && node->nameLen == strlen(mynode) && memcmp(mynode, node->name, node->nameLen) == 0);
assert(hash_ring_remove_node(ring, (uint8_t*)mynode, strlen(mynode)) == HASH_RING_OK);
assert(ring->numNodes == 2);
assert(hash_ring_get_node(ring, (uint8_t*)mynode, strlen(mynode)) == NULL);
// remove node1, and try to search for a key that went to it before, and verify it goes to node2
assert(hash_ring_remove_node(ring, (uint8_t*)mynode1, strlen(mynode1)) == HASH_RING_OK);
assert(ring->numNodes == 1);
node = hash_ring_find_node(ring, (uint8_t*)mykey, strlen(mykey));
assert(node != NULL && node->nameLen == strlen(mynode2) && memcmp(mynode2, node->name, node->nameLen) == 0);
hash_ring_free(ring);
}
void testAddMultipleTimes() {
printf("Test adding a node multiple times...\n");
hash_ring_t *ring = hash_ring_create(1, HASH_FUNCTION_SHA1);
assert(ring != NULL);
char *mynode = "mynode";
hash_ring_add_node(ring, (uint8_t*)mynode, strlen(mynode));
assert(ring->numNodes == 1);
assert(hash_ring_add_node(ring, (uint8_t*)mynode, strlen(mynode)) == HASH_RING_ERR);
assert(ring->numNodes == 1);
hash_ring_free(ring);
}
Jump to Line
Something went wrong with that request. Please try again.