使用Redis实现高流量的限速器
Redis是生产环境中默默无闻的主力配置。它不常用作主要的数据存储，但它可存储和访问临时数据（度量，会话状态，缓存等损失可以容忍的数据）方面有一个甜蜜点，并且速度非常快，不仅提供了最佳性能，还通过一组有用的内置数据结构提供了高效的算法。它是现代技术栈中最常见的主要部件之一。
Stripe的限速器建立在Redis的基础之上，直到最近，他们都运行在Redis 的一个非常Hot的实例上。服务器上有用于故障转移的follower，但在任何时候，只有一个节点处理每个操作。
你不得不佩服这样的系统。各种消息称，Redis可以在一个节点上每秒处理一百万次操作 - 我们项目不需要那么多，但是也有很多操作。每个速率限制检查都需要运行多个Redis命令，并且每个API请求都要通过很多速率的限制器。一个节点每秒处理大约数十到数十万个操作。
我们最终通过迁移到10个节点的Redis群集来实现这个目标。对性能的影响可以忽略不计，我们现在有一个简单的配置开关可以实现水平可伸缩性。
操作的限制
在更换系统之前，应该理解导致原始故障的原因和结果。
Redis的一个值得理解的特性是：它是一个单线程程序。但是会有后台线程处理一些像删除对象这样的操作，实际上所有正在执行的操作都堵塞在访问单个流控制点上。理解这点相对容易--Redis需要保证操作的原子性（无论是单一命令MULTI，还是 EXEC），这是源于它一次只执行其中一个操作的事实。
这个单线程模型确实是我们的瓶颈。
面对失败
即使以最大容量运营，我们发现Redis也会非常优雅地降级。主要表现：从与Redis交谈通信的节点观察到的基线连接性错误率增加 - 为了容忍发生故障的Redis，它们受到连接和读取超时（约0.1秒）的限制，并且与过载主机无法无法建立连接。
Redis这种表现虽然不是最佳的，但大部分时间情况都是好的。只有当合法 用户能够成功进行身份验证并在底层数据库上运行昂贵的操作时，它才会成为一个真正的问题，因为我们的目标是拦截巨大的非法流量冲击（即数量级超过允许的限制）。
这些流量峰值会导致错误率的成比例增加，并且许多流量还应该被允许通过，因为限速器默认是允许在错误情况下通过请求。这会给后端数据库带来更大的压力，这种压力在过载时不会像Redis那样优雅地失败。很容易看到数据库分区几乎完全无法操作。
Redis Cluster的分片模型
Redis的核心设计价值在于速度，而Redis集群的构建方式不会对此产生影响。与许多其他分布式模型不同，在其输出响应成功信号时，Redis集群中的操作并未在多个节点上进行确认，而是更像是一组独立的Redis通过分散空间来分担工作负载。这牺牲了高可用性，有利于保持操作的快速性 - 与标准的Redis独立实例相比，针对Redis群集运行操作的额外开销可以忽略不计。
分片是根据key进行的，可能的key总数分为16,384个插槽。key的插槽是通过稳定的哈希散列函数计算的，所有客户端都知道该如何操作：
HASH_SLOT = CRC16(key) mod 16384
例如，如果我们想执行GET foo，我们会得到foo的以下插槽号：
HASH_SLOT = CRC16("foo") mod 16384 = 12182
集群中的每个节点将处理16,384个插槽中的一部分，确切数量取决于节点数量。节点彼此通信以协调插槽分配以及可用性和插槽的再平衡。
客户端使用该CLUSTER系列命令来查询群集的状态。一个常见的操作是CLUSTER NODES获得插槽到节点的映射，其结果通常在本地缓存，并保持数据新鲜。
127.0.0.1:30002 master - 0 1426238316232 2 connected 5461-10922
127.0.0.1:30003 master - 0 1426238318243 3 connected 10923-16383
127.0.0.1:30001 myself,master - 0 0 1 connected 0-5460
我简化了上面的输出，但重要的部分是第一列中的主机地址和最后一个中的数字。5461-10922意味着这个节点处理开始于5461和结束于10922的插槽范围。
`MOVED`重定向
如果Redis群集中的某个节点接收到一个插槽不处理的的key的命令，则不会尝试向其他插槽转发该命令。相反，客户端会被告知在其他地方再次尝试。这是以MOVED新目标的地址作为回应的形式 ：
GET foo
-MOVED 3999 127.0.0.1:6381
在集群重新平衡期间，插槽会从一个节点迁移到另一个节点，MOVED是服务器用于告诉客户端其插槽到节点的本地映射已过时的重要信号。
每个节点都知道当前的插槽映射，理论上，一个节点接收到它无法处理的操作时会向合适的节点询问结果并将其转发回客户端，但是发送MOVED是一个有意的设计选择。它会使得客户端实现添加一些额外的复杂性，从而换得快速和确定的性能。只要客户端的映射是新鲜的，操作总是以一一次性完成。由于再平衡相对较少，因此在集群的使用期限内分摊的协调开销可以忽略不计。
客户如何执行请求
Redis客户端需要一些额外的功能来支持Redis群集，其中最重要的功能是支持key哈希散列算法和维护插槽到节点映射的方案，以便他们知道在哪里分派命令。
一般来说，客户端会像这样操作：
1.在启动时，连接到一个节点并获取映射表CLUSTER NODES。
2.正常执行命令，根据key和槽映射定位服务器。
3.如果MOVED收到，请返回到1。
多线程客户端在接收到MOVED时，可以将映射表标记为脏来进行优化，并且使用线程跟随MOVED到新目标的响应执行相应命令，同时后台线程异步刷新映射表。实际上，即使存在重新平衡可能性，大多数插槽也不会移动，因此该模型允许大多数命令在没有开销的情况下继续执行。
使用哈希散列标签本地化多键操作
在Redis中通过使用EVAL运行带有多个key的操作，同时伴随Lua脚本。这是实现速率限制的一个特别重要的特性，因为所有通过单一EVAL方式分派的工作都是原子性的。这使我们能够正确计算剩余配额，即使存在可能冲突的并发操作时也是如此。
分布式模型会使这种类型的多键操作变得困难。由于每个key的槽都是通过散列来计算的，因此不能保证相关密钥会映射到同一个槽。我的key是user123.first_name和user123.last_name显然意味着属于一起的key, 最终却可能位于集群中的两个完全不同的节点上，读取二者任一的操作无法在一个节点上完成，必须昂贵地远程获取另外一个节点。
举例来说，我们有一个EVAL操作，将姓和名连接起来以产生一个人的全名：
# Gets the full name of a user
EVAL "return redis.call('GET', KEYS[1]) .. ' ' .. redis.call('GET', KEYS[2])"
2 "user123.first_name" "user123.last_name"
示例调用：
> SET "user123.first_name" William
> SET "user123.last_name" Adama
> EVAL "..." 2 "user123.first_name" "user123.last_name"
"William Adama"
如果Redis Cluster没有提供这种方式，该脚本将无法正常运行。幸运的是，它通过使用哈希标签实现hash tags。
对于EVAL需要跨节点操作,Redis集群是禁止它们（再次优化速度的选择）。相反，如果需要确保任何特定映射的key属于同一个插槽的，用户这需要使用哈希标签来计算，哈希标签看起来像一个key名称中的花括号，并且它们规定只有括号部分能用于哈希。
我们将通过重新定义我们的key来修复我们的脚本，通过哈希标签共享user123：
> EVAL "..." 2 "{user123}.first_name" "{user123}.last_name"
计算其中一个插槽时：
HASH_SLOT = CRC16("{user123}.first_name") mod 16384
= CRC16("user123") mod 16384
= 13438
{user123}.first_name和{user123}.last_name现在保证映射到相同的插槽，并且EVAL包含它们的操作将毫无问题。这只是一个基本的例子，但是相同的概念一直映射到复杂的速率限制器实现。
简单可靠
向Redis集群过渡非常顺利，最困难的部分是支持Redis Cluster客户端用于生产。即使到了今天，良好的客户支持也有点多余，这可能表明Redis速度足够快，大多数使用它的人可以通过简单的独立实例实现。我们的错误率急剧下降，我们相信我们有充足的跑道来保持持续增长。
在哲学上，Redis Cluster的设计有很多让人喜欢之处 - 简单但功能强大。特别是当涉及到分布式系统时，许多实现过程非常复杂，并且在生产中遇到的棘手问题时，复杂程度可能是灾难性的。Redis Cluster具有可扩展性，但却不是非常复杂，即使像我这样的非专业人员也可以专注正在做的事情上。它的设计文档是全面的，但也是平易近人的。
在成立之后的几个月里，尽管一天中的每一秒钟都有相当多的负荷，但我还是没有再碰过它。这是生产系统中罕见的质量，甚至在Postgres等我的其他使用中也没有发现。我们需要更多像Redis这样的构建块来做他们应该做的事，然后忘记它。