1차 시도: 배열
직접 구현을 시도하며 가장 먼저 고려한 자료구조는 배열이었다.
문자열은 일렬로 나열된 글자들이므로 가장 먼저 떠오르는 배열을 사용하기로 했다.
index의 위치에 단순히 삽입하려 시도했고, 만약 index가 같다면 time을 기준으로 정렬하도록 했다.
(나중에 생성된 글자가 같은 index에서 더 앞에 오도록)
만약, 모든 조건이 같다면 (index가 같고 Date.now()를 통해 얻는 ms 단위의 시간조차 같은 경우) 사용자의 id를 기준으로 정렬하도록 했다.
(사용자의 id는 그때그때 다르지만 서로 다른 클라이언트에서 각각 병합을 수행해도 같은 결과가 나와야 했기 때문에 최후의 수단으로 활용)
index는 textarea 태그에서 이벤트를 감지하여 커서의 위치를 기반으로 파악했다.
위의 기본 내용을 토대로 코드를 작성해보자.
interface CRDTToken {
index: number;
letter: string;
time: number;
id: string;
}
interface CRDTRemoteToken extends CRDTToken {
type: 'insert' | 'delete';
}
interface CRDTDeleteToken {
type: 'delete';
index: number;
length: number;
}우선 각 글자의 정보를 담고 있는 토큰을 생성했다.
이후, 다른 피어에게 전송할 CRDTRemoteToken을 생성하고 삭제되는 경우에 사용할 CRDTDeleteToken을 생성했다.
export default class CRDT {
private CRDTTokens: CRDTToken[];
private id: string;
constructor(id: string) {
this.CRDTTokens = [];
this.id = id;
}
localInsert(selectionStart: number, letter: string, time: number): CRDTRemoteToken {
const result = { index: selectionStart, letter, time, id: this.id };
this.CRDTTokens.splice(selectionStart - 1, 0, result);
console.log(this.CRDTTokens);
return { type: 'insert', ...result };
}
localDelete(selectionStart: number, length: number): CRDTDeleteToken {
this.CRDTTokens.splice(selectionStart, length);
console.log(this.CRDTTokens);
return { type: 'delete', index: selectionStart, length };
}
remoteInsert(remoteToken: CRDTToken) {
this.CRDTTokens.splice(remoteToken.index - 1, 0, remoteToken);
this.CRDTTokens.sort((a, b) => {
if (a.index !== b.index) return a.index - b.index; // index 기준으로 오름차순 정렬
else if (a.time !== b.time) return b.time - a.time; // time 기준으로 오름차순 정렬
else return a.id.localeCompare(b.id); // id 기준으로 오름차순 정렬
});
console.log(this.CRDTTokens);
}
remoteDelete(remoteToken: CRDTDeleteToken) {
this.CRDTTokens.splice(remoteToken.index, remoteToken.length);
console.log(this.CRDTTokens);
}
toString() {
return this.CRDTTokens.reduce((text, token) => text + token.letter, '');
}
}(해당 코드는 한 글자가 입력되는 경우만 다루고 있다)
결과를 보면 의도한 대로 잘 작동하는 것으로 보인다.
하지만, 문자열 중간에 새로운 문자를 삽입하는 경우 글자가 밀리게 되는 문제가 발생했다.
- 로컬(0번 인덱스는 캡처 실수로 인한 누락):
print<test>(1234)
[
(...),
{
"index": 6,
"letter": "<",
"time": 1700208782900,
"id": "123"
},
{
"index": 7,
"letter": "t",
"time": 1700208783516,
"id": "123"
},
{
"index": 8,
"letter": "e",
"time": 1700208783800,
"id": "123"
},
{
"index": 9,
"letter": "s",
"time": 1700208784113,
"id": "123"
},
{
"index": 10,
"letter": "t",
"time": 1700208784278,
"id": "123"
},
{
"index": 11,
"letter": ">",
"time": 1700208784669,
"id": "123"
},
{
"index": 6,
"letter": "(",
"time": 1700208628515,
"id": "123"
},
{
"index": 7,
"letter": "1",
"time": 1700208628859,
"id": "123"
},
{
"index": 8,
"letter": "2",
"time": 1700208628941,
"id": "123"
},
{
"index": 9,
"letter": "3",
"time": 1700208629014,
"id": "123"
},
{
"index": 10,
"letter": "4",
"time": 1700208629177,
"id": "123"
},
{
"index": 11,
"letter": ")",
"time": 1700208629399,
"id": "123"
}
]- 원격:
print<(t1e2s3t4>)
[
(...),
{
"index": 6,
"letter": "<",
"time": 1700208782900,
"id": "123"
},
{
"index": 6,
"letter": "(",
"time": 1700208628515,
"id": "123"
},
{
"index": 7,
"letter": "t",
"time": 1700208783516,
"id": "123"
},
{
"index": 7,
"letter": "1",
"time": 1700208628859,
"id": "123"
},
{
"index": 8,
"letter": "e",
"time": 1700208783800,
"id": "123"
},
{
"index": 8,
"letter": "2",
"time": 1700208628941,
"id": "123"
},
{
"index": 9,
"letter": "s",
"time": 1700208784113,
"id": "123"
},
{
"index": 9,
"letter": "3",
"time": 1700208629014,
"id": "123"
},
{
"index": 10,
"letter": "t",
"time": 1700208784278,
"id": "123"
},
{
"index": 10,
"letter": "4",
"time": 1700208629177,
"id": "123"
},
{
"index": 11,
"letter": ">",
"time": 1700208784669,
"id": "123"
},
{
"index": 11,
"letter": ")",
"time": 1700208629399,
"id": "123"
}
]위의 사진에서 볼 수 있듯이 print(1234)에서 print<test>(1234)로 수정하는 경우 로컬에서는 잘 되지만 원격에서는 print<(t1e2s3t4>)가 되는 문제가 발생한다.
원인은 단순 인덱스를 사용한 것에 있다.
단순 인덱스를 사용했기 때문에 로컬에서는 6, 7, 8, 9, 10, 11, 6, 7, 8, 9, 10, 11이 되지만 원격에서 병합 및 정렬한 뒤에는 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11이 된다.
현재 코드에서는 <test>를 삽입하는 경우
6번 인덱스에 < 삽입
7번 인덱스에 t 삽입
(...)
11번 인덱스에 > 삽입
위의 과정을 거치기 때문에 최종 결과가 6, 7, 8, 9, 10, 11, 6, 7, 8, 9, 10, 11이 된다.
하지만, 원격에서 병합하는 경우
- index 기준으로 정렬
- time 기준으로 정렬
- id 기준으로 정렬
위의 과정으로 병합하기 때문에 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11이 되는 것이다.
결론
위의 문제를 해결할 수 있는 방법은 전체 요소에 대해 다시 index를 부여하는 것이 있을 것 같다.
print(1234)에서 print<test>(1234)가 된다면 삽입 이후 index를 다시 부여한 뒤 (p(0) ~ )(16)) 그 결과를 원격으로 전송하는 것이다.
위의 방법대로 전체 요소에 대해 index를 다시 부여하게 된다면 결국 하는 비효율적인 작업이 요구되었다.
이것은 배열의 장점이 사라진 것으로 판단되며 다음 시도에서는 다른 자료 구조를 사용할 수 있을 것이다.
