Cassandra SASI Index 技术解密-阿里云开发者社区

开发者社区> 中国Cassandra技术社区> 正文

Cassandra SASI Index 技术解密

简介: 这篇博客从技术上深入探讨了新的SASI索引,该索引可以在Cassandra中进行全文搜索(自Cassandra 3.4以来引入,但因相关重大bug的修复,我建议至少使用Cassandra 3.5以上)。

这篇博客从技术上深入探讨了新的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);
}

image


稍后,当将MemTables刷新到磁盘时,SASI将为每个SSTable 创建一个OnDiskIndex文件。

image

此写路径适用于:

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

如果对SSTables进行compaction,则OnDiskIndex文件也将遵循压实周期,并将最终合并为1个大的OnDiskIndex文件

image

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;
}

AtomicBTreePartition.RowUpdater.apply

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 text, ascii, varchar Guava ConcurrentSuffixTree name LIKE'John%' 
name LIKE'%nathan'name
LIKE'%nat%'
name ='Johnathan' 
PREFIX 其他(int,date,uuid ...) 修改后的JDK ConcurrentSkipListSet age= 20
age> = 20 and age<= 30
SPARSE 其他(int,date,uuid ...) 修改后的JDK 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大小未达到1Gbterm则处理下一个,否则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中描述。从更高的角度来看,OnDiskIndexSPARSE模式的布局为:
image


该header block包含通用元数据信息。该数据块包含匹配的token(多个)和offset(多个)索引数据。该指针块包含指向更低层级指针块。可以将其视为二叉树,其目标是帮助快速执行term的二叉查找。
Levels Count指示当前的block pointer具有的层级
Pointer Block MetaData Block Meta包含指向指针和数据块的偏移量,以加快磁盘访问速度。
Level Index Offset是整个元数据信息块与文件开头之间的偏移量

请注意,header,数据和指针块的长度是4k的倍数。这是专门为与磁盘上的块大小对齐而设计的。

2)header block

image

Descriptor Version是当前硬编码值:ab
Term Size取决于索引列的数据类型:

Data Type Term Size
intfloat 4
bigintdoubletimestamp 8
uuidtimeuuid 16
all other types -1 (variable size)


Min TermMax Term分别代表此索引文件中找到的最小与最大索引值。索引值按其类型排序(文本->字典顺序,时间戳->日期排序等)。这些最小/最大条件对范围查询很有用,并且如果[最小-最大]范围与查询之一不匹配,则SASI可以跳过整个索引文件。
Min Pk 和 Max Pk分别表示在该索引文件的匹配分区的最小&最大分区键。如果搜索查询指定了分区键,它们将再次用于跳过索引文件。
索引模式只是(PREFIXCONTAINSSPARSE)选项之一
Has PartialCASSANDRA-11434引入的布尔标志,用于向后兼容并在将索引模式CONTAINSNonTokenizingAnalyzer结合使用时启用前缀和等值匹配。下一章将对此进行详细说明。

3)非SPARSE数据块

image

Terms Count表示下一个term块中的term数。
Offsets Arrayterm块中每个条目从当前位置开始的相对偏移的数组
Term Block是一个包含term及其元数据的块,下面将对其进行描述。
TokenTree Block是一个包含token值的二进制树的块,下面将对其进行描述。
Padding 是用于4k对齐的填充区

4)非SPARSE Term Block

image

非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

image

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中的分区偏移量列表以进行查找。
image

term-TokenTree链接

6)SPARSE模式布局

如果选择索引SPARSE模式,则布局略有不同:
image

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数据块

image

SPARSE数据块
SPARSE数据块包含一个SPARSE Term Block(如下所述)并且对于每个64个条目,增加了额外的Super TokenTree Block。后者只是先前64个小型TokenTree块的合并。
因为它是一个SPARSE索引,所以对于每个索引值,最多有5个匹配的行。大多数情况下,只有1个匹配行,因此TokenTree block确实很小,几乎只包含1个条目:(token值,偏移量)。

因此,超级token树块在那里将所有(token值,偏移量)数据聚合到一个超级树中,以加速覆盖范围广泛的值的查询。

