레디스 콜렉션

이번 포스트에서는..

저번 포스트에서는 기본적인 데이터 타입을 설명했다. 이번 포스트에선 한발 더 나아가 Set, Sorted Set, Bitmap, Hyperloglog 데이터 타입을 살펴보려 한다.

이 글은 레디스 기본 데이터 타입 포스트와 이어집니다.

Sets

셋은 스트링과는 구분되는 순서가 없는 콜렉션이다. 중복되는 원소를 셋에 집어넣을수 없으며 내부적으로 해쉬테이블처럼 구현됐다. 이러한 이유는 최적화 때문인데, 멤버 추가, 삭제, 서치 등의 시간이 \(O(1)\)에 실행되기 때문이다.

셋의 메모리 footprint?는 모든 멤버가 정수일 경우 줄일 수 있다. 멤버 최종 수는 set-max-inset-entries에 의존하며 이는 챕터 4에서 추후 설명하겠다.

원소 개수는 \(2^{32} -1\)이며 40억개 저장 가능하다.

아래는 Sets의 사용 사례다.

• 데이터 필터링: 예를들어 특정 도시에서 출발하여 다른 도시에 도착하는 지정된 항공편을 필터링 할 수 있다.
• 데이터 그루핑: 비슷한 제품을 본 모든 사용자를 그룹핑(아마존의 추천 시스템)
• 멤버쉽 체킹: 블랙리스트에 존재하는지를 확인.

SADD

SADD는 하나 혹은 그 이상의 멤버를 추가하기 위한 커맨드다. 만약 추가하려는 멤버가 존재할 경우 이를 기각하고, 추가된 멤버 수를 리턴한다.

$ redis-cli
127.0.0.1:6379> SADD user:max:favorite_artists "Arcade Fire" "Arctic Monkeys"
"Belle & Sebastian" "Lenine"
(integer) 4
127.0.0.1:6379> SADD user:hugo:favorite_artists "Daft Punk" "The Kooks" "Arctic
Monkeys"
(integer) 3

SINTER

SINTER 커맨드는 하나 혹은 그 이상의 셋을 받고, 모든 셋에 공통적으로 존재하는 멤버를 배열로 리턴한다.

아래 예제는 Hugo와 Max가 공통적으로 좋아하는 아티스트를 보여준다.

127.0.0.1:6379> SINTER user:max:favorite_artists user:hugo:favorite_artists
1) "Arctic Monkeys"

SDIFF

SDIFF 커맨드는 하나 혹은 그 이상의 셋을 받는다. 뒤에 따라오는 셋에 존재하지 않는 모든 멤버를 리턴한다. 이 커맨드는 키 네임의 순서가 중요하다. 존재하지 않는 모든 키는 빈 집합으로 간주된다.

127.0.0.1:6379> SDIFF user:max:favorite_artists user:hugo:favorite_artists
1) "Belle & Sebastian"
2) "Arcade Fire"
3) "Lenine"

두 번째 예제는 user:max:favorite_artists의 존재하지 않는 user:hugo:favorite_artists의 멤버를 모두 리턴한다.

127.0.0.1:6379> SDIFF user:hugo:favorite_artists user:max:favorite_artists
1) "Daft Punk"
2) "The Kooks"

SUNION

SUNION 커맨드는 하나 혹은 그 이상의 셋을 받는다. 모든 셋의 모든 멤버를 리턴한다. 중복되는 멤버는 한 번만 보여준다.

127.0.0.1:6379> SUNION user:max:favorite_artists user:hugo:favorite_artists
1) "Lenine"
2) "Daft Punk"
3) "Belle & Sebastian"
4) "Arctic Monkeys"
5) "Arcade Fire"
6) "The Kooks"

SPANDMEMBER

SPNADMEMBER는 주어진 셋에 랜덤한 멤버를 리턴한다. 셋은 순서가 없기 때문에 위치 인덱스 값으로 반환할 수 없다.

127.0.0.1:6379> SRANDMEMBER user:max:favorite_artists
"Arcade Fire"
127.0.0.1:6379> SRANDMEMBER user:max:favorite_artists
"Lenine"

