Redis data structures - SET

Contents

소프트웨어 프로그래밍에서 가장 먼저 다루는 데이터 스트럭처는 비트, 배열, 스트링, 리스트다. 단순해서 배우고 응용하기 쉽고, 다른 데이터 스트럭처를 이해하기 위한 기본이 되기 때문이다. 단점은 단순한 만큼 응용범위도 넓지 않다는데 있다.

Sets는 좀 더 복잡하고 그 만큼 더 다양한 응용을 할 수 있다.

Sets는 key에 하나 이상의 value를 가지는 데이터 스트럭쳐다. 값은 정렬되지는 않지만 데이터 중복을 허용하지 않는다. SADD 명령으로 key에 value를 추가 할 수 있다. 그리고 SMEMBERS명령으로 value들을 가져올 수 있다. SADD와 SMEMBERS 사용 예제다. java를 두번 add 요청을 했지만 두번째 add 요청은 무시된 걸(반환 갓이 0 이다) 알 수 있다. 여기에서 의문점 List와 뭐가 다른가. ? LPUSH로 값을 입력하고 LRANGE 로 값을 읽는 것과 어떤 차이가 있을까 ?

1. 위 예제로 set은 중복을 허용하지 않는다는 걸 알았다. List는 중복을 허용 한다.
2. List는 삽입 순서에 따라 정렬이 된다. 한편 set은 정렬되지 않는 value의 모음이다. 순서를 유지하지 않는다.

Set도 List와 마찬가지로 string을 저장한다는 점에서 유사점이 있다. 하지만 List와는 달리 해시 테이블을 사용해서 모든 문자열을 고유하게 유지한다. Set은 List와 다르게 순서가 없기 때문에 아이템을 POP 하거나 Push 할 수 없다. 대신 SADD와 SREM을 이용해서 아이템을 추가하거나 삭제한다. 또한 SISMEMBER로 찾는 아이템이 있는지 확인 할 수 있고 SMEMBERS로 전체 아이템 목록을 가져올 수 있다.

시간 복잡도(time Complexity)관점에서 살펴보자. List는 내부적으로 링크드 리스트다. 따라서 List의 크기와 상관 없이 처음과 마지막에 아이템을 추가하는 것은 O(1)이 된다. 하지만 목록의 중간에 있는 아이템을 찾는데는 시간이 걸릴 수 있다. 이 작업은 기본적으로 O(n)이다. 반면 SET은 아이템 추가, 삭제, 확인에 O(1)복잡도를 가진다.

만약 자료구조에 임의의 아이템이 있는지를 확인하는 작업이 요구된다면 List가 아닌 Set을 사용하도록하자. 그밖에 Union, Diff, Intersection 같은 연산을 수행 할 수 있는 것도 장점이다. 가장 큰 장점은 정렬된 set을 만들 수 있다는 점이다. 이 내용은 따로 다루도록 하겠다.

아래는 SET 데이터 스트럭처를 위해서 사용 할수 있는 명령들이다.

명령	설명
SADD	Set에 아이템을 추가한다.
SMEMBERS	Set에 있는 아이템 목록을 가져온다.
SISMEMBER	Set에 아이템이 있는지 확인한다.
SREM	Set에서 아이템을 삭제한다.
SDIFF	첫 번째 set와 나머지 set의 차이를 반환한다.
SUNION	모든 set의 아이템을 반환한다.
SINTER	모든 set에서 공통된 아이템을 반환한다.

온라인 책을 서비스하려고 한다. 태그 기반의 검색&분류 기능을 추가하기로 했다. 책은 하나 이상의 태그를 가질 수 있으며, 사용자는 여러 개의 태그를 조합해서 가장 적합한 책 목록을 확인 할 수 있다. 책 정보는 SET 명령으로 입력하기로 했다.

python과 programming 모두에 태깅된 책을 찾아보자. "Diving into python"과 "Running Python"이 검색됐다.

"python"과 "cloud"에 태깅된 책을 찾아보자.

Redis는 Sorted Set을 지원한다. "정렬을 위한 필드를 제공하고 여기에 정렬 값을 설정하는 것으로 아이템을 정렬 할 수 있다"는 점을 제외하면 set과 동일하다. Sorted set에서의 아이템 추가, 삭제, 확인의 시간 복잡도는 O(1)이다. 하나의 set당 최대 2^32 - 1(약 40억)개의 아이템을 저장 할 수 있다.

ZADD 명령으로 아이템을 삽입할 수 있다.

