보조 인덱싱(Secondary Indexing)

Redis에서 보조 인덱스를 만드는 방법을 다뤄요. Redis는 값이 복잡한 데이터 구조일 수 있어서 "그냥 키-값 저장소"는 아니지만, API 수준에서는 데이터가 키 이름으로 다뤄지는 외부적 키-값 껍질을 가져요. 네이티브하게 Redis는 *기본 키 접근(primary key access)*만 제공한다고 볼 수 있어요. 하지만 Redis는 데이터 구조 서버이므로, 그 능력을 인덱싱에 활용해 여러 종류의 보조 인덱스(복합/다중 컬럼 인덱스 포함)를 만들 수 있어요.

출처: https://redis.io/docs/latest/develop/clients/patterns/indexes/

이 문서는 다음 데이터 구조를 써서 Redis에서 인덱스를 만드는 방법을 설명해요.

다양한 필드 타입을 쓰는 해시와 JSON 문서. Redis Search와 함께 사용.
ID나 다른 숫자 필드로 보조 인덱스를 만드는 sorted sets.
더 고급 보조 인덱스, 복합 인덱스, 그래프 탐색 인덱스를 만드는 사전식(lexicographical) 범위의 sorted sets.
랜덤 인덱스를 만드는 sets.
간단한 반복 인덱스와 마지막 N개 항목 인덱스를 만드는 lists.
라벨이 있는 time series.

Redis로 인덱스를 구현하고 유지하는 것은 고급 주제라, 데이터에 복잡한 쿼리를 수행해야 하는 대부분의 사용자는 관계형 저장소가 더 나은지 이해해야 해요. 하지만 종종, 특히 캐싱 시나리오에서, 일종의 인덱싱이 필요한 일반 쿼리를 빠르게 하기 위해 인덱스된 데이터를 Redis에 저장할 명시적 필요가 있어요.

해시와 JSON 인덱스

Redis Search는 다양한 필드 타입으로 해시와 JSON 키를 모두 인덱싱하고 쿼리할 수 있는 능력을 제공해요.

TEXT
TAG
NUMERIC
GEO
VECTOR
GEOSHAPE

FT.CREATE 명령으로 해시나 JSON 키를 인덱싱한 뒤, 인덱스에 정의된 접두사를 쓰는 모든 키는 FT.SEARCH와 FT.AGGREGATE 명령으로 쿼리할 수 있어요.

해시와 JSON 인덱스 생성에 관한 자세한 내용은 다음 페이지를 참조하세요.

sorted sets로 만드는 간단한 숫자 인덱스

Redis로 만들 수 있는 가장 간단한 보조 인덱스는 sorted set 데이터 타입을 쓰는 거예요. 이는 각 요소의 score인 부동 소수점 숫자로 정렬된 요소 집합을 나타내는 데이터 구조예요. 요소는 가장 작은 score부터 가장 큰 score 순으로 정렬돼요.

score는 배정밀도(double precision) 부동 소수점이므로, 바닐라 sorted sets로 만들 수 있는 인덱스는 인덱싱 필드가 주어진 범위 내의 숫자인 것들로 제한돼요.

이런 종류의 인덱스를 만드는 두 명령은 ZADD와, 항목을 추가하고 지정된 범위 내 항목을 가져오기 위한 BYSCORE 인자를 가진 ZRANGE예요.

예를 들어, 사람 이름 집합을 나이별로 인덱싱할 수 있어요. sorted set에 요소를 추가하는데, 요소는 사람 이름이고 score는 나이가 돼요.

ZADD myindex 25 Manuel
ZADD myindex 18 Anna
ZADD myindex 35 Jon
ZADD myindex 67 Helen

나이가 20에서 40 사이인 모든 사람을 가져오려면 다음 명령을 쓸 수 있어요.

ZRANGE myindex 20 40 BYSCORE
1) "Manuel"
2) "Jon"

ZRANGE의 WITHSCORES 옵션을 쓰면 반환된 요소와 연결된 score도 얻을 수 있어요.

ZCOUNT 명령은 요소를 실제로 가져오지 않고 주어진 범위 내 요소 수를 가져오는 데 쓸 수 있어요. 특히 이 연산이 범위 크기와 무관하게 로그 시간에 실행된다는 점에서 유용해요.

범위는 포함( inclusive) 또는 제외(exclusive)일 수 있어요. 자세한 내용은 ZRANGE 명령 문서를 참조하세요.

메모: ZRANGE를 BYSCORE와 REV 인자와 함께 쓰면 범위를 역순으로 쿼리할 수 있어요. 데이터가 특정 방향(오름차순 또는 내림차순)으로 인덱스되어 있을 때 반대로 정보를 가져오고 싶을 때 자주 유용해요.

객체 ID를 연결된 값으로 사용하기