8)SPARSE term Block

image

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)指针块

现在,我们描述指针块的构建方式及其布局。
image



每次数据块达到4k的数据量时,数据块都会刷新到磁盘,并且最后一项将向上提升为pointer level。当该指针块内容再次达到4k的数据量时,它将刷新到磁盘,并且最后一个“ 指针项”(如下所述)被提升到更高级别,依此类推。
SASI从下至上建立索引数据,例如,首先建立数据级别,然后建立所有指针级别,直到根指针级别。这种自下而上的方法的优点是不需要大量内存,因为每4k数据块都会将数据刷新到磁盘上。在每个Pointer Level内,适用相同的4k数据规则,最后结束时会创建出一种二叉树。
与经典的B + Tree相反,指针块树仅在4k数据阈值上累加级别,因此不能保证树的平衡。
term在数据级别进行排好序,因此每个指针级别内的term也将排好序。
现在让我们看一下每个指针块的结构:
image

指针块
同样,该结构与Data Block非常相似。唯一的区别是指针term块而不是term块。
image

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)元数据信息

image



元数据信息块组成:

  • 级别数Pointer Block中的指针层级数
  • Pointer Block Meta:指针块计数和这些块的偏移量
  • Data Block Meta:数据块计数和这些块的偏移量
  • Super Block Meta(仅适用于SPARSE模式):Super TokenTree Block计数和这些块的偏移量
  • Level Index Offset:从文件开头到元数据信息块的偏移

image

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]

image

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 4
> 3
< 2
!= 1
其他自定义表达式 0

使用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
image

step 1
由于AND子句是可交换和关联的,SASI可以将fname谓词与age谓词合并。
image

现在,不等于运算符(!=)可以与前缀搜索合并为排除过滤器。

实际上,内部不相等谓词是使用排除过滤器进行范围扫描(在token范围内扫描)的。如果查询只有不相等的谓词,则SASI需要扫描所有OnDiskIndex文件并删除不需要的值。这不是很高效,但不可避免。
但是,如果将不相等的谓词与其他谓词(LIKE或不等式)结合使用,则SASI将在对后者进行搜索时将前者作为排除过滤器嵌入。
最后,age因为AND是可交换的和关联的,所以age谓词 可以再次合并在一起。
image

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”)(请参见上面的数据布局)。
然后,它将所有指针块元数据数据块元数据加载到内存中。image
指针块二分查找
搜索term时,SASI使用指针块执行从根指针级别到最后指针级别的二分查找。从最后一个指针级别SASI知道应该在哪个数据块中(因为指针项保留对数据块索引的引用),因此它应该寻找实际匹配的值(如果有)。
在每个数据块中,由于对term进行了排序,因此SASI可以再次使用二分查找来快速匹配目标值。image
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 SingleReadCommandCassandra负责获取匹配的行并应用对帐逻辑(最后写入胜出,墓碑...)

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中,以帮助跳过数据块。但是同样,这将需要在索引文件中存储更多的额外数据,并使读取路径更加复杂。
无论如何,对于大量数据的线性扫描,当前的读取路径并不是非常快,因此可以打开JIRACASSANDRA-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 PREFIX NonTokenizingAnalyzer 2Mb 0.29
albums_year_idx PREFIX N/A 2.3Mb 0.34
albums_artist_idx CONTAINS NonTokenizingAnalyzer 30Mb 4.41
albums_title_idx CONTAINS StandardAnalyzer 41Mb 6.03

如我们所见,使用CONTAINS模式可以将磁盘使用量提高x4-x6。由于专辑标题往往是长文本,因此膨胀率为x6。如果选择NonTokenizingAnalyzer则膨胀率会更多,因为StandardAnalyzer将文本拆分为标记,删除停用词并执行词干。所有这些有助于减小term的总大小。
结论是,慎重地使用CONTAINS模式并准备以磁盘空间为代价。没有办法避免它。即使使用像ElasticSearchSolr之类的高效搜索引擎,出于性能考虑,官方仍建议避免使用子字符串搜索(_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_idxresource_dsp_code_idx)。
每个索引列的基数为:

  • period_end_month_int36个不同的值
  • territory_code7个不同的值
  • dsp_code7个不同的值

