Posts

fst库是"使用Automata和Rust索引1,600,000,000Keys"作者所建立的实现其博客思想的库。作者文章的后续就是针对其博客思想的构建历程，我们在这里先插入一下作者实现的这个库的一些主要功能，方便理解作者后续的思想。原文地址 fst是一个用于有效存储和搜索有序集合或者key是字符串的map的库。这个crate的一个关键设计目标是支持存储和搜索非常大的集合或map（即数十亿）。这意味着已经付出了很多努力来确保所有操作都是内存高效的。 fst is a library for efficiently storing and searching ordered sets or maps where the keys are byte strings. A key design goal of this crate is to support storing and searching very large sets or maps (i.e., billions). This means that much effort has gone in to making sure that all operations are memory efficient. 集合和映射由有限状态机(FSA)表示，它是一种对key中公共前缀和后缀的压缩形式。此外，有限状态机可以有效的对自动机（如正则表达式或模糊查询的Levenshtein距离）或字典范围进行查询。 Sets and maps are represented by a finite state machine, which acts as a form of compression on common prefixes and suffixes in the keys....

有序map(Ordered maps) 与有序集合一样，有序map类似于map，但在map的键上定义了顺序。就像集合一样，有序map通常使用二叉搜索树或btree实现，无序map通常使用哈希表实现。在我们的例子中，我们将看一个使用确定性非循环有限状态转换器的实现（缩写为 FST）。 As with ordered sets, an ordered map is like a map, but with an ordering defined on the keys of the map. Just like sets, ordered maps are typically implemented with a binary search tree or a btree, and unordered maps are typically implemented with a hash table. In our case, we will look at an implementation that uses a deterministic acyclic finite state transducer (abbreviated FST)....

原文链接 目录 (Table of Contents) 这篇文章很长，所以我整理了一个目录, 如果你想跳过某些内容。 This article is pretty long, so I’ve put together a table of contents in case you want to skip around. 第一部分讨论了有限状态机及其作为数据结构的抽象用途。本节旨在为您提供一个推理数据结构的思维模型。本节没有代码。 The first section discusses finite state machines and their use as data structures in the abstract. This section is meant to give you a mental model with which to reason about the data structure. There is no code in this section. 第二部分采用第一部分中开发的抽象，并用一个实现来演示它。本节主要是概述如何使用我的fst 库。本节包含代码。我们将讨论一些实现细节，但会避免过于混乱。如果您不关心代码而只想查看真实数据的实验，则可以跳过此部分。...

原文链接 事实证明，有限状态机对表达计算以外的其他事情很有用。有限状态机也可以用来紧凑地表示可以快速搜索的有序集合(Maps)或字符串映射(Sets)。 It turns out that finite state machines are useful for things other than expressing computation. Finite state machines can also be used to compactly represent ordered sets or maps of strings that can be searched very quickly. 在本文中，我将向您介绍有限状态机作为表示有序集合和映射的数据结构。这包括引入一个用 Rust 编写的实现，称为 fst crate。它带有完整的 API 文档。我还将向您展示如何使用简单的命令行工具构建它们。最后，我将讨论一些实验，最终从 2015 年 7 月的 Common Crawl Archive 中索引超过 1,600,000,000 个 URL（134 GB） In this article, I will teach you about finite state machines as a data structure for representing ordered sets and maps....

新进入公司，接手了一个发票系统。技术是比较简单的，就是普通的springboot架构加上mysql的数据库。数据量整体上也不是很大，总表也就千万级别的数据，理论上这点数据不应该有什么性能问题的，但是其中的一个菜单在查询的时候，总是感觉到特别的慢。 比较慢的这个菜单我们称之为A菜单，A菜单和B菜单，C菜单在底层是公用的同一个mybatis的select语句。同时，查询时都会加上时间范围的限制，而且这个时间字段也是正常加上索引的。但是很奇怪的是，A菜单查询时经常需要几十秒，有时甚至查不到结果。B菜单和C菜单速度就很快了，一般1秒内都会查询出结果。大家都是用时间范围查询，也没加其他太多的条件。理论上不大可能有很大差别的。后面无意间发现，连查出来的数据量都不一样，这就更奇怪了，页面的查询条件也一样啊。 在下面我们先回顾一下SQL的八股，对于数据库中字段为NULL的八股。 NULL值会影响一些函数的统计，如count，遇到NULL值，这条记录不会统计在内。 B+树不存储NULL，所以索引用不到NULL，会造成第一点中说的统计不到的问题。 NOT IN子查询在有NULL值的情况下返回的结果都是空值。 MySQL在进行比较的时候，NULL会参与字段的比较，因为NULL是一种比较特殊的数据类型，数据库在处理时需要进行特数处理，增加了数据库处理记录的复杂性。 此次的问题就在于八股中的第二点。后续经过仔细的排查，我发现A菜单中的时间范围对应的字段是create_time, 表中所有的行都存在create_time值。虽然create_time字段存在索引，但是可能由于表太大，且时间范围内命中的记录又比较多，因此sql最终执行的时候优化并没有走索引，而是全表，后续加上了force index，A菜单的查询效率就从60+秒降到了3+秒.B菜单和C菜单中的时间范围对应的字段是apply_time, 因为业务逻辑的原因，这个字段不为空的行数其实并没有很多，量级大概在10W+，同时这个字段上也加上了索引，结合八股的第二条，我们就可以知道B菜单和C菜单其实一直是在10W+数据中进行筛选，所以速度也比较快,同时查询出来的数据也相对少很多。