24.03.19 TIL - LexoRank

1. LexoRank 모듈을 검색하게 된 이유

nest.js로 trello같은 kanban board 시스템을 만들기 위해 로직을 고려하던 중 linked list 자료구조를 채용하려고 했다. 하지만 프로젝트에서 typeOrm을 사용하고 있는 특성상 linked list는 적용이 쉽지 않다는 피드백을 듣고 다른 방법을 고려하고 있었다. 일단, 당초에 함께 고려되었던 부동소수점을 이용한 배열 정렬을 써보자는 의견으로 모아졌다. 하지만 구글링을 하던 중 더 좋은 방법이 있는것 같아 적용해보고자 한다.

 

2. LexoRank 모듈 구조

Bucket | FixedKey : VariableKey

의 형태로 이루어진 코드이고 각 요소에는 기존 랭킹 시스템의 한계를 극복하기 위한 명확한 역할이 부여돼 있다. 순서를 숫자가 아닌 문자열을 이용해 표시해 주는 것이다. 하나의 순서를 바꿀 떄 하나의 리소스만 업데이트 할 수 있게 해준다.

 

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

기존 방식의 한계를 극복한 방법

기존방식의 한계	LexoRank에서 극복한 방법
Integer 방식: 순서 병경 시 수정 범위가 큼(O(N))	문저열 순위값을 통해 수정 범위 축소(O(1))
GreenHopper 방식: 빠른 순위값 고갈 및 재조정 시 시스템 중단	무중단 대조정으로 순위값 고갈 방지
Linked List방식: 순서 변경 시 2~4번의 고정비용 발생 및 목록 조회 시 전체 스캔	인덱스 스캔으로 고정 비용 없이 빠른 조회

 

 

3. 숫자 방식과의 차이

order 1과 2 사이로 수정할 때 1.5로 업데이트 한다면 하나의 업데이트로 요구조건을 만족할 수 있는데 요청이 잦아지면 소수점이 길어지고 너무 많은 리소스가 소모되면 서버에 부하가 커지는데, 문자열은 그렇지 않다.

 

Int 타입의 1,2사이에는 간격이 없지만, AAA-BBB사이에는 AAAA ~ AAAZ까지 무한개가 있다. 이런 이론에 착안한 것이 LexoRank인 것이다. 프로젝트에 적용해보고 난 후 업데이트하도록 하겠다.

 

장점은 하나의 데이터만 업테이트해도 되고, 데이터가 예측가능한 형태이며 stateless한 랭크를 이용할 수 있다는 점이다. 왜냐하면 간격이 좁아져도 쉽게 리밸런싱이 가능하기 때문이다.

 

출처 : https://velog.io/@ksi05503/%EB%8B%B9%EC%8B%A0%EC%9D%98-%EC%96%B4%ED%94%8C%EB%A6%AC%EC%BC%80%EC%9D%B4%EC%85%98-%EB%A1%9C%EC%A7%81%EC%97%90-LexoRank-%EB%A5%BC-%EC%A0%81%EC%9A%A9%ED%95%B4%EC%95%BC%ED%95%98%EB%8A%94-%EC%9D%B4%EC%9C%A0

어플리케이션에서 LexoRank 모듈이 정말 유용한 이유

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

Jira의 이슈 정렬 방식이 Integer 방식이 아니라고?!