CRDT 그림판 구현, 그리고 최적화

이전 ‘CRDT, 실시간으로 데이터 일관성을 유지하는 법’ 글에서 CRDT에 대해서 알아보았습니다. CRDT 기술로 여러 실시간 협업 서비스를 만들 수 있습니다. CRDT 관련된 글을 찾던 도중 ‘Building a Collaborative Pixel Art Editor with CRDTs’ 를 보면서 블로그 대문 페이지에 그림판을 만들어 보고 싶었습니다. 기존에는 정적인 이미지를 두었는데, 이를 그림판으로 유동적으로 수정하기도 하고 간이 방명록의 느낌으로 두면 재밌겠다고 생각했습니다. CRDT 기술을 활용해서 그림판을 만든 과정을 차례로 소개하는 시간을 가져보도록 하겠습니다.

먼저, 서비스를 어떻게 설계할 것인가부터 시작했습니다. 현재의 상황을 파악하고 다음과 같은 정리를 할 수 있었습니다.

1. 블로그 대문 페이지에 구현해야하니 NextJS(TypeScript) 위에 코드를 작성해야한다
2. 그림 정보를 저장해야하므로 해당 정보를 저장할 서버가 필요하다
3. 불특정 다수의 사용자한테 그림이 실시간으로 공유되어야 한다
4. CRDT 그림판을 사용함으로써 보안 측면에서나 시스템 측면으로 위험이 없는지 확인이 필요하다 (ex. 그림 데이터로 인한 메모리 초과, 수 많은 사람들의 접속으로 인한 메모리 부족)

2번의 경우, 웹 터미널을 구축할 때 사용한 서버를 활용하기로 했습니다. 3번 같은 경우는 서비스 대상을 ‘설명탕’ 블로그에 접속하는 사용자로 가정했습니다. 따라서 불특정 다수한테 그림판을 제공하고 실시간으로 그림을 보여주기 위해 단방향 통신인 HTTP가 아닌 양방향 통신이 가능한 Socket.IO 기술을 채택했습니다. 마지막으로 4번은 불특정 다수가 마음대로 접근할 수 있는 서비스라 보안 측면으로 위험이 될 수 있는 부분이 있지 않은지 확인해 주었습니다. 예를 들어 비정상적으로 큰 그림 데이터로 인한 서버 메모리 초과라든지, WebSocket 통신 connection이 너무 많이 이루어져 서버 메모리 부족 상태라든지, 그림 그리기 요청이 너무 많아 서버 처리가 힘들다든지 등에 대한 생각을 하면서 코드를 작성하였습니다.

---

4번 같은 경우, 트래픽이 나지 않은 환경에서는 크게 신경 쓰지 않아도 되지만 해당 문제를 생각해 보고 보완하는 게 재미인 거 같습니다.

---

이제 코드를 생각해 보겠습니다. 어느 부분부터 코드로 작성해야할 지 막막했는데 ‘Building a Collaborative Pixel Art Editor with CRDTs’ 글을 작성한 jakelazaroff의 코드가 있어 해당 코드를 뼈대로 잡았습니다. 코드를 NextJS에 맞게 수정 후 사용자 간 통신을 위해 Socket.IO 모듈을 설정하였습니다. 그림판 크기는 64 * 64로 설정하고 검정색 이외의 색을 선택할 수 있도록 palette를 준비하였습니다.

TYPESCRIPT
const CRDT = () => {
    const socket = io(
        process.env.NODE_ENV === 'production' ? `${process.env.CRDT_SOCKET_URL}` : 'http://localhost:3000/crdt',
        {
            transports: ['websocket'],
        }
    );

    const clearCanvas = () => socket.emit('clear');

    useEffect(() => {
        const canvas = canvasRef.current;
        const palette = paletteRef.current;

        if (!canvas || !palette) {
            return;
        }

        const artBoard = { w: 64, h: 64 };
        const editor = new PixelEditor(canvas, artBoard);

        // 그림을 그리면 서버로 그림 정보(state) 전송
        editor.onchange = (state) => socket.emit('write', state);
        // 색상 선택
        palette.oninput = () => {
            const hex = palette.value.substring(1).match(/[\da-f]{2}/g) || [];
            const rgb = hex.map((byte) => parseInt(byte, 16));

            if (rgb.length === 3) {
                editor.color = rgb as RGB;
            }
        };

        // socket 첫 연결 시 state 가져오기
        socket.once('init', (state) => editor.receive(state));
        // 다른 사용자가 그림을 그렸다면 해당 state를 가져오고 merge
        socket.on('merge', (state) => editor.receive(state));
        // 그림판 초기화
        socket.on('clear', () => editor.clear());

        return () => {
            editor.onchange = () => null;
            socket.disconnect();
        };
    }, []);

    ...
}

