Guaranted-order-of-Messages

1. 실시간 분산 채팅 시스템의 메시지 순서 보장 전략

• 이 문서는 실시간 분산 채팅 시스템에서 메시지 순서를 보장하기 위한 전략을 다룹니다.

2. 메시지 순서 유지가 어려운 이유

2. 메시지 순서의 기준 비교

• 메시지의 정렬 키로 무엇을 사용할지에 따라 동일한 순서 보장의 용이성과 구현 난이도가 달라집니다.
• 여기서는 메시지의 정렬 키로 사용할 수 있는 몇 가지 방법을 비교합니다.
• 어떤 기준이든 중요한 것은, 그 키가 충돌 없이 단조 증가하도록 관리하고, 모든 참여자에게 동일하게 적용되어야 한다는 점입니다.

2.1 타임스탬프

• 각 메시지를 서버에 도착한 시간이나 DB에 기록된 시간으로 정렬하는 방법입니다.

2.1.1 장점

• 장점은 직관적이고 추가 메타데이터가 거의 필요 없다는 점입니다.
• 한편 수신 시각은 메시지의 실제 전송 시각과 유사하므로 사용자 입장에서 "이 메시지가 언제 왔는가"를 알 수 있다는 장점이 있습니다
  • 이는 UI 표시에 활용하고, 정렬은 다른 키로 하는 식으로 분리하는 것이 권장됩니다.

2.1.1 한계

• 분산 시스템에서 서버들 간 시각 싱크가 완벽하지 않으면 순서가 어긋날 수 있습니다.
  • 예를 들어 서버 A가 B보다 5ms 시계가 빨라 A에서 나중에 온 메시지가 B의 조금 먼저 온 메시지보다 시간이 앞설 수 있습니다.
• 단일 서버에서도 두 개의 메시지가 서버 시각 기준 똑같은 타임스탬프를 가질 수도 있고, 이 경우 어느 것을 먼저 보여줄지 모호합니다.
  • 이 경우 결정적 순서를 정할 수 없습니다.
  • 모든 곳에서 타임 스탬프가 동일한 경우 어떻게 정렬할지에 대한 규칙이 필요합니다.
• DST 변경 등으로 시계가 역행하면 문제가 복잡해집니다. 따라서 단순 타임스탬프로는 일관성과 정확성을 담보하기 어렵습니다.

정보

DST는 여름철에 일조 시간을 더 효율적으로 활용하기 위해 시계를 앞당기는 제도입니다. 보통 봄에 시계를 1시간 앞으로 당기고(spring forward), 가을에 1시간 뒤로 돌립니다(fall back). 가을에 시계를 뒤로 돌릴 때, 같은 시간대가 하루에 두 번 발생합니다.

2.2 메시지 ID 기반 정렬

• 메시지마다 고유 ID (예: UUID, Snowflake ID 등)를 생성하여 그 ID의 크기 또는 순서로 정렬하는 방법입니다.
• 현재 메시지 정렬을 위해 UUID v6(시간 기반 UUID)을 사용하고 있지만, 이것만으로 절대적인 순서 보장은 어렵습니다.
• UUID v6는 동일한 노드(시스템)에서 생성될 때 완전한 단조 증가를 보장하도록 설계되었습니다.
• 시간 기반 필드가 가장 중요한 비트에 위치하고, 클럭 시퀀스가 그 다음으로 중요한 비트에 위치합니다.
• 같은 시스템 내에서는 UUID v6는 생성 시간에 따라 정렬되며, 동일한 시간에 생성된 경우 클럭 시퀀스 번호에 따라 정렬됩니다.
• 다만, 다음과 같은 제한 사항이 있습니다.
  • 서로 다른 시스템에서 생성된 UUID v6 간에는 완전한 단조성을 보장할 수 없습니다. 시스템 시계가 다를 수 있기 때문입니다.
  • 시스템 시계가 뒤로 조정된 경우(예: NTP 조정) 단조성이 깨질 수 있습니다.
• 즉 분산 환경에서 UUID v6를 사용하더라도, 메시지 순서를 보장하기 위해서는 추가적인 조치가 필요합니다.

2.2.1 장점

• 분산 환경에서 유일성을 유지하면서 대략적인 전송 순서대로 증가한다는 장점이 있습니다.
• 별도의 중앙 시퀀스 서버 없이도 각 서버에서 독립적으로 메시지를 생성할 수 있습니다.
• 시간 기반 ID는 준수한 성능과 분산 특성으로 많은 시스템에서 쓰이고, 채팅에서도 특별한 충돌 상황만 없다면 잘 동작합니다.
  • 채팅 애플리케이션에서는 나노초 단위의 정확한 메시지 발생 순서는 사용자 경험에 큰 영향을 미치지 않습니다.
  • 모든 클라이언트에서 UUID로 정렬하면 항상 동일한 순서가 나옵니다.
  • 대부분의 경우 시간적으로 먼저 발생한 메시지가 먼저 표시됩니다.

