마인드맵에 Tree 자료구조가 적합하다고 생각되어서 Tree 자료구조에 대해서 작업기반 CRDT를 적용하려고 했다.

기본적인 구조

crdt 그림.png

CRDT 내부에는 마인드맵에 사용될 Tree 인스턴스가 있고, CRDT는 Tree의 메소드를 사용해서 Tree를 조작하는 구조로 되어있다. Tree는 일반적인 트리와 비슷하게 구현되어 있다.

CRDT의 구현

CRDT 구현의 주요한 부분은 2가지가 있다.

  1. Operation
  2. Clock

Operation

CRDT는 Operation을 주고 받으면서도 충돌이 일어나지 않도록 한다.

operation.png

동기화가 일어났을 때, 모든 Tree들은 같은 상태를 가지고 있어야한다. 이 과정은 Operation 내부에 가지고 있는 Clock을 가지고 이루어진다. Clock의 비교를 통해서 각 Operation들은 모든 트리에서 정해진 순서를 가지게 된다.

따라서 각 작업들은 동기화되는 순간에 정해진 순서를 만들기 위해서 기존에 적용되었던 작업들이 되돌려질 수 있도록 해야 한다. 각 작업들에 대해서 실행(do), 되돌리기(undo), 다시하기(redo) 동작을 구현하도록 했다.

export class OperationAdd<T> extends Operation<T> {
  description: T;
  parentId: string;

  constructor(input: OperationAddInput<T>) {
    super('add', input.id, input.clock);
    this.description = input.description;
    this.parentId = input.parentId;
  }

  doOperation(tree: Tree<T>): OperationLog<T> {
    tree.addNode(this.id, this.parentId, this.description);
    return { operation: this };
  }

  undoOperation(tree: Tree<T>, log: OperationLog<T>): void {
    tree.removeNode(log.operation.id);
  }

  redoOperation(tree: Tree<T>, log: OperationLog<T>): OperationLog<T> {
    tree.attachNode(log.operation.id, this.parentId);
    return { operation: this };
  }
}

Clock

Clock간의 비교는 counter 프로퍼티로 비교한다. 동시에 생성되는 등 여러 이유로 같은 counter값으로 생성되었을 때는 id값으로 비교하도록 한다. id값은 트리가 가지고 있는 id이다.

export class Clock {
  id: string;
  counter: number;

	compare(remoteClock: Clock): COMPARE {
    if (this.counter > remoteClock.counter) return COMPARE.GREATER;
    if (this.counter === remoteClock.counter && this.id > remoteClock.id) {
      return COMPARE.GREATER;
    }
    return COMPARE.LESS;
  }
}

왜 timestamp가 아니라 counter로 비교할까?

처음 만들 때는 counter가 아니라 timestamp를 통해서 비교하면 되지 않을까? 라고 생각해서 timestamp로 처리를 했었다. crdt구현하고 timestamp가 아니라 counter로 처리하는 이유를 알아보니 로컬 시간이 바뀌면 timestamp도 바뀌게 된다. 따라서 글로벌 시계와 동기화되지 않은 기기와 통신하면 작업의 순서가 제대로 이루어지지 않게 된다.

참고자료