天天看點

Cassandra SASI Index 技術解密入群邀約

這篇部落格從技術上深入探讨了新的SASI索引,該索引可以在Cassandra中進行全文搜尋(自Cassandra 3.4以來引入,但因相關重大bug的修複,我建議至少使用Cassandra 3.5以上)。

對于本文的其餘部分,Cassandra == Apache Cassandra™

A)什麼是SASI?

SASI 是SSTable-Attached Secondary Index縮寫,例如SASI索引檔案生命周期和對應SSTable是相同。SASI是由以下工程師團隊研發的,下面是所有貢獻者的清單:

  • Pavel Yaskevich
  • Jordan West
  • Jason Brown
  • Mikhail Stepura
  • Michael Kjellman

SASI并不是另一種全新Cassandra二級索引接口的實作,它引入了一個新的想法:讓索引檔案遵循的SSTable的生命周期。這意味着每當在磁盤上建立SSTable時,也會建立相應的SASI索引檔案。什麼時候建立SSTables?

  1. 正常flush時
  2. 在壓實期間
  3. 在流操作期間(節點加入或下架)

為了啟用這種新架構,必須修改Cassandra源代碼以引入新

SSTableFlushObserver

類,該新類的目标是攔截SSTable重新整理并生成相應的SASI索引檔案。

B)SASI文法和用法

SASI使用标準CQL文法建立自定義二級索引。讓我們看看所有可用的索引選項。

1)對于文本資料類型(text,varchar和ascii)

索引

mode

  • PREFIX:允許通過以下方式比對文本值:
    • 使用

      LIKE 'prefix%'

      文法的字首
    • 使用相等(=)的完全比對
  • CONTAINS:允許通過以下方式比對文本值:
    • LIKE 'prefix%'

      字首文法(如果使用

      org.apache.cassandra.index.sasi.analyzer.NonTokenizingAnalyzer

    • LIKE '%suffix'

      字尾文法
    • LIKE '%substring%'

      子字元串文法
    • 使用等号(=)的完全比對(如果使用

      org.apache.cassandra.index.sasi.analyzer.NonTokenizingAnalyzer

mode

  • analyzed

    (是/否):激活文本分析。警告:小寫/大寫規範化需要分析器

分析器類(

analyzer_class

):

  • org.apache.cassandra.index.sasi.analyzer.NonTokenizingAnalyzer

    有選項:
    • case_sensitive

       (是/否):使用區分大小寫進行搜尋
    • normalize_lowercase

       (是/否):将文本存儲為小寫
    • normalize_uppercase

       (是/否):将文本存儲為大寫
  • org.apache.cassandra.index.sasi.analyzer.StandardAnalyzer

    • tokenization_locale

      :用于切詞,詞幹和停用詞跳過的語言環境
    • tokenization_enable_stemming

      (是/否):啟用 詞幹 (取決于語言環境)
    • tokenization_skip_stop_words

       (是/否):跳過停用詞(取決于語言環境)
    • tokenization_normalize_lowercase

    • tokenization_normalize_uppercase

文字索引示例

// Full text search on albums title
CREATE CUSTOM INDEX albums_title_idx ON music.albums(title) 
USING 'org.apache.cassandra.index.sasi.SASIIndex'
WITH OPTIONS = {
    'mode': 'CONTAINS',
    'analyzer_class': 'org.apache.cassandra.index.sasi.analyzer.StandardAnalyzer',
    'tokenization_enable_stemming': 'true',
    'tokenization_locale': 'en',
    'tokenization_skip_stop_words': 'true',
    'analyzed': 'true',
    'tokenization_normalize_lowercase': 'true'
};
 
// Full text search on artist name with neither Tokenization nor case sensitivity
CREATE CUSTOM INDEX albums_artist_idx ON music.albums(artist) 
USING 'org.apache.cassandra.index.sasi.SASIIndex'
WITH OPTIONS = {
     'mode': 'PREFIX', 
     'analyzer_class': 'org.apache.cassandra.index.sasi.analyzer.NonTokenizingAnalyzer',
     'case_sensitive': 'false'
};           

1)對于其他資料類型(int,日期,uuid…)

mode

  • PREFIX:允許通過以下方式比對值:
    • 等号(=)
    • 範圍(<,≤,>,≥)
  • SPARSE:允許通過以下方式比對SPARSE索引值:
關于SPARSE模式有一個重要的說明。通過稀疏,這意味着每個索引值,也有極少數(實際上最多5)比對的行。如果比對行多于5條,則将引發類似于以下内容的異常:

java.io.IOException: Term - 'xxx' belongs to more than 5 keys in SPARSE mode, which is not allowed.

SPARSE模式主要用于索引非常唯一的值,并允許高效存儲和高效範圍查詢。例如,如果您要存儲使用者帳戶并在該

account_creation_date

列上建立索引(毫秒精度),則給定日期的比對使用者可能很少。但是,您将能夠以

WHERE account_creation_date > xxx AND account_creation_date < yyy

有效的方式查找在(xxx,yyy)之間建立了帳戶的使用者。

數字索引示例

// Range search on numeric value
CREATE CUSTOM INDEX albums_year_idx ON music.albums(year) 
USING 'org.apache.cassandra.index.sasi.SASIIndex'
WITH OPTIONS = {'mode': 'PREFIX'};           

3)對于所有資料類型

  • max_compaction_flush_memory_in_mb

    :定義

    OnDiskIndex

    資料結構在compaction期間要保留在記憶體中的最大大小。如果索引超過此大小,它将被分段重新整理到磁盤,并在第二遍中合并在一起以建立最終

    OnDiskIndex

     檔案

C)SASI生命周期

當将mutation推送到節點時,首先将其寫入CommitLog,然後放入MemTable中。同時,将mutation索引到SASI記憶體索引結構(

[IndexMemtable](https://github.com/apache/cassandra/blob/trunk/src/java/org/apache/cassandra/index/sasi/memory/IndexMemtable.java)

)中

IndexMemtable.index

public long index(DecoratedKey key, ByteBuffer value)
{
    if (value == null || value.remaining() == 0)
        return 0;
 
    AbstractType<?> validator = index.columnIndex.getValidator();
    if (!TypeUtil.isValid(value, validator))
    {
        int size = value.remaining();
        if ((value = TypeUtil.tryUpcast(value, validator)) == null)
        {
            logger.error("Can't add column {} to index for key: {}, value size {}, validator: {}.",
                         index.columnIndex.getColumnName(),
                         index.columnIndex.keyValidator().getString(key.getKey()),
                         FBUtilities.prettyPrintMemory(size),
                         validator);
            return 0;
        }
    }
 
    return index.add(key, value);
}           
Cassandra SASI Index 技術解密入群邀約

稍後,當将MemTables重新整理到磁盤時,SASI将為每個SSTable 建立一個OnDiskIndex檔案。

Cassandra SASI Index 技術解密入群邀約

此寫路徑适用于:

  • 正常mutation
  • read repairs
  • normal repairs
  • hints replays
  • 流操作(節點加入,節點下架)

如果對SSTables進行compaction,則OnDiskIndex檔案也将遵循壓實周期,并将最終合并為1個大的OnDiskIndex檔案

Cassandra SASI Index 技術解密入群邀約

D)寫路徑

