|
Приветствую всех.
Хочется обсудить с вами проблема выбора альтернативного алгоритма выбора узла с кешем.
Эта проблема частично обсуждалась на http://www.serverphorums.com/read.php?9,192006
На данный момент я использую CRC32 алгоритм, который предлагается модулем ngx_http_upstream_hash_module от Evan Miller
Преимущества:
~ быстрота вычисления узла;
~ поддержка всеми языками программирования;
Недостатки:
~ в случае падения узла с memcached происходит rehash валидных ключей, что приводит к сильной нагрузке на базу данных.
~ в случае восстановления узла, или добавления нового также происходит значительная потеря валидных ключей, связанная с перемещением их на новые ноды
согласно алгоритма CRC32 ( f(ключ) = crc32(ключ) % количество_серверов )
На backend я использую Java. Приложение соединяется с кэшем через java memcached API : spymemcached.
Таким образом возникает проблема согласованного выбора узла между java (spymemcached) и nginx.
Гарантированно одинаково Java и nginx работает только по протоколу CRC32.
Какие же альтернативы предлагаются?
----
Наиболее известная альтернатива :
Алгоритм консистентного (согласованного) кэширования ketama от last.fm. Принцип работы хорошо объяснен в статье на хабре:http://habrahabr.ru/blogs/webdev/42972/
Сначала рассмотрим nginx.
Если порыться в сторонних модулях к nginx, то можно найти 2 модуля для консистентного кэширования:
- ngx_http_upstream_consistent_hash от Mauro Stettler
- nginx-upstream-consistent от dctrwatson
Оба модуля работают, но выбирают узлы по-разному. Выбор узла с memcached не совпадает с выбором узла через spymemcached.
Вообще spymemcached поддерживает следующие алгоритмы:
-----------
public long hash(final String k) {
long rv = 0;
switch (this) {
case NATIVE_HASH:
rv = k.hashCode();
break;
case CRC32_HASH:
// return (crc32(shift) >> 16) & 0x7fff;
CRC32 crc32 = new CRC32();
crc32.update(KeyUtil.getKeyBytes(k));
rv = (crc32.getValue() >> 16) & 0x7fff;
break;
case FNV1_64_HASH: {
// Thanks to pierre@xxxxxxxxxxxxxx for the pointer
rv = FNV_64_INIT;
int len = k.length();
for (int i = 0; i < len; i++) {
rv *= FNV_64_PRIME;
rv ^= k.charAt(i);
}
}
break;
case FNV1A_64_HASH: {
rv = FNV_64_INIT;
int len = k.length();
for (int i = 0; i < len; i++) {
rv ^= k.charAt(i);
rv *= FNV_64_PRIME;
}
}
break;
case FNV1_32_HASH: {
rv = FNV_32_INIT;
int len = k.length();
for (int i = 0; i < len; i++) {
rv *= FNV_32_PRIME;
rv ^= k.charAt(i);
}
}
break;
case FNV1A_32_HASH: {
rv = FNV_32_INIT;
int len = k.length();
for (int i = 0; i < len; i++) {
rv ^= k.charAt(i);
rv *= FNV_32_PRIME;
}
}
break;
case KETAMA_HASH:
/*MD5-based hash algorithm used by ketama.*/
byte[] bKey=computeMd5(k);
rv = ((long) (bKey[3] & 0xFF) << 24)
| ((long) (bKey[2] & 0xFF) << 16)
| ((long) (bKey[1] & 0xFF) << 8)
| (bKey[0] & 0xFF);
break;
default:
assert false;
}
return rv & 0xffffffffL; /* Truncate to 32-bits */
}
На практике ketama-алгоритм вычисления (через MD5!) правильного узла в spymemcached не совпадает ни с одним из ketama-алгоритмов вычисления (тоже через MD5)
в указанных выше nginx модулях.
Кто-нибудь может подсказать как добиться согласованной работы ketama-алгоритма между различными языками программирования?
P.S.
Также spy memcached предлагает еще один алгоритм: FNV.
Может nginx поддерживать его? Если такие модули?
--
Best Regards, Eugene Batogov
| 
