sorted set 기능 검토 및 개발

[minkikim89]

ARCUS는 현재 sorted set 기능을 지원하지 않는다. 응용에서 ARCUS를 활용하는 데 있어 sorted set 기능이 필요한 경우도 있으므로, 이를 설계하고 개발한다.

[dongwooklee96]

하시는 분이 없다면 제가 진행해보도록 하겠습니다.

[jhpark816]

Sorted set 기능이 필요한 이유를 남깁니다.

먼저, b+tree collection은

• <bkey, data> 구조의 element 집합이며,
• bkey 기준으로 index를 생성하여 element들을 정렬하고, bkey 기반의 exact search와 range search를 제공합니다.

대부분의 응용들에서 b+tree 기능이 활용도가 매우 높지만, 몇 개 응용에서 부족한 기능이 있습니다. 이러한 부족한 기능을 보완하기 위하여 sorted set 기능을 개발하려는 것입니다. Sorted set 개념은 b+tree element의 data 부분에 대해 아래 2가지 기능을 제공하려는 것입니다.

• data의 uniqueness 보장
• data 기준으로 bkey 조회

활용 예를 들면, 아래와 같습니다.

• data의 uniqueness 보장 - 이벤트에 참가 목록 유지
  • b+tree collection에 <이벤트 참가 시간, 이벤트 참가 사용자ID> 목록을 유지하려고 합니다.
  • 어떤 사용자가 이벤트 참가 버튼을 클릭하여 b+tree collection에 등록이 되었습니다.
  • 그 이후에 그 사용자가 다시 이벤트 참가 버튼을 클릭하여 이벤트에 다시 참가할 경우, 그 사용자는 이미 이벤트에 참가자 라는 것을 알 수 있어야 합니다.
  • 이 경우, 한 사용자가 중복 등록되는 것을 막기 위하여 data 부분이 set 개념을 가져야 합니다.
• data 기준으로 bkey 조회
  • 향후에 ARCUS 에서 GIS 연산을 제공할 계획이 있습니다.
  • 예를 들어, 여러 상점들의 위치 정보를 저장한다고 가정합니다.
    • 이 경우, b+tree에 <position, 상점 name(or ID)>을 저장하게 됩니다.
    • 그리고, 어떤 사용자의 position이 있으면, 그 position에서 1km 이내에 있는 상점 목록을 구할 수 있게 됩니다.
    • 반대로, 어떤 상점 이름으로 그 상점의 위치를 구하고자 한다면, 상점 name을 가지고 position을 얻는 기능이 필요합니다.
  • 추가 사항으로, 앞서 이벤트 참가 목록 유지하는 경우에서도
    • 어떤 사용자가 언제 이벤트에 참가하였는 지를 알고자 한다면, 참가자 ID를 기반으로 element를 찾아 시간을 얻을 수 있어야 합니다.

좀 더 넓게 설명하면, 이는 RDBMS에서 테이블에 어떤 index를 두는 것과 같은 문제입니다.
< bkey, data > 구조와 같이 2개 칼럼으로 구성된 레코드들의 집합이 있고, 어떤 칼럼들의 조합에 대해 index를 둘 것인가의 문제입니다. index를 많이 둘수록 다양한 조회 성능을 개선할 수 있지만, store 연산의 수행 cost가 커집니다.

• 현재 ARCUS B+tree collection은 bkey 칼럼에 대해 unique index만을 두고 있습니다.
• Sorted set은 추가적으로 data 칼럼에 대해 unique index를 두자는 것입니다.
  • 실 구현에서는 unique index 기능을 가지면서 가장 간단한 구조체를 사용하는 것이 좋습니다.
  • 예를 들어, b+tree 구조와 같이 복잡한 구조의 index가 아니라 hash 같은 간단한 구조의 index를 두는 것이 낫습니다.
• 이를 더 확장할 수 있지만, 활용 용도가 낮아서 추가 확장은 하지 않으려고 합니다. (현재 생각)
  • data 칼럼에 non-unique index를 두거나
  • <bkey, data> 복합 칼럼 index를 두거나
  • <data , bkey> 복합 칼럼 index를 둘 수 있습니다.

