《数据结构与算法之美》实战篇笔记

2021-06-01

摘要：极客时间《数据结构与算法之美》实战篇笔记，Redis、搜索引擎、Disruptor、鉴权限流、短网址服务涉及到的数据结构

Redis

介绍

Redis 数据库是一种键值（Key-Value）非关系型数据库。它只能通过“键”来查询“值”，也让 Redis 的读写效率非常高。键的数据类型是字符串，值的数据类型有很多，常用的有：字符串、列表、字典、集合、有序集合。Redis 主要是作为内存数据库来使用，数据主要是存储在内存中的，但也支持将数据存储在硬盘中。

列表（List

列表对应两种实现方法：压缩列表（ziplist）和双向循环列表
1、压缩列表
当列表中存储的数据量比较小，且满足两点要求：1、列表中保存的单个数据（有可能是字符串类型的）小于 64 字节；2、列表中数据个数少于 512 个。这时会使用压缩列表。
压缩列表相较于数组的存储思路而言更节省内存。数组要求每个元素的大小相同，如果要存储不同长度的字符串，那就需要用最大长度的字符串大小作为元素的大小。压缩数组是通过一片连续的内存空间，来存储数据，且允许存储的数据大小不同。但压缩数组不支持随机访问，一般是通过 key 获取整个 value 的值，也就是整个压缩列表的数据。
2、双向循环列表
不满足压缩列表的要求时就会使用双向循环列表来存储数据。Redis 额外定义一个 list 结构体，来组织链表的首、尾指针和和长度等信息

字典（hash）

字典类型用来存储一组数据对，每个数据对又包含键值两部分。字典也有两种实现方法：压缩列表和散列表
1、压缩列表
当数据量比较小，满足两点要求：1、字典中的键和值都小于 64 字节；2、字典中键值对的个数小于 512 个。
2、散列表
不满足压缩列表的要求时就会使用散列表存储数据。Redis 使用 MurmurHash2 作为哈希函数，使用链表法解决哈希冲突问题，并且支持渐进式扩容缩容策略，将数据的搬移分批进行

集合（set）

集合用来存储一组不重复的数据。有两种实现方法：1、有序数组；2、散列表
1、有序数组
当数据满足两点要求：1、存储的数据都是整数；2、存储的数据元素个数不超过 512 个。就会使用有序数组
2、散列表
当数据不满足有序数组要求时，就会使用散列表

有序集合（sortedset）

有序集合用来存储一组数据，并且每个数据会附带一个得分。通过得分大小，将数据组织成跳表，以支持快速地按照得分值、得分区间获取数据。两种实现方法：1、压缩列表；2、跳表
1、压缩列表
当数据量比较小，且满足两点要求：1、所有数据的大小都要小于 64 字节；2、元素个数要小于 128 个。会使用压缩列表实现有序集合。
2、跳表
不满压缩列表的要求时会使用跳表

数据结构持久化

“持久化”可以笼统地理解为“存储到磁盘”。一般有两种方法将数据结构持久化到硬盘：
1、Redis 采用的持久化思路，清除原有的存储结构，只将数据存储到磁盘中。但数据从硬盘还原到内存的过程，会耗用比较多的时间。
2、保留原来的存储格式，将数据按照原有的格式存储在磁盘中

搜索引擎

搜索引擎大致可以分为四个部分：搜集、分析、索引、查询。

搜集

搜集就是利用爬虫爬取网页。搜索引擎把整个互联网看作数据结构中的有向图，把每个页面看作一个顶点。如果页面包含包含另一个页面的链接，那就在两个顶点之间连一条有向边，然后利用图的广度优先搜索来遍历整个互联网中的网页。广度优先搜索策略，将权重比较高的页面链接作为种子链接放入队列，不停的出队、爬取页面，再将页面中的新链接入队
关键技术细节：
1、待爬取网页链接文件：links.bin
用一个存储在磁盘中的文件（links.bin）来作为广度优先搜索中的队列，爬虫从 links.bin 文件中，取出链接去爬取对应的页面。将页面解析出来的链接，再存储到 links.bin 文件中。这样硬盘可以存储比内存更多的链接，也支持断点续爬。
2、网页判重文件：bloom_filter.bin
使用布隆过滤器避免重复爬取相同的网页，且定期地将布隆过滤器持久化到磁盘中，存储在 bloom_filter.bin 文件中。发生机器宕机也可以在重启后，从磁盘中读取 bloom_filter.bin 文件，将数据恢复到内存中
3、原始网页存储文件：doc_raw.bin
爬取网页后，要将其存储下来，以供后面的分析、索引操作使用。如果每个页面单独保存为一个文件，这样数量会很多。使用一个文件存储多个页面数据，每个个网页之间，通过一定的标识进行分隔（\t\r\n等）、索引（doc_id），方便后续读取。

