search

naver / arcus-memcached

ARCUS memory cache server
https://github.com/naver/arcus
Apache License 2.0
70 stars 55 forks source link

sorted set 기능 검토 및 개발 #480

Open minkikim89 opened 4 years ago

minkikim89 commented 4 years ago

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

dongwooklee96 commented 4 years ago

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

jhpark816 commented 4 years ago

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

먼저, b+tree collection은

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

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

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

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

dongwooklee96 commented 4 years ago

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

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 commented 4 years ago

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

dongwooklee96 commented 4 years ago

@jhpark816

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

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

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

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

[참고자료]

jhpark816 commented 4 years ago

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

jhpark816 commented 3 years ago

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

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

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

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

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

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

검토 바랍니다.

dongwooklee96 commented 3 years ago

  1. 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에 추가하려고 하는데, 어떻게 생각하시나요?

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

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

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

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

jhpark816 commented 3 years ago

@dongwooklee96

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

dongwooklee96 commented 2 years ago

@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;
jhpark816 commented 2 years ago

@dongwooklee96

dongwooklee96 commented 2 years ago

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

Screen Shot 2021-10-02 at 10 36 22 PM

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;
        }
   ...
jhpark816 commented 2 years ago

@dongwooklee96

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