gimmizz
commented
1 year ago Consistent Hashing in AWS DynamoDB
- https://medium.com/@adityashete009/consistent-hashing-amazon-dynamodb-part-1-f5719aff7681
- DynamoDB Partitioning : https://docs.aws.amazon.com/ko_kr/amazondynamodb/latest/developerguide/HowItWorks.Partitions.html
AWS DynamoDB: key-value NoSQL Database- Table 생성 시에는 Partition Key 와 Sort Key 를 지정해주어야 한다.
- DynamoDB Partitioning
- DynamoDB 내부에는 해쉬 함수(Hash Function)가 존재하고, 이 함수는 파티션 키를 입력받고 출력 값으로 데이터를 저장할 파티션을 결정한다.
- Partition Key
- 물리적인 공간인 파티션을 구분하기 위한 키
- 동일한 파티션 키를 지닌 데이터는 물리적으로 가까운 위치에 저장
- 스케일이 아무리 커져도 주소를 알고 있어 데이터를 빠르게 가져올 수 있다
- 때문에 파티션 키로는 일치하는 값만 가져올 수 있고, =, >, < 등과 같은 연산자를 사용하는 범위지정 방식의 검색은 지원하지 않음.
- Sort Key
- 파티션 안에서 데이터를 정렬하기 위한 키
- DynamoDB에서는 Number, Binary, String 타입을 지원
- 단순 정렬이기 때문에 파티션의 사이즈가 커져도 데이터를 빠르게 가져올 수 있다.
- Partition Key 와는 달리 범위지정 방식의 검색을 지원하지만, 정렬 키만 가지고는 검색할 수 없음
- DynamoDB 는 consistent hashing 을 사용한다.
- 아래 그림에서, Token 은 Server 의 positions in the ring 를 뜻한다.
- DynamoDB 는 Virtual Node 개념을 사용한다.
- physical한 노드를 여러개의 논리적인 노드로 나타낸다.
- 책에 나온 대로, 노드의 분포를 균일하게 유지하기 위함. 노드간 간격이 균일해야 노드가 처리하는 부하가 비슷할 것.
- 언제 사용될까?
- Partitioning Algorithm
- DynamoDB에서 get이나 put 요청을 처리하는 노드를 coordinator 노드라고 함.
- 요청하는 key에 따라 coordinator 노드가 달라짐
- 모든 노드는 특정 key 범위를 처리하도록 역할이 지정되어 있으며 이 범위를 정하는 과정이 Partitioning Algorithm
get요청
- Hash Algorithm 을 통해 특정 key 의 포지션/Token 값을 구한다.
- md5 hash 알고리즘을 통해 128bit 로 반환
- 서버의 해시값 (=Token) 을 만날 때까지 시계방향/반시계방향으로 이동, 가장 먼저 도달하는 Token 에 해당하는 서버에 저장되어있을 것
put요청.- 위와 동일한 알고리즘
- 링의 시계방향을 돌며 첫 번째로 마주치는 노드가 바로 coordinator 노드가 된다.
- coordinator 노드는 오브젝트를 write 하고 옆 노드로 복제본을 전송하는 역할 및 클라이언트에게 OK응답을 보내는 역할을 수행
추가 정보
Enoch-Kim
jiyoungjha
matteblack9
How Discord Scaled Elixir to 5,000,000 Concurrent Users:
https://discord.com/blog/how-discord-scaled-elixir-to-5-000-000-concurrent-users (2017년 7월 기재)
처음에는(그룹이 25이하였을 때) 사용자가 guild(internal for a “Discord Server”)에 접근하면 guild publish가 모든 다른 연결된 세션에 이 연결을 알렸다. 그리고 사람들이 큰 스케일 그룹으로 디스코드를 사용하기 시작하면서 더 많은 디스코드 서버를 보유하게 되었다. 그러면서 피크 시간동안에는 프로세스가 메시지 큐를 따라가지 못하게 되고... 특정 시점에 수동으로 개입해서 메세지 생성하는 피쳐를 꺼야했다 (부하 대처를 위해). 그러다 길드 프로세스 내에 hot path를 benchmarking하는 것을 시작했고, 이 툴을 사용해서 뭐가 문제 인지 찾아보고~~ (Erlang 프로세스간 메세지를 보내는게 예상보다 싸지 않았고 프로세스 스케줄링을 위해 사용되는 작업의 비용도 비싸. Erlang프로세스는 단일 스레드여서 작업을 병렬로 실행하려면 샤드를 해야해(힘든일임 다른방법필요))
노드간 메세지 전달 성능을 부스팅하는 것에 관한 블로그 포스트를 보고 영감을 받아서, manifold 탄생.
Message Fanout
Manifold: Fast batch message passing between nodes for Erlang/Elixir.
Manifold는 PIDs의 원격노드로 메세지 전송작업을 분산시켜, 최대
send/2(=관련된 원격 노드 수)만 전송되도록 한다. 이걸 어떻게 하냐면: 원격 노드 별로 PID를 그룹화 -> 각 노드의 Manifold.Partitioner로 전송 -> partitioner가 PID를 일관되게 hash -> 코어 수별로 그룹화 -> child workers에게 전송 -> 실제 프로세스로 전송Fast Access Shared Data
디스코드는 consistent hashing을 사용하는 분산 시스템.
링 형태의 데이터 구조를 만들기 위해 library by Chris Moos via a Erlang C port (process responsible for interfacing with C code) 사용했는데, 디스코드가 확장됨에 따라 사용자가 다시 연결할 때 burst 발생한다는걸 알게되었다. 링 제어를 담담하는 Erlang 프로세스가 바빠져서(hot path) 링에 대한 요청을 따라가지 못하고 전체 시스템에 과부하.
몇가지 조사 끝에 VM기능을 이용하는 모듈인 mochiglobal 발견. 항상 같은 상수 데이터를 리턴하는 함수를 Erlang이 보면, read-only shared heap에 이 데이터를 넣는다.
여기에 일부기능을 추가해서 fastglobal을 만들었다.
Limited Concurrency
거의 5백만 세션 프로세스가 guild_pid조회를 처리하는 프로세스 중 10개(각 길드노드에 하나씩)에 stamp를 시도하고 있다는 새로운 문제 발생. 근본적 문제는 guild 레지스트리에 대한 세션 프로세스 호출이 timeout 발생해서 이 요청들이 큐에 남아있다. backoff후에 요청을 다시 시도하지만 지속적으로 요청이 쌓여서 복구할 수 없는 상태가 된다.
일부 연구끝에 발견 :ets.update_counter/4, ETS키 내부에 있는 숫자에 대해 atomic 조건부 증분 작업을 수행한다. 이것이 이들의 semaphore 라이브러리를 만드는게 기본이되었다.
서비스가 죽는일이 발생해도 세션 서비스는 잘 살아있다!