1)記憶體中

當将mutation追加到MemTable時,

AtomicBTreePartition.RowUpdater.apply()

将調用這些方法,并将mutation傳遞到适當的索引器

AtomicBTreePartition.RowUpdater.apply

public Row apply(Row insert)
{
    Row data = Rows.copy(insert, builder(insert.clustering())).build();
    indexer.onInserted(insert);
 
    this.dataSize += data.dataSize();
    this.heapSize += data.unsharedHeapSizeExcludingData();
    if (inserted == null)
        inserted = new ArrayList<>();
    inserted.add(data);
    return data;
}           
public Row apply(Row existing, Row update)
{
    Row.Builder builder = builder(existing.clustering());
    colUpdateTimeDelta = Math.min(colUpdateTimeDelta, Rows.merge(existing, update, builder, nowInSec));
 
    Row reconciled = builder.build();
 
    indexer.onUpdated(existing, reconciled);
 
    dataSize += reconciled.dataSize() - existing.dataSize();
    heapSize += reconciled.unsharedHeapSizeExcludingData() - existing.unsharedHeapSizeExcludingData();
    if (inserted == null)
        inserted = new ArrayList<>();
    inserted.add(reconciled);
    discard(existing);
 
    return reconciled;
}           

如果是SASI,它将調用

IndexMemtable.index()

函數。根據索引列的類型和索引模式,使用适當的資料結構來存儲索引值:

索引模式 資料類型 資料結構 使用文法
PREFIX text, ascii, varchar Guava 

ConcurrentRadixTree

name LIKE'John%'

name ='Johnathan'

CONTAINS

ConcurrentSuffixTree

name LIKE'John%' 

name LIKE'%nathan'name

LIKE'%nat%'

name ='Johnathan' 

其他(int,date,uuid ...) 修改後的JDK 

ConcurrentSkipListSet

age= 20

age> = 20 and age<= 30

SPARSE

ConcurrentSkipListSet

event_date >= '2016-03-23 00:00:00+0000'

AND

event_date <= '2016-04-23 00:00:00+0000'

*僅在

org.apache.cassandra.index.sasi.analyzer.NonTokenizingAnalyzer

*使用時

請注意,SASI不會攔截DELETE進行索引。實際上,已删除資料的分辨由Cassandra在讀取時候識别。SASI僅索引INSERT和UPDATE

2)flush

當Cassandra準備将SSTables重新整理到磁盤時,它将調用

SSTableWriter.observers()

以擷取所有觀察者的清單。目前隻有SASI注冊觀察者,它是

PerSSTableIndexWriter

類。native二級索引沒有實作任何觀察者:

SSTableWriter.observers

private static Collection<SSTableFlushObserver> observers(Descriptor descriptor,
                                                          Collection<Index> indexes,
                                                          OperationType operationType)
{
    if (indexes == null)
        return Collections.emptyList();
 
    List<SSTableFlushObserver> observers = new ArrayList<>(indexes.size());
    for (Index index : indexes)
    {
        SSTableFlushObserver observer = index.getFlushObserver(descriptor, operationType);
        if (observer != null)
        {
            observer.begin();
            observers.add(observer);
        }
    }
 
    return ImmutableList.copyOf(observers);
}           

然後,對于要寫入磁盤的每個新分區,

BigTableWriter.append()

将調用每個觀察者

startPartition()

方法,并傳遞目前partition在SSTable 主鍵index檔案中的偏移量:

BigTableWriter.append

public RowIndexEntry append(UnfilteredRowIterator iterator)
{
    DecoratedKey key = iterator.partitionKey();
 
    if (key.getKey().remaining() > FBUtilities.MAX_UNSIGNED_SHORT)
    {
        logger.error("Key size {} exceeds maximum of {}, skipping row", key.getKey().remaining(), FBUtilities.MAX_UNSIGNED_SHORT);
        return null;
    }
 
    if (iterator.isEmpty())
        return null;
 
    long startPosition = beforeAppend(key);
    observers.forEach((o) -> o.startPartition(key, iwriter.indexFile.position()));
     
    ...
     
}           

對于分區中的每一行,該方法将調用

org.apache.cassandra.db.ColumnIndex.add()

,并将通知每個觀察者要操作索引行内容

ColumnIndex.add

private void add(Unfiltered unfiltered) throws IOException
{
    long pos = currentPosition();
 
    if (firstClustering == null)
    {
        // Beginning of an index block. Remember the start and position
        firstClustering = unfiltered.clustering();
        startPosition = pos;
    }
 
    UnfilteredSerializer.serializer.serialize(unfiltered, header, writer, pos - previousRowStart, version);
 
    // notify observers about each new row
    if (!observers.isEmpty())
        observers.forEach((o) -> o.nextUnfilteredCluster(unfiltered));
    ...
}           

當到達MemTable的末尾時,将調用

SSTableWriter.finish()

該方法以觸發實際的重新整理。此代碼還通知任何注冊了的觀察員完成他們的工作

SSTableWriter.finish(boolean openResult)

public SSTableReader finish(boolean openResult)
{
    setOpenResult(openResult);
    txnProxy.finish();
    observers.forEach(SSTableFlushObserver::complete);
    return finished();
}           

從SASI角度來看,索引部分是在類

PerSSTableIndexWriter

内部完成的。

所有的索引邏輯都是通過

PerSSTableIndexWriter.Index.add()

method完成的對。于每個索引值(在源代碼中稱為

term

),分析器類會将其拆分為多個token(如果

StandardAnalyzer

使用了),并将(term, partition key as token value, partition offset in SSTable))三元組傳遞給該類

OnDiskIndexBuilder

如果建構的

OnDiskIndex

大小未達到1Gb,

term

則處理下一個,否則SASI将安排該部分段的異步重新整理到磁盤并開始建構新的部分。

PerSSTableIndexWriter.Index.add(ByteBuffer term, DecoratedKey key, long keyPosition)

public void add(ByteBuffer term, DecoratedKey key, long keyPosition)
        {
            if (term.remaining() == 0)
                return;
 
            boolean isAdded = false;
 
            analyzer.reset(term);
            while (analyzer.hasNext())
            {
                ByteBuffer token = analyzer.next();
                int size = token.remaining();
 
                if (token.remaining() >= OnDiskIndexBuilder.MAX_TERM_SIZE)
                {
                    logger.info("Rejecting value (size {}, maximum {}) for column {} (analyzed {}) at {} SSTable.",
                            FBUtilities.prettyPrintMemory(term.remaining()),
                            FBUtilities.prettyPrintMemory(OnDiskIndexBuilder.MAX_TERM_SIZE),
                            columnIndex.getColumnName(),
                            columnIndex.getMode().isAnalyzed,
                            descriptor);
                    continue;
                }
 
                if (!TypeUtil.isValid(token, columnIndex.getValidator()))
                {
                    if ((token = TypeUtil.tryUpcast(token, columnIndex.getValidator())) == null)
                    {
                        logger.info("({}) Failed to add {} to index for key: {}, value size was {}, validator is {}.",
                                    outputFile,
                                    columnIndex.getColumnName(),
                                    keyValidator.getString(key.getKey()),
                                    FBUtilities.prettyPrintMemory(size),
                                    columnIndex.getValidator());
                        continue;
                    }
                }
 
                currentBuilder.add(token, key, keyPosition);
                isAdded = true;
            }
 
            if (!isAdded || currentBuilder.estimatedMemoryUse() < maxMemorySize)
                return; // non of the generated tokens were added to the index or memory size wasn't reached
 
            segments.add(getExecutor().submit(scheduleSegmentFlush(false)));
        }           

