fractional-indexing: 드래그 앤 드롭 정렬 구현과 인덱스 충돌 최적화

정렬 가능한 리스트의 인덱스 충돌 피하기

정수 인덱스의 한계

드래그 앤 드롭으로 순서를 바꿀 수 있는 리스트를 구현해본 적 있으시죠. 보통은 이렇게 저장합니다.

[
  { "id": "a", "order": 1 },
  { "id": "b", "order": 2 },
  { "id": "c", "order": 3 }
]

b를 맨 앞으로 옮기면 어떻게 될까요? b는 0이 되고, a는 여전히 1이니까 괜찮아 보입니다. 그런데 a와 b 사이에 새 아이템을 끼워 넣으려면 a를 2로, c를 3으로 밀어야 하죠. 즉, 하나를 바꾸면 나머지도 함께 업데이트해야 합니다.

협업 툴처럼 여러 사용자가 동시에 조작하는 환경에서는 이 구조가 충돌을 유발하기 쉽습니다. 같은 구간을 두 명이 동시에 수정하면, 누가 먼저 썼는지에 따라 순서가 꼬이거나 대량 업데이트 충돌이 발생할 수 있기 때문입니다.

fractional-indexing이란

David Greenspan이 Implementing Fractional Indexing에서 소개한 방식입니다. 아이디어 자체는 단순합니다. 순서를 정수 대신 정렬 가능한 문자열 키로 표현하는 것입니다.

[
  { "id": "a", "order": "a0" },
  { "id": "b", "order": "a1" },
  { "id": "c", "order": "a2" }
]

a1과 a2 사이에 아이템을 넣고 싶다면? 둘의 중간값인 a1V 같은 키를 부여하면 됩니다. 나머지는 그대로입니다.

Figma가 멀티플레이어 편집에서 실제로 이 방식을 씁니다. 자식 노드의 순서를 관리할 때 fractional indexing을 채택했고, 순서 변경 시 해당 노드 하나만 업데이트하면 되는 구조이죠.

라이브러리 사용법

JavaScript에는 fractional-indexing 패키지가 있습니다.

npm install fractional-indexing

import { generateKeyBetween, generateNKeysBetween } from 'fractional-indexing';

// 첫 번째 키 생성
const first = generateKeyBetween(null, null);
// → 'a0'

// 맨 앞에 삽입
const zeroth = generateKeyBetween(null, first);
// → 'Zz'

// 맨 뒤에 삽입
const second = generateKeyBetween(first, null);
// → 'a1'

// 두 키 사이에 새 키 생성
const third = generateKeyBetween(second, null); // 'a2'
const mid = generateKeyBetween(second, third);
// → 'a1V'

// 여러 개 한 번에
const keys = generateNKeysBetween('a0', 'a2', 2);
// → ['a0G', 'a0V']

DB에는 이 키를 문자열로 저장하고, 정렬할 때 lexicographic order로 ORDER BY 하면 됩니다. 알파벳 순서가 곧 의도한 순서와 일치하도록 설계된 구조이기 때문입니다.

다른 정렬 관리 방식들

fractional-indexing 말고도 몇 가지 접근법이 있습니다. 각각 트레이드오프가 있습니다.

정수 간격 방식 (gap strategy)

가장 단순한 방법입니다. 처음부터 간격을 넉넉하게 줍니다.

[
  { "id": "a", "order": 1000 },
  { "id": "b", "order": 2000 },
  { "id": "c", "order": 3000 }
]

a와 b 사이에 끼우려면 order: 1500을 주면 되죠. 단순하고 빠릅니다. 다만 간격이 소진되면 결국 reindex가 필요합니다. 삽입이 반복되다 보면 1500 → 1250 → 1375 → ... 식으로 결국 충돌이 생기는 것은 시간문제입니다.

timestamp 방식

삽입 시각을 order로 쓰는 방식입니다.

const item = {
  id: 'a',
  order: Date.now(), // 1700000001000
};

구현이 제일 쉽습니다. 그런데 동시에 두 클라이언트가 같은 시각에 삽입하면 순서가 애매해집니다. 단일 사용자 앱이라면 충분하지만, 협업 환경에서는 신뢰하기 어렵습니다.

linked list 방식

각 아이템이 다음 아이템의 id를 가리키는 구조입니다.

[
  { "id": "a", "next": "b" },
  { "id": "b", "next": "c" },
  { "id": "c", "next": null }
]

삽입 시 주변 노드만 업데이트하면 되니 변경 범위가 작습니다. 다만 전체 순서를 읽으려면 traversal이 필요하고, DB에서 ORDER BY 한 방에 안 된다는 게 단점입니다. 순서를 자주 읽는 서비스라면 쿼리 비용이 눈에 띄게 커질 수 있습니다.

결국 선택 기준

정렬이 자주 발생하거나 여러 사용자가 동시에 조작하는 환경이라면 fractional-indexing이 사실상 표준에 가깝습니다. 단순한 단일 사용자 앱이라면 정수 간격 방식으로도 충분합니다.

주의할 점

키가 무한정 길어지는 경우가 생길 수 있습니다. 동일한 두 키 사이에서 계속 새 키를 생성하면 문자열이 점점 길어지기 때문입니다. 이를 보통 rebalancing이라고 부르는데, 주기적으로 전체 순서를 새로운 키로 다시 할당해주는 작업이 필요합니다. 자주 발생하진 않지만, 장기 운영 서비스라면 미리 고려해두는 것이 좋습니다.

또 하나는 정렬 기준을 문자열 비교로 일관되게 유지해야 한다는 점입니다. DB, 서버, 클라이언트가 서로 다른 비교 방식을 쓰면 순서가 어긋날 수 있으니, 저장 형식과 정렬 규칙을 처음부터 명확히 맞춰두는 편이 좋습니다.

마치며

정수 인덱스로 순서를 관리하다 보면 언젠가는 벽에 부딪히게 됩니다. fractional-indexing은 그 문제를 꽤 우아하게 해결해주는 방식이죠. 특히 실시간 협업이나 낙관적 업데이트가 필요한 상황이라면 한 번쯤 고려해볼 만합니다.

Refs

• fractional-indexing - npm
• Implementing Fractional Indexing - David Greenspan
• Figma: Realtime Editing of Ordered Sequences
• Figma: How Figma's multiplayer technology works