TrafficServer一致性Hash的实验分析

#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <stdio.h>

#define CLUSTER_MAX_MACHINES 256
#define CLUSTER_HASH_TABLE_SIZE 32707

struct ClusterMachine
{
  unsigned int ip;
};

struct ClusterConfiguration
{
  int n_machines;
  ClusterMachine *machines[CLUSTER_MAX_MACHINES];
  unsigned char hash_table[CLUSTER_HASH_TABLE_SIZE];
};

inline unsigned int
next_rand(unsigned int *p)
{
  unsigned int seed = *p;
  seed = 1103515145 * seed + 12345;
  *p = seed;
  return seed;
}

void
build_hash_table_machine(ClusterConfiguration * c)
{
  int left = CLUSTER_HASH_TABLE_SIZE;
  int m = 0;
  int i = 0;
  unsigned int rnd[CLUSTER_MAX_MACHINES];
  unsigned int mach[CLUSTER_MAX_MACHINES];
  int total = CLUSTER_HASH_TABLE_SIZE;

  for (i = 0; i < c->n_machines; i++) {
    int mine = total / (c->n_machines - i);
    mach[i] = mine;
    total -= mine;
  }

  for (m = 0; m < c->n_machines; m++)
    rnd[m] = (((c->machines[m]->ip >> 15) & 0x7FFF) ^ (c->machines[m]->ip & 0x7FFF))
      ^ (c->machines[m]->ip >> 30);

  for (i = 0; i < CLUSTER_HASH_TABLE_SIZE; i++)
    c->hash_table[i] = 255;

  m = 0;
  while (left) {
    do {
      i = next_rand(&rnd[m]) % CLUSTER_HASH_TABLE_SIZE;
    } while (c->hash_table[i] != 255);
    mach[m]--;
    c->hash_table[i] = m;
    left--;
    m = (m + 1) % c->n_machines;
  }
}

void
configuration_add_machine(ClusterConfiguration * cc, Machine * m)
{
  int i = 0;
  for (i = 0; i < cc->n_machines; i++) {
    if (cc->machines[i]->ip > m->ip)
      break;
  }

  for (int j = cc->n_machines - 1; j >= i; j--)
    cc->machines[j + 1] = cc->machines[j];
  cc->machines[i] = m;
  cc->n_machines++;

  build_hash_table_machine(cc);
}

void
configuration_remove_machine(ClusterConfiguration * cc, Machine * m)
{
  printf("remove machines = %u\n", m->ip);
  for (int i = 0; i < cc->n_machines - 1; i++)
    if (m == cc->machines[i])
      m = cc->machines[i] = cc->machines[i + 1];
  cc->n_machines--;

  build_hash_table_machine(cc);
}

int
main(int argc, char **argv)
{
  ClusterConfiguration mycc;
  mycc.n_machines=0;
  ClusterMachine *mymach;
  unsigned int fail;
  for (int i = 0; i < CLUSTER_HASH_TABLE_SIZE; i++)
    mycc.hash_table[i]=255;

  for(int i = 1; i < argc; i++) {
//printf("arg%d = %s\n", i, argv[i]);
    mymach=new Machine;
    mymach->ip=inet_addr(argv[i]);
//printf("machine ip = %u\n", mymach.ip);
    configuration_add_machine(&mycc, mymach);
    //printf("n_machines = %u\n", mycc.n_machines);
  }

  ClusterConfiguration newcc=mycc;
  for(int i = 0; i < mycc.n_machines; i++) {
    printf("n_machines = %u\n", newcc.machines[i]->ip);
  }
  for(int i = 0; i < mycc.n_machines; i++) {
    newcc=mycc;
    configuration_remove_machine(&newcc, mycc.machines[i]);
    printf("n_machines = %u\n", newcc.n_machines);
    fail=0;
    for (int j = 0; j < CLUSTER_HASH_TABLE_SIZE; j++) {
      if( mycc.hash_table[j] != i ){
        if ( mycc.hash_table[j] < i ) {
          if ( mycc.hash_table[j] != newcc.hash_table[j] ) {
            fail++;
          }
        }
        else {
          if ( mycc.hash_table[j] != newcc.hash_table[j] +1) {
            fail++;
          }
        }
      }
    }
    printf("Machine %u fail= %u\n", mycc.machines[i]->ip, fail);
  }
return(0);
}