// 网页编号 网页大小 网页内容 分隔符
doc1_id \t doc1_size \t doc1 \r\n\r\n
doc2_id \t doc2_size \t doc2 \r\n\r\n
...

当这个文件大于一定数值时，可以新建一个文件来存储新爬取的页面数据
4、网页链接及其编号的对应文件：doc_id.bin
按照网页被爬取的先后顺序，从小到大依次为文件中的网页数据编号，并将网页链接跟编号（doc_id）之间的对应关系，存储在 doc_id.bin 文件中。

分析

爬虫爬取网页后，需要对网页进行离线分析。分析主要包括两部分：
1、抽取网页文本信息
先去掉<style></style><script></script><option></option>这三组标签中的内容（可以利用 AC 自动机），再去掉所有 HTML 标签
2、分词并创建临时索引
得到网页的文本内容后，需要进行分词并创建临时索引。如果是英文网页，通过空格、标点符号等分隔符就可以将每个单词分割开来。如果是中文，简单的方法：基于字典和规则的分词方法。借助词库并采用最长匹配规则，比如将词库中的单词，构建成 Trie 树结构，然后拿网页文本在 Trie 树中匹配。每个网页匹配后都得到一组单词列表，然后使用一个散列表维护单词编号与单词之间的关系。再将单词编号与网页之间的对应关系（doc_id）写入到临时索引文件 tmp_Index.bin 中，像这样存储单词编号更节省存储空间。

// 单词编号 网页编号 分隔符
term1_id \t doc_id \r\n
term2_id \t doc_id \r\n
...

处理完所有网页后，再将单词与编号之间的对应关系写到文件 term_id.bin 中。
分析阶段最后得到两个文件：临时索引文件（tmp_index.bin）和单词编号文件（term_id.bin）

索引

索引阶段主要负责将分析阶段产生的临时索引，构建成倒排索引（Inverted index）。倒排索引中记录了每个单词以及包含它的网页列表，例如：

// 单词编号 包含该单词的网页列表 分隔符
term1_id \t did1,did2,...,didn \r\n
term2_id \t did1,did2,...,didn \r\n
...

通过临时索引文件，使用多路归并排序的方法来构建出倒排索引文件。将临时索引文件分割成多个小文件，先对每个小文件独立排序，相同的单词就被排列到了一起。之后顺序地遍历排好序的小文件，将每个单词对应的网页编号列表找出来，然后把它们存储在小份倒排索引文件中，最后将所有小份倒排索引文件合成最终的倒排索引文件。同时，将每个单词编号在倒排索引文件中的偏移位置存储在文件 term_offset.bin 中，以便快速地查找某个单词编号在倒排索引中存储的位置，进而快速地从倒排索引中读取单词编号对应的网页编号列表。

1
2
3

// 单词编号 偏移位置 分隔符
term1_id \t offset1 \r\n
term2_id \t offset2 \r\n

索引阶段得到两个文件：倒排索引文件（index.bin）和单词编号在索引文件中的偏移位置的文件（term_offset.bin）

查询

经过前面三个阶段的处理，得到四个文件：
1、doc_id.bin：记录网页链接和编号之间的对应关系。
2、term_id.bin：记录单词和编号之间的对应关系。
3、index.bin：记录每个单词编号以及对应包含它的网页编号列表。
4、term_offsert.bin：记录每个单词编号在倒排索引文件中的偏移位置。
这四个文件中，除了倒排索引文件（index.bin）比较大之外，其他的都比较小。为了方便快速查找数据，将其他三个文件加载到内存中，并组织成散列表存储对应数据。
搜索的过程：
1、对用户输入的文本进行分词，得到 k 个关键词
2、去 term_id.bin 对应的散列表中匹配这 k 个关键词，得到 k 个单词对应的单词编号
3、去 term_offset.bin 对应的散列表中，查找每个单词编号在倒排索引文件中的偏移位置，得到 k 个偏移位置
4、去倒排索引 index.bin 中，查找 k 个单词对应的包含它的网页编号列表，得到 k 个网页编号列表
5、针对这 k 个网页编号列表，借助散列表来统计每个网页编号出现的次数。按照出现次数的多少，从小到大排序，得到一组网页编号。出现次数越多，说明网页跟查询内容的相关度越大
6、在 doc_id.bin 文件中查找这组网页编号对应的网页链接，然后分页展示给用户