2.2.2 한계

• 완벽한 단조 증가 보장 없음: UUID v6 등의 시간 기반 UUID도 완벽히 증가하지 않을 수 있어, 동시 생성 시 메시지 순서가 역전될 가능성이 있습니다.
• 시계 동기화 이슈: 분산 서버들의 시스템 시계 불일치로 인해 UUID 생성 시각의 상대적 크기가 실제 발생 순서와 다를 수 있습니다.
• 메시지 누락 감지 불가
  • 클라이언트는 UUID를 기반으로 한 메시지를 받았을 때, 이전에 어떤 메시지들이 있어야 하는지 알 방법이 없습니다
  • 일련번호 방식이라면 "3 다음에 4"라는 연속성이 명확하여 메시지 3이 누락되었는지 즉시 판단할 수 있습니다.
  • UUID는 다음/이전 값을 예측할 수 없는 구조이므로 중간에 누락된 메시지가 있는지 감지할 수 없습니다.
• 연속적 시퀀스 식별 불가: 메시지 정렬에는 사용할 수 있으나 순차적 전달 보장에는 부적합합니다.
  • 일련번호 방식에서는 클라이언트가 4번 메시지를 받았을 때 바로 이전 3번 메시지 처리 여부를 확인하고, 누락된 경우 4번 메시지를 버퍼링하며 3번을 기다릴 수 있습니다.
  • 그러나 UUID는 다음/이전 값을 예측할 수 없는 구조이므로, 클라이언트는 어떤 메시지가 누락되었는지 식별할 수 없어 이러한 순차적 버퍼링 메커니즘을 구현할 수 없습니다.
  • 따라서 메시지의 순서는 정렬할 수 있지만, 중간 메시지 누락 여부를 감지하고 순차적 전달을 보장하는 데에는 추가적인 메커니즘이 필요합니다.

2.3 일련번호

• 중앙 집중식 시퀀스 생성기를 사용하여 증분값을 정렬 기준으로 삼는 방법입니다.
• 이 경우 각 메시지에는 예를 들어 전역적으로 증가하는 64비트 정수 ID가 붙거나, 최소한 방 내에서 증가하는 번호가 붙습니다.
• DB라면 AUTO_INCREMENT 기본키를 활용해 메시지 ID를 증가시키는 것으로 순서를 보장할 수 있습니다.
• 이 값은 절대적인 순서를 나타내므로, 이것으로 정렬하면 모든 클라이언트가 완전히 동일한 순서를 보게 됩니다.

2.3.1 장점

• 장점은 논리적으로 깔끔한 순서 보장으로, 설계 개념이 단순합니다.
• 또한 클라이언트 입장에서도 번호가 쭉 증가하는 것을 보면 메시지 순서를 쉽게 이해할 수 있습니다.

2.3.2 한계

• 단점은 분산 환경에서 그 번호를 생성/동기화하는 비용입니다.
• 이 방식은 가장 단순하고 직관적으로 완벽한 총순서를 제공하지만 단일 장애점(SPOF)이나 성능 병목이 될 수 있습니다.
• 중앙 DB에 넣는 방식은 트랜잭션 부담이 있고, Redis 같은 인메모리 카운터도 결국 싱글 노드가 처리하므로 확장성의 한계가 있습니다.
• 여러 서버가 있는 경우 이 시퀀스 동기화를 위해 분산 락이나 리더 선출(예: Raft) 같은 메커니즘이 필요하여 복잡성이 올라갑니다.
  • Raft와 Paxos는 분산 시스템에서 합의(consensus) 문제를 해결하기 위한 알고리즘입니다.
  • 이 두 알고리즘은 네트워크나 노드의 장애가 발생하더라도 여러 노드가 동일한 상태를 유지하도록 보장합니다.
• 지역적 순서 번호 생성기에 대해서 알아보기
  • 메시지의 순서는 같은 채팅방 내에서만 보장되므로, 각 채팅방마다 지역적 시퀀스 번호를 부여하는 방법도 있습니다.

2.4 비교

• 타임스탬프
  • 장점: 직관적이고 추가 메타데이터가 거의 필요 없음
  • 단점: 분산 시스템에서 시각 싱크가 완벽하지 않으면 순서가 어긋날 수 있음, 동시 메시지 구분 어려움