위 예시에서는 이름을 나이에 연결했어요. 하지만 일반적으로는 다른 곳에 저장된 객체의 어떤 필드를 인덱싱하고 싶을 수 있어요. sorted set 값을 직접 사용해 인덱싱된 필드와 연결된 데이터를 저장하는 대신, 객체의 ID만 저장할 수 있어요.

예를 들어 사용자를 나타내는 Redis 해시가 있다고 해볼게요. 각 사용자는 ID로 직접 접근 가능한 단일 키로 표현돼요.

HMSET user:1 id 1 username antirez ctime 1444809424 age 38
HMSET user:2 id 2 username maria ctime 1444808132 age 42
HMSET user:3 id 3 username jballard ctime 1443246218 age 33

사용자를 나이별로 쿼리하는 인덱스를 만들고 싶다면 이렇게 할 수 있어요.

ZADD user.age.index 38 1
ZADD user.age.index 42 2
ZADD user.age.index 33 3

이번에는 sorted set에서 score와 연결된 값이 객체의 ID예요. 그래서 ZRANGE에 BYSCORE 인자로 인덱스를 쿼리하면, 필요한 정보를 HGETALL이나 유사한 명령으로 다시 가져와야 해요. 명백한 장점은 인덱싱된 필드를 바꾸지 않는 한, 객체가 바뀌어도 인덱스를 건드릴 필요가 없다는 거예요.

다음 예시에서 우리는 거의 항상 인덱스와 연결된 값으로 ID를 쓸 거예요. 보통 이쪽이 더 타당한 설계기 때문이에요(몇 가지 예외 있음).

간단한 sorted set 인덱스 갱신하기

시간이 지나면서 변하는 것을 인덱싱하는 경우가 많아요. 위 예시에서 사용자의 나이는 매년 바뀌어요. 그런 경우 나이 자체 대신 생년월일을 인덱스로 쓰는 것이 이치에 맞지만, 어떤 필드는 때때로 바뀌고 인덱스가 이 변화를 반영하기를 원하는 경우도 있어요.

ZADD 명령은 같은 값에 다른 score로 요소를 다시 추가하면 단순히 score를 갱신하고 요소를 올바른 위치로 옮기기 때문에, 간단한 인덱스 갱신을 아주 사소하게 만들어줘요. 그래서 사용자 antirez가 39세가 되었다면, 사용자 해시의 데이터와 인덱스 둘 다 갱신하기 위해 다음 두 명령을 실행하면 돼요.

HSET user:1 age 39
ZADD user.age.index 39 1

이 연산은 두 필드가 모두 갱신되거나 아무것도 갱신되지 않도록 MULTI/EXEC 트랜잭션으로 감쌀 수 있어요.

다차원 데이터를 선형 데이터로 바꾸기

sorted sets로 만든 인덱스는 단일 숫자 값만 인덱싱할 수 있어요. 그래서 이런 인덱스로 다차원적인 것을 인덱싱하는 것은 불가능하다고 생각할 수 있지만, 항상 그런 건 아니에요. 다차원적인 것을 효율적으로 선형으로 표현할 수 있다면, 단순한 sorted set으로 인덱싱하는 것이 종종 가능해요.

예를 들어 Redis geo 인덱싱 API는 Geo hash라는 기법으로 위치를 위도·경도별로 인덱싱하는 데 sorted set을 써요. sorted set의 score는 경도와 위도의 비트를 번갈아 나타내므로, sorted set의 선형 score를 지구 표면의 많은 작은 사각형에 매핑해요. 8+1 방식의 중심과 이웃 탐색을 하면 반경으로 요소를 가져올 수 있어요.

score의 한계

sorted set 요소의 score는 배정밀도 부동 소수점이에요. 내부적으로 지수 표현을 사용하므로 서로 다른 십진수나 정수 값을 서로 다른 오차로 표현할 수 있어요. 하지만 인덱싱에 흥미로운 것은 score가 항상 -9007199254740992과 9007199254740992 사이(즉 -/+ 2^53)의 숫자를 오류 없이 표현할 수 있다는 점이에요.

훨씬 큰 숫자를 표현할 때는 사전식 인덱스(lexicographical index)라고 하는, 어떤 정밀도의 숫자도 인덱싱할 수 있는 다른 형태의 인덱싱이 필요해요.

시계열 인덱스(Time series indexes)

TS.CREATE 명령으로 새 시계열을 만들 때, 하나 이상의 LABELS를 연결할 수 있어요. 각 라벨은 이름-값 쌍이며, 이름과 값 모두 텍스트예요. 라벨은 다양한 시계열 명령으로 시계열 키 그룹에 쿼리를 실행할 수 있게 해주는 보조 인덱스 역할을 해요.

라벨로 시계열을 만드는 예시는 time series quickstart guide를 참조하세요.