分段重新整理索引檔案的原因是為了避免

OutOfMemoryException

。重新整理所有段後,将它們縫合在一起以建立最終

OnDiskIndex

檔案。

記憶體門檻值在方法中定義 

PerSSTableIndexWriter.maxMemorySize()

PerSSTableIndexWriter.maxMemorySize(ColumnIndex columnIndex)

protected long maxMemorySize(ColumnIndex columnIndex)
{
    // 1G for memtable and configuration for compaction
    return source == OperationType.FLUSH ? 1073741824L : columnIndex.getMode().maxCompactionFlushMemoryInMb;
}           

SSTable重新整理完成後,将調用

PerSSTableIndexWriter.complete()

該方法,如果存在多個段,則它将觸發索引段的縫合。

拼接階段是必需的,因為terms在每個段中排序,但不是全局的。拼接過程将有助于對term進行全局排序,并将所有TokenTree合并在一起以建立最終的索引檔案。

PerSSTableIndexWriter.complete

public void complete(final CountDownLatch latch)
{
    logger.info("Scheduling index flush to {}", outputFile);
 
    getExecutor().submit((Runnable) () -> {
        long start1 = System.nanoTime();
 
        OnDiskIndex[] parts = new OnDiskIndex[segments.size() + 1];
 
        try
        {
            // no parts present, build entire index from memory
            if (segments.isEmpty())
            {
                scheduleSegmentFlush(true).call();
                return;
            }
 
            // parts are present but there is something still in memory, let's flush that inline
            if (!currentBuilder.isEmpty())
            {
                @SuppressWarnings("resource")
                OnDiskIndex last = scheduleSegmentFlush(false).call();
                segments.add(Futures.immediateFuture(last));
            }
 
            int index = 0;
            ByteBuffer combinedMin = null, combinedMax = null;
 
            for (Future<OnDiskIndex> f : segments)
            {
                OnDiskIndex part = f.get();
                if (part == null)
                    continue;
 
                parts[index++] = part;
                combinedMin = (combinedMin == null || keyValidator.compare(combinedMin, part.minKey()) > 0) ? part.minKey() : combinedMin;
                combinedMax = (combinedMax == null || keyValidator.compare(combinedMax, part.maxKey()) < 0) ? part.maxKey() : combinedMax;
            }
 
            OnDiskIndexBuilder builder = newIndexBuilder();
            builder.finish(Pair.create(combinedMin, combinedMax),
                           new File(outputFile),
                           new CombinedTermIterator(parts));
        }
        catch (Exception | FSError e)
        {
            logger.error("Failed to flush index {}.", outputFile, e);
            FileUtils.delete(outputFile);
        }
        finally
        {
            logger.info("Index flush to {} took {} ms.", outputFile, TimeUnit.NANOSECONDS.toMillis(System.nanoTime() - start1));
 
            for (int segment = 0; segment < segmentNumber; segment++)
            {
                OnDiskIndex part = parts[segment];
 
                if (part != null)
                    FileUtils.closeQuietly(part);
 
                FileUtils.delete(outputFile + "_" + segment);
            }
 
            latch.countDown();
        }
    });
}           

E)磁盤上的資料格式和布局

1)非SPARSE模式布局

OnDiskIndex

的所有格式都在類

OnDiskIndexBuilder

中描述。從更高的角度來看,

OnDiskIndex

非SPARSE模式的布局為:

Cassandra SASI Index 技術解密入群邀約

該header block包含通用中繼資料資訊。該資料塊包含比對的token(多個)和offset(多個)索引資料。該指針塊包含指向更低層級指針塊。可以将其視為二叉樹,其目标是幫助快速執行term的二叉查找。

Levels Count訓示目前的block pointer具有的層級數

Pointer Block Meta和Data Block Meta包含指向指針和資料塊的偏移量,以加快磁盤通路速度。

Level Index Offset是整個中繼資料資訊塊與檔案開頭之間的偏移量

請注意,header,資料和指針塊的長度是4k的倍數。這是專門為與磁盤上的塊大小對齊而設計的。

2)header block

Cassandra SASI Index 技術解密入群邀約

該Descriptor Version是目前寫死值:

ab

該Term Size取決于索引列的資料類型:

Data Type Term Size
int, float 4
bigint, double, timestamp 8
uuid, timeuuid 16
all other types -1 (variable size)

Min Term和Max Term分别代表此索引檔案中找到的最小與最大索引值。索引值按其類型排序(文本->字典順序,時間戳->日期排序等)。這些最小/最大條件對範圍查詢很有用,并且如果[最小-最大]範圍與查詢之一不比對,則SASI可以跳過整個索引檔案。

Min Pk 和 Max Pk分别表示在該索引檔案的比對分區的最小&最大分區鍵。如果搜尋查詢指定了分區鍵,它們将再次用于跳過索引檔案。

索引模式隻是(PREFIX,CONTAINS或SPARSE)選項之一

Has Partial是

CASSANDRA-11434

引入的布爾标志,用于向後相容并在将索引模式CONTAINS與

NonTokenizingAnalyzer

結合使用時啟用字首和等值比對。下一章将對此進行詳細說明。

3)非SPARSE資料塊

Cassandra SASI Index 技術解密入群邀約

Terms Count表示下一個term塊中的term數。

Offsets Array是term塊中每個條目從目前位置開始的相對偏移的數組

Term Block是一個包含term及其中繼資料的塊,下面将對其進行描述。

TokenTree Block是一個包含token值的二進制樹的塊,下面将對其進行描述。

Padding 是用于4k對齊的填充區

4)非SPARSE Term Block

Cassandra SASI Index 技術解密入群邀約

非SPARSE term塊中的每個條目都擁有一個Partial Bit位,該位告訴目前term是原始term還是其字尾之一。然後寫入該term本身,後跟0x0位元組,然後是TokenTree偏移量。此偏移量指向此Term塊之後TokenTree塊中的節點。

Example of non SPARSE term block content (mode = CONTAINS, names = {Helen, Jonathan, Patrick})