SISMEMBER, SREM, SCARD, SMEMBERS

SISMEMBER는 멤버가 셋 안에 존재하는지 확인한다. 존재할 경우에는 1, 아닐 경우에는 0을 리턴한다.

SISMEMBERS는 셋에 존재하는 모든 멤버를 리턴한다.

SREM은 멤버를 셋에서 삭제하고 인티저 값을 리턴한다.

SCARD는 멤버의 수를 리턴한다.

127.0.0.1:6379> SISMEMBER user:max:favorite_artists "Arctic Monkeys"
(integer) 1
127.0.0.1:6379> SREM user:max:favorite_artists "Arctic Monkeys"
(integer) 1
127.0.0.1:6379> SISMEMBER user:max:favorite_artists "Arctic Monkeys"
(integer) 0
127.0.0.1:6379> SCARD user:max:favorite_artists
(integer) 3
127.0.0.1:6379> SMEMBERS user:max:favorite_artists
1) "Belle & Sebastian"
2) "Arcade Fire"
3) "Lenine"

Sorted Sets

Sorted Set 은 Set과 매우 흡사하다. 하지만 각 멤버들이 연관된 스코어를 가지고 있다. 다른 말로 하자면, Sorted Set은 중복된 멤버를 가지지 않고, 스코어에의해서 정렬된 Strings다. 스코어는 중복될 수 있다. 이러한 경우에는 lexicographically하게 정렬한다.

Sorted Set 작업은 매우 빠르지만 Set의 작업보단 빠르지 않다. 추가, 삭제 갱신은 \(O(logN)\)이 걸린다. 내부적으로 Sorted Set은 두 개의 자료구조로 나뉘어져 있다.

• skip list with hash table 스킵 리스트는 정렬된 원소 시퀀스를 빠르게 탐색하기 위한 자료구조다.
• zset-max-ziplist-entries 과 zset-max-ziplist-value에 기반한 ziplist 이는 챕터 4에서 다루도록 한다.

아래는 Sorted Set의 사용사례다.

• 웨이팅 리스트
• 온라인 게임과 같은 곳에 리더보드
• 자동완성 시스템

ZADD

ZADD는 하나 혹은 그 이상 멤버를 Sorted Set에 추가한다. 이미 Sorted Set에 존재하는 멤버일 경우에는 요청을 무시한다. 추가된 멤버를 정수 값으로 반환한다.

$ redis-cli
127.0.0.1:6379> ZADD leaders 100 "Alice"
(integer) 1
127.0.0.1:6379> ZADD leaders 100 "Zed"
(integer) 1
127.0.0.1:6379> ZADD leaders 102 "Hugo"
(integer) 1
127.0.0.1:6379> ZADD leaders 101 "Max"
(integer) 1

Sorted Set에 멤버는 스코어와 문자열로 추가된다. 앞에서도 설명했듯이 두가지 정렬 기준이 존재하는데, 스코어 순으로 정렬하며, 만약 스코어가 같을 경우에는 멤버의 문자열 값을 lexicographically하게 정렬한다. 앞 예제에서는 Alice와 Zed가 같은 스코어를 가지기 때문에, 알파벳 순으로 정렬된다.

ZRANGE, ZREVRANGE ~ WITHSCORES

ZRANGE는 주어진 범위에 해당되는 멤버를 출력하며, 오름차순으로 출력한다.

ZREVRANGE는 주어진 범위에 해당되는 멤버를 출력하며, 내림차순으로 출력한다.

위 두 커맨드에 WITHSCORES를 옵션 파라미터로 줄 수 있으며, 스코어를 같이 출력하게 된다.

127.0.0.1:6379> ZREVRANGE leaders 0 -1 WITHSCORES
1) "Hugo"
2) "102"
3) "Max"
4) "101"
5) "Zed"
6) "100"
7) "Alice"
8) "100"

127.0.0.1:6379> ZREVRANGE leaders 0 -1
1) "Hugo"
2) "Max"
3) "Zed"
4) "Alice"

ZREM

ZREM은 멤버를 지운다.