TS.MGET, TS.MRANGE, TS.MREVRANGE 명령은 지정된 라벨이나 라벨 관련 필터 표현식을 기준으로 여러 시계열에서 동작해요. TS.QUERYINDEX 명령은 주어진 라벨 관련 필터 표현식과 일치하는 모든 시계열 키를 반환해요.

사전식 인덱스(Lexicographical indexes)

Redis sorted sets에는 흥미로운 속성이 있어요. 요소가 같은 score로 추가되면 문자열을 memcmp() 함수로 바이너리 데이터처럼 비교해 사전식으로 정렬돼요.

C 언어나 memcmp 함수를 모르는 사람을 위해 설명하면, 같은 score를 가진 요소는 바이트의 원시값을 바이트 단위로 비교해 정렬된다는 뜻이에요. 첫 바이트가 같으면 두 번째를 검사하는 식이에요. 두 문자열의 공통 접두사가 같으면 더 긴 문자열이 더 크다고 간주되므로, "foobar"는 "foo"보다 커요.

ZRANGE나 ZLEXCOUNT 같은 명령은 모든 요소가 같은 score를 가진 sorted sets에 사용될 때 사전식으로 범위를 쿼리하고 셀 수 있어요.

이 Redis 기능은 기본적으로 전통적인 데이터베이스에서 인덱스를 구현하는 데 자주 쓰이는 b-tree 데이터 구조와 동등해요. 짐작하듯이, 이를 이용해 꽤 멋진 인덱스를 Redis 데이터 구조로 구현할 수 있어요.

사전식 인덱스를 쓰기 전에, 이 특수 동작 모드에서 sorted sets이 어떻게 동작하는지 확인해볼게요. 같은 score로 요소를 추가해야 하므로, 우리는 항상 특수 score인 0을 쓸 거예요.

ZADD myindex 0 baaa
ZADD myindex 0 abbb
ZADD myindex 0 aaaa
ZADD myindex 0 bbbb

sorted set에서 모든 요소를 가져오면 그것들이 사전식으로 정렬되어 있음을 즉시 알 수 있어요.

ZRANGE myindex 0 -1
1) "aaaa"
2) "abbb"
3) "baaa"
4) "bbbb"

이제 ZRANGE를 BYLEX 인자와 함께 써서 범위 쿼리를 수행할 수 있어요.

ZRANGE myindex [a (b BYLEX
1) "aaaa"
2) "abbb"

범위 쿼리에서 범위를 식별하는 min과 max 요소 앞에 [와 ( 특수 문자를 붙였음을 주목하세요. 이 접두사는 필수이며, 범위의 요소가 포함인지 제외인지를 지정해요. 그래서 범위 [a (b는 a 포함과 b 제외 사이의 모든 요소, 즉 a로 시작하는 모든 요소를 달라는 뜻이에요.

무한히 음의 문자열과 무한히 양의 문자열을 나타내는 두 특수 문자도 있는데, 바로 -와 +예요.

ZRANGE myindex [b + BYLEX
1) "baaa"
2) "bbbb"

이 정도가 기본이에요. 이제 이 기능들로 인덱스를 만드는 방법을 볼게요.

첫 번째 예시: 검색어 완성(completion)

인덱싱의 흥미로운 응용은 완성(completion)이에요. 완성은 검색 엔진에 쿼리를 입력하기 시작할 때 일어나요. UI가 사용자가 입력할 것 같은 것을 예상해, 같은 문자로 시작하는 공통 쿼리를 제공하지요.

완성에 대한 단순한 접근은 사용자로부터 받는 모든 쿼리를 인덱스에 추가하는 거예요. 예를 들어 사용자가 banana를 검색하면:

ZADD myindex 0 banana

그리고 지금까지 마주친 모든 검색 쿼리에 대해 이렇게 해요. 사용자 입력을 완성하고 싶을 때 ZRANGE를 BYLEX 인자로 써서 범위 쿼리를 실행해요. 사용자가 검색 폼에 "bit"를 입력 중이고 "bit"로 시작하는 가능한 검색 키워드를 제공하고 싶다고 상상해봐요. Redis에 다음과 같은 명령을 보내요.

ZRANGE myindex "[bit" "[bit\xff" BYLEX

기본적으로 지금 입력 중인 문자열을 시작으로, 같은 문자열에 255로 설정된 끝바이트(\xff)를 붙인 것을 범위의 끝으로 해서 범위를 만들어요. 이렇게 하면 사용자가 입력 중인 문자열로 시작하는 모든 문자열을 얻어요.

너무 많은 항목이 반환되지 않도록 LIMIT 옵션을 써서 결과 수를 줄일 수 있어요.

빈도(frequency)를 더하기

위 접근은 다소 단순해요. 모든 사용자 검색이 이 방식으로 똑같기 때문이에요. 실제 시스템에서는 빈도에 따라 문자열을 완성하고 싶어요. 매우 인기 있는 검색이 매우 드물게 입력되는 검색 문자열보다 더 높은 확률로 제안될 거예요.

빈도에 의존하면서, 동시에 더 이상 인기 없는 검색을 제거해 미래 입력에 자동으로 적응하는 것을 구현하려면 매우 간단한 스트리밍 알고리즘을 쓸 수 있어요.

먼저, 검색어뿐 아니라 그 검색어와 연결된 빈도도 저장하도록 인덱스를 수정해요. banana를 추가하는 대신 banana:1을 추가하는 거예요. 여기서 1은 빈도예요.

ZADD myindex 0 banana:1

또한 검색어가 이미 인덱스에 있으면 인덱스를 증가시키는 로직이 필요해요. 그래서 실제로는 이렇게 할 거예요.

ZRANGE myindex "[banana:" + BYLEX LIMIT 0 1
1) "banana:1"

이것은 존재한다면 banana의 단일 항목을 반환해요. 그런 다음 연결된 빈도를 증가시키고 다음 두 명령을 보낼 수 있어요.

ZREM myindex 0 banana:1
ZADD myindex 0 banana:2

동시 갱신이 가능하므로, 위 세 명령은 Lua script로 보내는 것이 좋아요. 그러면 Lua 스크립트가 원자적으로 이전 카운트를 얻고 증가된 score로 항목을 다시 추가해요.

그 결과, 사용자가 banana를 검색할 때마다 항목이 갱신돼요.

더 있습니다. 우리의 목표는 매우 자주 검색되는 항목만 갖는 거예요. 그래서 어떤 형태의 제거(purging)가 필요해요. 실제로 사용자 입력을 완성하기 위해 인덱스를 쿼리하면 이렇게 보일 수 있어요.

ZRANGE myindex "[banana:" + BYLEX LIMIT 0 10
1) "banana:123"
2) "banaooo:1"
3) "banned user:49"
4) "banning:89"

