정의
리스트나 트리에서 항목 순서를 자주 바꾸는데, 여러 사람이 동시에 편집해도 순서가 안 깨지게 하고 싶을 때 쓰는 방식이다. 항목마다 정수 번호(0,1,2…) 대신 정렬되는 문자열 키를 붙이고, "B 다음에 넣어줘"처럼 이웃을 기준으로 삽입한다.
정확히는, Fractional indexing(분수 색인)은 컬렉션 항목마다 lexicographic sort(문자열을 사전순으로 비교) 가능한 문자열 키(position이라 부른다)를 부여하고, 삽입·이동 의도를 "index n번째"가 아니라 이웃 anchor id(after/before — 어느 항목 앞/뒤에 넣을지 가리키는 기준점) 로 표현하는 순서 모델이다. 중간 삽입 시 기존 항목의 키를 바꾸지 않고, 두 키 사이에 새 키만 생성한다.
왜 필요한가
정수 index로 순서를 매기면 이런 문제가 생긴다. (1) 중간에 하나 끼워 넣을 때마다 뒤 항목 번호를 전부 다시 매겨야 하고(renumber), (2) 두 사람이 동시에 "같은 3번 자리에 삽입"하면 충돌하고, (3) 이미 지워진 항목을 기준으로 삼은 뒤늦은 편집(stale patch — 오래되어 유효하지 않은 변경 요청)이 실패한다.
협업 todo 리스트·문서 블록 형제 순서·칸반 카드처럼 순서 변경이 잦고 여러 클라이언트가 동시(concurrent)에 만지는 데이터는, 정수 대신 fractional key + "이웃 기준" 의도 + tie-break(동점 처리 규칙)로 이 세 문제를 피하는 선택을 실무에서 자주 한다.
동작 원리
- 저장 계층: 각 sibling에
position: string(예"a0","a0V"). - 의도 계층: patch
{ after: "block-a", block: newBlock }. - 정렬:
compare(position)lexicographic; 동률이면(clientId, opId)tie-break. - 삽입:
generateKeyBetween(prev, next)— 두 key 사이 문자열 생성. - Rebalance: key 길이가 커지면 같은 순서를 유지한 채 짧은 key로 재할당.
| 문제 | integer index | fractional + anchor |
|---|---|---|
| 중간 insert | O(n) renumber | O(1) new key |
| concurrent insert | index collision | tie-break |
| stale anchor | throw | fallback chain / tail |
실무 적용
Subtree를 다른 parent로 promote/move할 때 nested position을 그대로 reuse하면 새 sibling set에서 sort가 깨질 수 있다 — 새 bounds 사이 position 재할당이 필요하다. offline replay에서 anchor가 삭제되었으면 fallbackAfter[] chain으로 대체 anchor를 찾거나 tail append한다.
트레이드오프
- key 문자열 길이가 시간에 따라 증가 → 주기적 rebalance 필요.
- human-readable order number는 저장하지 않음 — UI ordinal은 render time derive.
- full CRDT보다 가볍지만 server/client merge 정책·tie-break 계약이 필요.
사용하면 안 되는 경우
- 순서가 거의 바뀌지 않고 단일 writer인 작은 설정 배열 — integer index로 충분.
- position key만 있고 anchor fallback 없이 offline을 허용 — stale patch 실패율 급증.
흔한 실수
- patch에 index, storage에 position 혼용 — 의도와 SoT 불일치.
- sort-on-read everywhere — 성능·일관성 문제.
- promote 시 position reuse — sibling sort corruption.
- tie-break 없이 position만 — concurrent insert 비결정적.
관련 개념
- optimistic-outbox-rebase — concurrent patch 수렴
- inverted-index-full-text-search — 다른 종류의 “index”(검색)와 혼동 주의