마지막으로, sorted set 개념을 외부에는 어떻게 제공할 것인가 입니다. 아직, 이 부분까지는 크게 고민하지 않았는 데, 가급적 아래의 전자 방식을 먼저 검토해 볼 것입니다.

• arcus의 b+tree collection 기능을 확장하여 제공할 수도 있고,
• redis 처럼 sorted set collection을 따로 만들어 제공할 수도 있습니다.

[dongwooklee96]

상세한 설명 정말로 감사합니다. 제대로 이해했는지 몰라서 확인차 질문 드립니다.

Sorted set은 추가적으로 data 칼럼에 대해 unique index를 두자는 것입니다. 실 구현에서는 unique index 기능을 가지면서 가장 간단한 구조체를 사용하는 것이 좋습니다. 예를 들어, b+tree 구조와 같이 복잡한 구조의 index가 아니라 hash 같은 간단한 구조의 index를 두는 것이 낫습니다.

b+tree와는 다른 간단한 구조의 index를 가질 수 있는 자료구조를 생성하여, sorted set을 구현하는게 맞나요?

마지막으로, sorted set 개념을 외부에는 어떻게 제공할 것인가 입니다. 아직, 이 부분까지는 크게 고민하지 않았는 데, 가급적 아래의 전자 방식을 먼저 검토해 볼 것입니다.

• arcus의 b+tree collection 기능을 확장하여 제공할 수도 있고,
• redis 처럼 sorted set collection을 따로 만들어 제공할 수도 있습니다.

전자의 방식을 먼저 고려해 보신다는게 sorted set 개념을 b+ tree collection 의 옵션과 같은 형태로 사용할 수 있게 제공한다는 뜻인가요?

[jhpark816]

@dongwooklee96 예. 맞습니다. 아래에 보강 설명을 붙입니다.

• 기준으로 uniqueness 보장과 exact search 기능만 있으면 되며, 이를 통해 sorted set 기능을 구현할 수 있습니다.
  • 따라서, range search를 위한 b+tree index까지는 필요하지 않습니다.
  • hash index 구조이어도 충분하고, 더 간단한 구조이어도 됩니다.
• b+tree collection 생성 옵션으로 sorted set 기능이 표현되면 좋을 것 같습니다.
  • 어떤 옵션으로 제공하여야 b+tree collection에 자연스러운 형태가 될 지를 판단해야 합니다.

[dongwooklee96]

@jhpark816

예. 맞습니다. 아래에 보강 설명을 붙입니다.

• 기준으로 uniqueness 보장과 exact search 기능만 있으면 되며, 이를 통해 sorted set 기능을 구현할 수 있습니다.

  • 따라서, range search를 위한 b+tree index까지는 필요하지 않습니다.
  • hash index 구조이어도 충분하고, 더 간단한 구조이어도 됩니다.

sorted set을 지원하는 Redis에서 어떻게 구현하였는지를 보았는데, skip list 라는 자료구조를 이용하여 구현되었습니다. 조금 변형하기는 하였지만 기본 아이디어는 같습니다. Arcus에서도 이와 같이 구현하는건 어떻게 생각하시나요?

[참고자료]

• SkipList
• Redis SKIP List of ZSETS (SORTED SETS)
• Why Redis SortedSet uses Skip List instead of Balanced Tree?

[jhpark816]

@dongwooklee96 skip list이어도 됩니다. 감사합니다.

[jhpark816]

@dongwooklee96 skip list는 맞지 않는 데, 마지막 코멘트에서 제가 실수를 한 것 같습니다.

redis에서 sorted set 구현을 위해 아래 2가지 data structure를 사용합니다.

• skip list + hash table
  • skip list: score 순서로 정렬 목적
  • hash table: set의 uniqueness 구현

