爱吃胡萝卜

The Log-Structured Merge-tree (LSM-tree) is a disk-based data structure designed to provide low-cost indexing for a file experiencing a high rate of record inserts (and deletes) over an extended period. LSM tree 基于“磁盘批量顺序写性能高于随机写”这一理论基础，提供高性能写入能力，代价是牺牲一部分读性能和空间效率。为了弥补读取性能，需要进一步设计，这也是其名字——Log-Structured Merge Tree 的由来。 写入过程LSM Tree 由存在于内存与磁盘上的部分组成，Memtable 和 SSTable，内存中又可以进一步划分成两个，如上图所示，顶部区域实际包含 Mutable memtable 和 Immutable memtable。 Mutable memtable： 所有操作直接写入 Mutable memtable，数据会按照 key 有序存储。一 ...

Fixed window固定窗口算法又叫计数法，在固定时间窗口里记录请求次数，当计数达到阈值时，拒绝请求。当前时间窗口结束后，重置计数器。 这种算法到优点是简单易实现。缺点是可能存流量尖刺，即请求集中在两个时间窗口交界处。 Sliding window滑动窗口算法是固定窗口算法的改进版，在固定窗口的基础上又划分若干子窗口，每个字窗口单独计数，每次只往前移动一个子窗口。相比固定窗口，随着子窗口数量增加，其限流计算更加准确。 不过这种方式也只是缓解了固定窗口算法的缺点，并不能彻底解决。 Sliding log滑动日志算法会记录每个请求的时间戳，然后计算最近一个时间窗口内的请求数量，如果达到上限，则请求拒绝。 这种算法的优点是限流精确，缺点也很明显，因为要在内存中记录每一条请求的时间戳，会占用较多内存。 Leaky bucket漏桶算法会维护一个单端队列，从请求在尾部排队，以固定速率从队列头部取出请求进行处理，队列长度达到上限时拒绝服务。因这种模型就像一个水桶，底部以固定流速漏水，所以称为漏桶算法。 这种算法能够对突发流量进行整形并以恒定速率进行处理，保证系统的稳定运行。缺点是，它不能很好处 ...

一般大型系统中，数据通常分布在多台机器上，并且为了稳定的性能表现，数据还需要均匀分布。 初步的做法 首先计算 hash(object_key)，然后对 numbers_of_servers 取模得到目标 server。 这种方式的问题核心是，numbers_of_servers 在 server 下线或新 server 加入时会发生变化，从而 object_key 的计算结果也因此发生变化。 hash 环 既然 numbers_of_servers 是一个不稳定因素，那么就需要将其替换成稳定的因素。 这里的做法是，对 server_name 或 server_ip 应用相同的 hash 函数，这时得到了 v_object 和 v_server。将 hash 函数的取值区间首位相连得到一个环， 然后根据 v_object 和 v_server 环上的位置，为 object 选择对应的 server。这里的规则一般是，按照顺时针方向搜索第一个 server。 理想情况下，现有节点下线或新节点加入都将不会导致所有 object_key 的重新分配。 但是现实中，数据可能不是完全均匀分布，也就 ...

Bloom filter 是用来回答“某元素是否在集合中”这个问题的，答案可能是“Firm no”或“Probably yes”，但是 Bloom filter 相比 hash table 占用内存更少，空间效率更高。也就是说，Bloom filter 通过牺牲准确性交换空间。Bloom filter 主要用在需要减少访问速度更慢的更低一级存储（或数据源）次数的场景，比如优化内存穿透。 Bloom filter 如何工作Bloom filter 由 m 个比特的字节数组和 k 个 hash 函数组成。当一个元素被添加到 filter 中时，会先调用 k 个 hash 函数计算得到 k 个整数，将字节数组中对应 bit 置为 1。当查询时，如果对应 bit 全部为 1，则元素可能在集合中（hash 冲突）；如果任一位置 bit 为 0，则元素一定不在集合中。 使用多少个 hash 函数取决于期望的错误率是多少，m 大小则与 k 和集合规模成正比。 Key takeawaysBloom filter wikipedia Bloom Filter

缓存穿透（cache penetration）缓存穿透指既不存在缓存也不存在于数据库的数据被访问，所有的查询请求都直接打到数据库。这种数据可能被恶意请求，对数据库造成压力。 Solution： 对请求进行初步检查，过滤掉显然非法的访问。 在缓存写入 empty 数据，并设置一个较短的过期时间。 使用 Bloom filter。 缓存击穿（cache breakdown）缓存击穿指某条热点数据不在缓存中，同时有大量的请求访问该数据，所有的请求将打到数据库。 Solution： 热点数据永不过期，同时使用后台任务主动更新缓存，而不是被动写入缓存。 使用互斥锁，当缓存不存在时，只允许一个请求查询数据，其它未获取到锁的请求将挂起直到缓存ready。为避免过多挂起请求，挂起的请求到一定数量后将直接返回失败响应。 缓存雪崩（cache avalanche）缓存雪崩指短时间内大批量缓存失效或者缓存服务不可用，请求压力直接来到数据库。通常同样的过期时间可能引起类似的问题。 Solution： 为缓存过期时间加上一个随机的偏移量。 如果是热点数据，在服务启动时就主动将数据加载进缓存，同时不设置 ...

