Ketama hash collision 시의 owner 결정

[jhpark816]

Hash collision 발생 시의 owner 결정 방식으로
hostname 비교하여 작은 hostname의 cache node가 owner가 되도록 한다.

현재 cache server, java-client는 모두 반영된 상태이고,
c-client만 남아있는 상태이다.

수백개 이상의 캐시 인스턴스를 가지는 대규모 클러스터인 경우
ketama hash collision이 발생하므로,
이러한 대규모 클러스터에서 사용하기 위해서는 수정해야 한다.

[uhm0311]

@jhpark816

java-client에서 해당 부분을 보니 TreeMap<Long, SortedSet< MemcachedNode >> 으로 관리하고 있습니다.
c-client에서 .cc 파일은 C++ 소스 코드이므로 std::map과 std::set을 사용할 수 있습니다.
의사 코드로 작업 방향을 표현하자면 다음과 같이 될 것 같습니다.

// hash ring update
...
std::map<uin32_t, std::set<memcached_server_instance_st>> new_continumm;
...
for (uint32_t x= 0; x < pointer_per_hash; x++)
{
  uint32_t hash= ketama_server_hash(sort_host, (size_t)sort_host_length, x);
  list[host_index].index= host_index;

  new_continumm[hash].set_compare_function(compare_servers)
  new_continuum[hash].add(list[host_index]);
}
...

// hash ring read
return ptr->ketama.info->continuum[continuum.ceilling_key(hash)].first_item()->index;

[jhpark816]

@uhm0311

• C++ 라이브러리 도입하는 것은 나중에 고려하고
• 기존 구현 기준으로, 아래 사항을 먼저 확인하면 좋겠습니다.
  • collision 처리하기 위한 설계
  • 구현 부담
  • 성능 포함한 장단점
• 위 내용에 C++ 라이브러리 사용 시의 비교는 포함되어도 됩니다.

[uhm0311]

@jhpark816

• hash ring은 qsort() 함수를 통해 정렬 되므로, compare 함수에 hash 값이 동일한 경우 hostname과 port를 기준으로 정렬하도록 하고, hash ring read 과정에서 선택된 continuum item과 인접한 item의 해시가 동일할 때 해시가 같은 가장 왼쪽의 item을 사용하도록 하면 될 것 같습니다.
• 구현 부담은 크지 않습니다.
• qsort() 함수를 이용하여 정렬하므로 정렬 과정에 실행 속도 성능 영향은 없습니다. 단, qsort() 함수를 수행하는 시점에서 continuum item에 hostname과 port 정보가 있어야 하므로 메모리 사용량은 증가합니다.
• hash ring read 단계에서는 인접해 있으면서 해시 값이 동일한 continuum item들 중 가장 왼쪽을 선택하는 과정에서 해시 값이 동일한 continuum item 개수만큼 반복문을 돌리게 됩니다. 따라서 read 과정에서는 해시 값이 동일한 아이템의 개수만큼 성능에 영향이 있을 것입니다.

[jhpark816]

@uhm0311
C++ 라이브러리 이용한 방안과 비교하면, 기존 구현의 성능은 어떻게 될 거라 예측하나요?

[uhm0311]

@jhpark816

• 기존 구현에서 hash ring update 부분은 qsort()에서 O(N * logN)입니다.
• 기존 구현에서 hash ring read 부분은 binary search에서 평균 O(logN), 최악의 경우 O(N)입니다.
• C++ 라이브러리 사용 시 hash ring update 부분은 map에 접근하여 set에 추가할 때 동일한 해시 값이 없어서 set의 크기가 0인 경우에는 O(logN)입니다. set의 크기가 0이 아닌 경우에는 O(logN * logN)입니다.
• C++ 라이브러리 사용 시 hash ring read 부분은 map에 접근할 때 O(logN)입니다. 자가 균형 이진 트리이므로 최악의 경우에도 O(logN)입니다.

[jhpark816]

@uhm0311
우선은 기존 구현 기준으로 수정하도록 합시다.

[jhpark816]

본 이슈에 대해 PR merge 되었으므로, close 합니다.