这篇博客从技术上深入探讨了新的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？
- 正常flush时
- 在压实期间
- 在流操作期间（节点加入或下架）
为了启用这种新架构，必须修改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
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);
} 
稍后，当将MemTables刷新到磁盘时，SASI将为每个SSTable 创建一个OnDiskIndex文件。
此写路径适用于：
- 正常mutation
- read repairs
- normal repairs
- hints replays
- 流操作（节点加入，节点下架）
如果对SSTables进行compaction，则OnDiskIndex文件也将遵循压实周期，并将最终合并为1个大的OnDiskIndex文件
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 | name LIKE'John％' name ='Johnathan' |
| CONTAINS | | name LIKE'John％' name LIKE'％nathan'name LIKE'％nat％' name ='Johnathan' | |
| 其他（int，date，uuid ...） | 修改后的JDK | age= 20 age> = 20 and age<= 30 | |
| SPARSE | | 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模式的布局为：
该header block包含通用元数据信息。该数据块包含匹配的token（多个）和offset（多个）索引数据。该指针块包含指向更低层级指针块。可以将其视为二叉树，其目标是帮助快速执行term的二叉查找。
Levels Count指示当前的block pointer具有的层级数
Pointer Block Meta和Data Block Meta包含指向指针和数据块的偏移量，以加快磁盘访问速度。
Level Index Offset是整个元数据信息块与文件开头之间的偏移量
请注意，header，数据和指针块的长度是4k的倍数。这是专门为与磁盘上的块大小对齐而设计的。
2）header block
该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数据块
Terms Count表示下一个term块中的term数。
Offsets Array是term块中每个条目从当前位置开始的相对偏移的数组
Term Block是一个包含term及其元数据的块，下面将对其进行描述。
TokenTree Block是一个包含token值的二进制树的块，下面将对其进行描述。
Padding 是用于4k对齐的填充区
4）非SPARSE Term Block
非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
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中的分区偏移量列表以进行查找。
term-TokenTree链接
6）SPARSE模式布局
如果选择索引SPARSE模式，则布局略有不同：
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数据块
SPARSE数据块
SPARSE数据块包含一个SPARSE Term Block（如下所述）并且对于每个64个条目，增加了额外的Super TokenTree Block。后者只是先前64个小型TokenTree块的合并。
因为它是一个SPARSE索引，所以对于每个索引值，最多有5个匹配的行。大多数情况下，只有1个匹配行，因此TokenTree block确实很小，几乎只包含1个条目：（token值，偏移量）。
因此，超级token树块在那里将所有（token值，偏移量）数据聚合到一个超级树中，以加速覆盖范围广泛的值的查询。
8）SPARSE term Block
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）指针块
现在，我们描述指针块的构建方式及其布局。
每次数据块达到4k的数据量时，数据块都会刷新到磁盘，并且最后一项将向上提升为pointer level。当该指针块内容再次达到4k的数据量时，它将刷新到磁盘，并且最后一个“ 指针项”（如下所述）被提升到更高级别，依此类推。
SASI从下至上建立索引数据，例如，首先建立数据级别，然后建立所有指针级别，直到根指针级别。这种自下而上的方法的优点是不需要大量内存，因为每4k数据块都会将数据刷新到磁盘上。在每个Pointer Level内，适用相同的4k数据规则，最后结束时会创建出一种二叉树。
与经典的B + Tree相反，指针块树仅在4k数据阈值块上累加级别，因此不能保证树的平衡。
term在数据级别进行排好序，因此每个指针级别内的term也将排好序。
现在让我们看一下每个指针块的结构：
指针块
同样，该结构与Data Block非常相似。唯一的区别是指针term块而不是term块。
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）元数据信息
该元数据信息块组成：
- 级别数：Pointer Block中的指针层级数
- Pointer Block Meta：指针块计数和这些块的偏移量
- Data Block Meta：数据块计数和这些块的偏移量
- Super Block Meta（仅适用于SPARSE模式）：Super TokenTree Block计数和这些块的偏移量
- Level Index Offset：从文件开头到元数据信息块的偏移量
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] 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的真正动力。它负责：
- 创建查询计划
- 分析查询
- 建立一个表达式树
- 使用谓词下推和合并优化表达式树
- 执行查询
首先，分析查询表达式（谓词）并将其分组为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
step 1
由于AND子句是可交换和关联的，SASI可以将
fname
谓词与
age
谓词合并。
现在，不等于运算符（
!=
）可以与前缀搜索合并为排除过滤器。
实际上，内部不相等谓词是使用排除过滤器进行范围扫描（在token范围内扫描）的。如果查询只有不相等的谓词，则SASI需要扫描所有OnDiskIndex文件并删除不需要的值。这不是很高效，但不可避免。
但是，如果将不相等的谓词与其他谓词（LIKE或不等式）结合使用，则SASI将在对后者进行搜索时将前者作为排除过滤器嵌入。
最后，
age
因为AND是可交换的和关联的，所以age谓词 可以再次合并在一起。
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”）（请参见上面的数据布局）。
然后，它将所有指针块元数据和数据块元数据加载到内存中。
指针块二分查找
搜索term时，SASI使用指针块执行从根指针级别到最后指针级别的二分查找。从最后一个指针级别，SASI知道应该在哪个数据块中（因为指针项保留对数据块索引的引用），因此它应该寻找实际匹配的值（如果有）。
在每个数据块中，由于对term进行了排序，因此SASI可以再次使用二分查找来快速匹配目标值。
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 | | 2Mb | 0.29 | |
| albums_year_idx | N/A | 2.3Mb | 0.34 | |
| albums_artist_idx | | 30Mb | 4.41 | |
| albums_title_idx | | 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
-
territory_code
-
dsp_code
然后，我在这些机器上部署了一个位于同一地点的Spark安装，并使用一个Spark脚本注入了13亿行。
如果没有SASI索引，则插入花费了大约4小时。使用以上3个指标，大约需要6小时。显然，由于创建和刷新索引文件所需的开销，索引会影响写入和压缩吞吐量。
我还对从现有数据构建SASI索引所花费的时间进行了基准测试：
-
period_end_month_int
-
territory_code
-
model_code
接下来，我对查询延迟进行了基准测试。有2种不同的方案。首先，我使用服务器端分页来获取与某些谓词匹配的所有数据。第二个测试添加了一个具有不同值的LIMIT子句，以查看它如何影响响应时间。
请注意，如果未设置LIMIT，则_fetchSize = 10000_且每个页面的睡眠间隔为20 ms
| 查询 | limit | 行数 | 耗时 |
|---|---|---|---|
| no | 36109986 | 609s |
| 2781492 | 330s | |
| 1044547 | 372s | |
| 360334 | 116s | |
| 100 | 26ms | |
| 1000 | 143ms | |
| 10000 | 693ms | |
| 100000 | 5087ms | |
| 35ms | ||
| 175ms | ||
| 1375ms | ||
| 16984ms | ||
| 71ms | ||
| 337ms | ||
| 4548ms | ||
| 8658ms | ||
| 378ms | ||
| 2952ms | ||
| 5026ms | ||
| 16319ms |
结果非常有趣。当使用服务器端分页从Cassandra中提取所有数据时，我们需要更多的谓词来缩小结果集的范围，因此速度更快，因为要检索的行数更少，这非常直观。
但是，使用LIMIT的查询结果更加令人惊讶。对于较小的limit值，我们可以看到添加的谓词越多，查询的速度就越慢...直到某个阈值（大约_10000行_），在该阈值下延迟看起来与服务器端分页查询更相似。
基准限制100
基准限制1000
基准限额10000
基准限额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