127.0.0.1:6379> ZREM leaders "Hugo"
(integer) 1
127.0.0.1:6379> ZREVRANGE leaders 0 -1
1) "Max"
2) "Zed"
3) "Alice"

ZSCORE, ZRANK, ZREVRANK

ZSCORE는 특정 멤버에 스코어를 반환한다.

ZRANK는 특정 멤버에 랭크(인덱스)를 반환한다.

ZREVRANK 는 특정 멤버에 랭크를 high to low 방향에서 인덱스를 반환한다.

127.0.0.1:6379> ZSCORE leaders "Max"
"101"
127.0.0.1:6379> ZRANK leaders "Max"
(integer) 2
127.0.0.1:6379> ZREVRANK leaders "Max"
(integer) 0

Bitmap

비트맵이 실제 데이터 타입은 아니고, 스트링이다. 스트링에 비트 오퍼레이션을 진행하기 위해 만들어진 데이터 타입이라 볼 수 있다. 레디스에선 이를 조작할 수 있는 커맨드들을 제공하기에 데이터 타입으로 취급한다.

Bitmap은 0과 1을 저장할 수 있는 비트 시퀀스이다. 레디스 공식 문서에서 비트맵에 인덱스는 offset으로 불린다.

비트맵이 메모리를 어떻게 효율적으로 사용하는지 알기위해선 Set과 비교해볼 필요가있다.

Comparison Scenario

만약 5백만명의 사용자가 존재하고, 하루에 2백만명 정도의 사용자가 웹사이트에 접속한다고 가정하자. 이때 사용자 아이디는 4byte 정수값으로 표현된다.

웹사이트에 당일 접속한 모든 유저의 아이디를 저장하는 기능을 구현한다하면, (비트맵에선 오프셋이 유저의 아이디를 매핑할 것이다) 이러한 상황에서 두 자료구조는 아래와 같은 구현 스펙이 결정된다.

Redis Key	Data type	Amount of bits per user	Stored users	Total memory
visits:2015-01-01	Bitmap	1 bit	5 million	1 * 5000000 bits = 625kB
visits:2015-01-01	Set	32 bit	2 million	32 * 2000000 bits = 8MB

최악의 상황에서도 비트맵은 Set보다 괜찮은 메모리 효율을 보여주고 있다. 하지만 그렇다고해서 항상 비트맵이 효율적이라고 단정지을 순 없다. 아래 테이블을 보자.

Redis Key	Data type	Amount of bits per user	Stored users	Total memory
visits:2015-01-01	Bitmap	1 bit	5 million	1 * 5000000 bits = 625kB
visits:2015-01-01	Set	32 bit	100	32 * 100 bits = 3.125KB

비트맵은 실시간 분석에 사용하기 적합한 자료구조이다. 예를들어, 사용자 X가 Y를 얼마나 행했는가에 대한 질문 혹은 얼마나 많은 유저가 Y라는 이벤트를 행했는지 확인할 수있다. 아래는 Bitmap에 대한 사용 예시다.

• 얼마나 많은 사람이 오늘 이 블로그 포스트를 봤는가?
• 특정 유저 1이 오늘 이 블로그를 읽었는가?

SETBIT

SETBIT는 특정 비트맵에 있는 오프셋을 설정한다. 1과 0만을 값으로 받으며, 만약 존재하지 않을 경우 생성한다.

127.0.0.1:6379> SETBIT visits:2015-01-01 10 1
(integer) 0
127.0.0.1:6379> SETBIT visits:2015-01-01 15 1
(integer) 0
127.0.0.1:6379> SETBIT visits:2015-01-02 10 1
(integer) 0
127.0.0.1:6379> SETBIT visits:2015-01-02 11 1
(integer) 0

GETBIT

GETBIT는 특정 비트맵에 있는 오프셋을 가져온다.

127.0.0.1:6379> GETBIT visits:2015-01-01 10
(integer) 1
127.0.0.1:6379> GETBIT visits:2015-01-02 15
(integer) 0

BITCOUNT

BITCOUNT는 특정 비트맵에 1로 설정된 오프셋의 개수를 반환한다. 현재 예제에서는 당일 날 접속한 사용자가 몇명인지 반환한다.

