git.m6w6.name Git - m6w6/libmemcached/blob - libhashkit/ketama.cc

   1 /* HashKit
   2  * Copyright (C) 2006-2009 Brian Aker
   3  * All rights reserved.
   4  *
   5  * Use and distribution licensed under the BSD license.  See
   6  * the COPYING file in the parent directory for full text.
   7  */
   8
   9 #include <libhashkit/common.h>
  10 #include <math.h>
  11
  12 #if 0
  13 static uint32_t ketama_server_hash(const char *key, unsigned int key_length, int alignment)
  14 {
  15   unsigned char results[16];
  16
  17   md5_signature((unsigned char*)key, key_length, results);
  18   return ((uint32_t) (results[3 + alignment * 4] & 0xFF) << 24)
  19     | ((uint32_t) (results[2 + alignment * 4] & 0xFF) << 16)
  20     | ((uint32_t) (results[1 + alignment * 4] & 0xFF) << 8)
  21     | (results[0 + alignment * 4] & 0xFF);
  22 }
  23
  24 static int continuum_points_cmp(const void *t1, const void *t2)
  25 {
  26   hashkit_continuum_point_st *ct1= (hashkit_continuum_point_st *)t1;
  27   hashkit_continuum_point_st *ct2= (hashkit_continuum_point_st *)t2;
  28
  29   if (ct1->value == ct2->value)
  30     return 0;
  31   else if (ct1->value > ct2->value)
  32     return 1;
  33   else
  34     return -1;
  35 }
  36
  37 int update_continuum(hashkit_st *hashkit)
  38 {
  39   uint32_t count;
  40   uint32_t continuum_index= 0;
  41   uint32_t value;
  42   uint32_t points_index;
  43   uint32_t points_count= 0;
  44   uint32_t points_per_server;
  45   uint32_t points_per_hash;
  46   uint64_t total_weight= 0;
  47   uint32_t live_servers;
  48   uint8_t *context;
  49
  50   if (hashkit->active_fn != NULL || hashkit->weight_fn != NULL)
  51   {
  52     live_servers= 0;
  53
  54     for (count= 0, context= hashkit->list; count < hashkit->list_size;
  55          count++, context+= hashkit->context_size)
  56     {
  57       if (hashkit->active_fn != NULL)
  58       {
  59         if (hashkit->active_fn(context))
  60           live_servers++;
  61         else
  62           continue;
  63       }
  64
  65       if (hashkit->weight_fn != NULL)
  66         total_weight+= hashkit->weight_fn(context);
  67     }
  68   }
  69
  70   if (hashkit->active_fn == NULL)
  71     live_servers= (uint32_t)hashkit->list_size;
  72
  73   if (live_servers == 0)
  74     return 0;
  75
  76   if (hashkit->weight_fn == NULL)
  77   {
  78     points_per_server= HASHKIT_POINTS_PER_NODE;
  79     points_per_hash= 1;
  80   }
  81   else
  82   {
  83     points_per_server= HASHKIT_POINTS_PER_NODE_WEIGHTED;
  84     points_per_hash= 4;
  85   }
  86
  87   if (live_servers > hashkit->continuum_count)
  88   {
  89     hashkit_continuum_point_st *new_continuum;
  90
  91     new_continuum= realloc(hashkit->continuum,
  92                            sizeof(hashkit_continuum_point_st) *
  93                            (live_servers + HASHKIT_CONTINUUM_ADDITION) *
  94                            points_per_server);
  95
  96     if (new_continuum == NULL)
  97       return ENOMEM;
  98
  99     hashkit->continuum= new_continuum;
 100     hashkit->continuum_count= live_servers + HASHKIT_CONTINUUM_ADDITION;
 101   }
 102
 103   for (count= 0, context= hashkit->list; count < hashkit->list_size;
 104        count++, context+= hashkit->context_size)
 105   {
 106     if (hashkit->active_fn != NULL && hashkit->active_fn(context) == false)
 107       continue;
 108
 109     if (hashkit->weight_fn != NULL)
 110     {
 111         float pct = (float)hashkit->weight_fn(context) / (float)total_weight;
 112         points_per_server= (uint32_t) ((floorf((float) (pct * HASHKIT_POINTS_PER_NODE_WEIGHTED / 4 * (float)live_servers + 0.0000000001))) * 4);
 113     }
 114
 115     for (points_index= 0;
 116          points_index < points_per_server / points_per_hash;
 117          points_index++)
 118     {
 119       char sort_host[HASHKIT_CONTINUUM_KEY_SIZE]= "";
 120       size_t sort_host_length;
 121
 122       if (hashkit->continuum_key_fn == NULL)
 123       {
 124         sort_host_length= (size_t) snprintf(sort_host, HASHKIT_CONTINUUM_KEY_SIZE, "%u",
 125                                             points_index);
 126       }
 127       else
 128       {
 129         sort_host_length= hashkit->continuum_key_fn(sort_host, HASHKIT_CONTINUUM_KEY_SIZE,
 130                                                  points_index, context);
 131       }
 132
 133       if (hashkit->weight_fn == NULL)
 134       {
 135         if (hashkit->continuum_hash_fn == NULL)
 136           value= hashkit_default(sort_host, sort_host_length);
 137         else
 138           value= hashkit->continuum_hash_fn(sort_host, sort_host_length);
 139
 140         hashkit->continuum[continuum_index].index= count;
 141         hashkit->continuum[continuum_index++].value= value;
 142       }
 143       else
 144       {
 145         unsigned int i;
 146         for (i = 0; i < points_per_hash; i++)
 147         {
 148            value= ketama_server_hash(sort_host, (uint32_t) sort_host_length, (int) i);
 149            hashkit->continuum[continuum_index].index= count;
 150            hashkit->continuum[continuum_index++].value= value;
 151         }
 152       }
 153     }
 154
 155     points_count+= points_per_server;
 156   }
 157
 158   hashkit->continuum_points_count= points_count;
 159   qsort(hashkit->continuum, hashkit->continuum_points_count, sizeof(hashkit_continuum_point_st),
 160         continuum_points_cmp);
 161
 162   return 0;
 163 }
 164 #endif