배열에서 연결리스트로

이전 글에서 블록 기반 마크다운 에디터의 기본적인 구조와 키보드 이벤트 핸들링에 대해 설명했습니다. 이번 글에서는 에디터의 블록 관리 방식을 배열 기반에서 연결 리스트 기반으로 마이그레이션한 과정을 다루고, 그 이유와 함께 마이그레이션을 통해 얻은 장점들을 작성하겠습니다.

왜 변경했을까?

CRDT

협업 편집 환경에서 데이터의 일관성과 충돌 없는 병합을 보장하기 위해 CRDT를 도입하기로 결정했습니다. CRDT는 분산 환경에서 데이터를 병합할 때 충돌을 방지하고 일관성을 유지할 수 있도록 설계된 데이터 구조로 다양한 알고리즘이 있지만 우리가 구현하려는 알고리즘에서는 블록 데이터를 연결리스트 구조로 관리해야 했습니다.

배열 기반의 한계

기존의 배열 기반 구조는 각 블록을 배열의 인덱스를 통해 관리했습니다. 이는 단순한 구현과 빠른 접근성을 제공하지만, 다음과 같은 한계가 존재했습니다.

• 포인터 관리의 복잡성: CRDT가 배열의 인덱스를 기반으로 동작할 경우, 각 블록의 위치가 빈번하게 변경될 수 있어 포인터 관리가 어려울 수 있습니다. 또한 개별 블록에서 위치 인덱스 뿐만이 아니라 prevId , nextId , parentId 등 각각의 포인터 정보를 블록이 생성, 수정, 삭제될때마다 일일이 수정해 줘야 하는 번거로움이 있었습니다.
• 동시성 처리의 어려움: 여러 사용자가 동시에 편집할 때, 배열의 인덱스가 변경되면 충돌이 발생할 가능성이 있습니다.
• 성능 저하: 배열의 중간에 블록을 삽입하거나 삭제할 때마다 인덱스를 재정렬해야 하므로 성능이 저하될 수 있습니다.

연결리스트 구조의 장점

• CRDT 연동시 유리함: 서버에서는 블록을 연결리스트 구조로 관리하고, 클라이언트에서 배열구조로 관리한다면 추가적인 데이터 가공 단계가 필요합니다. 하지만 클라이언트에서도 연결리스트 구조로 관리한다면 동일한 데이터 구조로 관리할 수 있어 유지보수에 용이합니다.
• 포인터 관리의 단순화: 각 블록이 이전과 다음 블록을 직접 참조하므로, 블록의 위치 변경 시 포인터만 업데이트하면 되므로 간단하게 블록간 계층구조를 관리할 수 있습니다.
• 동시성 처리 용이: 여러 사용자가 동시에 블록을 삽입하거나 삭제할 때, 포인터를 통해 충돌을 최소화할 수 있습니다.
• 성능 향상: 생각하지 못했던 내용인데, 배열 구조와 달리 블록의 삽입과 삭제가 O(1)에 가까운 시간 복잡도로 처리되어 성능상 이점이 있을것 같습니다.

배열 기반 코드와 연결리스트 기반 코드의 차이점

변경된 부분의 코드만 작성했습니다!

블록 데이터 구조

배열

가장 핵심적인 내용으로, 가장 많이 변경된 부분입니다. 기존의 배열 기반 구조에서는 모든 블록이 배열의 인덱스를 통해 관리되었으나 이는 단순한 구현과 빠른 접근성을 제공하지만, 다음과 같은 한계가 있습니다.