高性能队列 Disruptor

Disruptor 是一种内存消息队列，它基于循环队列的“生产者 - 消费者模型”。

// 最简单的单线程“生产者 - 消费者模型”
public class Queue {
  private Long[] data;
  private int size = 0, head = 0, tail = 0;
  public Queue(int size) {
    this.data = new Long[size];
    this.size = size;
  }
  // 添加
  public boolean add(Long element) {
    if ((tail + 1) % size == head) return false; // 队列满了就不再添加
    data[tail] = element; // a 位置
    tail = (tail + 1) % size; // b 位置
    return true;
  }
  // 移除
  public Long poll() {
    if (head == tail) return null; // 首尾指针相同说明队列空了
    long ret = data[head];
    head = (head + 1) % size;
    return ret;
  }
}
// 生产者
public class Producer {
  private Queue queue;
  public Producer(Queue queue) {
    this.queue = queue;
  }

  public void produce(Long data) throws InterruptedException {
    while (!queue.add(data)) { // 队列满时让线程睡眠
      Thread.sleep(100);
    }
  }
}
// 消费者
public class Consumer {
  private Queue queue;
  public Consumer(Queue queue) {
    this.queue = queue;
  }

  public void comsume() throws InterruptedException {
    while (true) {
      Long data = queue.poll();
      if (data == null) { // 队列空时让线程睡眠
        Thread.sleep(100);
      } else {
        // 消费数据的业务逻辑
      }
    }
  }
}

基于加锁的并发“生产者 - 消费者模型”

多个线程操作同一个队列时，上面的代码会有两个问题：1、多个生产者写入的数据可能相互覆盖；2、多个消费者可能读取重复的数据。在极端情况下，多个线程同时执行 add 方法，如果前面的线程刚刚执行 a 位置代码，还未执行 b 位置的代码， tail 未更新，就有后面其他线程同时执行 a 代码，那么队列同一个位置，后面线程的元素会覆盖前面线程的元素。同理，poll 方法会造成问题 2。最简单的处理方法就是给这段代码加锁，同一时间只允许一个线程执行 add 或 poll 函数，但这样会使执行效率下降。

基于无锁的并发“生产者 - 消费者模型”

Disruptor 的思路：往队列中添加数据之前，先申请可用空闲存储单元，并且是批量地申请连续的 n 个（n≥1）存储单元，申请存储单元的过程是需要加锁的，每组存储单元是都是一个线程独享的。读取数据时，先去申请一批连续可读的存储单元，这个申请的过程也是需要加锁的，当申请到这批存储单元之后，后续的读取操作就可以不用加锁了。
Disruptor 有个弊端：前面线程申请一组存储单位在没有完全写入数据之前，后面的数据会被机制忽略而无法读取的。

鉴权限流

快速鉴权

1、精确匹配规则
只有当请求 URL 跟规则中配置的某个接口精确匹配时，这个请求才会被接受、处理。不同的应用对应不同的规则集合，采用散列表来存储这种对应关系。每个应用对应的规则集合都存储在一个字符串数组中，将用户请求的 URL 跟这个数组元素遍历匹配。规则不会经常变动，可以将字符串按照大小规则排序，将其组织成有序数组，这样匹配时可以使用二分查找算法来加快匹配速度。
2、前缀匹配规则
只要某条规则可以匹配请求 URL 的前缀，这个请求就会被处理。不同的应用对应不同的规则集合，采用散列表来存储这种对应关系。Trie 树非常适合用来做前缀匹配，可以将每个应用的规则集合组织成 Trie 树这种数据结构。Trie 树中的每个节点存储接口被“/”分割之后的子目录：“/user/name”被分割为“user”和“name”两个子目录。同时把每个节点的子节点们，组织成有序数组这种数据结构，可以利用二分查找算法，决定从一个节点应该跳到哪一个子节点。
3、模糊匹配规则
如果规则中包含通配符，比如“*”表示匹配任意多个子目录，“”表示匹配任意一个子目录。如果请求 URL 可以跟某条规则模糊匹配，那么这个请求就会被处理。不同的应用对应不同的规则集合，还是使用散列表来存储对应关系。存储规则集合则可以把不包含通配符的规则和包含通配符的规则分开处理，把不包含通配符的规则类似上面两类的，组织成有序数组或者 Trie 树。剩下包含通配符的规则存储在一个数组中，采用回溯算法，拿请求 URL 跟每条规则逐一进行模糊匹配。先匹配不包含通配符的有序数组或 Trie 树，不匹配后再匹配数组中包含通配符的规则。

精准限流

