#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <stdlib.h>
#define NODENUM 10
#define SERVER "server"
#define OBJECT "object"
#define ONLINE 1
#define OFFLINE 0
#define KEYLEN 10
struct virtual_node
{
uint32_t hash;
};
struct node
{
int replicas;
struct virtual_node vnode[NODENUM];
int stat;
};
struct consistent_hash
{
struct node *node[NODENUM];
uint32_t (*hashfunc) (const char *);
int (*lookup) (struct consistent_hash *, const char *);
void (*remove) (struct consistent_hash *, int);
int (*add) (struct consistent_hash *, struct node *);
};
uint32_t
jenkinhash (const char *key)
{
uint32_t hash, i;
for (; *key; ++key)
{
hash += *key;
hash += (hash << 10);
hash ^= (hash >> 6);
}
hash += (hash << 3);
hash ^= (hash >> 11);
hash += (hash << 15);
return hash;
}
double
calculateSD (int data[])
{
double sum = 0.0, mean, SD = 0.0;
int i;
for (i = 0; i < 10; ++i)
{
sum += data[i];
}
mean = sum / 10;
for (i = 0; i < 10; ++i)
SD += pow (data[i] - mean, 2);
return sqrt (SD / 10);
}
int
node_init (struct node *node, int replicas)
{
if (node == NULL)
{
return -1;
}
node->stat = ONLINE;
node->replicas = replicas;
return 0;
}
int
conhash_lookup (struct consistent_hash *conhash, const char *object)
{
if (conhash == NULL || object == NULL)
{
return -1;
}
uint32_t hash = conhash->hashfunc (object);
//printf("object hash %ld\n", hash);
uint32_t nearest = UINT32_MAX;
uint32_t minimum = UINT32_MAX;
int nodeid = -1;
int min_nodeid = -1;
for (int i = 0; i < NODENUM; i++)
{
if (conhash->node[i] == NULL || conhash->node[i]->stat == OFFLINE)
{
continue;
}
for (int j = 0; j < conhash->node[i]->replicas; j++)
{
if (conhash->node[i]->vnode[j].hash > hash
&& conhash->node[i]->vnode[j].hash < nearest)
{
nearest = conhash->node[i]->vnode[j].hash;
nodeid = i;
}
if (conhash->node[i]->vnode[j].hash < minimum )
{
minimum = conhash->node[i]->vnode[j].hash;
min_nodeid = i;
}
}
}
if (nodeid == -1 )
{
if( min_nodeid != -1)
{
//printf("minnodeid %d\n", min_nodeid);
return min_nodeid;
}
}
//printf("nodeid %d\n", nodeid);
return nodeid;
}
void
calccount (int count[], int nodeid)
{
if (nodeid >= 0 && nodeid <= NODENUM)
{
count[nodeid]++;
}
}
void
test (struct consistent_hash *conhash)
{
int count[NODENUM] = { -1 };
int i;
memset (count, 0, sizeof (int) * NODENUM);
for (i = 0; i < 1000000; i++)
{
char object[64] = { 0 };
int nodeid;
snprintf (object, sizeof (object), "%s%ld", OBJECT, i);
nodeid = conhash->lookup (conhash, object);
calccount (count, nodeid);
}
for (i = 0; i < NODENUM; i++)
{
printf ("node %d = %d \n", i, count[i]);
//printf (" %d \n", count[i]);
}
double sd = calculateSD (count);
printf ("SD = %lf\n", sd);
}
void
remove_node (struct consistent_hash *conhash, int nodeid)
{
conhash->node[nodeid]->stat = OFFLINE;
conhash->node[nodeid] = NULL;
return;
}
int
add_node (struct consistent_hash *conhash, struct node *node)
{
for (int i = 0; i < NODENUM; i++)
{
if (conhash->node[i] == NULL)
{
conhash->node[i] = node;
char buff[64] = { 0 };
for (int j = 0; j < node->replicas; j++)
{
snprintf (buff, sizeof (buff), "%0x%s%0x", node, SERVER, j);
node->vnode[j].hash = conhash->hashfunc (buff);
}
return 0;
}
}
return -1;
}
void
conhash_init (struct consistent_hash *conhash)
{
conhash->hashfunc = jenkinhash;
conhash->lookup = conhash_lookup;
conhash->remove = remove_node;
conhash->add = add_node;
for (int i = 0; i < NODENUM; i++)
{
conhash->node[i] = NULL;
}
return;
}
struct consistent_hash conhash;
struct node node[NODENUM];
void
test_removenode_at_one_vnode ()
{
//test remove node
conhash_init (&conhash);
for (int i = 0; i < NODENUM; i++)
{
node_init (&node[i], 1);
conhash.add (&conhash, node + i);
}
test (&conhash);
conhash.remove (&conhash, 5);
test (&conhash);
}
void
test_removenode_at_mult_vnode ()
{
//test remove node
conhash_init (&conhash);
for (int i = 0; i < NODENUM; i++)
{
node_init (&node[i], 10);
conhash.add (&conhash, &node[i]);
}
test (&conhash);
conhash.remove (&conhash, 5);
test (&conhash);
}
void
test_add_vnode ()
{
//test add virtual node
for (int vnode = 1; vnode < NODENUM; vnode++)
{
conhash_init (&conhash);
for (int i = 0; i < NODENUM; i++)
{
node_init (&node[i], vnode);
conhash.add (&conhash, node + i);
}
test (&conhash);
}
}
void
test_add_one_vnode ()
{
conhash_init (&conhash);
node_init (&node[0], 1);
conhash.add (&conhash, &node[0]);
//printf("node 0 hash %ld\n", node[0].vnode[0].hash);
//printf("node 0 stat %ld\n", node[0].stat);
node_init (&node[1], 1);
int ret;
ret = conhash.add (&conhash, &node[1]);
//printf("node 1 hash %ld\n", node[1].vnode[0].hash);
//printf("node 1 stat %ld\n", node[1].stat);
node_init (&node[2], 1);
conhash.add (&conhash, &node[2]);
test (&conhash);
node_init (&node[3], 1);
conhash.add (&conhash, &node[3]);
test (&conhash);
}
void
main ()
{
test_removenode_at_one_vnode ();
test_removenode_at_mult_vnode ();
}
评论