Terms Count : 20, Offsets [0, 9, 21, 34, 43, 54, 63, 73, 85, 99, 109, 125, 133, 143, 151, 164, 179, 193, 204, 215]
Data Term (partial ? true)  : an. 0x0, TokenTree offset : 0
Data Term (partial ? true)  : athan. 0x0, TokenTree offset : 80
Data Term (partial ? true)  : atrick. 0x0, TokenTree offset : 160
Data Term (partial ? true)  : ck. 0x0, TokenTree offset : 240
Data Term (partial ? true)  : elen. 0x0, TokenTree offset : 320
Data Term (partial ? true)  : en. 0x0, TokenTree offset : 400
Data Term (partial ? true)  : han. 0x0, TokenTree offset : 480
Data Term (partial ? false) : helen. 0x0, TokenTree offset : 560
Data Term (partial ? true)  : hnathan. 0x0, TokenTree offset : 640
Data Term (partial ? true)  : ick. 0x0, TokenTree offset : 720
Data Term (partial ? false) : johnathan. 0x0, TokenTree offset : 800
Data Term (partial ? true)  : k. 0x0, TokenTree offset : 880
Data Term (partial ? true)  : len. 0x0, TokenTree offset : 960
Data Term (partial ? true)  : n. 0x0, TokenTree offset : 1040
Data Term (partial ? true)  : nathan. 0x0, TokenTree offset : 1136
Data Term (partial ? true)  : ohnathan. 0x0, TokenTree offset : 1216
Data Term (partial ? false) : patrick. 0x0, TokenTree offset : 1296
Data Term (partial ? true)  : rick. 0x0, TokenTree offset : 1376
Data Term (partial ? true)  : than. 0x0, TokenTree offset : 1456
Data Term (partial ? true)  : trick. 0x0, TokenTree offset : 1536           
請注意,term在每個term塊内部以及不同term塊之間是排好序的。

5)通用TokenTree Block

Cassandra SASI Index 技術解密入群邀約

node header:

  • InfoByte是一個标志。0表示目前節點是一個根節點。1表示目前節點是葉子節點,而3表示目前節點是單個節點樹的最後一個Leaf節點或Root節點。
  • token count給出給定term的比對token數量,token就是partitionKey通過murmur3 hash算出來的長整形值。
  • 最小token和最大token是不言自明的

Node Entries塊包含了(token值,偏移量(多個))序列 。由于可能發生(盡管非常罕見)的哈希沖突,是以單個token值可以引用多個分區鍵,進而可以引用SSTable中的多個偏移量。

TokenTree塊内容的示例(1個根/葉節點+ 1個具有3個葉節點的根節點)

Root Header -- Infobyte : 3, tokens count : 3, min token : -4628280296660234682, max token : 5209625165902544754
                token : -4628280296660234682, offset data : 626062
                token : -276633795570262675, offset data : 1236735
                token : 5209625165902544754, offset data : 2004475
 
...
Root Header -- Infobyte : 0, tokens count : 2, min token : 1002236203180810244, max token : 9166816315445099933
Child offsets: [4096, 8192, 12288]
Leaf Header -- Infobyte : 1, tokens count : 248, min token : -9120558309355192568, max token : 947122733220850512
                token : -9120558309355192568, offset data : 13568
                token : -9115699645219380894, offset data : 14118
                token : -9110053775482800927, offset data : 15042
                token : -9087332613408394714, offset data : 17704
 
                ...
 
Leaf Header -- Infobyte : 1, tokens count : 194, min token : 1002236203180810244, max token : 9139944811025517925
                token : 1002236203180810244, offset data : 1416779
                token : 1079301330783368458, offset data : 1427152
                token : 1136093249390936984, offset data : 1434834
                token : 1165503468422334041, offset data : 1438905 
 
                ...
 
Leaf Header -- Infobyte : 3, tokens count : 1, min token : 9166816315445099933, max token : 9166816315445099933
                token : 9166816315445099933, offset data : 2567147           

在Term塊内,有TokenTree偏移量,指向TokenTree塊内的條目。通過這種布局,每個term都可以引用相應SSTable中的分區偏移量清單以進行查找。

Cassandra SASI Index 技術解密入群邀約

term-TokenTree連結

6)SPARSE模式布局

如果選擇索引SPARSE模式,則布局略有不同:

Cassandra SASI Index 技術解密入群邀約

SPARSE模式OnDiskIndex

在中繼資料資訊區域的末尾添加了一個新的 Super Block Meta。

該Super Block Meta給出了下面描述的所有Super TokenTree Blocks的數量和偏移量

Example of Super Block Meta content

Super Block offset count : 12
Super Block offsets : [528384, 1220608, 1916928, 2609152, 3301376, 3997696, 4689920, 5382144, 6078464, 6770688, 7462912, 7995392]           

7)SPARSE資料塊

Cassandra SASI Index 技術解密入群邀約

SPARSE資料塊

SPARSE資料塊包含一個SPARSE Term Block(如下所述)并且對于每個64個條目,增加了額外的Super TokenTree Block。後者隻是先前64個小型TokenTree塊的合并。

因為它是一個SPARSE索引,是以對于每個索引值,最多有5個比對的行。大多數情況下,隻有1個比對行,是以TokenTree block确實很小,幾乎隻包含1個條目:(token值,偏移量)。

是以,超級token樹塊在那裡将所有(token值,偏移量)資料聚合到一個超級樹中,以加速覆寫範圍廣泛的值的查詢。

8)SPARSE term Block

Cassandra SASI Index 技術解密入群邀約

SPARSE Term Block

對于SPARSE Term Block,不像之前存TokenTree偏移量了,SASI僅存儲token計數和token數組(對于存在哈希沖突的情況)。

SPARSE term塊内容示例

Term count : 151, Offsets [0, 25, 50, 75, 100, 125, 150, 175, 200, 225, 250, 275, 300, 325, 350, 375, 400, 425, 450, 475, 500, 525, 550, 575, 600, 625, 650, 675, 700, 725, 750, 775, 800, 825, 850, 875, 900, 925, 950, 975, 1000, 1025, 1050, 1075, 1100, 1125, 1150, 1175, 1200, 1225, 1250, 1275, 1300, 1325, 1350, 1375, 1400, 1425, 1450, 1475, 1500, 1525, 1550, 1575, 1600, 1625, 1650, 1675, 1700, 1725, 1750, 1775, 1800, 1825, 1850, 1875, 1900, 1925, 1950, 1975, 2000, 2025, 2050, 2075, 2100, 2125, 2150, 2175, 2200, 2225, 2250, 2275, 2300, 2325, 2350, 2375, 2400, 2425, 2450, 2475, 2500, 2525, 2550, 2575, 2600, 2625, 2650, 2675, 2700, 2725, 2750, 2775, 2800, 2825, 2850, 2875, 2900, 2925, 2950, 2975, 3000, 3025, 3050, 3075, 3100, 3125, 3150, 3175, 3200, 3225, 3250, 3275, 3300, 3325, 3350, 3375, 3400, 3425, 3450, 3475, 3500, 3525, 3550, 3575, 3600, 3625, 3650, 3675, 3700, 3725, 3750]
SPARSE mode Data Term (partial ? false) : 00006d9c-2e82-4121-af62-4985ef049ab2. Token count : 1, Tokens [454478372476719604]
SPARSE mode Data Term (partial ? false) : 0000b112-bd10-4b0f-b630-756d58a120f5. Token count : 1, Tokens [-4566353347737760613]
SPARSE mode Data Term (partial ? false) : 0000c8a7-77a5-4556-aba9-7ae25484e1ac. Token count : 1, Tokens [7930016921529937694]
SPARSE mode Data Term (partial ? false) : 00022bcc-d2c7-43b7-81e0-78e8cea743e6. Token count : 1, Tokens [1669390735346713894]
SPARSE mode Data Term (partial ? false) : 0002aded-efc8-46ea-acb7-56839003eed9. Token count : 1, Tokens [8078947252161450449]
SPARSE mode Data Term (partial ? false) : 0002ffe6-cb63-4055-a3ce-f40a4bc57b46. Token count : 1, Tokens [339460836208023232]
SPARSE mode Data Term (partial ? false) : 0003b80b-3231-447f-a52c-0733cdcb4fc0. Token count : 1, Tokens [-3305941541833453269]
SPARSE mode Data Term (partial ? false) : 000477ab-8965-4d79-9cab-a1257f794eeb. Token count : 1, Tokens [-471202335109983528]
SPARSE mode Data Term (partial ? false) : 0005751e-327c-4c00-8a91-2ff78c41835f. Token count : 1, Tokens [7499979976904876222]
 
