Fly.io 분산 시스템 챌린지(Maelstrom) 기록-2

#2: Unique ID Generation(https://fly.io/dist-sys/2)

N개의 노드로 이뤄진 클러스터 환경에서 유일한 ID를 생성해내는 챌린지다.

--node-count 3

테스트 실행 시점에 위 옵션을 넣어주면 maelstrom 에서 JVM 프로세스를 노드 개수만큼 띄워준다.

 

유일한 ID를 생성하기 위해서는 로컬에서 CAS를 지원하는 클래스를 사용할 수 있다. (e.g. AtomicLong)

분산 환경에서는 각 노드가 로컬 ID의 변경 이벤트를 공유하지 않기 때문에, ID가 반드시 중복될 수 있다.

 

간단한 해결법은, ID를 어느 노드에서 생성했는지 식별자를 추가해주면 된다.

분산 환경에서 식별자 생성의 대표적인 예로 Snowflake ID를 떠올릴 수 있다.

https://en.wikipedia.org/wiki/Snowflake_ID

Snowflake ID - Wikipedia

 

ID 값을 생성할 때, node의 하위 4비트(해시 충돌이 없다는 가정하에, 2^4개의 노드만큼 tolerant)를 추가해줬다.

long tag = (nodeId.hashCode() & 0xFL) << 60;
long sequence = idGenerator.getAndIncrement() & ((1L << 60) -1);
long id = tag | sequence;
body.put("id", id);

 

 

결과 확인

./maelstrom test -w unique-ids \
--bin run.sh \
--time-limit 30 \
--rate 1000 \
--node-count 3 \
--availability total \
--nemesis partition

# expected
Everything looks good! ヽ(‘ー`)ノ

 

github: https://github.com/bidulgi69/maelstrom-challenge

GitHub - bidulgi69/maelstrom-challenge: https://github.com/jepsen-io/maelstrom, https://fly.io/dist-sys