전체 글

[CRDT] LSEQ 만들기

참고한 코드https://github.com/Chat-Wane/LSEQTree/tree/masterhttps://github.com/nkohari/kseq/tree/master 아주 간단한 기능을 구현할 때 최소한으로 필요한 메소드만 만들어가는 방식으로 할 것이다.  1. 최소값, 최대값으로 초기화하는 것부터 하기우선 LSeqTree, LSeqNode 클래스부터 만들자. @Getterpublic class LSeqTree { private int boundary = 10; private String siteId; private LSeqNode root; public LSeqTree(String siteId) { this.siteId = siteId; this..

[CRDT] LSEQ: 분산 협업 편집에서 시퀀스를 위한 적응적 구조 번역

원문 링크 1. 소개이 논문에서는 선, 단어, 문자와 같은 기본 요소의 순서를 구현하는 것을 시퀀스 CRDT라고 부른다. 시퀀스 CRDT는 삽입 횟수에 따라 선형적인 공간복잡도를 갖는다. 따라서 편집 동작에 크게 의존한다. 일부 편집 시나리오는 영구적인 성능 저하로 이어지기도 한다. 요소의 전체 순서를 유지하기 위해 구조의 각 기본 요소(문서편집기에서는 문자)에 고유하고 변경 불가능한 식별자가 할당된다. 식별자도 종류가 있는데...고정 크기 식별자 예: WOOT, CT, RGA 등.툼스톤이 있기 때문에 주기적으로 정리하는 고비용 연산 필요.식별자 길이가 고정이니까 식별자 자체 크기는 일정하게 유지됨.하지만 삭제 연산이 많이 발생하면 툼스톤 수가 증가하여 공간 복잡도가 높아짐.가변 크기 식별자 예: Log..

[스프링부트] CRDT 실시간 협업 에디터 만들기 - 실행취소, 오류 개선 등

이번에는 실행취소(Undo)를 구현하고 식별자 길이 문제를 해결해보겠다. 1. 실행취소 구현 - 클라이언트스택을 사용할 것이다. 왜냐하면. 그러게. 당연한 거 ㅏㅇ냐? class Document { constructor() { this.textLines = []; this.undoStack = []; this.MAX_UNDO_STACK_SIZE = 20; } pushUndo(operation, lineIndex, identifier) { this.undoStack.push({operation, lineIndex, identifier}); if (this.undoStack.length > this.MAX_UNDO_STACK_SI..