홈페이지에 접속했을 때 서버로부터 WebSocket 통신으로 그림 정보(state)를 받습니다. 본인이나 다른 사용자가 그림을 그리면 그림 정보를 가져와 merge 합니다. Merge의 로직은 CRDT의 LWW Register를 적용했습니다. LWW Register에 대해 알고 싶으면 이전에 작성했던 글을 참고하면 되겠습니다. 데이터 충돌 없이 그림을 그리기 위해 coord, peer, timestamp, RGB 4개의 데이터를 JSON 형식으로 주고 받았습니다.

• coord
  • 그림 좌표 정보
  • 그림 좌표(x, y)는 number 타입이 아닌 “x,y” string 타입으로 변환 후 사용
• peer
  • 여러 사람들을 구분하기 위한 고유 아이디 값
• timestamp
  • 데이터 충돌을 막기 위한 정보
  • 해당 좌표를 클릭하면 단순히 1이 증가되는 logical clock 형태
• RGB
  • 빨강, 초록, 파랑 값을 number 타입으로 저장

아래는 “seol” 사용자가 (5, 4) 좌표에는 검정색(0, 0, 0)으로 1번 (7, 7) 좌표에는 빨간색(255, 3, 0)으로 2번 점을 찍었을 때의 JSON 예시입니다.

JSON
// coord: [peer, timestamp, RGB]

{
  "5,4": ["seol", 1, [0, 0, 0]],
  "7,7": ["seol", 2, [255, 3, 0]]
}

TYPESCRIPT
type RGB = [number, number, number];
type State = {
  [coord: string]: LWWRegister["state"];
};

/** LWWMap.ts의 일부분 */
export class LWWMap {
  private _data = new Map<string, LWWRegister>();

  /**
   * @param {State} 서버로부터 받은 그림 정보
   */
  merge(state: State) {
    for (const [coord, remote] of Object.entries(state)) {
      // 해당 좌표(coord)에 데이터가 있는지 확인
      const local = this._data.get(coord);

      if (local) {
        // 해당 좌표 데이터가 있다면, merge
        local.merge(remote);
      } else {
        // 해당 좌표 데이터가 없다면, 데이터 추가
        this._data.set(coord, new LWWRegister(coord, remote));
      }
    }
  }
}

/** LWWRegister.ts의 merge 함수 */
export class LWWRegister {
  readonly coord: string;
  state: [peer: string, timestamp: number, value: RGB];

  merge(state: LWWRegister["state"]) {
    const [remotePeer, remoteTimestamp] = state;
    const [localPeer, localTimestamp] = this.state;

    // 서버로부터 받은 timestamp가 local timestamp보다 작으면
    // 우선순위에 밀리기 때문에 해당 데이터는 버린다
    if (localTimestamp > remoteTimestamp) {
      return;
    }

    // 서버로부터 받은 timestamp와 local timestamp가 같으면
    // peer string을 비교하여 값이 큰 값을 기준으로 데이터가 쓰여진다
    if (localTimestamp === remoteTimestamp && localPeer > remotePeer) {
      return;
    }

    this.state = state;
  }
}

---

앞서 언급했듯이 서버와 사용자 간의 양방향 통신을 위해 HTTP 통신이 아닌 WebSocket 통신을 사용했습니다. 사용자의 요청과 응답을 실시간으로 서버와 통신을 해야하니 HTTP 보다 WebSocket 통신이 적절하다고 생각했습니다.

다른 실시간 협업 도구는 통신이 어떻게 이루어지는 궁금했습니다. Notion과 Google Docs에 접속하여 웹 브라우저 네트워크 탭을 확인해 보았는데 제 예상과 달리 HTTP으로만 통신했습니다. 사용자의 요청과 응답을 실시간으로 받아야 할 텐데 HTTP 프로토콜만 쓴다는 게 신기했습니다. 어떻게 HTTP만 가지고 실시간으로 요청과 응답을 받는 건지에 대한 궁금증이 남았습니다.

