Связка nginx-memcached и различные алгоритмы выбора узла с memcached ...

[Eugene Batogov]

Приветствую всех.
Хочется обсудить с вами проблема выбора альтернативного алгоритма выбора узла с кешем.
Эта проблема частично обсуждалась  на 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 at demartines.com 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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://nginx.org/pipermail/nginx-ru/attachments/20110607/646156f9/attachment-0001.html>