[Server] Set collection item delete 성능 개선

minzu0306 commented 8 years ago

btree collection 성능개선과 동일하게 set collection도 성능 개선 작업 진행

minzu0306 commented 8 years ago

do_set_node_unlink(engine, info, node, hidx)

do_set_node_unlink(engine, set_meta_info info, set_hash_node par_node, const int par_hidx)
- par_node == NULL : node가 root node
- node = (set_hash_node *)par_node->htab[par_hidx]; : 삭제해야할 node 적재
- assert(node->tot_hash_cnt ==0) : node 밑에 child node가 없어야함
- if ( node->htab[hidx] >0 ) : node 밑에 elem이 있다는 뜻
- elem을 head에 연결시킴
- assert(fcnt == node->tot_elem_cnt) : 모든 elem을 head에 옮겼는지 확인
- par_node->htab[hidx] = head; : 옮긴 elem들을 삭제할 node의 index에 적재
- par_node->tot_elem_cnt += fcnt; elem갯수 더해줌
- decrese_collection_space()
- do_set_node_free(engine, node): node free

minzu0306 commented 8 years ago

do_set_elem_unlink(engine, info, node, hidx, NULL, elem, )

do_set_elem_unlink(engine, set_meta_info info, set_hash_node node, const int hidx, set_elem_item prev, set_elem_item elem, enum)
- if (prev != NULL) prev->next = elem->next; : prev가 null이 아니면 prev와 next 연결
- else node->htab[hidx] = elem->next ; 삭제할 elem의 위치에 elem->next 적재
- decrease_collection_space
- do_set_elem_free(engine, elem) : elem free
삭제할 elem의 prev, next를 연결해주고 elem free시키는 함수

minzu0306 commented 8 years ago

do_set_elem_traverse_dfs(engine, info, info->root, count, true, NULL)

