순서가 있는 데이터를 다뤄야 하는 경우가 존재한다.
예시)
일반적인 흐름은 다음과 같다.
이때, 성능과 동시성을 고려해야 한다.
물론, 데이터와 로직의 특성상 이를 고려하지 않을 수도 있다.
이를 해결할 수 있는 방법들이 존재한다.
데이터를 수정하면?
수정과 동시에 영향을 받은 요소들의 순서를 수정한다.
ID=6인 새 아이템을 1번 위치와 2번 위치 사이에 삽입
변경 전:
1(1) 2(2) 3(3) 4(4) 5(5)(앞에 있는 값이 순서, 괄호 안에 있는 값이 ID)
변경 후:
1(1) 2(6) 3(2) 4(3) 5(4) 6(5)→ ID 6을 새로 넣으면서, 기존 ID 2~5의 순서 값을 전부 +1씩 UPDATE 해야 한다.
ID 자체는 불변이지만, 순서 값은 영향받은 모든 행이 갱신된다.
일반적인 방법으로 이해하기 쉽다.
순서가 정수이며, 그 순서대로 정렬이 보장된다.
1000개 중 맨 앞 INSERT 시, 999개 UPDATE
→ UPDATE로 인한 lock 시간 및 B-tree 인덱스 재조정이 발생한다.
아이템이 수십 개 이하이고, 순서 변경이 드물거나
동시 편집이 없는 시나리오(단일 사용자용 데이터)에서 사용 가능하다.
값을 정수가 아니라 실수로 관리한다.
두 아이템 사이의 평균값을 새 아이템의 순서로 넣는다.
ID=6인 새 아이템을 1(1)과 2(2) 사이에 삽입
변경 전:
1(1) 2(2) 3(3) 4(4) 5(5)변경 후:
1(1) 1.5(6) 2(2) 3(3) 4(4) 5(5)→ 기존 ID 1~5의 순서 값은 전혀 변하지 않는다.
새 아이템의 sort_key를 (1 + 2) / 2 = 1.5로 계산해 INSERT만 하면 끝.
1과 2 사이에 계속 값을 넣는다고 가정하면
1.5 → 1.25 → 1.125 → 1.0625 → 1.03125 → ...
소수점이 계속 늘어나게 된다.
부동소수점 정밀도 한계로 (a + b) / 2 == a 가 되는 지점이 발생한다.
범위를 늘려도 결국 동일하다 (float는 상대 정밀도를 가짐).
일반적인 사용 패턴(랜덤 위치 삽입)이면, 수천~수백만 번도 버틸 수 있다.
추가로, 임계치가 발생했을 때만 rebalance 하면 문제없이 동작한다.
숫자를 사용하지 않고, Base 95 문자열을 사전식 정렬로 순서가 보장되게 하는 방식.
ID=6인 새 아이템을 a0(1)과 a1(2) 사이에 삽입
변경 전:
a0(1) a1(2) a2(3) a3(4) a4(5)변경 후:
a0(1) a0V(6) a1(2) a2(3) a3(4) a4(5)→ 기존 ID 1~5의 sort_key는 전혀 바뀌지 않는다.
새 아이템(ID 6)의 sort_key를 "a0"과 "a1" 사이의 값 "a0V"로 계산해 INSERT만 하면 끝.
V는 ASCII에서'0'과'1'사이의 중간 정렬 문자.
사전식 정렬로"a0" < "a0V" < "a1"이 성립한다.
Figma, Notion, Linear가 이 방식을 사용한다고 한다.
많은 곳에서 사용하기 때문에 라이브러리로 제공된다.
import { generateKeyBetween } from 'fractional-indexing';
const first = generateKeyBetween(null, null); // "a0"
const second = generateKeyBetween("a0", null); // "a1"
const between = generateKeyBetween("a0", "a1"); // "a0V"아래에서 설명하지만, 일반적으로 클라이언트 측에서 구현하므로 Java 라이브러리는 없었다.
왜 동시성이 강한가?
두 사용자가 동시에
a0-a1사이에 삽입해도, 각자 새로운 sort_key를 만들어내기 때문에
기존 아이템의 값은 손대지 않는다.Integer 방식은 같은 order 값(예: 둘 다
3)을 노리게 되어 UNIQUE 제약 위반이나
한쪽 덮어쓰기가 발생하지만, Fractional Indexing은 키 공간이 조밀해서 겹칠 확률이
거의 없다. (완전히 같은 키가 나오는 극단적 상황에는 timestamp나 client_id suffix로
tiebreaker를 건다)
위 문자열 기반 Fractional Indexing의 개선 버전이다.
Base 36과 bucket 시스템을 통해 주기적으로 리밸런싱을 해 너무 길어지지 않게 한다.
Jira가 사용하는 방식이다.
Jira는 3개의 bucket(0|, 1|, 2|)을 prefix로 사용한다.
0| bucket 사용 → 0|hzzzzz, 0|i00000, ...1|)으로 점진적으로 이사2|로 → 다시 0|로 돌아간다.결과적으로 리밸런싱을 "서비스 중단 없이" 수행 가능.
무거운 전체 재정렬 대신, bucket rotation으로 O(N) 비용을 분산시킨다.
Base 95 vs Base 36
- Base 95는
!부터~까지 printable ASCII 95자를 사용한다 (숫자 + 영문 + 특수문자).
이모지 같은 유니코드 문자는 포함되지 않는다.- Base 36은 숫자(0-9)와 영문 소문자(a-z)만 사용한다.
- Base 95가 약 1.27배 더 compact 하다 (
log(95) / log(36) ≈ 1.27).- Figma 같이 레이어가 어마어마할 때는 극한의 최적화를 위해 Base 95를 채택한 것으로 보인다.
- 반대로 Jira(LexoRank)는 가독성 / URL-safe / 로그 친화성 때문에 Base 36을 고른 듯.
위 문자열 기반 Fractional Indexing과 동일하므로 생략!
그나마 다르다면, bucket 기반 주기적 rebalance로 실전에서 키 길이가 무한정 커지는 문제를 해결했다는 점.
| 방식 | 삽입 비용 | 동시성 | 구현 복잡도 | 추천 상황 |
|---|---|---|---|---|
| Integer UPDATE | O(N) | ❌ 나쁨 | ⭐ 낮음 | 수십 개 이하, 단일 사용자 |
| Float Fractional | O(1) | 🟡 양호 | ⭐ 낮음 | 소~중규모, 가끔 rebalance |
| String Fractional | O(1) | ✅ 우수 | ⭐⭐ 중간 | 협업 도구, 무한 분할 필요 |
| LexoRank | O(1) | ✅ 우수 | ⭐⭐⭐ 높음 | 엔터프라이즈 (Jira급) |
reorder API를 서버에 전송move API를 서버에 전송대략 봐도, 프론트에서 처리하는 게 현대적이다.
대신, 백엔드는
등을 할 수 있다.
단, 외부 개발자에게 공개된 API거나 감사 로그가 중요한 도메인이라면 서버 처리가 여전히 유효하다.
클라이언트를 신뢰할 수 없는 경우의 얘기.
Fractional Indexing 부분에서 숫자 Fractional Indexing을 그냥 String으로 저장하면 안 된다.
String 인덱스는 사전식 정렬이기 때문에 의도와 값이 달라질 수 있다.
자릿수가 바뀌면 정렬이 깨진다. (문자열 비교에서는 "9"가 "10"보다 더 크다)
즉, 자릿수를 다르게 하면 안 되고 + 고정된 범위를 보장해야만 숫자 Fractional Indexing을 String으로 저장할 수 있다.
대부분은 단일 요청과 순서 변경일 것이다.
혹시나, 다중 사용자의 데이터를 수정해야 하거나 & 순서 변경 시 1000개의 순서를 변경해야 한다면 이런 방식들을 고려해볼 만하다.