• 메시지 ID 기반 정렬
  • 장점: 분산 환경에서 유일성을 유지하면서 대략적인 전송 순서대로 증가
  • 단점: 완벽한 단조 증가 보장 없음, 시계 동기화 이슈, 메시지 누락 감지 불가
• 일련번호
  • 장점: 논리적으로 깔끔한 순서 보장, 설계 개념이 단순
  • 단점: 분산 환경에서 번호 생성/동기화 비용, 단일 장애점(SPOF) 및 성능 병목 가능성

3. 실시간성과 메세지의 순서

• 실시간성(저지연)과 순서 일관성(정확한 총순서)은 때로 상충하는 목표입니다.
• 완벽한 순서 동기화를 추구하다 보면 자연히 대기 시간(latency)이 늘어날 수밖에 없습니다

3.1 순서 보장

• 모든 메시지가 전역적으로 순서가 맞게 도달하도록 하려면, 가장 단순하게는 느린 메시지를 기다려야 합니다.
• 예를 들어 위에서 말한 버퍼링을 적극 활용하면, 네트워크나 처리 지연으로 늦게 온 메시지도 제자리를 찾을 때까지 다른 메시지 출력을 늦춤으로써 일관된 순서를 보여줄 수 있습니다.
• 그러나 이 경우 사용자 입장에서 어떤 메시지는 분명 전송되었는데 상대방 채팅창에 몇 초 후에 나타나는 현상을 볼 수도 있습니다.
• 이는 실시간성 저하로 이어져 대화 흐름에 지장을 줄 수 있습니다.

3. 단일 사용자 연속 메시지의 순서 보장

• 한 사용자가 연달아 여러 메시지를 보낼 때, 사용자가 보낸 순서 그대로 모든 사람이 보게 해야 합니다.
• 예를 들어 사용자가 안녕을 보내고 곧바로 하세요를 보냈다면, 두 메시지는 반드시 순서대로 보여야 합니다.
• 이를 보장하기 위한 전략은 다음과 같습니다.

3.1 클라이언트 시퀀스 번호 부여

• 각 사용자가 보낸 메시지에 클라이언트가 로컬 연속 번호를 붙여 서버에 전달하는 방법입니다.
• 예를 들어 클라이언트가 메시지를 보낼 때 seq: 1, 다음 메시지 seq: 2 이런 식으로 번호를 매겨 보내는 것입니다.
• 서버는 같은 사용자의 메시지라면 이 시퀀스를 참고하여 혹시 순서가 뒤섞였을 경우 재정렬할 수 있습니다.
• 물론 악의적이거나 버그있는 클라이언트를 신뢰해야 하는 문제가 있어, 필요한 경우 서버에서 사용자별 seq 검증이 필요합니다.

3.2 Lamport 논리 시계 적용

• Leslie Lamport의 논리 시계(Lamport Clock)를 이용하면, 동일 프로세스 내 이벤트 순서를 자동으로 반영할 수 있습니다.
• Lamport 시계에서는 각 프로세스(여기서는 클라이언트)가 자신의 논리 시간을 가지고 있다가 메시지 전송 시 증가시켜 타임스탬프를 붙입니다.
• 동일 클라이언트에서 보낸 연속 메시지라면 Lamport 타임스탬프가 자연스럽게 이전 메시지보다 큰 값을 갖게 되므로 순서 비교가 가능합니다.

3.3 선택

• 일반적으로 한 사용자가 보낸 순서는 해당 사용자가 가장 잘 알기 때문에, 클라이언트에 시퀀스 부여 로직을 두고 서버는 검증/조정만 하는 방식을 많이 택합니다.

4. 단일 채팅방 내 메시지 순서 보장

• 여러 사용자가 동시에 또는 빠르게 번갈아 메시지를 보낼 경우, 전역적으로 일관된 하나의 순서를 결정해야 합니다.

4.1 서버 전역 시퀀스 번호 부여

• 모든 메시지에 대해 중앙에서 일련번호를 발급하는 방법입니다.
• 중앙 메시지 생성기가 전역 시퀀서 역할을 하여 메시지가 생성될 때마다 증가하는 전역 메시지 번호를 할당합니다.
• 이렇게 하면 숫자가 작은 메시지가 먼저 발생한 것이 되므로, 모든 클라이언트는 이 번호로 정렬하면 동일한 순서를 보게 됩니다.
• 구현 예시
  • Redis의 원자적 INCR을 이용해 room:123:message_seq 키를 두고 매 메시지마다 증가시켜 얻은 번호를 부여합니다.
  • 관계형 DB 시퀀스/AutoIncrement 컬럼을 이용해 메시지 ID를 부여합니다.
