Redis INTSET(정수 배열) of SETS

들어가기

SET의 메인 데이터 구조는 해시 테이블(Hash Table)이지만, 데이터가 정수이고 개수가 비교적 적을 때는 정수 배열 데이터 구조를 사용한다.   정수 배열 데이터 구조는 해시 테이블에 비해 메모리를 적게 사용합니다.   그럼, 정수 배열 데이터 구조가 어떻게 생겼고, 얼마나 메모리를 절약할 수 있는지, 성능은 어떤지 알아봅시다.

정수 구분

정수 배열에는 정수만 입력 가능합니다.   멤버 중 하나라도 정수가 아니면 해시 테이블로 변환됩니다.   여기에서 정수란 어떤 것인지 알아봅시다.

• 1.1 : 실수이므로 정수가 아님.   실수는 정밀도와 차지하는 메모리를 고려할 때 문자 그대로 저장하는 것이 더 나음.
• 01 : 정수 같아 보이나 앞에 0이 있어서 정수가 아님.   정수로 변환하면 원래대로 복원할 수 없어짐.
• 1,234 : 콤마가 있어서 정수가 아님. 이것도 정수로 변환하면 원래대로 복원할 수 없음.
• -1234 : 정수임.
• -1,234 : 정수가 아님.

데이터 구조

정수 배열은 내부적으로 intset으로 칭하며, OBJECT encoding 명령으로 확인하면 intset으로 나온다.   정수 배열(intset)은 헤더 8 바이트와 정수 배열로 구성된다.  구조는 아래 그림과 같다.



• encoding : 4 바이트이고, 2, 4, 8 중 하나의 값을 가집니다.
  저장되는 정수 크기에 따른 바이트 수를 나타냅니다.
  멤버 값이 모두 2 바이트 정수 범위(-32,768 ~ 32,767) 내에 들면 2,
  멤버 값이 모두 4 바이트 정수 범위(-2,147,483,648 ~ 2,147,483,647) 내에 들면 4,
  멤버 값이 모두 8 바이트 정수 범위(-9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807) 내에 들면 8입니다.
  
length : 4 바이트이고, SET의 길이, 즉 멤버 수를 나타냅니다.
• contents : 정수를 배열로 저장합니다.   값의 범위에 따라 2, 4, 8 바이트 정수 배열 중 한 가지로 구성됩니다.  
• SET은 원소의 중복을 허용하지 않기 때문에 Intset은 원소를 소트해서 저장합니다.
• 2 바이트 정수 배열 : 멤버가 4일 경우 헤더 8 바이트 + 2 * 4 = 8 바이트, 총 16 바이트입니다.
  
• 4 바이트 정수 배열 : 멤버가 4일 경우 헤더 8 바이트 + 4 * 4 = 16 바이트, 총 24 바이트입니다.
  16 비트에서는 32767이 최댓값인데, 32768이 입력되면 4 바이트 정수 배열로 바뀐다.   이것을 업그레이드라고 한다.
  
• 8 바이트 정수 배열 : 멤버가 4일 경우 헤더 8 바이트 + 8 * 4 = 32 바이트, 총 40 바이트입니다.
  32 비트에서는 -2147483648이 최솟값인데, -2147483649가 입력되면 8 바이트 정수 배열로 바뀐다.
  
• 정수 배열은 업그레이드는 되지만, 다운그레이드는 되지 않는다.   숫자가 적어졌다고 해서 8 바이트 정수 배열이 4 바이트 정수 배열로 바뀌지는 않는다.   업그레이드는 일반적인 입력 시간보다 수십 배 더 시간이 걸린다.   다운그레이드를 허용한다면 다음과 같은 일이 발생할 것이다.   멤버가 500개이고 나머지 값은 모두 2 바이트 범위 내 정수인데, 한 값만 32767에서 32768로 바뀌고, 다시 32767로 바뀌는 것이 반복되면, 업그레이드와 다운그레이드가 반복되어 서버 부하가 커지고 성능에 매우 악영향을 미칠 것이다.   이것을 파닥거림 효과(flapping effect)라고 하는데, 이러한 이유 때문에 다운그레이드는 허용하지 않는다.

메모리 사용량 테스트