자세한 기술은 알지 못하였지만, HTTP 연결을 맺고 바로 끊지 않는 방식(Long Polling처럼)이 WebSocket 연결보다 더 효율적인 건지, 서비스 규모가 크다면 수백 개 이상의 WebSocket 연결을 맺는 거보다 HTTP 연결을 맺는 게 더 나은 걸까요? 🤔

---

서버 코드도 알아보도록 하겠습니다. WebSocket 이벤트를 정의하고 그림 정보를 저장할 변수를 선언하여 관리합니다. 홈페이지에 접속하면 WebSocket 연결을 맺는데 혹여나 너무 많은 연결로 인한 메모리 사용으로 서버가 못 버틸 수도 있으니 최대 연결 수를 두었습니다. Socket.IO에서 maximum connection limit 옵션이 없어 별도의 count 변수를 두어 WebSocket 연결하거나 해제할 때 count 값을 조절하였습니다. 따라서 적절한 최대 연결 회수 값을 고민해야 했는데, 한 번에 100명 이상의 사용자가 홈페이지를 보는 경우가 없다고 생각하여 100을 기준으로 로직을 설계하였습니다.

TYPESCRIPT
type RGB = [number, number, number];
type CrdtState = [string, [peer: string, timestamp: number, value: RGB]];

const w = 64,
  h = 64;

export default class CrdtGateway
  implements OnGatewayConnection, OnGatewayDisconnect
{
  private count: number = 0;
  private states: CrdtState = ["", ["", 0, [0, 0, 0]]];

  handleConnection(@ConnectedSocket() socket: Socket) {
    // 최대 WebSocket 연결 수는 100이하로 설정
    if (this.count > 100) {
      Logger.error("[CRDT Socket Connect]: Too many connections");
      socket.disconnect();
      return;
    }

    // WebSocket 연결이 되면 count 변수 값 증가
    this.count++;

    Logger.log(`[CRDT Socket Connect]: ${socket.id} - ${this.count}`);
    // 초기 그림 정보 사용자한테 전달
    socket.emit("init", this.states);
  }

  handleDisconnect(@ConnectedSocket() socket: Socket) {
    // WebSocket 연결 해제가 되면 count 변수 값 감소
    this.count--;
    Logger.log(`[CRDT Socket Disconnect]: ${socket.id}`);
  }

  @SubscribeMessage("write")
  write(@ConnectedSocket() socket: Socket, @MessageBody() state: CrdtState) {
    // 그림 정보 길이가 그림판 길이보다 클 경우 무시
    if (state.data[1].length > w * h) {
      Logger.error("[CRDT Socket Write]: Invalid data");
      return;
    }

    // 그림 정보 업데이트 후 다른 사용자한테 전달
    this.states = state;
    socket.broadcast.emit("merge", state);
  }

  @SubscribeMessage("clear")
  clear(@ConnectedSocket() socket: Socket) {
    this.states = ["", ["", 0, [0, 0, 0]]];

    socket.emit("clear");
    socket.broadcast.emit("clear");
  }
}

---

count 변수로 WebSocket 연결 제한을 두었는데, 만약 사용자로부터 네트워크 지연, 동시성과 같은 이유로 WebSocket 해제 과정이 제대로 이루어지지 않아 count 변수가 업데이트되지 않을 수 있지 않을까요?

자체 테스트와 1개월 이상 운영해 본 결과, 트래픽 요청이 많지 않은 서비스 환경에서는 해당 문제가 발생하지 않았습니다. 만약 이 문제를 보완한다면 명시적으로 추가적인 WebSocket 이벤트나 HTTP 통신으로 연결을 해제한다는 과정을 추가하여 보완할 수 있을 거 같습니다.

---

그림 정보를 관리하는 states 변수에 대해서도 생각해 봐야 합니다. 그림 정보를 변수로 관리한다는 의미는 서버의 메모리에 저장한다는 이야기로, states 값에 따라 자칫 잘못하면 서버가 죽거나 보안 측면으로 위험할 수 있습니다. 이를 방지하기 위해 2가지 장치를 두었습니다.

1. 컨테이너 메모리 자원 제한
2. states 변수 길이 검사