分布式锁原则 安全性：任意时刻，只有一个客户端能持有锁，保证临界资源的安全访问。 可用性：无死锁，锁总是能够在某一时刻被释放，即使持有锁的客户端未释放锁便意外结束。 容错性：只要集群中大多数节点存活，客户端就能正常加锁释放锁。 Redis-based 分布式锁 到 Redlock 之前都基于单实例 redis 实现。 SETNX + EXPIRE1234567lock_key = "xxx"if redis.setnx(lock_key, lock_value) == 1: redis.expire(lock_key, 1000) try: # process finally: redis.del(lock_key) setnx 和 expire 不是原子操作，如果 setnx 后正要 expire 时客户端进程 crash 或者 Redis 重启，锁将无法得到释放。 SETNX + value=datetime1234567891011lock_key = "xxx"expiration = datetime. ...

早期服务端程序处理用户请求时，会为每一个新连接创建线程处理请求，随着并发量越来越高，“thread-per-connection” 这种模式的弊端开始显现。一来线程创建本身有开销，二来上下文切换也会带来额外开销。引入线程池可以一定程度上缓解，但更深层次的问题开始浮现，连接建立（accept）后通常不能马上读取到client的请求数据（recv），也就是说线程池内线程处于挂起状态。 一个直观的想法就是，连接建立后直到有数据可读时才开启线程进行处理，避免线程挂起。 单线程 Reactor Synchronous Event Demultiplexer: 指代各种多路复用机制。 Handle: 文件描述符或句柄。 Event Handler: 处理 Handle 的上的各种事件，比如 READ, WRITE。 Initiation Dispatcher: 核心类，维护一个基于 Synchronous Event Demultiplexer 的事件循环监听 Handle 各种事件并分发给 Event Handler 进行处理。 Logging Acceptor 是 Event Hand ...

Selectselect 允许程序同时监听多个文件描述符，直到一个或多个文件描述符变为ready状态（可读、可写、异常），最多支持同时监听 FD_SETSIZE(default 1024 on Linux) 个文件描述符。当 select 返回时，传入的三个 fd_set 将被（in-place）修改，用于标识那些ready的文件描述符，也就是说，每次调用 select 都需要重新初始化 fd_set 并拷贝至 Kernel space，当监听文件描述符数量多时，拷贝开销也是相当可观的。FD_SETSIZE 的限制是由于文件描述符在 fd_set 中以数组形式保存。 select 使用示例1234567891011121314151617181920212223242526272829#include <stdio.h>#include <stdlib.h>#include <sys/select.h>int main(void) { // initialize fd_set fd_set rfds; FD_ZERO(&rfd ...

1. Cache-aside 这是最常用的 pattern，实现简单也足够灵活，系统能够承受一定程度的 cache failure。 1.1. Pros 简单灵活。 1.2. Cons 使用方（Application）需管理缓存与下一级存储。 写请求有可能造成缓存与下一级存储不一致，通过写数据库后删缓存可以降低不一致的可能性，根据系统要求可以再配合 TTL、异步任务甚至是分布式事务。 2. Read-through 相比较 Cache-aside，Read-through 为使用方管理了缓存与第一级存储，使用更加方便，表现上就像是一个自带缓存的存储接口。 2.1. Pros 接口简单，使用方便。 2.2. Cons 灵活性相比 Cache-aside 低一些。 3. Write-through 结构与 Read-through 一样，提供简单的接口。写入缓存后同步写入下一级存储，整个写操作完成，适用写少的情况。 3.1. Pros 接口简单，使用方便。 3.2. Cons 写操作延迟稍高，除了写库外，还有一次额外写缓存。 4. Write-behind 与 Write-th ...

Based on Redis 7.0.11. maxmemory 配置1maxmemory 100mb 64 bit 系统下默认行为没有内存上限，32 bit 系统则默认是 3GB。虽然 64 bit 系统能够提供近乎无穷大的地址空间，但是物理内存是有限的，如果 Redis 占用内存超过物理内存上限，访问键时可能导致频繁的缺页异常，吞吐量降低。 设置上限后的另一个问题：满了怎么办？ maxmemory-policy description noeviction 内存达到上限时，拒绝添加新键 allkeys-lru 在键空间中根据 LRU 算法淘汰键 allkeys-lfu 在键空间中根据 LFU 算法淘汰键 volatile-lru 在 expires 中根据 LRU 算法淘汰键 volatile-lfu 在 expires 中根据 LFU 算法淘汰键 allkeys-random 在键空间中随机选择键淘汰 volatile-random 在 expires 中随机选择键淘汰 volatile-ttl 淘汰 expires 中 ttl 最小 ...