child prefixes 관리 구조 개선 - skip list 사용

[jhpark816]

child prefixes 관리 구조를 개선한다.

기존 구조

• prefix hash table에 child prefixes도 함께 연결하여 관리하고 있다.
• 이로 인한 이슈는
  • 최상위 prefix 탐색 시 child prefixes 포함하여 탐색하게 되므로 탐색 비용이 커지며, 탐색 시에 child prefixes를 제외하는 로직을 가져야 한다.
  • 최상위 prefix 제거 시에 child prefixes도 함께 제거해야 한다. 이 경우, prefix hash table의 모든 prefixes를 탐색해야 하는 부담이 있다.
  • 많은 수의 child prefixes가 생성되면, prefix hash table 탐색 비용이 커지며, prefix hash table 확장이 고려되어야 한다.

개선 구조

• prefix hash table에는 최상위 prefixes 들만 연결하여 관리한다.
• 최상위 prefix에 속하는 child prefixes들을 skip list로 관리하며, 최상위 prefix에서 skip list를 접근하도록 한다.
• 따라서,
  • 최상위 prefix 탐색은 prefix hash table을 탐색하면 된다.
  • 특정 최상위 prefix의 child prefixes는 그 prefix에 포함된 skip_list를 탐색하여 접근할 수 있다.
  • 최상위 prefixes만 prefix hash table에 연결되므로, prefix hash table 확장을 고려하지 않아도 된다.
• 참고로, 특정 child prefix 조회는 prefix hash table 탐색 외에 skip list 탐색 부담이 있지만 무시할 만한 정도이다.

[matteblack9]

@jhpark816 skip list로 구현하기 전 고려해야할 점이 몇 가지 있습니다.

1. skip list의 노드 중 p^i 개는 i개의 포인터를 가지게 되는데, 삽입되는 노드의 포인터 개수를 결정하는 p라는 확률분포를 무엇으로 지정해야하는가 하는 논의점이 있습니다. 일반적으로는, p = 1/2일 때 속도가 가장 빠르지만, 속도와 메모리 효율을 고려했을 때 p = 1/4 로 하는 경우도 있습니다. child prefix개수의 경우, 제 생각에는 매우 많아질 것 같지는 않아서 p = 1/2 로 설정해도 괜찮을 것 같습니다.

2. 1과 관련된 문제점인데요,

   static int _rand_level() 
   { 
   float r = (float)rand()/RAND_MAX; 
   int lvl = 0; 
   while (r < P && lvl < MAXLVL) 
   { 
       lvl++; 
       r = (float)rand()/RAND_MAX; 
   } 
   return lvl; 
   }; 

   라는 스킵리스트 노드의 포인터 개수를 결정하는 함수가 있다고 가정할 때, rand()를 사용할 때, 시드값 설정 함수 인자로 무엇을 주어야하는지 결정해야될 것 같습니다. 일반적으로 시드값으로 시간값을 주는 데, 시드값으로 시간값을 줘도 상관이 없을까요?

3. skip list의SKIPLIST_MAX_LEVEL 을 정해야 합니다. 어느 정도 크기가 적당할까요?

[dongwooklee96]

저도 b+tree 컬렉션에서 sorted set을 구현하는데 #480 skip list로 구현하려고 하고 있습니다. 혹시 이번 이슈와 공통된 내용이 있다면 같이 논의해도 될까요?

[jhpark816]

@HarryKim93 @dongwooklee96 오늘 바쁜 일들이 많아 확인하지 못했는 데, 조만간 확인하고 의견을 달도록 하겠습니다.

[jhpark816]

@HarryKim93 의견입니다.

• p = 1/4로 하면 좋겠습니다.
  • 매크로 or 상수 변수로 설정을 변경할 수 있으면 좋겠습니다.
  • 향후에 1/2와 1/4인 경우를 비교해 볼 수 있습니다.
• random value generator
  • 시간 값을 seed 값으로 주도록 하시죠.
  • rand() vs. random() 검토하여 적절한 함수를 사용 바랍니다.
• SKIPLIST_MAX_LEVEL
  • 8 정도이면 충분할 것 같습니다.
  • 이 값도 매크로 or 상수 변수로 설정을 변경할 수 있으면 됩니다.
• 기타
  • prefix max length가 크지 않기 때문에 prefix_t 구조체에 고정 크기의 name 필드를 추가할 까 생각합니다.
  • 향후 검토해 보고, 진행하겠습니다.

@dongwooklee96 계속 신경 쓰고 있었군요. sorted set에 관해서는 현 시점에서 다시 검토해 보고 의견을 드리겠습니다. 혹시 많이 진행된 상태인가요 ?

[dongwooklee96]

@jhpark816 아니요 많이 진행하지는 않았습니다. 이제 막 분석하는 단계입니다.

[jhpark816]

@dongwooklee96 다행입니다. sorted set에 관해 이슈 https://github.com/naver/arcus-memcached/issues/480 에 의견을 남겨 두었으므로 확인해 주기 바랍니다.