最简单的限流算法叫固定时间窗口限流算法：选定一个时间起点，之后每当有接口请求到来就将计数器加一。当出现累加访问次数超过限流值的情况时，我们就拒绝后续的访问请求。当进入下一个时间窗口之后，计数器就清零重新计数。固定时间窗口限流算法的限流策略过于粗略，稍加改造成滑动时间窗口限流算法：限制任意时间窗口内，接口请求数都不能超过某个阈值。
实现滑动时间窗口限流算法：假设限流的规则是在任意 1s 内，接口的请求次数都不能大于 K 次。维护一个 K+1 大小的循环队列，用来记录 1s 内到来的请求。当有新的请求到来时，将队列中与这个新请求的时间间隔超过 1s 的请求从队列中删除。然后再来看循环队列中是否有空闲位置，如果有位置，将这个请求排在队尾；如果没有，说明请求数量已经超限制，这个请求被拒绝。

短网址服务

短网址服务利用哈希算法把一个长的网址转化成一个短的网址，访问这个短网址获取到原始网址，之后就跳转到原始网址。

MurmurHash 算法

MurmurHash 算法提供了两种长度的哈希值，一种是 32bits，一种是 128bits。为了让最终生成的网址尽可能的短，选用 32bits 的哈希值。
1、让短网址更短
将 10 进制的哈希值转化成更高进制的哈希值，这样哈希值就变短了。在网址 URL 中，常用的合法字符有 0～9、a～z、A～Z 这样 62 个字符。将 10 进制的哈希值转化成 62 进制的哈希值，然后拼接到短网址服务的域名后面。
2、解决哈希冲突问题
一般情况下，需要保存短网址跟原始网址之间的对应关系。得到短网址后，现在库中查询是否已经有对应的短网址。如果没有，将短网址与原始网址之间的对应关系存入库中；如果有，需要判断原网址是否一样，如果一样则还可以使用该短网址；如果不一样，说明冲突了。此时可以给原始网址拼接一串特殊字符，然后再计算哈希值。如果还冲突，可以更换特殊字符继续计算哈希值，直到不冲突，最后将短网址与原网址的对应关系存入库中。当用户查询时，将查询到的原网址去除特殊字符后返回即可。
3、优化哈希算法生成短网址的性能
当库中数据很大时，在库中判断是否冲突时会很慢。有几种方法可以提高性能：
1）可以给短网址字段添加 B+ 树索引，这样通过短网址查询原始网址的速度就提高了。
2）在短网址生成的过程中，会执行两条 SQL 语句。第一个是通过短网址查询短网址与原始网址的对应关系，第二个是将新生成的短网址和原始网址之间的对应关系存储到数据库。这种 IO 通信耗时以及 SQL 语句的执行，才是整个短网址服务的性能瓶颈所在。为了减少 SQL语句，在库的表中添加一个唯一索引，直接尝试将短网址和原网址写入库中，如果能写入，说明没有违反唯一索引，即没有冲突。如果反馈违反唯一索引引发异常，说明发生了冲突，需要重新处理冲突，然后写入短网址和原网址的对应关系。
3）使用布隆过滤器，把已经生成的短网址，构建成布隆过滤器。如果新生成的网址没有在布隆过滤器中找到，说明没有发生冲突，将短网址和原网址关系入库即可

通过 ID 生成器生成短网址

除了使用哈希算法生成短网址，还可以通过 ID 生成器生成短网址。ID 自增生成器选一个号码，将其转化成 62 进制表示法后拼接到短网址服务的域名后面，生成最终的短网址。最后将短网址和原网址的关系存入库中。这样做会有些问题：
1、相同的原始网址可能会对应不同的短网址
每来一个原始网址就生成一个短网址，一个原始网址可能多次生成不同的短网址，一般有两种处理方法：
1）不处理，不会影响到用户体验
2）借助哈希算法生成短网址的处理思想，先查询库中是否存在原网址，如果有就直接将短网址返回。但这样做会添加一个查询原网址的索引，内存增加的同时，索引的增加会使插入、删除等操作的性能下降
2、实现高性能的 ID 生成器
思路：批量生成 ID
1）给 ID 生成器装多个前置发号器，给每个 ID 生成器批量的发号（每个一个 100 个）。每次接受到短网址生成请求时，就选择一个 ID 生成器发号，多个前置发号器可以明显提高发号效率
2）直接实现多个 ID 生成器同时服务，要求每个服务按照一定规则生成 ID ，以保证所有 ID 不重复。比如 10 个服务，每个服务只生成尾号是 0~9 某一个数字的 ID。