Mingyu Kim

Set - InSet

1. 오직 “정수”만을 위한 초슬림 구조

SADD myset 10 20 30처럼 오직 정수 데이터만 넣는다면, 레디스는 비싼 Hash Table대신 IntSet이라는 특수한 배열 구조를 사용한다.

• 구조
  • Encoding (4바이트): 현재 배열이 몇 비트인지 정보를 저장
  • Length (4바이트): 배열에 담긴 정수의 총 개수
  • Contents: 실제 정수들이 오름차순으로 정렬되어 들어있는 공간. 포인터가 전혀 없는 순수 데이터 배열
• 특징: 모든 데이터를 정렬된 상태로 메모리에 다닥다닥 붙여서 저장
• 메모리 효율: Hash Table은 각 노드마다 포인터와 메타데이터가 붙어 메모리 소모가 크지만, IntSet은 딱 정수값 자체의 크기만큼만 사용

2. 업그레이드

처음부터 64비트(8바이트) 정수 공간을 할당하지 않고, 데이터의 크기에 따라 인코딩을 동적으로 바꾼다.

• NTSET_ENC_INT16: 모든 숫자가 2바이트 안에 들어오면 2바이트 배열로 관리
• INTSET_ENC_INT32: 4바이트가 필요한 숫자가 들어오는 순간, 전체 배열을 4바이트 단위로 확장
• INTSET_ENC_INT64: 8바이트가 필요한 숫자가 들어오면 전체를 8바이트 단위로 확장

한 번 커진 인코딩은 데이터가 삭제되어도 다시 작아지지는 않는다. (메모리 재할당 비용 때문)

3. 왜 정렬해서 저장할까?

IntSet은 Hash Table이 아니기 때문에 O(1) 조회가 불가능하다. 대신 데이터가 정렬되어 있어 이진 탐색을 사용하여 O(log N)의 속도로 데이터를 찾는다.

데이터가 수천 개 이하일 때는 메모리 로컬리티(CPU 캐시 효율) 덕분에 Hash Table보다 훨씬 효율적이다.

3. 언제 HashTable로 바뀌나?

아래 두 상황 중 하나라도 발생하면 바뀐다.

• 문자열 삽입: SADD myset "hello"처럼 정수가 아닌 값이 하나라도 들어오는 순간
• 개수 초과: 설정된 임계치(set-max-intset-entries, 기본값 512개)를 넘어서는 순간