좋은 재분할 알고리즘

Question

memcached 클라이언트 라이브러리를 구현 중입니다. 여러 대의 서버를 지원하기를 원하며로드 밸런싱 시스템을 추가하고 싶습니다.

기본적으로, 당신은 서버에 두 가지 작업을 수행 할 수 있습니다

• 저장하시오 value 주어진 그 key.
• key을 value으로 지정하십시오.

, 내가 가지고 싶은 우리는 내가 (0에서 N - 1에) N 서버가 있다고 가정 해 봅시다 주어진 key 및 서버 수 N에서의 [0, N[에 나에게 index을 줄 것이라고하는 다시 파티션 기능 범위.

unsigned int getServerIndex(const std::string& key, unsigned int serverCount); 

기능은 신속하고 가능한 한 간단해야하며, 다음과 같은 제약 존중해야한다 : 외부 라이브러리 (같은 OpenSSL와 해시를 사용하지 않고 내가이 을 할 수 있으면 좋겠다

getServerIndex(key, N) == getServerIndex(key, N); //aka. No random return. 

을 함수). 내 옵션은 무엇입니까?

---

사이드 노트 : 분명히

, 기본 구현 : D

이 정확하게 좋은 다시 분할 기능이 아니므로

unsigned int getServerIndex(const std::string& key, unsigned int serverCount) 
{ 
    return 0; 
} 

가 유효한 대답이 없습니다

---

추가 정보 :

키는 일반적으로 ANSI charset (대부분 [a-zA-Z0-9_-]) 내의 가능한 모든 문자열입니다. 크기는 one-char-key에서 원하는 크기에 이르기까지 다양 할 수 있습니다.

좋은 재분할 알고리즘 a 복귀의 가능성이 두 가지 키를 들면 b 복귀 확률로부터 (또는 멀지 않은) 동일한되는 알고리즘이다. 서버 수는 변경 될 수 있지만 드물게 주어진 key에 대한 반환 된 인덱스도 변경 될 수 있습니다.