TIL #56 LexoRank (Node.js 66일차)

LexoRank

- lexicographical rank" 줄임말로 문자열의 사전적 순서를 활용해 순위를 결정하는 알고리즘이다

LexoRank의 순위값 구조 및 작동 방법

 

1. Bucket: 순위값 고갈 시 기존 순서를 유지하며 무중단으로 재조정하기 위한 요소
2. FixedKey: 모든 항목에 기본으로 부여돼 기본 순위로 사용되는 요소로, 항목 간에 빠르게 비교할 수 있는 고정 길이 키
3. VariableKey: FixedKey 고갈 시 할당되는 가변 길이 키

 

Todo-A와 Todo-B 사이에 Todo-E를 삽입시 Todo-E에 Todo-A와 Todo-B 두 순위값의 중간에 해당하는 0|AAAB:를 FixedKey 값으로 할당

Todo-A와 Todo-B 사이의 순위값이 고갈됐다면, Todo-A의 FixedKey(AAAA) 뒤에 규칙에 따라 VariableKey를 추가해 Todo-A의 뒤에, Todo-B의 앞에 오는 값을 할당(예를 들어 규칙에 따른 VariableKey가 5라면 0|AAAA:5가 할당하고 이 때 LexoRank는 FixedKey와 VariableKey를 조합해 대상 항목만 변경하므로 O(1)에 순서를 정렬)

LexoRank의 순위값 고갈을 사전에 감지하고 무중단으로 재조정하는 방법

- 감지 방법

• 순위값의 길이가 첫 번째 임계값인 128자에 도달하면 12시간 뒤 재조정 예약
• 예약된 12시간 동안 두 번째 임계값인 160자에 도달하면 즉시 재조정 수행
• 길이가 254자에 도달하거나 초과하면, 그 이상의 값을 생성하는 순위 작업은 중지

- 재조정 방법

 재조정이 필요할 때 세 개의 Bucket(0, 1, 2)을 순환하며 사용합니다. Bucket 증가 시(예: 0 → 1 또는 1 → 2)에는 낮은 순위의 순위값(0|DDD)부터 간격을 넓혀가며 다음 버킷으로 재할당하고 이 방법을 통해 기존 순위를 유지하면서 무중단으로 순위값을 재조정이 가능( 재조정 상황을 제외하고는 일반적으로 하나의 Bucket만 사용 )

 

출처: https://techblog.lycorp.co.jp/ko/about-atlassian-jira-ranking-algorithm-lexorank