...           

9)指針塊

現在,我們描述指針塊的建構方式及其布局。

Cassandra SASI Index 技術解密入群邀約

每次資料塊達到4k的資料量時,資料塊都會重新整理到磁盤,并且最後一項将向上提升為pointer level。當該指針塊内容再次達到4k的資料量時,它将重新整理到磁盤,并且最後一個“ 指針項”(如下所述)被提升到更進階别,依此類推。

SASI從下至上建立索引資料,例如,首先建立資料級别,然後建立所有指針級别,直到根指針級别。這種自下而上的方法的優點是不需要大量記憶體,因為每4k資料塊都會将資料重新整理到磁盤上。在每個Pointer Level内,适用相同的4k資料規則,最後結束時會建立出一種二叉樹。

與經典的B + Tree相反,指針塊樹僅在4k資料門檻值塊上累加級别,是以不能保證樹的平衡。

term在資料級别進行排好序,是以每個指針級别内的term也将排好序。

現在讓我們看一下每個指針塊的結構:

Cassandra SASI Index 技術解密入群邀約

指針塊

同樣,該結構與Data Block非常相似。唯一的差別是指針term塊而不是term塊。

Cassandra SASI Index 技術解密入群邀約

Pointer Term Block

在每個Pointer Term Block内,每個項都指向“資料塊索引”,例如,相應資料塊在data level的索引位置。

該索引很有用,因為SASI将資料塊的所有偏移量存儲在數組中(可通過索引通路),該偏移數組存放在Data Block Meta 中。

Example of Pointer Block content

POINTERS BLOCKS
Term count: 7, Offsets [0, 20, 40, 60, 80, 100, 120]
Pointer Term (partial ? false) : fdcff974-bddd-4c4a-a6ff-6615de31d2a1, Block number : 740.
Pointer Term (partial ? false) : fe20819f-393c-483e-9e2f-cbd8193fdd15, Block number : 741.
Pointer Term (partial ? false) : fe722e4d-25c0-49cd-a9b3-914191e36e9c, Block number : 742.
Pointer Term (partial ? false) : fed46ad8-f5a8-406b-a29e-70e71f1862fd, Block number : 743.
Pointer Term (partial ? false) : ff352093-c3e4-4e57-83f5-fb5b9101e3e9, Block number : 744.
Pointer Term (partial ? false) : ff8c2aab-23d4-4b6e-a706-17dda3a78319, Block number : 745.
Pointer Term (partial ? false) : ffeb113c-0bdc-4be5-b3cf-1e0449b37938, Block number : 746.
Term count : 4, Offsets [0, 20, 40, 60]
Pointer Term (partial ? false) : 3f207887-da39-40c0-833c-91547548700f, Block number : 0.
Pointer Term (partial ? false) : 7e6f890a-43a8-4021-a473-f18d575d5466, Block number : 1.
Pointer Term (partial ? false) : be7c4641-d198-4a97-a279-28f54a8e1cc0, Block number : 2.
Pointer Term (partial ? false) : fd711b21-de0c-4270-bb03-956286a2c36a, Block number : 3.           

10)中繼資料資訊

Cassandra SASI Index 技術解密入群邀約

該中繼資料資訊塊組成:

  • 級别數:Pointer Block中的指針層級數
  • Pointer Block Meta:指針塊計數和這些塊的偏移量
  • Data Block Meta:資料塊計數和這些塊的偏移量
  • Super Block Meta(僅适用于SPARSE模式):Super TokenTree Block計數和這些塊的偏移量
  • Level Index Offset:從檔案開頭到中繼資料資訊塊的偏移量
Cassandra SASI Index 技術解密入群邀約

Example of Pointer Block Meta

Levels count : 2
--------------
POINTER BLOCKS META
Block offset count : 1, Block offsets : [37830656]
Block offset count : 2, Block offsets : [22806528, 37826560]           
Cassandra SASI Index 技術解密入群邀約

Example of Data Block Meta

DATA BLOCKS META
Block offset count : 748, Block offsets : [4096, 12288, 20480, ...]           

Example of Super Block Meta

Super Block offset count : 12, Super Block offsets : [528384, 1220608, 1916928, ...]           

即使在Pavel Yaskevich的幫助下,也很難對SASI源代碼進行反向工程來了解OnDiskIndex布局。原因是源代碼非常抽象(經常使用泛型和多态性使代碼互相化,這非常好)而很底層(使用位運算符來提高性能)。

為了能夠清楚地了解布局,我必須修補源代碼,以在OnDiskIndex建構的整個生命周期中引入調試點,并将内容輸出到檔案中

/tmp/debug_SASI.txt

。如果要檢視索引結構并檢視如何在磁盤上真正組織資料,隻需應用

SASI Debug Patch即可

。警告,該更新檔基于Cassandra 3.6-SNAPSPHOT建立。對于将來更新了SASI源碼的版本,應用此修補程式時,可能需要手動合并。

F)讀取路徑

1)Query Planner

內建的Query Planner是SASI的真正動力。它負責:

  1. 建立查詢計劃
  2. 分析查詢
  3. 建立一個表達式樹
  4. 使用謂詞下推和合并優化表達式樹
  5. 執行查詢

首先,分析查詢表達式(謂詞)并将其分組為MultiMap(具有多個值的映射)。表達式按列名排序,然後按運算符優先級排序。

操作符 優先級(值越大,優先級越高)
= 5
Like
>,≥ 3
<,≤ 2
!= 1
其他自定義表達式

使用LIKE謂詞的表達式将傳遞到分析器。如果使用

StandardAnalyzer

,則對查詢的值進行切詞,并将每個分詞作為替代添加。像這樣的查詢

WHERE title LIKE 'love sad'

将變成等價的

WHERE title LIKE 'love' OR title LIKE 'sad'

