SASI 인덱스
SASI 인덱스
SASIIndex(줄여서 SASI)는 Cassandra의 Index 인터페이스 구현으로, 기존 구현의 대안으로 사용할 수 있어요. SASI의 인덱싱과 쿼리는 Cassandra의 필요에 특별히 맞춰져 기존 구현보다 개선됩니다. SASI는 이전에 필터링을 요구했던 쿼리에서 우수한 성능을 냅니다. 이 성능을 달성하면서 SASI는 메모리, 디스크, CPU 사용에서 기존 구현보다 훨씬 덜 리소스 집약적이 되도록 목표합니다. 추가로 SASI는 문자열에 대한 prefix와 contains 쿼리(SQL의 LIKE = "foo*"나 LIKE = "*foo*"와 유사)를 지원합니다.
이어서 SASI를 시작하고 실행하는 방법, 예제로 사용법을 시연하고, 구현에 대한 몇 가지 세부 사항을 설명할게요.
출처: 문서
본문
SASI 사용
아래 예제는 테이블과 그 컬럼에 대한 인덱스를 만들고, 삽입된 일부 데이터에 쿼리를 수행하는 과정을 안내합니다.
아래 예제는 데모 키스페이스가 만들어져 사용 중이라고 가정합니다.
cqlsh> CREATE KEYSPACE demo WITH replication = {
... 'class': 'SimpleStrategy',
... 'replication_factor': '1'
... };
cqlsh> USE demo;
모든 예제는 sasi 테이블에서 수행됩니다:
cqlsh:demo> CREATE TABLE sasi (id uuid, first_name text, last_name text,
... age int, height int, created_at bigint, primary key (id));
인덱스 만들기
SASI 인덱스를 만들려면 CQL의 CREATE CUSTOM INDEX 문을 사용합니다:
cqlsh:demo> CREATE CUSTOM INDEX ON sasi (first_name) USING 'org.apache.cassandra.index.sasi.SASIIndex'
... WITH OPTIONS = {
... 'analyzer_class':
... 'org.apache.cassandra.index.sasi.analyzer.NonTokenizingAnalyzer',
... 'case_sensitive': 'false'
... };
cqlsh:demo> CREATE CUSTOM INDEX ON sasi (last_name) USING 'org.apache.cassandra.index.sasi.SASIIndex'
... WITH OPTIONS = {'mode': 'CONTAINS'};
cqlsh:demo> CREATE CUSTOM INDEX ON sasi (age) USING 'org.apache.cassandra.index.sasi.SASIIndex';
cqlsh:demo> CREATE CUSTOM INDEX ON sasi (created_at) USING 'org.apache.cassandra.index.sasi.SASIIndex'
... WITH OPTIONS = {'mode': 'SPARSE'};
만들어진 인덱스는 그 동작과 잠재적 성능을 사용자 지정하는 몇 가지 지정된 옵션이 있습니다. first_name의 인덱스는 대소문자를 구분하지 않습니다. analyzer는 이후 예제에서 더 논의합니다. NonTokenizingAnalyzer는 텍스트에 대해 어떤 분석도 수행하지 않아요. 각 인덱스는 PREFIX, CONTAINS, 또는 SPARSE 모드를 가지며, 첫 번째가 기본값입니다. last_name 인덱스는 접두사 대신 접미사에 매칭하는 CONTAINS 모드로 생성됩니다. 예제는 아래에서 사용할 수 있고 더 자세한 내용은 OnDiskIndex 섹션에서 찾을 수 있어요. created_at 컬럼은 SPARSE 모드로 생성되는데, 이는 매 밀리초마다 삽입되는 데이터의 타임스탬프 같은 크고 조밀한 숫자 범위 쿼리의 성능을 개선하기 위한 것입니다. SPARSE 구현의 세부 사항도 OnDiskIndex 섹션에서 찾을 수 있어요. age 인덱스는 기본 PREFIX 모드로 생성되며, 필드가 숫자이므로 대소문자 구분이나 텍스트 분석 옵션이 지정되지 않습니다.
다음 데이터를 삽입하고 nodetool flush를 수행한 뒤 SASI가 인덱스 플러시를 디스크로 수행하는 것을 Cassandra 로그에서 볼 수 있어요 — 다만 직접 flush 호출은 필요하지 않습니다(자세한 내용은 IndexMemtable 참고).
cqlsh:demo> INSERT INTO sasi (id, first_name, last_name, age, height, created_at)
... VALUES (556ebd54-cbe5-4b75-9aae-bf2a31a24500, 'Pavel', 'Yaskevich', 27, 181, 1442959315018);
cqlsh:demo> INSERT INTO sasi (id, first_name, last_name, age, height, created_at)
... VALUES (5770382a-c56f-4f3f-b755-450e24d55217, 'Jordan', 'West', 26, 173, 1442959315019);
cqlsh:demo> INSERT INTO sasi (id, first_name, last_name, age, height, created_at)
... VALUES (96053844-45c3-4f15-b1b7-b02c441d3ee1, 'Mikhail', 'Stepura', 36, 173, 1442959315020);
cqlsh:demo> INSERT INTO sasi (id, first_name, last_name, age, height, created_at)
... VALUES (f5dfcabe-de96-4148-9b80-a1c41ed276b4, 'Michael', 'Kjellman', 26, 180, 1442959315021);
cqlsh:demo> INSERT INTO sasi (id, first_name, last_name, age, height, created_at)
... VALUES (2970da43-e070-41a8-8bcb-35df7a0e608a, 'Johnny', 'Zhang', 32, 175, 1442959315022);
cqlsh:demo> INSERT INTO sasi (id, first_name, last_name, age, height, created_at)
... VALUES (6b757016-631d-4fdb-ac62-40b127ccfbc7, 'Jason', 'Brown', 40, 182, 1442959315023);
cqlsh:demo> INSERT INTO sasi (id, first_name, last_name, age, height, created_at)
... VALUES (8f909e8a-008e-49dd-8d43-1b0df348ed44, 'Vijay', 'Parthasarathy', 34, 183, 1442959315024);
cqlsh:demo> SELECT first_name, last_name, age, height, created_at FROM sasi;
first_name | last_name | age | height | created_at
------------+---------------+-----+--------+---------------
Michael | Kjellman | 26 | 180 | 1442959315021
Mikhail | Stepura | 36 | 173 | 1442959315020
Jason | Brown | 40 | 182 | 1442959315023
Pavel | Yaskevich | 27 | 181 | 1442959315018
Vijay | Parthasarathy | 34 | 183 | 1442959315024
Jordan | West | 26 | 173 | 1442959315019
Johnny | Zhang | 32 | 175 | 1442959315022
(7 rows)
동등성 및 접두사 쿼리
SASI는 PREFIX, CONTAINS, SUFFIX 검색을 위한 LIKE 문을 포함해 CQL이 이미 지원하는 모든 쿼리를 지원합니다.
cqlsh:demo> SELECT first_name, last_name, age, height, created_at FROM sasi
... WHERE first_name = 'Pavel';
first_name | last_name | age | height | created_at
-------------+-----------+-----+--------+---------------
Pavel | Yaskevich | 27 | 181 | 1442959315018
(1 rows)
cqlsh:demo> SELECT first_name, last_name, age, height, created_at FROM sasi
... WHERE first_name = 'pavel';
first_name | last_name | age | height | created_at
-------------+-----------+-----+--------+---------------
Pavel | Yaskevich | 27 | 181 | 1442959315018
(1 rows)
cqlsh:demo> SELECT first_name, last_name, age, height, created_at FROM sasi
... WHERE first_name LIKE 'M%';
first_name | last_name | age | height | created_at
------------+-----------+-----+--------+---------------
Michael | Kjellman | 26 | 180 | 1442959315021
Mikhail | Stepura | 36 | 173 | 1442959315020
(2 rows)
물론 인덱스 생성 시 제공된 옵션 때문에 first_name 컬럼에서는 쿼리의 대소문자가 중요하지 않습니다.
cqlsh:demo> SELECT first_name, last_name, age, height, created_at FROM sasi
... WHERE first_name LIKE 'm%';
first_name | last_name | age | height | created_at
------------+-----------+-----+--------+---------------
Michael | Kjellman | 26 | 180 | 1442959315021
Mikhail | Stepura | 36 | 173 | 1442959315020
(2 rows)
복합 쿼리 (Compound Queries)
SASI는 여러 조건(predicate)이 있는 쿼리를 지원합니다. 다만 기본 인덱싱 구현의 특성 때문에 CQL은 사용자가 그러한 쿼리의 잠재적 성능 함정에 opt-in하도록 ALLOW FILTERING을 지정하도록 요구합니다. SASI를 사용하면 ALLOW FILTERING을 포함해야 하는 요구는 문법 수정을 줄이기 위해 유지되지만, 필터링이 수행되지 않으므로 성능 함정은 존재하지 않아요. SASI가 여러 조건의 데이터를 어떻게 결합하는지에 대한 세부 사항은 아래 Implementation Details 섹션에서 확인할 수 있습니다.
cqlsh:demo> SELECT first_name, last_name, age, height, created_at FROM sasi
... WHERE first_name LIKE 'M%' and age < 30 ALLOW FILTERING;
first_name | last_name | age | height | created_at
------------+-----------+-----+--------+---------------
Michael | Kjellman | 26 | 180 | 1442959315021
(1 rows)
접미사 쿼리 (Suffix Queries)
다음 예제는 last_name 컬럼의 CONTAINS 모드를 시연합니다. 이 모드를 사용하면 조건이 검색 문자열을 하위 문자열로 포함하는 모든 문자열을 검색할 수 있어요. 이 경우 'a' 또는 'an'을 포함하는 문자열입니다.
cqlsh:demo> SELECT * FROM sasi WHERE last_name LIKE '%a%';
id | age | created_at | first_name | height | last_name
--------------------------------------+-----+---------------+------------+--------+---------------
f5dfcabe-de96-4148-9b80-a1c41ed276b4 | 26 | 1442959315021 | Michael | 180 | Kjellman
96053844-45c3-4f15-b1b7-b02c441d3ee1 | 36 | 1442959315020 | Mikhail | 173 | Stepura
556ebd54-cbe5-4b75-9aae-bf2a31a24500 | 27 | 1442959315018 | Pavel | 181 | Yaskevich
8f909e8a-008e-49dd-8d43-1b0df348ed44 | 34 | 1442959315024 | Vijay | 183 | Parthasarathy
2970da43-e070-41a8-8bcb-35df7a0e608a | 32 | 1442959315022 | Johnny | 175 | Zhang
(5 rows)
cqlsh:demo> SELECT * FROM sasi WHERE last_name LIKE '%an%';
id | age | created_at | first_name | height | last_name
--------------------------------------+-----+---------------+------------+--------+-----------
f5dfcabe-de96-4148-9b80-a1c41ed276b4 | 26 | 1442959315021 | Michael | 180 | Kjellman
2970da43-e070-41a8-8bcb-35df7a0e608a | 32 | 1442959315022 | Johnny | 175 | Zhang
(2 rows)
인덱스되지 않은 컬럼의 표현식
SASI는 height 같은 인덱스되지 않은 컬럼에 대한 필터링도 지원합니다. 표현식은 AND를 사용해 기존 쿼리만 좁힐 수 있어요.
cqlsh:demo> SELECT * FROM sasi WHERE last_name LIKE '%a%' AND height >= 175 ALLOW FILTERING;
id | age | created_at | first_name | height | last_name
--------------------------------------+-----+---------------+------------+--------+---------------
f5dfcabe-de96-4148-9b80-a1c41ed276b4 | 26 | 1442959315021 | Michael | 180 | Kjellman
556ebd54-cbe5-4b75-9aae-bf2a31a24500 | 27 | 1442959315018 | Pavel | 181 | Yaskevich
8f909e8a-008e-49dd-8d43-1b0df348ed44 | 34 | 1442959315024 | Vijay | 183 | Parthasarathy
2970da43-e070-41a8-8bcb-35df7a0e608a | 32 | 1442959315022 | Johnny | 175 | Zhang
(4 rows)
구분자 기반 토큰화 분석
제공되는 간단한 텍스트 분석은 구분자 기반 토큰화입니다. 이는 컬렉션 인덱싱의 대안을 제공합니다. 구분자로 구분된 텍스트는 CONTAINS 모드의 오버헤드나 PREFIX/SUFFIX 쿼리 사용 없이 인덱싱될 수 있기 때문이에요.
cqlsh:demo> ALTER TABLE sasi ADD aliases text;
cqlsh:demo> CREATE CUSTOM INDEX on sasi (aliases) USING 'org.apache.cassandra.index.sasi.SASIIndex'
... WITH OPTIONS = {
... 'analyzer_class': 'org.apache.cassandra.index.sasi.analyzer.DelimiterAnalyzer',
... 'delimiter': ',',
... 'mode': 'prefix',
... 'analyzed': 'true'};
cqlsh:demo> UPDATE sasi SET aliases = 'Mike,Mick,Mikey,Mickey' WHERE id = f5dfcabe-de96-4148-9b80-a1c41ed276b4;
cqlsh:demo> SELECT * FROM sasi WHERE aliases LIKE 'Mikey' ALLOW FILTERING;
id | age | aliases | created_at | first_name | height | last_name
--------------------------------------+-----+------------------------+---------------+------------+--------+-----------
f5dfcabe-de96-4148-9b80-a1c41ed276b4 | 26 | Mike,Mick,Mikey,Mickey | 1442959315021 | Michael | 180 | Kjellman
텍스트 분석 (토큰화 및 형태소 분석)
마지막으로 텍스트 분석을 시연하려면 테이블에 추가 컬럼이 필요합니다. 그 정의, 인덱스, 행을 업데이트하는 문이 아래에 표시됩니다.
cqlsh:demo> ALTER TABLE sasi ADD bio text;
cqlsh:demo> CREATE CUSTOM INDEX ON sasi (bio) USING 'org.apache.cassandra.index.sasi.SASIIndex'
... WITH OPTIONS = {
... 'analyzer_class': 'org.apache.cassandra.index.sasi.analyzer.StandardAnalyzer',
... 'tokenization_enable_stemming': 'true',
... 'analyzed': 'true',
... 'tokenization_normalize_lowercase': 'true',
... 'tokenization_locale': 'en'
... };
cqlsh:demo> UPDATE sasi SET bio = 'Software Engineer, who likes distributed systems, doesnt like to argue.' WHERE id = 5770382a-c56f-4f3f-b755-450e24d55217;
cqlsh:demo> UPDATE sasi SET bio = 'Software Engineer, works on the freight distribution at nights and likes arguing' WHERE id = 556ebd54-cbe5-4b75-9aae-bf2a31a24500;
cqlsh:demo> SELECT * FROM sasi;
id | age | bio | created_at | first_name | height | last_name
--------------------------------------+-----+----------------------------------------------------------------------------------+---------------+------------+--------+---------------
f5dfcabe-de96-4148-9b80-a1c41ed276b4 | 26 | null | 1442959315021 | Michael | 180 | Kjellman
96053844-45c3-4f15-b1b7-b02c441d3ee1 | 36 | null | 1442959315020 | Mikhail | 173 | Stepura
6b757016-631d-4fdb-ac62-40b127ccfbc7 | 40 | null | 1442959315023 | Jason | 182 | Brown
556ebd54-cbe5-4b75-9aae-bf2a31a24500 | 27 | Software Engineer, works on the freight distribution at nights and likes arguing | 1442959315018 | Pavel | 181 | Yaskevich
8f909e8a-008e-49dd-8d43-1b0df348ed44 | 34 | null | 1442959315024 | Vijay | 183 | Parthasarathy
5770382a-c56f-4f3f-b755-450e24d55217 | 26 | Software Engineer, who likes distributed systems, doesnt like to argue. | 1442959315019 | Jordan | 173 | West
2970da43-e070-41a8-8bcb-35df7a0e608a | 32 | null | 1442959315022 | Johnny | 175 | Zhang
(7 rows)
bio 컬럼은 StandardAnalyzer를 사용하고 analyzed가 true로 설정되도록 구성되었으므로 인덱스 항과 쿼리 검색 문자열이 형태소 분석(stemming)됩니다. tokenization_normalize_lowercase는 case_sensitive 속성과 유사하지만 StandardAnalyzer용입니다. 이 쿼리들은 StandardAnalyzer가 적용하는 형태소 분석을 시연합니다.
cqlsh:demo> SELECT * FROM sasi WHERE bio LIKE 'distributing';
id | age | bio | created_at | first_name | height | last_name
--------------------------------------+-----+----------------------------------------------------------------------------------+---------------+------------+--------+-----------
556ebd54-cbe5-4b75-9aae-bf2a31a24500 | 27 | Software Engineer, works on the freight distribution at nights and likes arguing | 1442959315018 | Pavel | 181 | Yaskevich
5770382a-c56f-4f3f-b755-450e24d55217 | 26 | Software Engineer, who likes distributed systems, doesnt like to argue. | 1442959315019 | Jordan | 173 | West
(2 rows)
cqlsh:demo> SELECT * FROM sasi WHERE bio LIKE 'they argued';
id | age | bio | created_at | first_name | height | last_name
--------------------------------------+-----+----------------------------------------------------------------------------------+---------------+------------+--------+-----------
556ebd54-cbe5-4b75-9aae-bf2a31a24500 | 27 | Software Engineer, works on the freight distribution at nights and likes arguing | 1442959315018 | Pavel | 181 | Yaskevich
5770382a-c56f-4f3f-b755-450e24d55217 | 26 | Software Engineer, who likes distributed systems, doesnt like to argue. | 1442959315019 | Jordan | 173 | West
(2 rows)
cqlsh:demo> SELECT * FROM sasi WHERE bio LIKE 'working at the company';
id | age | bio | created_at | first_name | height | last_name
--------------------------------------+-----+----------------------------------------------------------------------------------+---------------+------------+--------+-----------
556ebd54-cbe5-4b75-9aae-bf2a31a24500 | 27 | Software Engineer, works on the freight distribution at nights and likes arguing | 1442959315018 | Pavel | 181 | Yaskevich
(1 rows)
cqlsh:demo> SELECT * FROM sasi WHERE bio LIKE 'soft eng';
id | age | bio | created_at | first_name | height | last_name
--------------------------------------+-----+----------------------------------------------------------------------------------+---------------+------------+--------+-----------
556ebd54-cbe5-4b75-9aae-bf2a31a24500 | 27 | Software Engineer, works on the freight distribution at nights and likes arguing | 1442959315018 | Pavel | 181 | Yaskevich
5770382a-c56f-4f3f-b755-450e24d55217 | 26 | Software Engineer, who likes distributed systems, doesnt like to argue. | 1442959315019 | Jordan | 173 | West
(2 rows)
구현 세부 사항 (Implementation Details)
SASI는 표면적으로는 단순히 Index 인터페이스의 구현이지만, 그 내부에는 이를 충족하는 데 사용되는 여러 데이터 구조와 알고리즘이 있습니다. 이들이 여기서 설명됩니다. 추가로 SASI 통합을 지원하기 위한 Cassandra 내부의 변경도 설명해요.
Index 인터페이스는 구현자의 책임을 인덱싱(Indexing)과 쿼리(Querying) 두 부분으로 나눕니다. 또한 Cassandra는 그 책임을 메모리와 디스크 구성 요소로 나누는 것을 가능하게 합니다. SASI는 Cassandra의 write-once, 불변, 정렬된 데이터 모델을 활용해 멤테이블을 디스크로 플러시하는 것과 함께 인덱스를 구축합니다 — 이것이 SSTable Attached Secondary Index라는 이름의 기원입니다.
SASI 인덱스 데이터 구조는 SSTable이 기록될 때 메모리에 구축되고, SSTable 기록이 완료되기 전에 디스크로 플러시됩니다. 각 인덱스 파일의 기록은 디스크에 대한 순차 쓰기만 필요해요. 어떤 경우에는 메모리 사용을 줄이기 위해 부분 플러시가 수행되고 나중에 다시 이어붙입니다. 이 데이터 구조들은 이 사용 사례에 최적화되어 있습니다.
Cassandra의 정렬된 데이터 모델을 활용해, 쿼리 시점에 후보 인덱스를 검색을 위해 좁혀 작업량을 최소화합니다. 그런 다음 필요에 따라 디스크에서 데이터를 스트리밍하는 효율적인 방법으로 검색을 수행합니다.
인덱싱 (Indexing)
SASI는 SSTable마다 인덱스된 각 컬럼에 대한 인덱스 파일을 씁니다. 이 파일들의 데이터는 OnDiskIndexBuilder를 사용해 메모리에 구축됩니다. 디스크로 플러시된 후에는 OnDiskIndex 클래스를 사용해 데이터를 읽습니다. 이들은 효율적인 쓰기 또는 검색을 위해 조직된 인덱스된 항을 나타내는 바이트로 구성됩니다. 그들이 보유한 키와 값은 SSTable의 토큰과 위치를 나타내며, 쓰기를 위한 TokenTreeBuilder, 쿼리를 위한 TokenTree에 인덱스된 항마다 저장됩니다. 이 인덱스 파일은 더 빠른 접근을 위해 디스크에 기록된 후 메모리 매핑됩니다. 멤테이블의 데이터를 인덱싱하기 위해 SASI는 IndexMemtable 클래스를 사용합니다.
OnDiskIndex(Builder)
각 OnDiskIndex는 수정된 Suffix Array 데이터 구조의 인스턴스입니다. OnDiskIndex는 정렬된 항의 페이지 크기 블록과 항의 연관 데이터에 대한 포인터, 그리고 데이터 자체로 구성되며, 이 역시 하나 이상의 페이지 크기 블록에 저장됩니다. OnDiskIndex는 배열의 트리로 구조화되며, 각 수준은 아래 수준의 항을 설명하고 마지막 수준은 항 자체입니다. PointerLevels와 그 PointerBlocks는 항과 그 항으로 끝나는 다른 블록에 대한 포인터를 포함합니다. 마지막 수준인 DataLevel과 그 DataBlocks는 항을 포함하고 TokenTrees에 있는 데이터 자체를 가리킵니다.
OnDiskIndex에 기록되는 항은 그 모드(PREFIX, CONTAINS, 또는 SPARSE)에 따라 달라집니다. PREFIX와 SPARSE의 경우 항의 정확한 값이 OnDiskIndex마다 정확히 한 번 기록됩니다. 예를 들어 PREFIX 인덱스를 Jason, Jordan, Pavel 항으로 사용할 때 세 항 모두 인덱스에 포함됩니다. CONTAINS 인덱스는 각 항의 각 접미사에 대한 추가 항을 재귀적으로 기록합니다. 예를 들어 CONTAINS 인덱스가 이전 항을 저장한다면 ason, ordan, avel, son, rdan, vel 등도 저장합니다. 이는 문자열의 접미사에 대한 쿼리를 허용합니다. SPARSE 모드는 PREFIX와 달리 항 64 블록마다 각 항의 모든 TokenTree를 단일 것으로 병합하는 TokenTree가 구축된다는 점이 다릅니다. 이 데이터 사본은 예를 들어 타임스탬프의 큰 범위를 효율적으로 반복하는 데 사용됩니다. 인덱스 모드는 인덱스 생성 시 컬럼마다 구성 가능합니다.
TokenTree(Builder)
TokenTree는 잘 알려진 B+ 트리의 구현으로, 사용 사례에 맞게 수정되어 최적화되었습니다. 특히 SSTable의 위치 집합(long)과 토큰(long)을 연관시키도록 최적화되었습니다. long 값 집합을 허용함으로써 토큰의 해시 충돌 가능성을 수용하지만, 데이터 구조는 그러한 충돌의 드문 가능성에 맞게 최적화되어 있습니다.
write-once 환경에 최적화하기 위해 TokenTreeBuilder는 트리가 구축될 때 내부 노드를 완전히 로드하고, 데이터 구조를 대량 로드하기 위한 잘 알려진 알고리즘을 사용합니다.
TokenTree는 주어진 항과 일치하는 토큰과 파일 위치를 반복하는 수단을 제공하고, 그 반복에서 앞으로 건너뛰는 연산을 제공합니다. 이 연산은 쿼리 시점에 많이 사용됩니다.
IndexMemtable
IndexMemtable은 멤테이블에 보유된 인메모리 데이터를 인덱싱합니다. IndexMemtable은 다시 컬럼별로 TrieMemIndex 또는 SkipListMemIndex 중 하나를 관리합니다. 사용되는 인덱스 유형의 선택은 데이터에 따라 달라집니다. TrieMemIndex는 리터럴 타입에 사용됩니다. AsciiType과 UTF8Type은 기본적으로 리터럴 타입이지만, 인덱스 생성 시 is_literal 옵션으로 어떤 컬럼이든 리터럴 타입으로 구성할 수 있어요. 비리터럴 타입에는 SkipListMemIndex가 사용됩니다. TrieMemIndex는 문자형 데이터에 대한 접두사 쿼리를 효율적으로 지원하는 구현입니다. 반대로 SkipListMemIndex는 숫자 같은 다른 Cassandra 데이터 타입에 더 적합합니다.
TrieMemIndex는 com.googlecode.concurrenttrees 패키지의 ConcurrentRadixTree 또는 ConcurrentSuffixTree를 사용해 구축됩니다. 둘 사이의 선택은 인덱싱 모드(각각 PREFIX 또는 기타 모드, CONTAINS 모드)에 기반해 이루어집니다.
SkipListMemIndex는 java.util.concurrent.ConcurrentSkipListSet 위에 구축됩니다.
쿼리 (Querying)
내부 IndexExpression 표현을 SASI의 Operation과 Expression 트리로 변환하고, 수행될 작업량을 줄이기 위해 트리를 최적화하며, 쿼리 자체를 구동하는 책임을 가진 QueryPlan은 SASI 쿼리 구현의 일꾼입니다. 합집합(union)과 교집합(intersection) 연산을 효율적으로 수행하기 위해 SASI는 Cassandra의 MergeIterator와 유사하되 SASI의 사용에 특별히 맞춰지고 더 많은 기능을 포함하는 여러 iterator를 제공합니다. RangeUnionIterator는 이름이 시사하듯 쿼리와 일치하는 토큰/키 집합에 대해 집합 합집합을 수행하며, 각 집합에서 쿼리를 충족하는 데 필요한 만큼의 데이터만 읽습니다. RangeIntersectionIterator는 유사하게 자신의 데이터에 대해 집합 교집합을 수행합니다.
QueryPlan
검색 쿼리마다 생성되는 QueryPlan은 SASI 쿼리 구현의 핵심입니다. 그 작업은 분석(analysis)과 실행(execution) 두 단계로 나눌 수 있습니다.
분석 단계에서 QueryPlan은 Cassandra의 IndexExpressions 내부 표현(이 또한 OR과 괄호로 묶인 표현식 그룹화를 포함하는 쿼리를 인코딩하도록 수정되었으며, 아래 Cassandra Internal Changes 섹션 참고)에서 변환합니다. 이 과정은 Operations의 트리를 생성하며, 그 각각은 Expressions를 포함할 수 있고, 모두 쿼리의 대안적이고 더 효율적인 표현을 제공합니다.
실행 중에 QueryPlan은 Operation 트리에서 만들어진 DecoratedKey 생성 iterator를 사용합니다. 이 키들은 디스크에서 읽히고 쿼리를 충족하는지 확인하기 위한 최종 검사가 다시 한 번 Operation 트리를 사용해 이루어집니다. 원하는 양의 일치 데이터가 발견되거나 더 이상 일치하는 데이터가 없는 시점에 결과 집합은 기존 내부 구성 요소를 통해 조정자에게 반환됩니다.
테이블/컬럼패밀리별로 쿼리 수(전체/실패/타임아웃)와 지연 시간이 유지됩니다.
SASI는 또한 SSTable 전반에 걸쳐 같은 인덱스에 대한 항을 동시에 반복하는 것을 지원합니다. 동시성 계수는 cassandra.search_concurrency_factor 시스템 속성으로 제어됩니다. 기본값은 1입니다.
QueryController
각 QueryPlan은 실행 단계 전반에 걸쳐 사용되는 QueryController를 참조합니다. QueryController는 두 가지 책임이 있습니다: 리소스(인덱스)의 적절한 정리를 관리·보장하고, 사용자가 range slice timeout으로 지정한 쿼리당 시간 한도를 엄격히 적용하는 것입니다. 모든 인덱스는 나중에 안전하게 해제될 수 있도록 QueryController를 통해 접근됩니다. 시간 한도가 적용되도록 QueryController의 checkpoint 함수는 실행 경로의 특정 위치에서 호출됩니다.
QueryPlan 최적화
분석 단계에 있는 동안 QueryPlan은 쿼리에 대한 여러 잠재적 최적화를 수행합니다. 이 최적화의 목표는 실행 단계에서 수행되는 작업량을 줄이는 것입니다.
가장 간단한 최적화는 논리적 교집합(AND)으로 결합된 여러 표현식을 세 개 이상의 Expressions를 가진 단일 Operation으로 압축하는 것입니다. 예를 들어 WHERE age < 100 AND fname = 'p*' AND first_name != 'pa*' AND age > 21 쿼리는 수정하지 않으면 다음 트리를 가집니다:
┌───────┐
┌────────│ AND │──────┐
│ └───────┘ │
▼ ▼
┌───────┐ ┌──────────┐
┌─────│ AND │─────┐ │age < 100 │
│ └───────┘ │ └──────────┘
▼ ▼
┌──────────┐ ┌───────┐
│ fname=p* │ ┌─│ AND │───┐
└──────────┘ │ └───────┘ │
▼ ▼
┌──────────┐ ┌──────────┐
│fname!=pa*│ │ age > 21 │
└──────────┘ └──────────┘
QueryPlan은 루트가 마지막 AND이고 잎이 fname != pa*와 age > 21인 중복 오른쪽 가지를 제거합니다. 이 Expressions는 부모 AND로 압축되는데, AND가 결합법칙과 교환법칙을 따르므로 안전한 연산입니다. 결과 트리는 다음과 같습니다:
┌───────┐
┌────────│ AND │──────┐
│ └───────┘ │
▼ ▼
┌───────┐ ┌──────────┐
┌───────────│ AND │────────┐ │age < 100 │
│ └───────┘ │ └──────────┘
▼ │ ▼
┌──────────┐ │ ┌──────────┐
│ fname=p* │ ▼ │ age > 21 │
└──────────┘ ┌──────────┐ └──────────┘
│fname!=pa*│
└──────────┘
!=를 사용해 결과 집합에서 결과를 제외할 때 QueryPlan은 이를 처리하는 최선의 방법을 결정합니다. 예를 들어 범위 쿼리의 경우 제외를 위한 구멍이 있는 여러 부분으로 범위를 나누는 것이 최적일 수 있습니다. 이 예제 같은 문자열 쿼리에서는 인덱스를 스캔하는 동안 건너뛰거나 제외할 데이터를 단순히 기록하는 것이 더 최적입니다. 이 최적화 후 트리는 다음과 같습니다:
┌───────┐
┌────────│ AND │──────┐
│ └───────┘ │
▼ ▼
┌───────┐ ┌──────────┐
┌───────│ AND │────────┐ │age < 100 │
│ └───────┘ │ └──────────┘
▼ ▼
┌──────────────────┐ ┌──────────┐
│ fname=p* │ │ age > 21 │
│ exclusions=[pa*] │ └──────────┘
└──────────────────┘
이 쿼리에 적용되는 마지막 유형의 최적화는 — 물론 쿼리 의미를 수정하지 않고 — 트리의 가지에 걸쳐 범위 표현식을 병합하는 것입니다. 이 경우 쿼리가 모두 AND를 포함하므로 age 표현식을 축소할 수 있습니다. 이 최적화와 함께 처음의 불필요한 AND 축소를 다시 한 번 적용해 쿼리를 실행하는 데 사용하는 이 최종 트리를 만들 수 있습니다:
┌───────┐
┌──────│ AND │───────┐
│ └───────┘ │
▼ ▼
┌──────────────────┐ ┌────────────────┐
│ fname=p* │ │ 21 < age < 100 │
│ exclusions=[pa*] │ └────────────────┘
└──────────────────┘
Operations and Expressions
논의한 대로 QueryPlan은 Operations를 내부 노드로, Expressions를 잎으로 나타내는 트리를 최적화합니다. Operation 클래스는 더 구체적으로 0, 1, 2개의 Operations를 자식으로 가질 수 있고 무제한의 표현식을 가질 수 있어요. 아래 Range(Union|Intersection)Iterator 섹션에서 논의하는 쿼리 수행에 사용되는 iterator는 Operations 자식과 무관하게 결과를 투명하게 병합하는 데 필요한 로직을 구현합니다.
QueryPlan이 수행하는 최적화에 참여하는 것 외에도 Operation은 쿼리에서 반환된 행을 받아 실제로 일치하는지 최종 검증을 수행할 책임이 있습니다. 이 satisfiesBy 연산은 주어진 쿼리에 대한 Operation 트리의 루트에서 재귀적으로 수행됩니다. 이 검사는 주어진 행의 데이터에 대해 직접 수행됩니다. satisfiesBy가 어떻게 동작하는지에 대한 자세한 내용은 코드의 문서를 참고하세요.
Range(Union|Intersection)Iterator
추상 RangeIterator 클래스는 실행 경로의 다양한 계층에서 SASI가 수행하는 두 가지 주요 연산인 집합 교집합과 합집합에 대한 통합 인터페이스를 제공합니다. 이 연산들은 어느 집합의 요소에 대한 불필요한 읽기를 방지하기 위해 반복, 또는 스트리밍 방식으로 수행됩니다. 교집합과 합집합의 두 경우 모두 알고리즘은 데이터가 같은 정렬 순서(예: 항 또는 토큰 순서)로 미리 정렬되어 있음을 활용합니다.
RangeUnionIterator는 Sort-Merge-Join 알고리즘의 Merge-Join 부분을 outer-join(합집합)의 속성으로 수행합니다. 많은 iterator(합집합할 집합)에 대해 성능을 개선하는 여러 최적화로 구현됩니다. 특히 iterator는 데이터가 겹치는 범위의 하위 그룹을 많이 가질 가능성과 모든 범위가 서로 겹칠 드문 가능성을 활용합니다. 자세한 내용은 javadoc 참고.
RangeIntersectionIterator 자체는 RangeIterator의 하위 클래스가 아닙니다. 여러 클래스의 컨테이너이며, 그중 하나인 AbstractIntersectionIterator는 RangeIterator를 하위 클래스로 둡니다. SASI는 교집합 연산을 수행하는 두 가지 방법과 데이터의 일부 속성에 기반해 그 사이를 적응적으로 선택하는 기능을 지원합니다.
BounceIntersectionIterator와 BOUNCE 전략은 RangeUnionIterator처럼 Merge-Join을 수행하지만, 같은 값을 데이터 특정 병합 함수(예: 나중에 SSTable에서 조회하기 위해 list의 두 토큰을 병합)로 병합하는 inner-join과 유사한 성격입니다. 구현에 대한 자세한 내용은 javadoc 참고.
LookupIntersectionIterator와 LOOKUP 전략은 다른 연산을 수행하는데, 연관 데이터 구조에서의 조회, 또는 데이터베이스 용어로 해시 조회에 더 유사합니다. 다시 한 번 구현 세부 사항은 javadoc에서 찾을 수 있습니다.
두 iterator 사이의 선택(ADAPTIVE 전략)은 교집합되는 집합의 최소 및 최대 범위의 데이터 집합 크기 비율에 기반합니다. 최소 범위의 요소 수를 최대 범위의 요소 수로 나눈 값이 0.01 이하이면 ADAPTIVE 전략은 LookupIntersectionIterator를 선택하고, 그렇지 않으면 BounceIntersectionIterator를 선택합니다.
SASIIndex 클래스
위 구성 요소들은 Index를 구현하고 SASI 인덱스를 포함하는 테이블마다 인스턴스화되는 SASIIndex 클래스에 의해 결합됩니다. sasi.conf.DataTracker와 sasi.conf.view.View 구성 요소를 통해 테이블의 모든 인덱스를 관리하고, PerSSTableIndexWriter로 SSTable의 모든 인덱스 기록을 제어하며, Searcher로 검색을 시작합니다. 이 클래스들은 앞서 언급한 인덱싱 구성 요소를 Cassandra의 SSTable 수명 주기와 결합해, 인덱스가 Memtable이 플러시될 때뿐 아니라 SSTable이 컴팩션될 때도 기록되도록 보장합니다. 쿼리에 대해 Searcher는 QueryPlan에게 위임하고 SASI가 노출하는 예를 들어 지연 시간 메트릭을 업데이트하는 것 외에는 거의 하지 않습니다.
Cassandra 내부 변경
위 변경을 지원하고 Cassandra에 통합하기 위해 Cassandra 자체에 몇 가지 사소한 내부 변경이 이루어졌습니다. 여기서 설명합니다.
SSTable 쓰기 수명 주기 알림
SSTableFlushObserver는 observer 패턴과 같은 인터페이스로, 하위 클래스는 SSTable을 기록하는 수명 주기의 이벤트에 대해 알림을 받도록 등록할 수 있습니다. 하위 클래스는 플러시가 시작되고 끝날 때, 그리고 각 다음 행과 각 다음 컬럼이 기록되려 할 때 알림을 받을 수 있어요. 위에서 논의한 SASI의 PerSSTableIndexWriter가 현재 유일한 하위 클래스입니다.
한계 및 주의 사항 (Limitations and Caveats)
다음은 향후 업데이트에서 해결될 수 있지만 이 저장소에서는 사용할 수 없거나 현재 구현되지 않은 항목입니다.
- 클러스터는 LongTokens를 생성하는 파티셔너, 예를 들어 Murmur3Partitioner를 사용하도록 구성되어야 합니다. LongToken을 생성하지 않는 ByteOrderedPartitioner나 RandomPartitioner 같은 다른 기존 파티셔너는 SASI에서 작동하지 않습니다.
- 이 릴리스에서는 그들을 지원하기 위해 Cassandra 자체에 변경이 이루어지는 동안 Not Equals와 OR 지원이 제거되었습니다.
기여자 (Contributors)
- Pavel Yaskevich
- Jordan West
- Michael Kjellman
- Jason Brown
- Mikhail Stepura
더 알아보기 (Learn more)
- SASI 시작하기 또는 SASI 관련 CQL 인덱싱
- 데이터 정의(DDL) — CREATE CUSTOM INDEX 문