• NX : 기존 아이템을 업데이트하지 않고 항상 새로운 아이템을 만든다.
• XX : 아이템이 있을 경우 업데이트한다. 절대 아이템을 추가하지 않는다.
• CH : 아이템이 추가 됐을 때, 변경된 아이템의 총수. 예를 들어 이전 아이템과 동일한 score를 추가할 경우 값의 변경이 없기 때문에 0이 반환된다.
• INCR : 기존 score에 새로운 score를 더한다. 카운터를 증가하기 위해서 사용 할 수 있다.

  > ZADD tag 5 programming
  (integer) 1
  > ZADD tag 12 python
  (integer) 1
  > ZADD tag 8 ruby
  (integer) 1
  > ZADD tag 13 aws
  (integer) 1

ZRANGE명령으로 아이템을 가져올 수 있다. tag key에 저장된 아이템을 가져와보자. 아이템은 score를 기준으로 오름차순으로 정렬된다. withscore 옵션을 이용해서 각 아이템의 score도 출력할 수 있다. ZREVRANGE명령을 이용하면 내림차순으로 정렬된 아이템을 얻을 수 있다. Sorted Set을 이용해서, 카테고리별 인기 아이템을 서비스 할 수 있을 것이다. 개인화된 유저 추천 서비스를 만든다고 가정해 보자. 아래 그림을 보자.

유저 id를 key로 해서 방문한 카테고리이름과 방문횟수를 sorted set 형태로 저장을 한다. 간단하게 INCR을 하는 것으로 유저가 선호하는 카테고리 정보를 저장할 수 있을 것이다. 위 그림에서 3210 유저가 선호하는 카테고리는 "beauty"다. 그리고 각 카테고리 별로 인기있는 제품의 sorted set을 만든다. 위 그림에서 "beauty"카테고리의 인기 상품은 Fragrance와 Skincare다 그러므로 3120 유저에게는 Fragrance와 Skincare 제품을 추천하면 될 것이다. 물론 실제 서비스에서는 유저의 나이, 성별, 세부 제품별로 더 정교한 Set을 만들어야 할 것이다.

Set과 Sorted set을 이용해서 친구들간의 연결관계를 나타내는 소셜 그래프를 만들어보자. 아래와 같은 소셜 그래프가 있다고 가정해보자.

1번 유저를 중심으로 하는 소셜 그래프다. 화살표는 팔로잉을 의미한다. 이 그래프는 아래와 같이 설명 할 수 있을 것이다.

1. 1은 2와 3 두명의 팔로워를 두고 있다.
2. 1은 3는 서로를 팔로잉하고 있다. 즉 친구관계다.
3. 4와 5는 친구의 친구이니까 알 수도 있는 사람이 되며, 친구추천의 목적으로 사용 할 수 있을 것이다.

SET을 이용해서 이 구조를 만들어보자.

원하는 결과가 나오는지 테스트해보자.

이제 유저 1에 친구를 추천해보자. 예를 들어 유저 1이 유저 3을 방문했을 때, 그래프상에서 유저 3과 관련이 있는 유저를 추천해주면 될 것이다. 위 예제에서 4와 5를 추천하면 될 거다.

원하는 결과가(1은 자신이니 제외) 나왔다.

REDIS는 Sorted sets 자료구조를 제공한다. 사용자는 ZADD와 ZRANGE를 이용해서 Sorted set에 자료를 넣고 꺼낼 수 있다. ZADD의 사용법은 아래와 같다. Score를 이용해서 Value의 가중치를 설정할 수 있다.

인기 태그(Tag)를 알려주는 서비스를 만든다고 가정하고 테스트를 진행했다.

ZADD로 저장한 데이터는 ZRANGE와 ZREVRANGE로 가져올 수 있다. ZRANGE는 오름차순, ZREVRANGE는 내림차순으로 정렬해서 가져온다. 실 서비스에는 대부분 내림차순일 거다(쇼핑몰 저가 검색이라면 오름차순이겠지만).

ZRANGEBYSCORE명령을 이용해서 정렬된 스코어의 범위 검색이 가능하다. 쇼핑몰의 경우 특정 가격 내에 있는 상품 검색등에 사용 할 수 있을 거다.

ZRANGEBYLEX명령으로 멤버의 이름을 기준으로 범위 검색도 가능하다. 예를들어 "a 에서 ab" 사이에 있는 멤버들 찾을 수 있다.

  Redis Data structure - List 목차 Redis Data structure - Hash