이전에는 단순한 작업을 하는 백엔드 컨테이너 자원 제한의 필요성을 느끼지 못했습니다. 하지만 states 변수 조작 후 요청하여 비정상적인 크기를 가지게 된다거나, WebSocket 연결이 너무 많이 이루어진다던가 등 예상치 못한 방법으로부터 서버 안전성을 지켜야 합니다. 미연의 사고에 방지하고자 컨테이너 메모리 자원을 제한하는 설정을 추가했습니다. Docker Compose를 통해 컨테이너를 관리하는데 deploy.resources.limits 옵션으로 메모리 자원 제한을 설정하였습니다. 메모리 자원 제한 크기는 서버 메모리 크기(1GB)의 반으로 설정하였습니다. 해당 자원으로도 충분히 서비스를 운영할 수 있다고 판단했으며 이 수치는 추후 서비스 상태를 보며 조절할 예정입니다.

YAML
version: "3.5"

services:
  server:
    container_name: smt-server
    image: smt-server:prod
    deploy:
      resources:
        limits:
          memory: 512M

컨테이너 자원 제한으로 서버 전체가 죽는 상황을 방지할 수 있었습니다. 하지만 states 변수에 대한 불안감이 가시지 않았습니다. 혹여나 네트워크 요청 조작 등으로 의도치 않게 크기가 매우 큰 states 값이 넘어올 수 있습니다. 이렇게 되면 서버 메모리 낭비가 되고 불필요한 네트워크 통신 비용이 늘어나게 됩니다. 이를 위해 사용자로부터 받은 그림 정보 길이의 검사를 진행했습니다. 그림판 크기를 가로, 세로 64로 고정한다면 그림 정보 데이터길이는 4096(64 * 64)을 넘지 못합니다. 해당 길이를 넘으면 비정상적인 데이터 판단하고 그림 정보가 업데이트되지 못하도록 설정하였습니다.

---

그림 정보 데이터 길이는 검사했지만 다른 데이터 유효성 검사(ex. peer string length 검사, RGB 값 검사, timestamp 값 검사) 또한 필요합니다. 글에서 소개하지 않았지만 유효성 검사에 필요한 부분을 추가하였습니다.

---

서버 작업까지 완료하면 CRDT와 Socket.IO로 여러 사용자가 실시간으로 데이터 충돌없는 사용할 수 있는 그림판을 만들 수 있습니다. 홈페이지에 새로운 기능을 추가하여 기뻤지만 사용하다보니 하나의 크나큰 문제점을 발견하였습니다. 바로 ‘네트워크 통신 비용’입니다.

처음 홈페이지에 접속했을 때 WebSocket으로 그림 정보를 가져오거나, 그림을 그릴 때마다 서버로 그림 정보를 보낼 때의 네트워크 통신 비용이 무시하지 못했습니다. 네트워크 통신 비용 즉, 그림 정보 JSON 크기가 컸습니다.

8 * 8 그림판 기준으로 8개 점을 찍는데 약 1.5kB 데이터를 사용합니다. 64개 점을 찍으면(드래그 없이 개별적으로) 약 100 kB 데이터를 사용합니다. 연속적으로(드래그로) 64개 점을 그리고 무려 600kB 정도의 데이터를 통신하는 데 사용합니다.

아니, 64개 점을 그리는데 600 kB 크기의 데이터를 쓰다니… 개인적으로 충격으로 다가왔습니다. 그림 정보 크기를 줄이기 위해 다음의 최적화 작업을 진행했습니다.

1. 불필요한 그림 정보 삭제
2. RGB 중복 삭제
3. RGB 정보를 number에서 string으로 변경
4. 동일 좌표의 중복 요청 방지

그림 정보를 담은 JSON 구조를 다시 살펴보겠습니다.

JSON
// coord: [peer, timestamp, RGB]

{
  "5,4": ["seol", 1, [0, 0, 0]],
  "7,7": ["seol", 2, [255, 3, 0]]
}

여러 사용자가 그림판을 쓰지만 대문 페이지의 그림판은 ‘공용’으로 사용자 구분을 할 필요가 없습니다. peer 값이 사용자 구분을 하는 역할을 하는데 peer 변수가 필요 없으니 이 부분을 삭제해 조금이나마 JSON 길이를 줄일 수 있게 됩니다.

만약 같은 검정색(0, 0, 0)으로 그림을 그리게 된다면 아래와 같이 RGB 중복이 생깁니다.