예를 들어 아무도 "banaooo"를 검색하지 않는 것 같은데, 그 쿼리가 한 번 수행되었으므로 사용자에게 보여주게 돼요.

이렇게 할 수 있어요. 반환된 항목 중 하나를 랜덤하게 골라, 그 score를 1 감소시키고 새 score로 다시 추가해요. score가 0에 도달하면 목록에서 항목을 제거해요. 훨씬 더 고급 시스템을 쓸 수도 있지만, 핵심은 장기적으로 인덱스에 상위 검색어가 포함되고, 상위 검색어가 시간이 지나며 바뀌면 자동으로 적응한다는 거예요.

이 알고리즘의 개선은 항목을 가중치에 따라 고르는 거예요. score가 높을수록 score를 감소시키거나 축출하기 위해 고를 가능성이 낮아져요.

대소문자와 악센트에 대한 문자열 정규화

완성 예시에서는 항상 소문자 문자열을 썼어요. 하지만 현실은 훨씬 복잡해요. 언어에는 대문자 이름, 악센트 등이 있으니까요.

이 문제를 다루는 간단한 방법 중 하나는 사용자가 검색한 문자열을 실제로 정규화하는 거예요. 사용자가 "Banana", "BANANA", "Ba'nana" 중 무엇을 검색하든 항상 "banana"로 바꿀 수 있어요.

하지만 때로는 인덱싱을 위해 문자열을 정규화하더라도, 사용자에게 입력한 원래 항목을 보여주고 싶을 수 있어요. 이렇게 하려면 인덱스 형식을 바꿔, term:frequency 대신 normalized:frequency:original을 저장하면 돼요. 예:

ZADD myindex 0 banana:273:Banana

기본적으로 나중에 추출해 시각화에만 쓸 필드를 하나 더 추가하는 거예요. 범위는 항상 정규화된 문자열로 계산돼요. 이는 여러 응용이 있는 흔한 트릭이에요.

인덱스에 보조 정보 추가하기

sorted set을 직접 사용할 때 각 객체에는 score(인덱스로 쓰는)와 연결된 값, 두 가지 속성이 있어요. 사전식 인덱스를 쓰면 score는 항상 0으로 설정되어 사실상 사용되지 않아요. 남는 것은 요소 자체인 단일 문자열뿐이에요.

이전 완성 예시에서 했듯이 구분자를 써서 연결된 데이터를 여전히 저장할 수 있어요. 예를 들어 완성을 위해 빈도와 원본 단어를 추가하는 데 콜론을 썼어요.

일반적으로 인덱싱 키에 어떤 종류의 연결된 값이든 추가할 수 있어요. 사전식 인덱스를 써서 간단한 키-값 저장소를 구현하려면 항목을 key:value로 저장하면 돼요.

ZADD myindex 0 mykey:myvalue

그리고 키로 검색하려면:

ZRANGE myindex [mykey: + BYLEX LIMIT 0 1
1) "mykey:myvalue"