然后,我在这些机器上部署了一个位于同一地点的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' no 2781492 330s
WHERE period_end_month_int=201406 AND dsp_code='vevo' AND territory_code='FR' no 1044547 372s
WHERE period_end_month_int=201406 AND dsp_code='vevo'<br />AND territory_code='FR' AND model_code='AdFunded' no 360334 116s
WHERE period_end_month_int=201406 100 100 26ms
WHERE period_end_month_int=201406 1000 1000 143ms
WHERE period_end_month_int=201406 10000 10000 693ms
WHERE period_end_month_int=201406 100000 100000 5087ms
WHERE period_end_month_int=201406 AND dsp_code='vevo' 100 100 35ms
WHERE period_end_month_int=201406 AND dsp_code='vevo' 1000 1000 175ms
WHERE period_end_month_int=201406 AND dsp_code='vevo' 10000 10000 1375ms
WHERE period_end_month_int=201406 AND dsp_code='vevo' 100000 100000 16984ms
WHERE period_end_month_int=201406 AND dsp_code='vevo' AND territory_code='FR' 100 100 71ms
WHERE period_end_month_int=201406 AND dsp_code='vevo' AND territory_code='FR' 1000 1000 337ms
WHERE period_end_month_int=201406 AND dsp_code='vevo' AND territory_code='FR' 10000 10000 4548ms
WHERE period_end_month_int=201406 AND dsp_code='vevo' AND territory_code='FR' 100000 100000 8658ms
WHERE period_end_month_int=201406 AND dsp_code='vevo'<br />AND territory_code='FR' AND model_code='AdFunded' 100 100 378ms
WHERE period_end_month_int=201406 AND dsp_code='vevo'<br />AND territory_code='FR' AND model_code='AdFunded' 1000 1000 2952ms
WHERE period_end_month_int=201406 AND dsp_code='vevo'<br />AND territory_code='FR' AND model_code='AdFunded' 10000 10000 5026ms
WHERE period_end_month_int=201406 AND dsp_code='vevo'<br />AND territory_code='FR' AND model_code='AdFunded' 100000 100000 16319ms

结果非常有趣。当使用服务器端分页从Cassandra中提取所有数据时,我们需要更多的谓词来缩小结果集的范围,因此速度更快,因为要检索的行数更少,这非常直观。
但是,使用LIMIT的查询结果更加令人惊讶。对于较小的limit值,我们可以看到添加的谓词越多,查询的速度就越慢...直到某个阈值(大约_10000行_),在该阈值下延迟看起来与服务器端分页查询更相似。
image

基准限制100
image

基准限制1000
image

基准限额10000
image

基准限额100000
一种可能的解释是,您添加的谓词越多,SASI必须为该查询读取的索引文件越多,因此,对于较小的LIMIT值,与从Cassandra提取原始数据相比,它花费更多的时间在索引读取上。但超过LIMIT阈值时,添加更多谓词是有益的,因为您减少了返回的行数,从而限制了Cassandra顺序扫描。
一般而言,与使用ALLOW FILTERING和分页的全表扫描相比,使用SASI或任何二级索引查询返回的行数有所限制。这是为什么 ?因为将索引文件读入内存需要付出一定的代价,而且这种代价只有在返回的结果集增加时才会增加。
 

I)SASI与搜索引擎

有人想将SASI与经典搜索引擎(例如ElasticSearchSolrDatastax 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
8a55f5a99463a7276265074b1079d74f4ab3d164.png

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
中国Cassandra技术社区
使用钉钉扫一扫加入圈子
+ 订阅

Cassandra已有10年+的沉淀,基于Amazon DynamoDB的分布式设计和 Google Bigtable 的数据模型。具备诸多优异特性:采用分布式架构、无中心、支持多活、弹性可扩展、高可用、容错、一致性可调、提供类SQL查询语言CQL等。Cassandra为互联网业务而生,已在全球广大互联网公司有成熟应用,是目前最流行的宽表数据库。阿里云在2019年8月份全球首发云Cassandra服务。

官方博客
相关链接