(請參閱

Operation.analyzeGroup()

查詢優化的結果是一個操作樹(operation tree),其中的謂詞被合并并重新排列。

讓我們考慮以下查詢: 

WHERE age < 100 AND fname = 'p*' AND first_name != 'pa*' AND age > 21

Cassandra SASI Index 技術解密入群邀約

step 1

由于AND子句是可交換和關聯的,SASI可以将

fname

謂詞與

age

謂詞合并。

Cassandra SASI Index 技術解密入群邀約

現在,不等于運算符(

!=

)可以與字首搜尋合并為排除過濾器。

Cassandra SASI Index 技術解密入群邀約

實際上,内部不相等謂詞是使用排除過濾器進行範圍掃描(在token範圍内掃描)的。如果查詢隻有不相等的謂詞,則SASI需要掃描所有OnDiskIndex檔案并删除不需要的值。這不是很高效,但不可避免。

但是,如果将不相等的謂詞與其他謂詞(LIKE或不等式)結合使用,則SASI将在對後者進行搜尋時将前者作為排除過濾器嵌入。

最後,

age

因為AND是可交換的和關聯的,是以age謂詞 可以再次合并在一起。

Cassandra SASI Index 技術解密入群邀約

SASI Operation Tree步驟4

2)叢集讀取路徑

群集上SASI查詢的讀取路徑恰好是為正常範圍掃描查詢實作的路徑。請閱讀我有關native二級索引的文章

E)群集讀路徑

一章,以清楚地了解協調器如何在整個群集中發出查詢。

評估優先使用哪個索引時,

SASIIndex.getEstimatedResultRows()

傳回

Long.MIN_VALUE

會優先于native二級索引,是以用于第一輪查詢的計算CONCURRENCY_FACTOR的公式完全無效,并且始終傳回1。

SASIIndex.getEstimatedResultRows()

public long getEstimatedResultRows()
{
    // this is temporary (until proper QueryPlan is integrated into Cassandra)
    // and allows us to priority SASI indexes if any in the query since they
    // are going to be more efficient, to query and intersect, than built-in indexes.
    return Long.MIN_VALUE;
}            
結果,目前使用SASI進行的每次搜尋始終會命中同一節點,該節點是負責群集上第一個token範圍的節點。随後的查詢(如果有的話)最終将擴充到其他節點

我們希望一旦Query Plan完全內建到Cassandra中後,便會删掉這種臨時性取巧代碼。

3)本地讀取路徑

在每個本地節點上,SASI将使用記憶體映射的緩沖區将OnDiskIndex檔案加載到系統頁面緩存中,

org.apache.cassandra.index.sasi.utils.MappedBuffer

以加快讀取和搜尋的速度。

首先,在打開索引檔案時,SASI讀取檔案末尾的最後8個位元組,以擷取中繼資料資訊塊的偏移量(“ Level Index Offset”)(請參見上面的資料布局)。

然後,它将所有指針塊中繼資料和資料塊中繼資料加載到記憶體中。

Cassandra SASI Index 技術解密入群邀約

指針塊二分查找

搜尋term時,SASI使用指針塊執行從根指針級别到最後指針級别的二分查找。從最後一個指針級别,SASI知道應該在哪個資料塊中(因為指針項保留對資料塊索引的引用),是以它應該尋找實際比對的值(如果有)。

在每個資料塊中,由于對term進行了排序,是以SASI可以再次使用二分查找來快速比對目标值。

Cassandra SASI Index 技術解密入群邀約

Term Block Binary Search

對于字首搜尋,由于所有文本term均以其原始格式存儲,是以SASI會删除

%

字元并将搜尋的值與存儲的term字首進行比較,該字首的長度與前者相同。

例如,如果索引中包含的term

'Jonathan'

和查詢

LIKE 'John%'

,SASI将删除最後4個字元的

'Jonathan'

和比較

'Jona'

'John'

。在這種情況下,沒有比對項。

如果索引模式為CONTAINS,并且使用者發出字首或相等搜尋,則SASI将僅使用Partial Bit = false的存儲term。實際上,所有存儲的Partial Bit = true的term都表示它們是更長字元串的字尾,是以不能同時用于字首或相等搜尋。

讓我們來說明一個簡單的例子。以下使用索引模式為CONTAINS 并且分詞為

NonTokenizingAnalyzer

來索引人名Helen, Johnathan & Patrick:

Stored terms for CONTAINS mode

Data Term (partial ? true)  : an. 0x0, TokenTree offset : 0
Data Term (partial ? true)  : athan. 0x0, TokenTree offset : 80
Data Term (partial ? true)  : atrick. 0x0, TokenTree offset : 160
Data Term (partial ? true)  : ck. 0x0, TokenTree offset : 240
Data Term (partial ? true)  : elen. 0x0, TokenTree offset : 320
Data Term (partial ? true)  : en. 0x0, TokenTree offset : 400
Data Term (partial ? true)  : han. 0x0, TokenTree offset : 480
Data Term (partial ? false) : helen. 0x0, TokenTree offset : 560
Data Term (partial ? true)  : hnathan. 0x0, TokenTree offset : 640
Data Term (partial ? true)  : ick. 0x0, TokenTree offset : 720
Data Term (partial ? false) : johnathan. 0x0, TokenTree offset : 800
Data Term (partial ? true)  : k. 0x0, TokenTree offset : 880
Data Term (partial ? true)  : len. 0x0, TokenTree offset : 960
Data Term (partial ? true)  : n. 0x0, TokenTree offset : 1040
Data Term (partial ? true)  : nathan. 0x0, TokenTree offset : 1136
Data Term (partial ? true)  : ohnathan. 0x0, TokenTree offset : 1216
Data Term (partial ? false) : patrick. 0x0, TokenTree offset : 1296
Data Term (partial ? true)  : rick. 0x0, TokenTree offset : 1376
Data Term (partial ? true)  : than. 0x0, TokenTree offset : 1456
Data Term (partial ? true)  : trick. 0x0, TokenTree offset : 1536           

如果現在使用字首搜尋

LIKE 'John%'

,則在20個存儲的term中,隻有3個具有Partial Bit = false(helen,johnathan&patrick),并将用于字首比對。

找到比對項後,SASI會從SSTable的開頭傳回分區的token值和偏移量。

SSTableIndex.DecoratedKeyFetcher.apply()

方法将使用此偏移量從SSTable中檢索

DecoratedKey

。此方法隻是将工作委托給

SSTableReader.keyAt()

方法。

SSTableReader.keyAt(long indexPosition)

public DecoratedKey keyAt(long indexPosition) throws IOException
    {
        DecoratedKey key;
        try (FileDataInput in = ifile.createReader(indexPosition))
        {
            if (in.isEOF())
                return null;
 
            key = decorateKey(ByteBufferUtil.readWithShortLength(in));
 
            // hint read path about key location if caching is enabled
            // this saves index summary lookup and index file iteration which whould be pretty costly
            // especially in presence of promoted column indexes
            if (isKeyCacheSetup())
                cacheKey(key, rowIndexEntrySerializer.deserialize(in));
        }
 
        return key;
    }           

