本文总结常见的三种限流算法：时间窗口，令牌桶与漏桶算法。对算法思想进行介绍并且分析其异同。 时间窗口限流 固定时间窗口 所谓时间窗口限流，是指在一定的时间内，维护一个访问总量的数值，当其超过阈值时，拒绝后续所有的请求，直到进入下一个时间窗口。 上图横轴的每个时间节点都是一个时间窗口，我们可以看到，当请求没有超过阈值以前，请求为蓝色，可以正常进行，超过阈值的请求会被抛弃。 但是，这种算法有一个很明显的 临界问题 ：假设限流阀值为 5 个请求，单位时间窗口是 1s，如果我们在单位时间内的前 0.8-1s 和 1-1.2s，分别并发 5 个请求。虽然都没有超过阀值，但是如果算 0.8-1.2s，则并发数高达 10，已经超过单位时间 1s 不超过 5 阀值的定义了。 滑动时间窗口 滑动窗口限流可以解决固定窗口临界值的问题。它将单位时间周期分为n个小周期，分别记录每个小周期内接口的访问次数，并且根据时间滑动删除过期...

在实际业务运行过程中，有一种故障影响可能没有那么大，但发生的概率较高，这就是今天聊的接口级的故障。 接口级故障的典型表现就是，系统并没有宕机、网络也没有中断，但业务却出现问题了，例如业务响应缓慢、大量访问超时和大量访问出现异常（给用户弹出提示“无法连接数据库”）。 这类问题的主要原因在于系统压力太大、负载太高，导致无法快速处理业务请求，由此引发更多的后续问题。最常见的情况就是，数据库慢查询将数据库的服务器资源耗尽，导致读写超时，业务读写数据库时要么无法连接数据库、要么超时，最终用户看到的现象就是访问很慢，一会儿访问抛出异常，一会儿访问又是正常结果。 如果进一步探究，导致接口级故障的原因可以分为两大类： 1. 内部原因 ：包括程序bug导致死循环，某个接口导致数据库慢查询，程序逻辑不完善导致耗尽内存等。 2. 外部原因 ：包括黑客攻击，促销或者抢购引入了超出平时几倍甚至几十倍的用户，第三方系统大量请求，第三方系统响应缓慢等。 解决接口级故障的核心思想和异地多活基本类似，都是 优先保证核心业务 和 优先保证绝大部分用户 。常见的应对方法有四种，降级、...

理论 一致性哈希算法是一种常用的[分布式]()算法，其主要用途是在分布式系统中，将数据根据其键（key）进行散列（hash），然后将散列结果映射到环上，再根据数据节点的数量，将环划分为多个区间，每个节点负责处理环上一定区间范围内的数据。 普通哈希的问题 分布式集群中，对机器的添加删除，或者机器故障后自动脱离集群这些操作是集群管理最基本的功能。如果采用常用的hash(object)%N取模的方式，在节点进行添加或者删除后，需要重新进行迁移改变[映射关系]()，否则可能导致原有的数据无法找到。 举个栗子 随着业务和流量的增加，假如我们的Redis查询服务节点扩展到了3个，为了将查询请求进行均衡，每次请求都在相同的Redis中，使用hv = hash(key) % 3的方式计算，对每次查询请求都通过hash值计算，得出来0、1 、2的值分别对应服务节点的编号，计算得到的hv的值就去对应的节点处理。 但...

一、前言 首先，为什么我会学习数据结构与算法呢，其实主要是有两方面 第一，是我在今年的flag里明确说到我会学这个东西 第二，学了这些，对自己以后在工作或者面试也会带来许多好处 然后，本文是最近学习的一个 <span class="wx_text_underline" 总结文章</span ，文中的算法题， 大部分都是leetcode中 的，如不太理解题意，可直接去leetcode中找到对应的题。 二、基本概念 常常听到算法的时候，就会有人说到 时间复杂度 ， 空间复杂度 。那么这俩玩意是啥呢，下面我们就来一一解释 1. 时间复杂度 其实就是一个函数，用大 O 表示， 比如 O(1)、 O(n)... 它的作用就是用来 定义描述算法的运行时间 O(1)     let i = 0     i += 1 O(n)： 如果是 O(1) + O(n) 则还是 O(n)     for (let i = 0; i < n; i += 1) {  

本文是根据近期对 Etcd-Raft 的学习把自己的理解做个简单整理和分享。 近期负责的项目中有一个场景需要依赖数据一致性算法，因此做了一些相关的调研。本文是根据近期对【Etcd-Raft】的学习把自己的理解做个简单整理和分享。 注：本文并没有对Etcd/Raft源码和流程事无巨细的解剖，更多地关注其核心功能以及过程中个人觉得值得学习的点。 前言 Raft是什么？ Etcd是什么？  为什么选择etcd-raft  文章主要讲解 etcd/raft—— 原理解析篇。 一、原理解析 1. 最小原则 ...