네 종류(16, 32, 64 비트 이내 범위 정수와 문자열)의 데이터 1000개를 입력했다.


INT16 :             2,144 bytes
INT32 :             4,192 bytes
INT64 :             8,288 bytes
Hash Table : 88,352 bytes
위 표와 그래프에서 보는 것처럼 intset(정수 배열)에 입력했을때가 해시 테이블에 입력했을때보다, 훨씬 메모리를 절약한다.   해시 테이블은 INT64와 비교해도 10배 정도 더 메모리를 사용한다.   가능하면 데이터를 정수로 입력하면 메모리 절약에 효과적일 것이다.

성능 테스트

정수 배열(intset) 성능 테스트를 위해서 데이터를 세 종류로 구분해서 입력했다.
• 지속적으로 증가하는 데이터, 예: 1,2,3,...
• 랜덤 데이터, 예: 13,-6,0,...
• 지속적으로 감소하는 데이터, 예: 100,99,98,...


세로 단위: microseconds, 레디스 서버 내부 처리 시간
증가하는 경우가 가장 시간이 적게 걸리고, 랜덤, 감소 순으로 처리시간이 더 걸린다.   왜일까?   하나씩 살펴보자.

• 초기 상태의 정수 배열
  
  
• SADD key 8 : 배열 크기 증가와 입력 2 step으로 이루어진다.
  
  
• SADD key 3 : 배열 크기 증가, 값 이동, 입력 이렇게 3 step으로 이루어진다.   입력되는 값이 중간에 위치하므로 값 이동이 2개 발생했다.   이것이 랜덤 데이터에 해당한다.
  
  
• SADD key -2 : 배열 크기 증가, 값 이동, 입력 이렇게 3 step으로 이루어진다.   입력되는 값이 맨 앞에 위치하므로 값 이동이 4개 발생했다.   즉, 입력할 때마다 기존 입력된 값을 모두 이동해야 하므로 처리시간이 오래 걸린다.   이것이 지속적 감소 데이터에 해당한다.
  
  
그러므로 정수 배열(intset)을 사용할 때는 증가하는 값을 사용하는 것이 성능에 좋다.
• 메모리의 효율적인 이용과 성능을 생각할 때 가능한 한 정수를 사용하는 것이 좋겠습니다.
  멤버 수에 따라 정수 배열(intset)이 사용될지, 해시 테이블이 사용될지는 redis.conf에 파라미터 set-max-intset-entries으로 정해집니다.   기본값(default)는 512입니다.   필요에 따라 적당히 큰 값을 설정해서 사용해도 좋습니다.

관련 functions

흐름을 파악하기 쉽게 하기 위해 일부 펑션은 중복해서 표현했고, intset 펑션 위주로 표시했다.



특이하게 smembers 명령은 t_set.c에 없고 redis.c에서 sinterCommand를 바로 호출한다.


아래는 SADD 명령 내부 흐름을 좀 자세히 분석해 놓은 그림이다.

• lookupKeyWrite는 글로벌 펑션으로 키가 있는지 확인해서 있으면 리턴하고 없으면 생성한다.
• setTypeCreate은 값이 정수이고 set-max-intset-entries 이하면 intset을 생성하고, 아니면 해시 테이블을 생성한다.   이미 있으면 생성하지 않는다.
• tryObjectEncoding는 글로벌 펑션으로 값(value)를 정수로 변환하는 기능을 한다.
• setTypeAdd는 값을 입력하는 펑션으로 정수일 경우 intsetAdd를 호출한다.
• _intsetValueEncoding은 값의 크기에 따라 몇 바이트가 필요한지 리턴한다.
• intsetUpgradeAndAdd는 인코딩된 값의 범위보다 크면 업그레이드를 하고 값을 넣는다.
• _intsetSearch는 현재 SET에 값이 있는지 찾아서 위치를 리턴한다.
• _intsetResize는 zrealloc()으로 배열을 늘린다.
• intsetMoveTail은 값을 하나씩 옮긴다..
• _intsetSet는 값을 넣는다. 들어갈 위치와 공간은 앞의 펑션들에서 이미 얻었고, 확보했다.
• 위 세 개 펑션이 성능 테스트에서 설명했던 step 1 Resize, step 2 Move values, step 3 Set value에 해당한다.