do_set_elem_traver_dfs(engine, set_meta_info _info, set_hash_node node, const uint32_t count, const bool delete, set_elem_item _elem_array)
- if ( node->tot_hase_cnt > 0 ) : node 밑에 child node 존재
- if (child_node->tot_hash_cnt == 0 && child_node->tot_elem_cnt < (SET_MAX_HASHCHAIN_SIZE/2) : node 밑에 child node는 없고, elem만 남아있으면 node unlink 실행
- for (hidx = 0; hidx < SET_HASHTAB_SIZE; hidx++) : node가 child node는 없고 elem만 있을 때
- do_set_elem_unlink() 실행
- elem = (delete ? node->htab[hidx] : elem->next) : 기존 elem 삭제후 다음 elem 연결

minzu0306 commented 8 years ago

do_set_elem_delete 쓰는 함수
- do_item_alloc_internal, check_expired_collections
- do_item_reclaim, do_item_evict, do_item_repair
  - do_coll_all_elem_delete
sop 명령어에 의한 delete set 함수 구조
- set_elem_delete()
- do_set_elem_delete_with_values(engine, info, value, nbytes, )
  - ret = do_set_elem_traverse_delete(engine, info, info->root, hval, val, vlen)
  - do_set_node_unlink
  - do_set_elem_unlink
- do_item_release()

minzu0306 commented 8 years ago

내 생각으로는 do_set_elem_traverse_dfs()에서 if(child_node->tot_hash_cnt == 0 && child_node->tot_elem_cnt < (SET_MAX_HASHCHAIN_SIZE/2 ) 에서 if(child_node->tot_hash_cnt == 0 && child_node->tot_elem_cnt == 0 )으로 바꾸면 될거같다 하지만 그러면 elem이 없는 node들까지 쭉 훑게되므로 오버헤드가 생기게 된다

minzu0306 commented 8 years ago

설계 초안
- 기존 do_setelem

do_set_elem_delete_fast(engine, info, 30){
  do_set_elem_traverse_fast(engine, info, info->root, count)
}

do_set_elem_traverse_fast(engine, info, info->root, count){
 if(node->tot_hash_cnt >0){
   for (hidx = 0; hidx <node->tot_hash_cnt; hidx++){
      set_hash_node *child_node
      fcnt += do_set_elem_traverse_dfs();
      if ( child_node->tot_hash_cnt == 0 && child_node->tot_elem_cnt == 0)
          do_set_node_unlink(engine, info, node, hidx);
   }
 }
for (hidx=0; hidx<node->tot_elem_cnt; hidx++){
    if ( count < tot_elem_cnt){
        if ( 

    }
    if(node->hcnt[hidx] >0){
     set_elem_item *elem = node->htab[hidx];

}

collection_delete_thread()
{
info = (set_meta_info *)item_get_meta(it);
set_hash_node node = info->root;

node = do_set_elem_delete(engine, info, default_node, 30 ,ELEM_DELETE_COLL);
}

static set_hash_node do_set_elem_delete(struct default_engine *engine,
                                   set_meta_info *info, set_hash_node node, const uint32_t count,
                                   enum elem_delete_cause cause)
{
    assert(cause == ELEM_DELETE_COLL);
    //uint32_t fcnt = 0;
    if(info->root != NULL){
        if (node == info->root){
           node= do_set_elem_traver_dfs(engine, info, info->root, count, true, NULL);
        }else {
             node = do_set_elem_traverse_dfs(engine, info, node, count, true, NULL);
        }
        if (info->root->tot_hash_cnt == 0 && info->root->tot_elem_cnt == 0) {
            do_set_node_unlink(engine, info, NULL, 0);
        }
    }
    return node;
}

do_set_elem_traverse_dfs()

for (hidx = 0 ; hidx <SET_HASHTAB_SIZE; hidx++){
  if (node->

}

minzu0306 commented 8 years ago

collection_delete_thread()

#ifdef DELETE_NO_MERGE
     set_hash_node *node = info->root;
#endif

#ifdef DELETE_NO_MERGE
     node = do_set_elem_delete_fast(engine, info, node, 30);

#else
    (void)do_set_elem_delete(engine, info, 30, ELEM_DELETE_COLL);
#endif

do_set_elem_delete_fast()

 static set_hash_node do_set_elem_delete_fast(struct default_engine *engine, set_meta_info *info,
                                            set_hash_node *node, count uint32_t count)
{
    set_hash_node return_node;
    if (info->root != NULL){
        return_node = do_set_traverse_fast(engine, info, node, count);
        if (info->root->tot_hash_cnt == 0 && info->root->tot_elem_cnt == 0) {
             do_set_node_unlink(engine, info, NULL, 0);
             return NULL;
        }
     }
    return return_node;
}

do_set_elem_traverse_fast()

minzu0306 commented 8 years ago

처음 설계한 함수

#ifdef DELETE_NO_MERGE
static *set_hash_node do_set_elem_traverse_fast(struct default_engine *engine, set_meta_info *info,
                                                set_hash_node *node, const uint32_t *count)
{
    int hidx;
    const bool delete = true;
    set_hash_node *tempnode;

    if(node->tot_hash_cnt > 0){
        for (hidx = 0; hidx < SET_HASHTAB_SIZE; hidx++) {
            if (node->hcnt[hidx] == -1) {
                set_hash_node *child_node = (set_hash_node *)node->htab[hidx];
                tempnode = do_set_elem_traverse_fast(engine, info, child_node, count);

                if(child_node->tot_hash_cnt == 0 && child_node->tot_elem_cnt == 0){
                    do_set_node_unlink(engine, info, node, hidx);
                } else {
                    return tempnode;
                }
            }
            if (count == 0){
                if (node->tot_hash_cnt > 0 || node->tot_elem_cnt > 10){
                    return node;
                }else {
                    count = node->tot_elem_cnt;
                }
            }
       }
    }

    for (hidx = 0; hidx < SET_HASHTAB_SIZE; hidx++) {
       if (node->hcnt[hidx] > 0) {
            set_elem_item *elem = node->htab[hidx];
            while (elem != NULL) {
                /* delete element */
                if (delete) do_set_elem_unlink(engine, info, node, hidx, NULL, elem,ELEM_DELETE_NORMAL);

                count -= 1;
                if(count == 0){
                        if (node->tot_elem_cnt > 10 || node->tot_elem_cnt == 0){
                                return &node;
                        } else{
                                count = node->tot_elem_cnt;
                        }
                }
                elem = (delete ? node->htab[hidx] : elem->next);
            }
        }
    }

}

static void do_set_elem_delete_fast(struct default_engine *engine, set_meta_info *info,
                                             set_hash_node *node, const uint32_t count)
{
    set_hash_node *cur_node;
    const  uint32_t *rcnt = &count;
    if (info->root != NULL){
        cur_node = do_set_elem_traverse_fast(engine, info, node, rcnt);
        if(info->root->tot_hash_cnt == 0 && info->root->tot_elem_cnt ==0){
            do_set_node_unlink(engine, info, NULL, 0);
        }
    }
}
#endif

minzu0306 / tasks

[Server] Set collection item delete 성능 개선 #9