devcken.io

Thoughts, stories and ideas.

libketama: Consistent Hashing library for memcached clients

우리는 memcached 클라이언트가 키를 서버에 매핑하는 방법을 바꾸기 위해 Ketama를 만들었습니다. 이전에는, 클라이언트가 키를 다음과 같이 서버에 매핑했습니다:

server = serverlist[hash(key) % serverlist.length];  

즉, 풀에 서버를 추가하거나 제거할 때마다, 모든 것이 다른 서버에 해시되어, 전체 캐시를 효과적으로 삭제했습니다.

자주 memcached 풀에 서버를 추가(그리고 때로는 제거)하는데, 이 점이 이 라이브러리 작성의 이유가 됩니다 - memcached 풀이 결코 변경되지 않는다면, 이 글을 읽지 않아도 될 겁니다 :)

Ketama는 일치성 해싱 알고리즘의 구현으로, 모든 키에 대한 전체적인 리매핑을 일으키지 않고 memcached 풀에 서버를 추가하거나 제거할 수 있다는 것을 의미합니다.

동작 방법

  • 서버 목록을 받습니다(예: 1.2.3.4:11211, 5.6.7.8:11211, 9.8.7.6:11211).
  • 각 서버 문자열을 각각의 unsigned int으로 해싱합니다.
  • 개념 상, 이 숫자들은 컨티늄(continum)이라고 하는 원에 놓입니다(0에서 2^32까지의 시계를 상상해보세요).
  • 각각의 숫자는 그것이 해시된 서버에 연결되고, 해시된 숫자에 따라 컨티늄 상의 몇몇 지점에 서버가 놓입니다.
  • 키를 서버에 매핑하기 위해, 키를 단일 unsigned int로 해싱하고, 컨티늄 상에서 가장 큰 숫자를 찾습니다. 그 숫자와 연결된 서버가 그 키에 대한 올바른 서버입니다.

리스트에서 서버를 추가하거나 제거하는 경우, 적은 비율의 키만 다른 서버에 매핑됩니다.

코드

코드의 대부분은 C 라이브러리 (libketama)와 그것을 감싸는 php4 확장입니다. 또한 자바 클라이언트의 클래스도 포함시켰습니다(자바 컬렉션이 라이브러리를 더 쉽게 만듭니다). 네이티브 php 클래스로 래핑된 단일 서버의 memcached 클라이언트를 사용해 다중 서버를 사용할 수 있게 만들어, 해싱 메서드를 ketamafindserver 호출로 대체했습니다(필요하다면 이것을 libmemcache에 쉽게 끼워 넣을 수 있어야 합니다).

libketama on github

현재 10일 가까이 Last.fm의 모든 php 설치본과 자바 서비스의 상용에서 사용하고 있습니다. 데이터 센터 내 웹 서버의 부하를 원활하게 이동시킬 수 있도록 이 라이브러리를 제때에 시간에 맞추어 배포했습니다.

더 읽어볼 거리