그런 다음 콜론 뒤의 부분을 추출해 값을 가져와요. 하지만 이 경우 해결해야 할 문제는 충돌이에요. 콜론 문자가 키 자체의 일부일 수 있으므로, 추가하는 키와 절대 충돌하지 않도록 구분자를 골라야 해요.

Redis의 사전식 범위는 바이너리 세이프하므로 어떤 바이트나 바이트 시퀀스든 쓸 수 있어요. 하지만 신뢰할 수 없는 사용자 입력을 받는다면, 구분자가 키의 일부가 되지 않도록 어떤 형태의 이스케이핑을 쓰는 것이 좋아요.

예를 들어 두 개의 null 바이트 "\0\0"를 구분자로 쓴다면, 문자열의 null 바이트를 항상 두 바이트 시퀀스로 이스케이프하고 싶을 거예요.

숫자 패딩(Numerical padding)

사전식 인덱스는 문자열을 인덱싱할 때만 좋아 보일 수 있어요. 실제로는 임의 정밀도의 숫자를 인덱싱하는 데도 이 인덱스를 사용하는 것이 아주 간단해요.

ASCII 문자 집합에서 숫자는 0부터 9까지 순서대로 나타나므로, 숫자를 앞에 0으로 채우면(left-pad) 문자열로 비교할 때 숫자값 순서로 정렬돼요.

ZADD myindex 0 00324823481:foo
ZADD myindex 0 12838349234:bar
ZADD myindex 0 00000000111:zap

ZRANGE myindex 0 -1
1) "00000000111:zap"
2) "00324823481:foo"
3) "12838349234:bar"

우리가 원하는 만큼 큰 숫자 필드로 인덱스를 효과적으로 만들었어요. 이것은 정수 부분을 앞에 0으로, 소수 부분을 뒤에 0으로 채우면 어떤 정밀도의 부동 소수점에서도 동작해요. 다음 숫자 목록처럼요.

    01000000000000.11000000000000
    01000000000000.02200000000000
    00000002121241.34893482930000
    00999999999999.00000000000000

숫자를 이진 형태로 사용하기

숫자를 십진수로 저장하면 메모리를 너무 많이 쓸 수 있어요. 대안은 예를 들어 128비트 정수 같은 숫자를 이진 형태로 직접 저장하는 거예요. 하지만 이게 동작하려면 숫자를 빅 엔디언(big endian) 형식으로 저장해야 해요. 그래야 가장 중요한 바이트가 가장 덜 중요한 바이트보다 먼저 저장돼요. 이렇게 하면 Redis가 memcmp()로 문자열을 비교할 때 숫자를 값별로 정렬하게 돼요.

이진 형식으로 저장된 데이터는 디버깅에 덜 관찰 가능하고, 파싱·내보내기가 더 어렵다는 점을 기억하세요. 그래서 분명히 트레이드오프가 있어요.

복합 인덱스(Composite indexes)

지금까지 단일 필드를 인덱싱하는 방법을 살펴봤어요. 하지만 SQL 저장소는 여러 필드로 인덱스를 만들 수 있다는 것을 알고 있어요. 예를 들어 아주 큰 상점의 제품을 방 번호와 가격별로 인덱싱할 수 있어요.

주어진 방에서 주어진 가격 범위를 가진 모든 제품을 가져오는 쿼리를 실행해야 해요. 각 제품을 다음과 같이 인덱싱할 수 있어요.

ZADD myindex 0 0056:0028.44:90
ZADD myindex 0 0034:0011.00:832

여기서 필드는 room:price:product_id예요. 간단히 하기 위해 예시에서는 4자리 패딩만 썼어요. 보조 데이터(제품 ID)는 패딩이 필요 없어요.

그런 인덱스로 방 56에 있고 가격이 10~30달러 사이인 모든 제품을 얻는 것은 매우 쉬워요. 다음 명령만 실행하면 돼요.