Arcus에서 sorted set 개념을 제공하려면, 아래와 같이 hash table을 구현해야 합니다. 즉, redis의 skip list에 대응하는 b+tree 자료구조는 이미 존재하기 때문에 hash table 기능만 있으면 됩니다.

• b+tree + hash table
  • b+tree: bkey 순서로 정렬 목적
  • hash table: set의 uniqueness 구현

b+tree에 있는 모든 element의 value에 대해 hash table을 통해 uniquess를 보장하는 기능을 추가하면, sorted set 개념을 제공할 수 있게 됩니다.

ARCUS에서 sorted set 개념을 어떻게 제공할 지는 별도 이슈로 생각하면 좋겠습니다.

• 별도의 sorted set collection 모델로 제공할 수도 있고,
• b+tree collection의 추가 기능으로 제공할 수도 있습니다.

따라서, 작업은 아래와 같이 나누는 것이 좋을 것 같습니다.

• b+tree + hash table 구조를 저장 엔진 수준에서 먼저 제공
  • b+tree에 set 속성을 추가하여 set 여부를 나타내면 됩니다.
  • b+tree가 set 속성을 가진다면, 내부적으로 element value들에 대한 hash table을 생성하여 uniqueness를 보장하면 됩니다.
• sorted set 기능에 대한 command 제공
  • 현재 생각으론, btree의 추가 속성을 제공하는 형태로 기존 btree 명령을 확장하면 좋을 것 같습니다.
    • arcus의 b+tree collection을 강조하기 위함입니다.

검토 바랍니다.

[dongwooklee96]

b+tree + hash table 구조를 저장 엔진 수준에서 먼저 제공 b+tree에 set 속성을 추가하여 set 여부를 나타내면 됩니다. b+tree가 set 속성을 가진다면, 내부적으로 element value들에 대한 hash table을 생성하여 uniqueness를 보장하면 됩니다. sorted set 기능에 대한 command 제공

bop create <key> <attributes> [noreply]\r\n
* attributes: <flags> <exptime> <maxcount> [<ovflaction>] [unreadable]

set 속성은, attribute에 추가하려고 하는데, 어떻게 생각하시나요?

bop insert를 할 때, 중복된 값이 있을 경우 클라이언트에게 어떤 response_string을 전달해야 할지 또 bop가 제공하는 다른 연산의 경우 어떻게 동작하는지에 대한 설계는 제가 생각해보고 검토를 통해 합의되면 설계대로 개발하면 될까요? 3.

현재 생각으론, btree의 추가 속성을 제공하는 형태로 기존 btree 명령을 확장하면 좋을 것 같습니다. arcus의 b+tree collection을 강조하기 위함입니다.

저도 이 부분에 동의합니다. btree의 추가 속성을 제공하는 형태로 제공하는 것이 더 알맞을 것 같습니다.

제가 혹시 놓친 부분이 있다면 알려주시면 감사하겠습니다

[jhpark816]

@dongwooklee96

• collection 생성 속성 확장
  • ascii protocol 이다 보니, 명령 확장에 제약에 있습니다.
  • 현재로선 아래와 같이 "uniqueval" 속성을 추가하시죠.
    • <flags> <exptime> <maxcount> [<ovflaction>] [unreadable] [uniqueval]
  • 참고로, 향후 변경 가능성 있습니다.
• value 중복인 경우의 오류 타입과 메세지
  • 잠정적으로 아래와 같이 하시죠
    • 오류 타입: ENGINE_EVAL_EEXISTS
    • 오류 메세지: "ELEMENT_VALUE_EXISTS"
  • 참고로, 향후 변경 가능성 있습니다.

그 외는 개발하면서 논의 사항이 생기면, 그 때 논의하면 될 것 같습니다.

[dongwooklee96]

@jhpark816 안녕하세요 이슈를 구현하는 중에 궁금한 점이 있어서 질문드립니다. 현재 진행중인 이슈를 구현하는데 도움이 될 것 같아서 set 컬렉션의 insert 연산을 분석하고 있습니다.

