TIL 240718 - Lexorank

나만 알고싶으니까 발표날에 TIL로 옮겨야지...

 

1. 드래그 앤 드롭 정렬 알고리즘에 대한 고민...

정렬이 되어있는 여러 요소 중 하나를 드래그 앤 드롭으로 순서를 바꿨을 때, 해당 순서를 DB에서 변경하도록 하는 알고리즘이 필요했다. 단순히 배열의 순서를 바꾸자기엔 너무 많은 시간적 비용이 든다..

 

아래는 내가 생각해본 여러 방법들..

 

1) 리스트 테이블에 order 컬럼을 만들고, 순서가 바뀔때마다 카드의 순서를 담은 배열을 업데이트 하는 방법

 

2) 링크드리스트를 사용하여 해당 카드의 전, 후 카드 데이터를 수정하는 방법

 

3) 카드 테이블에 next 컬럼을 만들어, 해당 카드의 바로 뒷 순서의 카드 정보를 저장하는 방법

 

근데, 드래그 앤 드롭으로 순서를 바꾸는 기능은 웹사이트에서 쉽게 볼 수 있는데, 이걸 구현할 때 공통으로 쓰는 알고리즘이 있지 않을까..?해서 구글링을 해봄.

 

그렇게 해서 찾은게 LexoRank이다.

 

2. LexoRank

1) 간단한 원리

• 문자열의 사전적 순서를 활용해 순위를 결정하는 알고리즘
• 일반적인 숫자 정렬에서 100은 99보다 낮은 순위이지만, LexoRank에서는 사전적 정렬에 따라 1이 9보다 앞에 있으므로 100이 99보다 높은 순위.

 

2) 순위값 구조

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

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

 

3) 작동 방법

 

Todo-A의 Fixed-key가 0|AAAA, Todo-B의 Fixed-key가 0|AAAC라고 하자.

순위값이 0|B000인 Todo-C는 저 아래에 위치한다. 여기서 드래그 앤 드롭으로 아래에 있던 Todo-C를 Todo-A와 Todo-B 사이로 옮기게 될 경우, Todo-A와 Todo-B 두 Fixed Key의 중간에 해당하는 0|AAAB를 FixedKey 값으로 할당할 수 있다.

 

만약 Todo-A의 키가 0|AAAA이고, Todo-B의 키가 0|AAAB라면 두 키의 사잇값이 존재하지 않는다. 이를 Fixed-key가 고갈되었다고 표현하는데, 이 경우에는 Todo-A의 Fixed Key 규칙에 따라 Variable Key를 추가하여 Todo-A와 Todo-B의 사이의 값으로 할당한다. 예를 들어, 규칙에 따른 Variable Key가 5일 경우, 0|AAAA:5가 할당된다.

 

그런데, Variable Key 마저도 고갈될 경우에는 어떻게 하는가...

LexoRank는 순위값 고갈을 사전에 감지하여 무중단으로 재조정할 수 있다.

 

 

4) 순위값 고갈을 사전에 감지하는 방법

 

 Jira에서 사용하는 순위값 고갈을 감지하는 방법은 아래와 같다고 한다.

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

5) 무중단 재조정 방법

LexoRank는 재조정이 필요할 때 3개의 Bucket(0, 1, 2)를 순환하여 사용한다.

• Bucket 증가 시 낮은 순위값부터 간격을 넓혀가며 다음 버킷으로 재할당
  •  이전 순위값이  0|DDD, 0|DDC, 0|DDB 일 경우, 재조정 시 아래에서부터 1|CCC, 1|BBB, 1|AAA 로 재조정
• 현재 Bucket이 마지막 값인 2일 경우, 반대로 높은 순위의 순위값부터 간격을 넓혀가며 버킷 0으로 재할당