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번 샤드로 이동

분산환경이 아닌 일반적인 DB key 설계

시간 + 알파벳 + 시퀀스

예시)
20231130120030TR00000001 (24자리)

시간 : 작업 성격에 맞는 적당한 수준의 정밀한 시간

• key 앞에 시간을 붙여주면 DB에서 날짜로 기간 검색 시, index가 걸려있는 key 컬럼을 BETWEEN 등으로 걸어서 사용할 수 있으므로 PK 인덱스를 활용할 수 있음.
• 정렬 키로 활용 가능하니까, 별도 시간 컬럼 사용하지 않아도 되고, 인덱스 따로 생성 안해도 되고, 파티션키 따로 안써도 되니까 개발도 편하고. 해서 장점이 많다.
• 그렇지 않으면 인덱스 없는 상태로 풀스캔 하거나, 날짜 컬럼에도 index를 걸어야 한다.
• 어차피 테이블 사이즈가 커지면, PK를 파티션키로 넣어주어야 하는데 별도 날짜 사용하지 않고 PK를 기준 날짜로 사용해서 검색하면, 파티션키를 따로 넣어주지 않아도 된다는 효과가 있다.

알파벳 : 멱등성 키로 활용 할 때 다른 키와 겹치지 않기 위해 충분한 자리 수. 보통 2자리

• 서로 다른 id로 같은 API를 호출하게 되면 멱등성 키에 들어가는 값이 겹칠 수 있기 때문.
• 알파벳을 중간에 넣어줘서 확실하게 id를 구분해주면 겹칠일이 없다.
• 그 외 id만 보고 어떤 id인지 바로 알아챌 수 있음.

시퀀스 : 같은 시간에 채번 될 수 있는 최대개수보다 자리 수가 커야 함.

• 특히 배치처리 하면서 대량 채번하는 경우 자리수 고려해야 함.
• 예를 들어 99,999,999 건이 동시 채번 될 수 있으면
  • yyyyMMdd’TR’ + 8자리 ⇒ 18자리
  • yyyyMMddHHmmss’TR’ + 8자리 ⇒ 24자리
  • yyyyMMddHHmm’TR’ + 8자리 ⇒ 22자리