ZRANGE myindex [0056:0010.00 [0056:0030.00 BYLEX

위는 복합 인덱스(composed index)라고 불러요. 그 효과는 필드 순서와 실행하려는 쿼리에 따라 달라져요. 예를 들어 위 인덱스는 방 번호와 무관하게 특정 가격 범위의 모든 제품을 가져오는 데는 효율적으로 쓸 수 없어요. 하지만 가격과 무관하게 쿼리를 실행하는 데 기본 키를 쓸 수 있어요. 예: 방 44에 있는 모든 제품을 달라.

복합 인덱스는 매우 강력하고, 전통적인 저장소에서 복잡한 쿼리를 최적화하는 데 쓰여요. Redis에서는 전통적인 데이터 저장소에 저장된 무언가의 매우 빠른 인메모리 Redis 인덱스를 구현하거나, Redis 데이터를 직접 인덱싱하는 데 유용할 수 있어요.

사전식 인덱스 갱신하기

사전식 인덱스의 인덱스 값은 꽤 화려해질 수 있고, 객체에 대해 저장한 것으로부터 재구축하기 어렵거나 느릴 수 있어요. 그래서 인덱스 처리를 단순화하는 한 접근(메모리를 더 쓰는 비용)은 인덱스를 나타내는 sorted set과 함께, 객체 ID를 현재 인덱스 값에 매핑하는 해시도 두는 거예요.

예를 들어, 인덱싱할 때 해시에도 추가해요.

MULTI
ZADD myindex 0 0056:0028.44:90
HSET index.content 90 0056:0028.44:90
EXEC

이게 항상 필요한 건 아니지만 인덱스 갱신 연산을 단순화해요. 객체 ID 90에 대해 인덱싱한 이전 정보를 제거하려면, 객체의 현재 필드 값과 무관하게 객체 ID로 해시 값을 가져와 sorted set 뷰에서 ZREM하면 돼요.

Hexastore로 그래프 표현·쿼리하기

복합 인덱스의 멋진 점 중 하나는 Hexastore라는 데이터 구조를 사용해 그래프를 표현하기에 편리하다는 거예요.

hexastore는 주어(subject), 술어(predicate), *목적어(object)*로 형성된 객체 간 관계의 표현을 제공해요. 객체 간 단순한 관계는 이렇게 될 수 있어요.

antirez is-friend-of matteocollina

이 관계를 표현하려면 사전식 인덱스에 다음 요소를 저장할 수 있어요.

ZADD myindex 0 spo:antirez:is-friend-of:matteocollina

항목 앞에 spo 문자열을 붙였음을 주목하세요. 이것은 항목이 subject,predicate,object 관계를 나타낸다는 뜻이에요.

같은 관계에 대해 다른 순서로 5개 항목을 더 추가할 수 있어요.

ZADD myindex 0 sop:antirez:matteocollina:is-friend-of
ZADD myindex 0 ops:matteocollina:is-friend-of:antirez
ZADD myindex 0 osp:matteocollina:antirez:is-friend-of
ZADD myindex 0 pso:is-friend-of:antirez:matteocollina
ZADD myindex 0 pos:is-friend-of:matteocollina:antirez

이제 흥미로워지기 시작해요. 그래프를 여러 방식으로 쿼리할 수 있어요. 예를 들어, antirez가 친구인 사람들은 누구일까요?

ZRANGE myindex "[spo:antirez:is-friend-of:" "[spo:antirez:is-friend-of:\xff" BYLEX
1) "spo:antirez:is-friend-of:matteocollina"
2) "spo:antirez:is-friend-of:wonderwoman"
3) "spo:antirez:is-friend-of:spiderman"

또는 antirez가 주어이고 matteocollina가 목적어인 관계는 무엇일까요?

ZRANGE myindex "[sop:antirez:matteocollina:" "[sop:antirez:matteocollina:\xff" BYLEX
1) "sop:antirez:matteocollina:is-friend-of"
2) "sop:antirez:matteocollina:was-at-conference-with"
3) "sop:antirez:matteocollina:talked-with"

다른 쿼리들을 결합하면 멋진 질문을 할 수 있어요. 예: 맥주를 좋아하고 바르셀로나에 살며, matteocollina도 친구로 여기는 내 친구들은 누구? 이 정보를 얻기 위해 spo 쿼리로 내가 친구인 모든 사람을 찾아요. 각 결과에 대해 spo 쿼리를 실행해 그들이 맥주를 좋아하는지 확인하고, 이 관계를 찾지 못한 사람은 제거해요. 도시로 필터링하기 위해 다시 해요. 마지막으로 ops 쿼리를 실행해 얻은 목록 중 누가 matteocollina에게 친구로 여겨지는지 찾아요.

이 아이디어들을 더 잘 이해하려면 Matteo Collina의 Levelgraph 슬라이드를 꼭 확인하세요.

다차원 인덱스(Multi-dimensional indexes)

더 복잡한 인덱스 타입은 두 개 이상의 변수를 특정 범위에 대해 동시에 쿼리할 수 있게 하는 인덱스예요. 예를 들어 사람의 나이와 급여를 나타내는 데이터셋이 있고, 나이가 50~~55세이면서 급여가 70000~~85000인 모든 사람을 가져오고 싶을 수 있어요.

이 쿼리는 다중 컬럼 인덱스로 수행될 수 있지만, 첫 번째 변수를 선택하고 두 번째를 스캔해야 하므로 필요한 것보다 훨씬 많은 작업을 할 수 있어요. 이런 종류의 다중 변수 쿼리는 다른 데이터 구조로 수행할 수 있어요. 예를 들어 k-d trees나 r-trees 같은 다차원 트리가 때때로 쓰여요. 여기서는 Redis 사전식 범위를 사용해 아주 효율적으로 쿼리를 수행할 수 있게 해주는 표현 트릭을 써서, 데이터를 여러 차원으로 인덱싱하는 다른 방법을 설명할게요.