127.0.0.1:6379> BITCOUNT visits:2015-01-01
(integer) 2
127.0.0.1:6379> BITCOUNT visits:2015-01-02
(integer) 2

BITTOP

BITOP는 비트 연산을 수행하며 이에 대한 결과값을 저장할 destination key가 필요하다. 비트 오퍼레이션에는 OR, AND, XOR, AND 등이 있다.

127.0.0.1:6379> BITOP OR total_users visits:2015-01-01 visits:2015-01-02
(integer) 2
127.0.0.1:6379> BITCOUNT total_users
(integer) 3

HYperloglogs

Hyperloglog 또한 실제 데이터타입은 아니다. 개념적으로 Hyperloglog는 Set에 존재하는 unique element의 Cardinality 근사값을 제공하는 데에 효과적인 알고리즘이다.

\(O(1)\), 상수시간안에 이를 해결하며, 메모리 사용량도 매우 적기 때문에 효과적이다. 실제 데이터타입은 아니지만, 레디스에서 Hyperloglog를 사용하여 Set에 Cardinality를 계산 하기위해 String을 조작하는 커맨드를 제공한다.

하지만, Hyperloglog 사용할 때 알아둬야 할 것은 이 알고리즘은 확률적 알고리즘으로써 정확도가 100퍼센트는 아닌, 근사값을 예측하는 알고리즘이라는 것이다. Redis에서는 기본적으로 0.81퍼센트의 오차가 있다고 말한다.

알고리즘에 대한 설명은 HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm 에서 확인할 수 있다.

아래는 HyperLogLog에 사용 예시다.

• 웹사이트를 방문한 특정 유저의 수.
• 특정 시간 혹은 날짜에 나의 사이트에서 검색된 용어 개수
• 해쉬태크 개수
• 이 포스트에서 사용된 구별가능한 단어 개수

Countiong unique users - Hyperloglog vs Set

시간당 평균 10만명에 사용자가 접속한다고 하자. 각각의 사용자는 UUID(universally unique identifier)와 같은 32바이트 스트링(ex: de305d54-75b4-431b-adb2-eb6b9e546014)으로 특정된다.

Data type	Memory in an hour	Memory in a day	Memory in a month
HyperLogLog	12 kb	12 kB * 24 = 288 kB	288 kB * 30 = 8.4 MB
Set	32 bytes * 100000 = 3.2 MB	3.2 MB * 24 = 76.8 MB	76.8 MB * 30 = 2.25 GB

HyperLogLog는 시간당 특정 사용자가 접속한지 확인하기 위해 저장매체의 용량이 12kb 밖에 안된다.

PFADD

PFADD는 하나 혹은 그 이상의 스트링을 입력받으며, cardinality가 변경되었을 경우 1 아닐경우 0을 반환한다.

$ redis-cli
127.0.0.1:6379> PFADD visits:2015-01-01 "carl" "max" "hugo" "arthur"
(integer) 1
127.0.0.1:6379> PFADD visits:2015-01-01 "max" "hugo"
(integer) 0
127.0.0.1:6379> PFADD visits:2015-01-02 "max" "kc" "hugo" "renata"
(integer) 1

PFCOUNT

PFCOUNT는 하나 혹은 그 이상의 키를 받으며, 인자가 하나일 경우에는 approximate cardinality를 반환한다. 키가 여러 개일 경우 총 합을 반환한다.

127.0.0.1:6379> PFCOUNT visits:2015-01-01
(integer) 4
127.0.0.1:6379> PFCOUNT visits:2015-01-02
(integer) 4
127.0.0.1:6379> PFCOUNT visits:2015-01-01 visits:2015-01-02
(integer) 6

PFMERGE

PFMERGE는 destination key를 필요로 하며, 하나 혹은 그 이상의 키를 인자로 받아야 한다. 특정 Hyperloglog를 모두 저장한 값을 리턴한다.

127.0.0.1:6379> PFMERGE visits:total visits:2015-01-01 visits:2015-01-02
OK
127.0.0.1:6379> PFCOUNT visits:total
(integer) 6

Refernce

• Maxwell Dayvson Da Silva, Redis Essentials