JSON
// coord: [timestamp, RGB]

{
  "1,1": [1, [0, 0, 0]],
  "5,4": [1, [0, 0, 0]],
  "7,7": [2, [255, 3, 0]]
}

RGB 중복을 줄이고자 colors 항목을 만들고 기존 RGB 위치에 color index로 대체하여 중복을 줄였습니다.

JSON
// colors: [RGB]
// data: {
//     coord: [timestamp, colorIndex]
// }

{
  "colors": [
    [0, 0, 0],
    [255, 3, 0]
  ],
  "data": {
    "1,1": [1, 0],
    "5,4": [1, 0],
    "7,7": [2, 1]
  }
}

한 발 더 나아가 [number, number, number]로 표현한 RGB를 color hex code로 바꾸어 string으로 변환하여 관리해 줍니다. number로 RGB를 표현하면 최소 7자리에서 최대 13자리로(bracket, comma 포함) 표현되는 반면 color hex code는 8자리로(double quotes 포함) 고정입니다. 7, 8자리 number RGB를 제외한다면 소소한 길이 이득을 얻을 수 있습니다. “000000”와 같은 color hex code를 “00”으로도 표현할 수 있겠지만 이번 구현에는 제외하도록 하겠습니다.

TEXT
[0, 0, 0] -> "000000"
[255, 3, 0] -> "ff0300"
[255, 255, 255] -> "ffffff"

위의 내용을 정리하면 다음과 같은 JSON을 얻을 수 있습니다.

JSON
// before

{
  "1,1": ["seol", 1, [0, 0, 0]],
  "5,4": ["seol", 1, [0, 0, 0]],
  "7,7": ["seol", 2, [255, 3, 0]]
}

// after

{
  "colors": ["000000", "ff0300"],
  "data": {
    "1,1": [1, 0],
    "5,4": [1, 0],
    "7,7": [2, 1]
  }
}

이를 적용해 보면 8 * 8 그림판 기준 16개 점을 찍으면 6.43 kB에서 3.45 kB로 약 50% 크기가 줄어든 것을 확인할 수 있습니다.

마지막으로 진행한 최적화 작업은 ‘동일 좌표에 대한 중복 요청 방지’입니다. 최적화 작업 중 네트워크 통신 비용을 많이 줄여준 작업입니다. 일반적으로 그림판에 그림을 그릴 때 일일이 좌표를 클릭하기보다는 한 좌표를 기준으로 드래그하여 연속적으로 그립니다. 드래그할 때 한 좌표에 한 번의 통신이 일어나야 하는데 다음 좌표로 넘어가기 전까지 해당 좌표에 클릭 이벤트가 유지되면서 중복으로 서버 통신이 발생하는 문제가 생겼습니다. 이는 비효율적인 네트워크 통신이 일어나며 상당한 비용이 들었습니다. 이를 해결하기 위해 드래그할 때 해당 좌표를 한 번 칠했다면 추가적인 WebSocket 통신이 일어나지 않도록 수정했습니다. 단순한 해결 방법이지만 얻는 이득은 컸습니다. 64 * 64 그림판 기준으로 비슷한 그림을 그렸을 때 크기는 286 kB에서 155 kB로 약 45%, 통신 횟수는 270번에서 141번으로 약 48% 정도를 줄일 수 있었습니다.

앞의 작업을 진행하면서 클라이언트, 서버 코드 또한 이에 맞게 수정하였습니다. 최종적으로 기존과 비교하여 64 * 64 그림판에 그림을 그렸을 때 576 kB에서 116 kB로 약 80% 정도 통신 비용을 줄일 수 있었습니다. 이는 그림 정보가 많을 수록 더욱 효과적일 거라 생각되며 비용 절감에 의미 있는 작업이라 생각합니다. 기존과 대비하여 많은 개선을 이루어냈지만, 여전히 JSON 크기가 크다고 생각합니다. 바뀐 그림 정보만 전달하는 operation-based 방식이나 binary encoding으로 획기적으로 JSON 크기를 줄일 수 있을 거 같습니다. 기회가 된다면 더욱더 크기를 줄여보도록 해보겠습니다.

---

참고 자료

• https://jakelazaroff.com/words/building-a-collaborative-pixel-art-editor-with-crdts/
• https://jakelazaroff.com/words/making-crdts-98-percent-more-efficient/