데이터 샘플을 나타내는 공간의 점들이 있고, x와 y가 좌표라고 합시다. 두 변수의 최대값은 400이에요.

이런 종류의 쿼리를 빠르게 수행하는 데이터를 표현하려면 숫자를 0으로 채우는 것부터 시작해요. 예를 들어 점 10,25 (x,y)를 인덱스에 추가하고 싶다고 합시다. 예시의 최대 범위가 400이므로 세 자리로 채우면 돼요. 그러면:

x = 010
y = 025

이제 숫자를 인터리브(interleave)해요. x의 가장 왼쪽 자릿수, y의 가장 왼쪽 자릿수를 차례로 가져와 단일 숫자를 만들어요.

이것이 우리의 인덱스예요. 하지만 원래 표현을 더 쉽게 재구성하고 싶다면(공간을 희생하고) 원래 값을 추가 컬럼으로 추가할 수도 있어요.

001205:10:25

이제 이 표현과 그것이 범위 쿼리 맥락에서 왜 유용한지 따져볼게요. 예를 들어 파란 상자의 중심을 x=75, y=200이라고 합시다. 이 숫자를 앞에서처럼 자릿수를 인터리브해 인코딩할 수 있어요.

마지막 두 자리를 각각 00과 99로 치환하면 어떻게 될까요? 사전식으로 연속적인 범위를 얻어요.

027000 to 027099

이것이 매핑되는 것은 x가 70~~79, y가 200~~209 사이인 모든 값을 나타내는 사각형이에요. 이 특정 영역을 식별하기 위해 그 구간에 랜덤 점을 쓸 수 있어요.

그래서 위 사전식 쿼리로 그림의 특정 사각형에 있는 점을 쉽게 쿼리할 수 있어요. 하지만 사각형이 우리가 찾는 상자에 비해 너무 작아서 쿼리가 너무 많이 필요할 수 있어요. 그래서 마지막 두 자리를 00과 99로 치환하는 대신 마지막 네 자리에 대해 할 수 있어요. 다음 범위를 얻어요.

020000 029999

이번 범위는 x가 0~~99, y가 200~~299 사이인 모든 점을 나타내요. 이 구간에 랜덤 점을 그리면 더 큰 영역이 보여요.

이제 영역이 쿼리 범위보다 너무 커졌고, 여전히 검색 상자가 완전히 포함되진 않아요. 더 세밀함이 필요해요. 숫자를 이진 형태로 표현하면 쉽게 얻을 수 있어요. 이번에는 자릿수를 치환할 때 10배 큰 사각형이 아니라 2배 큰 사각형을 얻어요.

각 변수에 9비트만 필요하다고 가정한(값 400까지 표현) 이진 형식의 숫자는:

x = 75  -> 001001011
y = 200 -> 011001000

그래서 자릿수를 인터리브하면 인덱스의 표현은:

000111000011001010:75:200

인터리브 표현에서 마지막 2, 4, 6, 8, ... 비트를 0과 1로 치환할 때 범위가 어떻게 되는지 볼게요.

2 bits: x between 74 and 75, y between 200 and 201 (range=2)
4 bits: x between 72 and 75, y between 200 and 203 (range=4)
6 bits: x between 72 and 79, y between 200 and 207 (range=8)
8 bits: x between 64 and 79, y between 192 and 207 (range=16)

이런 식으로요. 이제 확실히 더 나은 세밀함을 얻었어요! 보시다시피 인덱스에서 N비트를 치환하면 변의 길이가 2^(N/2)인 검색 상자가 나와요.

그래서 검색 상자가 더 작은 차원을 확인하고, 이 숫자에 가장 가까운 2의 거듭제곱을 확인해요. 검색 상자는 50,100에서 100,300까지였으니 폭 50, 높이 200이에요. 둘 중 작은 50을 취해 가장 가까운 2의 거듭제곱인 64를 확인해요. 64는 2^6이므로, 인터리브 표현의 마지막 12비트를 치환해 얻은 인덱스로 작업해요(각 변수의 6비트만 치환하게 됨).

하지만 단일 사각형이 전체 검색을 덮지 못할 수 있어 더 필요할 수 있어요. 검색 상자의 왼쪽 아래 모서리(50,100)에서 시작해 각 숫자의 마지막 6비트를 0으로 치환해 첫 번째 범위를 찾아요. 그런 다음 오른쪽 위 모서리에도 똑같이 해요.

유효 비트만 증가시키는 두 개의 사소한 중첩 for 루프로, 이 둘 사이의 모든 사각형을 찾을 수 있어요. 각 사각형에 대해 두 숫자를 인터리브 표현으로 변환하고, 변환된 표현을 시작으로, 마지막 12비트를 켠 같은 표현을 범위 끝으로 해서 범위를 만들어요.

찾은 각 사각형에 대해 쿼리를 수행하고 그 안의 요소를 얻어, 검색 상자 밖에 있는 요소는 제거해요.

