Unique ID, Key 생성기 설계 (with Shard Key)

 

대규모시스템개발 #3 참고
7장. 분산 시스템을 위한 유일 ID 생성기 설계 참고

 

요구사항

1. 유일해야 함.
2. 시간 순으로 정렬 가능해야 함. (단 아주 작은 time slot 안에서는 순서가 보장되지 않아도 상관 없음)
3. 숫자로만 구성되어야 함.
4. DB 1대의 auto increment로 커버 불가한 규모.
5. 분산DB 사용 중이라, ID를 보고 샤드를 찾아갈 수 있어야 함.

 

1-4 sol

• 트위터의 snowflake
  • 데이터센터 위치, 서버 ID가 들어가서 어느 리전의 어느 서버가 채번하든 unique하도록.

• instagram 방식
  • shard ID를 넣었다.

 

5 sol -shard key에 대해서.

• id 자체를 shard key로 사용하는 방법도 가능은 하지만, 반드시 그래야 한다는 법은 없다.
• id 안에 shard key를 포함하도록 구성 할 수 있다. (instagram 방식)
• shard key를 별도 컬럼으로 가지고 있는 경우도 있다.

 

가장 심플하게 생각해보면 ) Shard key를 modular로 계산하는 경우?

`` shard_id = x % n`` 이면

공간 부족으로 새로운 서버가 추가될 때, 데이터의 이동이 많이 발생한다.

e.g., shard 3개, n=3으로 운용하는 상황에서 0번 shard에 들어가는 shard_id는 0, 3, 6, ...이다.

이 때 shard 1개가 추가되어 n=4가 되면,

shard_id 3은 3번 shard로,

shard_id 6은 2번 shard로 데이터를 재배치 해주어야 한다. (그래야 새로운 x % n으로 데이터를 찾아 갈 수 있으니까.)

 

이처럼 전체 shard에 걸쳐 데이터 이동이 일어나게 되어 매우 비효율적이다.

 

sol 5-1 확장성 해싱

• 8장. 직접화일 : 해시테이블, 확장성 해싱 VS 선형 해싱, Shard key  

 

sol 5-2 안정 해시

• 결국 ID 자체가 어떻게 구성 되어 있냐 보다는, 'ID에 대한 hash값을 보고 shard를 어떻게 찾아갈 것이냐, 어떻게 shard를 배치 할 것이냐'가 중요하다.
• ID에 shard 번호를 넣는 방식은, 해당 데이터는 반드시 그 샤드에 있어야만 하므로, 샤드가 다 찼을 때 데이터를 반으로 마이그 할 수 없다. 따라서 새로운 ID를 채번 할 때 해당 샤드 번호는 반환하지 않도록 해야 하는 등 여러모로 애매한 상황이 발생 할 수 있을 것 같다.
  • 인스타그램은 Logical Shard ID를 넣었는데, 안정해시 쓰는 것으로 보임. 어차피 ID 전체를 hash한걸 Logical Shard ID로 쓰나, 그냥 ID 안에 Logical Shard ID를 넣어서 hash 수행을 1회 줄이나 방법론적으로 크게 다른 부분은 없어보인다.

 

안정해시와 비슷하게, modular를 사용하면서 가상노드를 추가한 방법도 있다.

• share key 1-500은 0번샤드  /  500-1000은 1번샤드 운용
• 0번 샤드가 가득 찼을 때, 2번 샤드 증설
• 1-250은 0번 샤드에 두고, 251-500을 2번 샤드로 이동