調用此方法還會将條目拉到keyCache中,以便對該分區的後續通路将利用緩存直接通路磁盤上的分區。

找到

DecoratedKey

比對分區的後,SASI會将資料讀取部分移交給Cassandra 

SingleReadCommand

,Cassandra負責擷取比對的行并應用對帳邏輯(最後寫入勝出,墓碑...)

QueryController.getPartition(DecoratedKey key, ReadExecutionController executionController)

public UnfilteredRowIterator getPartition(DecoratedKey key, ReadExecutionController executionController)
{
    if (key == null)
        throw new NullPointerException();
    try
    {
        SinglePartitionReadCommand partition = SinglePartitionReadCommand.create(command.isForThrift(),
                                                                                 cfs.metadata,
                                                                                 command.nowInSec(),
                                                                                 command.columnFilter(),
                                                                                 command.rowFilter().withoutExpressions(),
                                                                                 DataLimits.NONE,
                                                                                 key,
                                                                                 command.clusteringIndexFilter(key));
 
        return partition.queryMemtableAndDisk(cfs, executionController.baseReadOpOrderGroup());
    }
    finally
    {
        checkpoint();
    }
}           

讀者應意識到SASI不能完全優化SSTable磁盤通路。實際上,索引僅儲存整個分區偏移量,而不存儲到精确比對的行。如果您的模式具有非常寬的分區,Cassandra将必須對其進行完全掃描以找到行。最糟糕的是,與native二級索引不同,在該二級索引中clustering值也保留在索引資料中,以幫助跳過到最近的位置,SASI索引僅提供分區偏移量。

我問Pavel Yaskevich,為什麼SASI團隊沒有進一步優化讀取路徑。事實證明,他們對此進行了考慮,但仍決定保留目前的設計。

實際上,為了改善讀取路徑,我們可以将偏移量存儲到行本身而不是分區中。但是問題出在Cassandra SSTable代碼基礎結構中,無法傳遞偏移量直接通路行。而且,至少要引入行偏移量,就需要進行重大更改。

第二個想法是将clustering值存儲在OnDiskIndex中,以幫助跳過資料塊。但是同樣,這将需要在索引檔案中存儲更多的額外資料,并使讀取路徑更加複雜。

無論如何,對于大量資料的線性掃描,目前的讀取路徑并不是非常快,是以可以打開JIRA

CASSANDRA-9259對其

進行改進,一旦完成,SASI自然可以從性能改進中受益。

G)磁盤空間使用

為了能夠搜尋字尾,SASI必須從原始term中計算出所有字尾組合,是以,term越長,存儲的字尾就越多。字尾數等于

term_size - 1

作為比較,我有一個

albums

具有以下架構的表:

Table Albums Schema

CREATE TABLE music.albums (
    id uuid PRIMARY KEY,
    artist text,
    country text,
    quality text,
    status text,
    title text,
    year int
)           

該表包含≈110 000張專輯,磁盤上的SSTable大小約為6.8Mb。我在此表上建立了一些索引。下面是每個索引的磁盤空間使用情況的概述:

Index Name Index Mode Analyzer Index Size Index Size/SSTable Size Ratio
albums_country_idx

NonTokenizingAnalyzer

2Mb 0.29
albums_year_idx N/A 2.3Mb 0.34
albums_artist_idx

NonTokenizingAnalyzer

30Mb 4.41
albums_title_idx

StandardAnalyzer

41Mb 6.03

如我們所見,使用CONTAINS模式可以将磁盤使用量提高x4-x6。由于專輯标題往往是長文本,是以膨脹率為x6。如果選擇

NonTokenizingAnalyzer

則膨脹率會更多,因為

StandardAnalyzer

将文本拆分為标記,删除停用詞并執行詞幹。所有這些有助于減小term的總大小。

結論是,慎重地使用CONTAINS模式并準備以磁盤空間為代價。沒有辦法避免它。即使使用像ElasticSearch或Solr之類的高效搜尋引擎,出于性能考慮,官方仍建議避免使用子字元串搜尋(_

LIKE %substring%

_)。

H)一些性能Benchmarks

以下是用于基準測試的硬體規格:

  • 13台裸機
  • 6個CPU(HT)= 12核
  • 64Gb RAM
  • 4個SSD RAID 0,總計1.5Tb

Cassandra配置:

  • numtoken:64
  • parallel_compactors:2個
  • compaction_throughput_mb_per_sec:256
  • 堆32Gb, GC:G1

Test Schema

CREATE KEYSPACE test WITH replication = {'class': 'NetworkTopologyStrategy', 'datacenter1': '2'}  AND durable_writes = true;
 
create table if not exists test.resource_bench ( 
 dsr_id uuid,
 rel_seq bigint,
 seq bigint,
 dsp_code varchar,
 model_code varchar,
 media_code varchar,
 transfer_code varchar,
 commercial_offer_code varchar,
 territory_code varchar,
 period_end_month_int int,
 authorized_societies_txt text,
 rel_type text,
 status text,
 dsp_release_code text,
 title text,
 contributors_name list<text>,
 unic_work text,
 paying_net_qty bigint,
PRIMARY KEY ((dsr_id, rel_seq), seq)
) WITH CLUSTERING ORDER BY (seq ASC)
AND compaction = {'class': 'org.apache.cassandra.db.compaction.SizeTieredCompactionStrategy', 'max_threshold': '32', 'min_threshold': '4'}; 
 
CREATE CUSTOM INDEX resource_period_end_month_int_idx ON sharon.resource_bench (period_end_month_int) USING 'org.apache.cassandra.index.sasi.SASIIndex' WITH OPTIONS = {'mode': 'PREFIX'};
 
CREATE CUSTOM INDEX resource_territory_code_idx ON sharon.resource_bench (territory_code) USING 'org.apache.cassandra.index.sasi.SASIIndex' WITH OPTIONS = {'analyzer_class': 'org.apache.cassandra.index.sasi.analyzer.NonTokenizingAnalyzer', 'case_sensitive': 'false'};
 
CREATE CUSTOM INDEX resource_dsp_code_idx ON sharon.resource_bench (dsp_code) USING 'org.apache.cassandra.index.sasi.SASIIndex' WITH OPTIONS = {'analyzer_class': 'org.apache.cassandra.index.sasi.analyzer.NonTokenizingAnalyzer', 'case_sensitive': 'false'};
           

該表具有1個數字DENSE索引(

resource_period_end_month_int_idx

)和2個文本DENSE索引(

resource_territory_code_idx

resource_dsp_code_idx

)。

每個索引列的基數為:

  • period_end_month_int

    :36個不同的值
  • territory_code

    :7個不同的值
  • dsp_code

然後,我在這些機器上部署了一個位于同一地點的Spark安裝,并使用一個Spark腳本注入了13億行。

如果沒有SASI索引,則插入花費了大約4小時。使用以上3個名額,大約需要6小時。顯然,由于建立和重新整理索引檔案所需的開銷,索引會影響寫入和壓縮吞吐量。