이것을 코드로 만드는 것은 간단해요. 다음은 Ruby 예시예요.

def spacequery(x0,y0,x1,y1,exp)
    bits=exp*2
    x_start = x0/(2**exp)
    x_end = x1/(2**exp)
    y_start = y0/(2**exp)
    y_end = y1/(2**exp)
    (x_start..x_end).each{|x|
        (y_start..y_end).each{|y|
            x_range_start = x*(2**exp)
            x_range_end = x_range_start | ((2**exp)-1)
            y_range_start = y*(2**exp)
            y_range_end = y_range_start | ((2**exp)-1)
            puts "#{x},#{y} x from #{x_range_start} to #{x_range_end}, y from #{y_range_start} to #{y_range_end}"

            # Turn it into interleaved form for ZRANGE query.
            # We assume we need 9 bits for each integer, so the final
            # interleaved representation will be 18 bits.
            xbin = x_range_start.to_s(2).rjust(9,'0')
            ybin = y_range_start.to_s(2).rjust(9,'0')
            s = xbin.split("").zip(ybin.split("")).flatten.compact.join("")
            # Now that we have the start of the range, calculate the end
            # by replacing the specified number of bits from 0 to 1.
            e = s[0..-(bits+1)]+("1"*bits)
            puts "ZRANGE myindex [#{s} [#{e} BYLEX"
        }
    }
end

spacequery(50,100,100,300,6)

즉시 명백하진 않지만 이것은 매우 유용한 인덱싱 전략이에요. 미래에 Redis에 네이티브로 구현될 수도 있어요. 지금으로서는 복잡성이 인덱싱과 쿼리를 수행하는 데 쓰는 라이브러리 안에 쉽게 캡슐화될 수 있다는 점이 좋아요. 이런 라이브러리의 예는 Redimension이에요. 여기 설명된 기법으로 Redis 안의 N차원 데이터를 인덱싱하는 proof of concept Ruby 라이브러리예요.

음수 또는 부동 소수점을 다루는 다차원 인덱스

음수 값을 표현하는 가장 간단한 방법은 부호 없는 정수로 작업하고 오프셋을 사용해 표현하는 거예요. 인덱스할 때 숫자를 인덱스 표현으로 변환하기 전에 가장 작은 음수 정수의 절대값을 더하는 거예요.

부동 소수점의 경우, 가장 간단한 접근은 유지하려는 소수점 아래 자릿수에 비례하는 10의 거듭제곱을 곱해 정수로 변환하는 것이에요.

비-범위 인덱스(Non-range indexes)

지금까지 범위나 단일 항목으로 쿼리하는 데 유용한 인덱스를 살펴봤어요. 하지만 Sets나 Lists 같은 다른 Redis 데이터 구조도 다른 종류의 인덱스를 만드는 데 쓸 수 있어요. 그것들은 아주 흔히 사용되지만, 실제로 인덱싱의 한 형태라는 것을 항상 깨닫지는 못할 수 있어요.

예를 들어 Sets 데이터 타입에 객체 ID를 인덱싱해, SRANDMEMBER를 통한 랜덤 요소 가져오기 연산으로 랜덤 객체 집합을 가져올 수 있어요. Sets는 특정 항목이 존재하는지, 또는 단일 부울 속성이 있는지만 테스트하면 될 때 존재 확인에도 쓸 수 있어요.

마찬가지로 Lists는 항목을 고정 순서로 인덱싱하는 데 쓸 수 있어요. 모든 항목을 Redis list에 추가하고, 같은 키 이름을 소스 및 목적지로 RPOPLPUSH로 리스트를 회전시킬 수 있어요. 이는 특정 항목 집합을 같은 순서로 계속해서 다시 처리하고 싶을 때 유용해요. 로컬 사본을 주기적으로 새로고침해야 하는 RSS 피드 시스템을 생각해보세요.

Redis와 함께 자주 쓰이는 또 다른 인기 인덱스는 capped list예요. 항목을 LPUSH로 추가하고 LTRIM으로 잘라내, 마주친 순서대로 마지막 N개 항목만 보여주는 뷰를 만드는 거예요.

인덱스 불일치(Index inconsistency)

인덱스를 갱신된 상태로 유지하는 것은 어려울 수 있어요. 몇 달이나 몇 년에 걸쳐 소프트웨어 버그, 네트워크 파티션 또는 다른 사건 때문에 불일치가 추가될 수 있어요.

다른 전략을 쓸 수 있어요. 인덱스 데이터가 Redis 외부에 있으면 read repair가 해결책이 될 수 있는데, 데이터가 요청될 때 지연 방식으로 고쳐지는 거예요. Redis 자체에 저장된 데이터를 인덱싱할 때는 SCAN 명령 계열을 써서, 인덱스를 처음부터 점진적으로 검증·갱신·재구축할 수 있어요.

보조 인덱싱(Secondary Indexing)