sorted set을 구현하자...

아주 아주 옛날에 할당 받은 이슈...

오픈소스 컨트리뷰톤 행사에 참여 할 때 Arcus 프로젝트에서 할당 받은 이슈가 하나 있었다.
그것은 바로 Arcus에서 sorted set 연산을 지원하는 것이였다.
행사가 끝나기 전에 컨트리뷰션을 하나라도 하고 싶다는 욕심에 쉬운 이슈를 할당 받아서 진행하게 되었지만, 행사가 끝난 지금은 시간에 압박을 받지 않고 구현을 할 수 있을 것 같다.
그럼에도 새로운 자료구조를 추가하는 일은 제법 난이도가 있는 이슈임에는 틀림이 없다.

https://github.com/naver/arcus-memcached/issues/480

우선 위 링크에 있는 이슈인데, 우선 다른 자료구조가 어떻게 구현되어 있고, 어떤 흐름으로 진행되는지 살펴보는 편이 좋을 것 같다. 기존의 자료구조의 연산이 어떻게 정의 되어 있는지를 살펴보기 위해서 이미 구현되어 있는 자료구조 중에서 B+tree를 살펴 봐야 겠다.

B+tree

일단 Arcus를 실행하여 B+ tree 연산을 해볼 것이다.

bop insert bkey1 90 6 create 11 0 0
datum9
bop insert bkey1 70 6
datum7
bop insert bkey1 50 6
datum5
bop insert bkey1 30 6
datum3
bop insert bkey1 10 6
datum1

위의 모습은 B+tree 5개의 연산을 수행한 모습이다. 결과는 아래와 같다.

CREATED_STORED
STORED
STORED
STORED
STORED

bop get bkey1 30..80

그리고 값을 얻기 위해서 위와 같은 연산을 하게 되면, 아래와 결과가 나오게 된다.

위의 결과를 보면, VALUE 11 3으로 나와있는데, 왼쪽부터 11 은 flag로 설정한 값이다. flag가 무엇인지는 링크에 잘 설명이 되어 있다. (https://github.com/naver/arcus-memcached/blob/master/doc/ch03-item-attributes.md) 그리로 뒤에 나오는 3은 조회된 데이터의 개수를 나타낸다.

맨 처음에 나오는 insert 뒤에 나오는 create 문은 insert 옵션으로 제공한다.
create 명령어가 따로 존재하며, 뒤에 나오는 숫자들은 다음과 같은 의미를 가진다.

flags | expiretime | maxcount # 11 0 0

• flag 속성 : 특정 아이템의 data-specific 정보를 저장하기 위한 목적으로 사용된다.
• expiretime : 아이테믜 expiretime 속성으로 그 item의 expiration 시간을 초 (second) 단위로 설정한다.
  -- -1 : sticky item으로 설정한다.
  -- 0 : never expired item으로 설정, 그러나 메모리 부족시에 evict 될 수 있다.
• maxcount 속성 : collection 아이템에만 유효한 속성으로, 하나의 collection에 저장할 수 있는 최대 element 수를 나타낸다.