和漏桶算法算法类似，令牌桶算法的核心是固定“进口”速率，可以应对突发流量，是非常非常常用的算法。

• 桶里装的是令牌
• 在被处理之前需要拿到一个令牌，请求处理完毕之后将这个令牌丢弃（删除）
• 拿不到令牌就被「流量干预」
• 根据限流大小，按照一定的速率往桶里添加令牌

通常在实现中，令牌的增加都是基于时间的延迟计算和预消费的思想。

漏桶算法把发请求的动作比作成注水到桶中，处理请求的过程可以比喻为漏桶漏水。

往桶中以任意速率流入水，以一定速率流出水，当水超过桶流量则丢弃，因为桶容量是不变的，保证了整体的速率。

滑动窗口其实就是对固定窗口做了进一步的细分，将原先的粒度切的更细，相当于固定窗口计数器算法的升级版。

如果固定窗口的「固定周期」已经很小了，那么使用滑动窗口的意义也就没有了。

本文整理了滑动窗口计数器的伪代码、Redis、Go 的实现方法。

是在 MySQL 5.0 后引入的的索引合并策略，它将每个索引查询的结果进行合并。

合并算法有三种：intersect（交集）、union（并集）、sort_union（不常见）。

固定窗口计数器规定单位时间处理的请求数量。该算法无法保证限流速率，因而无法保证突然激增的流量。优点是容易理解，实现简单。

本文整理了固定窗口计数器的伪代码、Redis、Go 和 Java 的实现方法和思路。

在 JDK 1.7 的实现中，使用头插法来实现元素的插入和数组扩容。

扩容的 Resize 包含扩容和 Rehash 两个步骤，Rehash 在并发的情况下可能会形成链表环。

Sun 认为这不是一个 Bug，因为 HashMap 本来就不支持并发，要并发就用 ConcurrentHashMap。

这个问题只存在于 JDK1.7 中，在 JDK1.8 中使用了不同的扩容实现方式，不会出现这种情况。

在 MySQL 5.6 版本后加入的新特性索引下推（Index Condition Pushdown）。 可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。

Index Filter 与 Table Filter 分离，Index Filter 下降到 InnoDB 的索引层面进行过滤，减少了回表与返回 MySQL Server 层的记录交互开销，提高了 SQL 的执行效率。

HashMap 是 Java 中最重要的数据结构，也是最常用的集合类型。面试中基本都会问到一两个 HashMap 相关的问题。

由于 JDK 1.8 对 HashMap 进行了优化，基本上重写了 HashMap 的实现，所以通常还会考查 HashMap 的优化点。

本文收集整理了网上一些相关介绍，也是我在面试中常被问到的相关内容。

本文整理了 MySQL InnoDB 存储引擎中，常见导致索引失效的原因。

MySQL 是否使用索引通常取决于优化器估算的结果，如果计算结果认为全表扫描比使用索引还快，那通常就使用全表扫描。

以下两大类查询语句会导致查询就算走索引也需要对结果进行处理，最终优化器不会使用索引进行查询：

1. 违反最左匹配原则
2. 索引列上面做操作

在 MySQL 中，主要有四种类型的索引，分别为： B-Tree 索引， Hash 索引， Fulltext 索引和 R-Tree 索引。

Innodb 存储引擎的 B-Tree 索引使用的存储结构实际上是 B+Tree。本文总结的几个索引使用原则主要基于 Innodb 存储引擎，原理便是依托于 B+ 树的特性。