최근 빅데이터를 다루기 위한 여러가지 기술들이 많이 사용되고 있다. 그 중 하나의 알고리즘을 소개해보고자 한다.
이들의 공통점은 skiplist 알고리즘을 사용한다는 것이다.
| Skip List | ||
|---|---|---|
| Type | List | |
| Invented | 1990 | |
| Invented by | W. Pugh | |
| Time complexity in big O notation | ||
| Average | Worst case | |
| Space | O(n) | O(n log n)[1] |
| Search | O(log n) | O(n)[1] |
| Insert | O(log n) | O(n) |
| Delete | O(log n) | O(n) |
대량의 데이터를 빠르게 검색이 가능하다는 장점이 있으며, 사용하는 방법에 따라서는 최상의 성능을 발휘하지만 몇가지 제약을 가지고 있기도 하다.
그래서, 나는 몇가지 기능을 수정해 보았다.
- 중복이 허용되는 구조
- 여러개의 skiplist 트리를 생성하는 세그먼트 구조
- Value 레퍼런스 구조
- Value Expire가 가능한 구조
- 직렬화가 가능한 데이터 저장 구조
- 저장된 데이터 위치의 순서를 가지고 있는 구조 (랭킹)
- 페이징 단위로 처리하여 파일로 관리되는 구조
이러한 처리를 통해, 좀더 능동적인 구조를 가질수 있도록 변경하였다.
이러한 변경을 한 목적이, 게임서버의 랭킹엔진으로 사용하고 ISAM엔진으로 사용하기 위함이었으므로..
위에서 나열한 기능을 적용하기 위해서 알아야 할 몇가지 TIP를 적어보고자 한다.
- 중복이 허용되는 구조
중복되는 데이터는 level = 1로 고정하고, 중복되지 않은 데이터는 level > 1 이상을 가지도록 구성
중복되는 데이터는 항상 처음에 위치하도록 한다. (이전 데이터의 level을 그대로 복사한다.)
- 여러개의 skiplist 트리를 생성하는 세그먼트 구조
하나의 데이터블럭을 공유하는 여러개의 skiplist를 가지게 하므로서, 멀티키 지원이 가능하도록 구성
skiplist는 head를 가지고 있는데, head의 연결 level중 사용되지 않은 level의 데이터를 segment 연결용으로 사용한다.
- Value 레퍼런스 구조
생성된 데이터의 Value를 다른 데이터와 연결하는 구조를 통해, Multi Key-Single Value가 가능한 구조로 구성
데이터의 길이가 0인 경우로 제한하여 사용하고, 연결하는 offset을 저장한다.
- Value Expire가 가능한 구조
데이터의 TTL (Time-To-Live)를 가질수 있도록 하여, 자동으로 소멸이 가능한 항목을 구성
데이터를 검색하면서 TTL이 설정된 항목이면 체크하여 자동 삭제되도록 한다.
- 직렬화가 가능한 데이터 저장 구조
해당 기능은, 내부의 저장 구조를 리니어하도록 구성하여, 통신을 통해 skiplist를 전송할수 있도록 처리한 구성
- 저장된 데이터 위치의 순서를 가지고 있는 구조 (랭킹)
해당처리는 Indexable SkipList에 이미 존재하는 알고리즘이다.
1 10
o---> o---------------------------------------------------------> o Top level
1 3 2 5
o---> o---------------> o---------> o---------------------------> o Level 3
1 2 1 2 3 2
o---> o---------> o---> o---------> o---------------> o---------> o Level 2
1 1 1 1 1 1 1 1 1 1 1
o---> o---> o---> o---> o---> o---> o---> o---> o---> o---> o---> o Bottom level
Head 1st 2nd 3rd 4th 5th 6th 7th 8th 9th 10th NIL
Node Node Node Node Node Node Node Node Node Node와 같은 처리를 다음과 같은 형식으로 처리한다.
function lookupByPositionIndex(i)
node ← head
i ← i + 1 # don't count the head as a step
for level from top to bottom do
while i ≥ node.width[level] do # if next step is not too far
i ← i - node.width[level] # subtract the current width
node ← node.next[level] # traverse forward at the current level
repeat
repeat
return node.value
end function- 페이징 단위로 처리하여 파일로 관리되는 구조 (Memory-Mapping 구조가 아닌 일정 블럭단위 크기)
level 이 동일한 블럭을 하나의 페이지에 저장하도록 구성한다.이를 통해, IO횟수를 줄일수 있다.
물론, 이러한 처리를 위해 LRU 캐싱 알고리즘도 추가로 고려해야 한다.
위의 변경사항 중 가장 고려사항이 많은 부분이 해당 처리인데, 문제는 페이징단위로 블럭화 시켜서 처리하다 보니 데이터의 삭제시 발생되는 가비지데이터의 처리가 이슈가 된다. 이러한 가비지를 무시하는 경우 저장되는 파일의 크기는 계속 늘어나기만 하기 때문에 이를 조정하는 처리를 해야 한다.
이러한 가비지를 최소화 하기 위해서는 일정 크기 단위로 데이터의 크기를 조정하여 처리하는 방법과, 가비지 데이터 여러개를 하나의 데이터로 만들어 사용할수 있는 방법이 제공되어야 한다.
** 해당 처리를 수행하기 위해, 내부적으로 사용하는 구조체는 다음과 같다. **
struct skipio_elem {
/*
* forward[SKIPIO_MAXLEVEL] 할당된 크기
*
* segment인 경우
* level = 0
* forward[SKIPIO_MAXLEVEL + 1] next segment offset
*
* data인 경우
* length > 0
* forward[SKIPIO_MAXLEVEL + 1] expire time
* length == 0
* forward[SKIPIO_MAXLEVEL + 1] reference elem
*
*/
int16_t segid;
int length; /* data의 length */
intptr_t offset; /* data가 위치한 offset */
int16_t level; /* 레벨 */
intptr_t forward[SKIPIO_MAXLEVEL + 2]; /* 다음 데이터의 오프셋 */
intptr_t distance[SKIPIO_MAXLEVEL + 1]; /* 다음 데이터까지의 거리 */
}; /* char key[offset] */