我還對從現有資料建構SASI索引所花費的時間進行了基準測試:

  • period_end_month_int

    :1h20
  • territory_code

    :1小時
  • model_code

    :(僅2個distinc值的DENSE文本索引):1h34

接下來,我對查詢延遲進行了基準測試。有2種不同的方案。首先,我使用伺服器端分頁來擷取與某些謂詞比對的所有資料。第二個測試添加了一個具有不同值的LIMIT子句,以檢視它如何影響響應時間。

請注意,如果未設定LIMIT,則_fetchSize = 10000_且每個頁面的睡眠間隔為20 ms
查詢 limit 行數 耗時

WHERE period_end_month_int=201401

no 36109986 609s

WHERE period_end_month_int=201406 AND dsp_code='vevo'

2781492 330s

WHERE period_end_month_int=201406 AND dsp_code='vevo' AND territory_code='FR'

1044547 372s

WHERE period_end_month_int=201406 AND dsp_code='vevo'<br />AND territory_code='FR' AND model_code='AdFunded'

360334 116s

WHERE period_end_month_int=201406

100 26ms

WHERE period_end_month_int=201406

1000 143ms

WHERE period_end_month_int=201406

10000 693ms

WHERE period_end_month_int=201406

100000 5087ms

WHERE period_end_month_int=201406 AND dsp_code='vevo'

35ms

WHERE period_end_month_int=201406 AND dsp_code='vevo'

175ms

WHERE period_end_month_int=201406 AND dsp_code='vevo'

1375ms

WHERE period_end_month_int=201406 AND dsp_code='vevo'

16984ms

WHERE period_end_month_int=201406 AND dsp_code='vevo' AND territory_code='FR'

71ms

WHERE period_end_month_int=201406 AND dsp_code='vevo' AND territory_code='FR'

337ms

WHERE period_end_month_int=201406 AND dsp_code='vevo' AND territory_code='FR'

4548ms

WHERE period_end_month_int=201406 AND dsp_code='vevo' AND territory_code='FR'

8658ms

WHERE period_end_month_int=201406 AND dsp_code='vevo'<br />AND territory_code='FR' AND model_code='AdFunded'

378ms

WHERE period_end_month_int=201406 AND dsp_code='vevo'<br />AND territory_code='FR' AND model_code='AdFunded'

2952ms

WHERE period_end_month_int=201406 AND dsp_code='vevo'<br />AND territory_code='FR' AND model_code='AdFunded'

5026ms

WHERE period_end_month_int=201406 AND dsp_code='vevo'<br />AND territory_code='FR' AND model_code='AdFunded'

16319ms

結果非常有趣。當使用伺服器端分頁從Cassandra中提取所有資料時,我們需要更多的謂詞來縮小結果集的範圍,是以速度更快,因為要檢索的行數更少,這非常直覺。

但是,使用LIMIT的查詢結果更加令人驚訝。對于較小的limit值,我們可以看到添加的謂詞越多,查詢的速度就越慢...直到某個門檻值(大約_10000行_),在該門檻值下延遲看起來與伺服器端分頁查詢更相似。

Cassandra SASI Index 技術解密入群邀約

基準限制100

Cassandra SASI Index 技術解密入群邀約

基準限制1000

Cassandra SASI Index 技術解密入群邀約

基準限額10000

Cassandra SASI Index 技術解密入群邀約

基準限額100000

一種可能的解釋是,您添加的謂詞越多,SASI必須為該查詢讀取的索引檔案越多,是以,對于較小的LIMIT值,與從Cassandra提取原始資料相比,它花費更多的時間在索引讀取上。但超過LIMIT門檻值時,添加更多謂詞是有益的,因為您減少了傳回的行數,進而限制了Cassandra順序掃描。

一般而言,與使用ALLOW FILTERING和分頁的全表掃描相比,使用SASI或任何二級索引查詢傳回的行數有所限制。這是為什麼 ?因為将索引檔案讀入記憶體需要付出一定的代價,而且這種代價隻有在傳回的結果集增加時才會增加。

I)SASI與搜尋引擎

有人想将SASI與經典搜尋引擎(例如ElasticSearch,Solr或Datastax Enterprise Search)進行比較。這種比較非常簡單。盡管具有便利性,并且SASI已與Cassandra和CQL 緊密內建,但與真正的搜尋引擎相比,它具有許多缺點。

  • SASI在磁盤上需要2次傳遞才能擷取資料:1次傳遞以讀取索引檔案,而1次傳遞為正常的Cassandra讀取路徑,而搜尋引擎以單次傳遞的方式檢索結果(DSE Search也具有_singlePass_選項)。根據實體學定律,即使我們改進了Cassandra中的順序讀取路徑,SASI始終會變慢
  • 盡管SASI允許切詞和CONTAINS模式進行全文搜尋,但對比對的term沒有評分
  • SASI以token範圍順序傳回結果,從使用者角度來看,可以将其視為随機順序。即使使用LIMIT子句,也不可能要求對結果進行整體排序。搜尋引擎沒有此限制
  • 最後但并非最不重要的一點是,無法使用SASI執行聚合(或faceting)。

話雖如此,如果您不需要排序,分組或計分,那麼SASI是搜尋引擎替代絕佳選擇。

但是,我永遠不會想到有一天可以在Cassandra用_

LIKE '%term%'

_謂詞,是以從這個角度來看,它已經比過去的局限性有了很大的改進。

J)SASI權衡

在以下情況下,您應該使用SASI:

  • 您需要多條件搜尋,而無需排序/分組/評分
  • 您的搜尋查詢通常需要100至1000行
  • 您總是知道要搜尋的行的分區鍵(此鍵也适用于native二級索引)
  • 您想要索引靜态列(SASI沒有懲罰,因為它索引了整個分區)

在以下情況下,應避免SASI:

  • 您要索引的分區非常寬,SASI僅提供分區偏移量。仍然需要在Cassandra一側執行昂貴的線性掃描,而無法使用clustering列來快速跳過塊
  • 您在搜尋延遲方面具有很強的SLA,例如亞秒級要求
  • 你需要搜尋分析場景
  • 搜尋結果的順序對您很重要

如果您決定在生産中嘗試使用SASI,請記住,SASI确實會影響您的寫入/重新整理吞吐量,壓縮吞吐量以及修複和流操作。可以預料的是,SASI索引檔案遵循SSTable生命周期。

還請注意CONTAINS模式,其磁盤空間開銷可能會過高。

避免單獨使用

!=

,因為它最終會掃描整個token範圍,這很費,與其他謂詞結合使用。

本文譯至原文:

http://www.doanduyhai.com/blog/?p=2058#sasi_syntax_and_usage

入群邀約

為了營造一個開放的 Cassandra 技術交流環境,社群建立了微信群公衆号和釘釘群,為廣大使用者提供專業的技術分享及問答,定期開展專家技術直播,歡迎大家加入。另外阿裡雲提供免費Cassandra試用:

https://www.aliyun.com/product/cds
Cassandra SASI Index 技術解密入群邀約

繼續閱讀