• 이 방식은 가장 단순하고 직관적으로 완벽한 총순서를 제공하지만 단일 장애점(SPOF)이나 성능 병목이 될 수 있습니다.
• 여러 서버가 있는 경우 이 시퀀스 동기화를 위해 분산 락이나 리더 선출(예: Raft) 같은 메커니즘이 필요하여 복잡성이 올라갑니다.
• 지역적 순서 번호 생성기에 대해서 알아보기
  • 메시지의 순서는 같은 채팅방 내에서만 보장되므로, 각 채팅방마다 지역적 시퀀스 번호를 부여하는 방법도 있습니다.

4.2 Lamport 논리 시계 (분산 논리 시계)

• Lamport 시계는 분산 시스템에서 원인-결과 관계(causal order)를 반영하여 부분 순서를 전체 순서로 확장할 수 있도록 합니다
• 각 메시지에 Lamport 타임스탬프를 붙이고, 타임스탬프가 작은 메시지를 먼저 처리하면 모든 노드에서 인과관계를 해치지 않는 총순서를 얻을 수 있습니다.
• 단, Lamport 시계만으로는 동시에 발생한(concurrent) 두 이벤트의 순서는 결정되지 않기 때문에, 일반적으로 타이브레이커(tie-breaker)를 둬야 합니다.
• 예를 들어 "Lamport 시계 값이 같다면 송신자 ID를 비교한다"와 같은 추가 규칙을 정하면 완전한 순서를 얻을 수 있습니다.
• Lamport 시계 방식은 비교적 구현이 단순하고 각 메시지에 숫자 하나를 붙이는 정도의 오버헤드로도 전역 정렬을 달성할 수 있다는 장점이 있습니다.
• 그러나 논리 시간이 실제 시간과 무관하기 때문에 사용자에게 "메시지가 도착한 실제 시각"의 감각을 주지는 못합니다.

4.3 Vector Clock

• 벡터 클럭은 각 노드(프로세스)마다 모든 노드에 대한 시간 벡터를 유지해, 메시지 간 선후 관계를 정교하게 파악합니다
• 이를 이용하면 어떤 메시지들이 **동시에 발생(서로 인과관계 없음)**했는지 검출할 수 있지만, 벡터 시계 그 자체로 총순서를 직접 부여하지는 않습니다.
• 벡터 값끼리 비교하여 **한쪽이 전체적으로 작다(crd)**면 그 순서를 정할 수 있지만, 동시에 발생한 경우 벡터 비교로는 동등하다고 나오므로 별도 처리가 필요합니다.
• 또한 노드 수가 N이면 시간 벡터 길이가 N이어서, **규모가 큰 채팅(노드 많음)**에서는 메시지마다 긴 벡터를 전송해야 하는 부담이 있습니다.
• 따라서 벡터 시계는 동시성 여부 판단에는 유용하나, 채팅 메시지의 실시간 총순서 결정에는 비효율적입니다.

4.4 선택

• 정리하면, 여러 사용자의 전역 메시지 순서를 위해서는 전역 일련번호 부여가 가장 확실하지만 비용이 있습니다.
• 논리 시계(Lamport)는 간단하면서 인과는 보장하나 동시 이벤트는 임의 순서를 정해야 합니다.
• 벡터 시계는 동시성 파악에는 좋으나 구현 부담이 큽니다.
• 현실 시스템에서는 전역 시퀀스 부여 또는 Lamport 시계 + 노드ID 타이브레이크 정도로도 충분한 경우가 많습니다.
• 여기서는 전역 시퀀스 부여 방식을 채택합니다.

5. 모든 클라이언트에서 동일한 메시지 순서 보장

5.1 전역 메시지 시퀀스 번호 부여

• 위의 전역 시퀀싱을 실제로 적용하면, 각 메시지에 순차 번호(id)가 붙어 모든 클라이언트가 이를 기준으로 정렬할 수 있습니다.
• 실제 구현에서는 각 방마다 지역적 시퀀스를 사용하는 방법도 있습니다.
• 예를 들어 Redis의 INCR을 이용해 각 방마다 메시지 시퀀스를 관리하고, 클라이언트는 이 번호로 정렬하여 보여주면 됩니다.

5.2

참고

• https://ably.com/blog/chat-architecture-reliable-message-ordering#:~:text=messages%20arrive%20out%20of%20sequence%2C,a%20confusing%20and%20fragmented%20experience