그런데 제가 아직 해시테이블에 대한 이해가 부족하여, set_hash_node 구조체에 대해서 이해가 잘 안가더라구요

typedef struct _set_hash_node {
    uint16_t refcount;
    uint8_t  slabs_clsid;         /* which slab class we're in */
    uint8_t  hdepth;
    uint16_t tot_elem_cnt;
    uint16_t tot_hash_cnt;
    int16_t  hcnt[SET_HASHTAB_SIZE];
    void    *htab[SET_HASHTAB_SIZE];
} set_hash_node;

• 여기서 hcnt와 htab이 어떤 역할을 하는지 잘 이해가 안되는데 설명해주실 수 있으신가요?

[jhpark816]

@dongwooklee96

• 각 set_hash_node는 하나의 hash table을 가집니다.
• htab은 SET_HASHTAB_SIZE 크기의 hash table 입니다.
• hcnt는 hash table에 있는 hash chain 길이를 가집니다. 따라서 hash table 크기의 배열 구조를 가지고 있습니다.
  • hcnt가 > 0 이면, 해당 hash bucket은 hash chain(즉, element list)를 가진다는 의미이고,
  • hcnt가 0 이면, 해당 hash bucket은 null 상태
  • hcnt가 -1이면, 하위 hash table을 가집니다. 즉, 하위 set_hash_node 구조체를 가집니다.

[dongwooklee96]

@jhpark816 답변 주셔서 감사합니다!

• 설명해주신것을 바탕으로 제가 이해한 것을 바탕으로 간단하게 그려봤는데, 이렇게 이해하면 될까요?

static ENGINE_ERROR_CODE do_set_elem_link(set_meta_info *info, set_elem_item *elem,
                                          const void *cookie)
{
    assert(info->root != NULL);
    set_hash_node *node = info->root;
    set_elem_item *find;
    int hidx = -1;

    /* set hash value */
    elem->hval = genhash_string_hash(elem->value, elem->nbytes);
    // 하위 해시 테이블을 가지고 있다면, 노드를 하위 해시 테이블로 변경
    while (node != NULL) {
        hidx = SET_GET_HASHIDX(elem->hval, node->hdepth);
        if (node->hcnt[hidx] >= 0) /* set element hash chain */
            break;
        node = node->htab[hidx];
    }
    assert(node != NULL);
    assert(hidx != -1);
    // 해시 체인을 모두 순회하면서 중복된 값을 가지는지 검사
    for (find = node->htab[hidx]; find != NULL; find = find->next) {
        if (set_hash_eq(elem->hval, elem->value, elem->nbytes,
                        find->hval, find->value, find->nbytes))
            break;
    }
    // 모두 순회하지 못했다면 중복된 값을 가지고 있다는 뜻이므로, 에러 코드 리턴
    if (find != NULL) {
        return ENGINE_ELEM_EEXISTS;
    }

    if (node->hcnt[hidx] >= SET_MAX_HASHCHAIN_SIZE) {
        set_hash_node *n_node = do_set_node_alloc(node->hdepth+1, cookie);
        if (n_node == NULL) {
            return ENGINE_ENOMEM;
        }
   ...

• 위의 코드는 do_set_elem_link 함수의 부분인데, 제가 올바르게 이해했는지 궁금합니다
• 추가적으로, hval, hdepth를 바탕으로, hidx를 반환하는 SET_GET_HASHIDX 함수에 대해서 궁금하고, hdepth가 어떤 것을 의미하는지 궁금합니다.

[jhpark816]

@dongwooklee96

• hash chain (the list of elements) 표현이 어색하지만, 잘 이해한 것 같습니다.
• set의 물리적 구조는 hash table들의 tree 구조로 되어 있습니다.
  • root hash table이 있고, 그 아래에 하위 hash table들이 존재할 수 있습니다.
  • hdepth는 tree 상에서 해당 hash table의 depth를 나타냅니다.
  • SET_GET_HASHIDX은 hval에서 hdepth에 해당하는 4 bits를 찾아냅니다.

이해 안 되면, 다시 알려주세요