发表更新语言 / Java10 分钟读完 (大约1426个字)

Caffeine W-TinyLFU

参考 Caffeine GitHub，Design of a Modern Cache，Cache Eviction and Expiration Policy，幻灯片。

计数方式

Count-min Sketch 是一种概率数据结构，底层使用计数器矩阵和多个哈希函数，原理类似布隆过滤器。添加元素会递增每行的计数器，取最小值作为频率的估计值，每行计数器的位置使用哈希函数计算得到。

执行流程

首先，新元素会进入 Window Cache，被 LRU 淘汰之后会尝试进入 Main Cache。W-TinyLFU 使用 Count-min Sketch 作为过滤器，被 Window Cache 淘汰的新元素会和 Main Cache 中 Probation 段即将淘汰的元素比较，如果新元素的访问频率更高则可以进入 Main Cache。Main Cache 的淘汰流程类似 Linux Page Cache，如果元素在 Probation 段，再次访问会升级到 Protected 段，长期不访问会降级/淘汰。计数器会定期衰减，以适应访问模式的变化。

Filter 可以有效减少顺序扫描导致的缓存污染，同时 Window Cache 给新元素提供增加频率的机会。较小的准入窗口适合偏向频率的负载，不适合偏向时间的负载。因为在偏向时间的负载中，元素可能还没来得及增加频率就被淘汰。可以使用爬山法（启发式算法）来选择最佳的窗口大小，当命中率发生较大变化时，就会触发该过程，以适应不同负载。

过期策略

Caffeine 根据过期时间是否固定来选择过期删除策略。如果过期时间固定，则使用 LRU 列表维护元素的过期顺序。如果过期时间可变，则使用分层时间轮算法，时间复杂度为 $O(1)$。多个时间轮可以表示不同的时间层级，例如例如天、小时、分钟和秒。单个时间轮是一个双向链表数组，每个链表代表一个粗略的时间跨度（在当前时间层级内）。

当上层时间轮转动时，上层时间轮的下一个桶会被刷新到下层时间轮，这些元素会被重新哈希并放置在相应的位置。例如，一天之后过期的元素在天数层级的时间轮中，一天之后，天数层级的时间轮转动，桶内元素需要以小时为跨度放置到下层时间轮。当最底层时间轮转动时，最底层时间轮的上一个桶中的元素会被逐出，因为元素已经过期。

并发设计

在大多数缓存淘汰策略中，读操作也会修改共享状态（策略信息），例如 LRU 的移动元素、LFU 的更新计数。为保证更新策略信息的线程安全，使用全局独占锁会有性能问题，使用分段锁也无法避免热点元素导致的性能问题（并发竞争单个锁）。另一种方法是将操作记录到缓冲区，然后异步批量处理，用于更新策略信息（读写哈希表不会阻塞）。

When contention becomes a bottleneck the next classic step has been to update only per entry metadata and use either a random sampling or a FIFO-based eviction policy. Those techniques can have great read performance, poor write performance, and difficulty in choosing a good victim.（没有看懂）

Caffeine 使用缓冲区优化，减少并发更新策略信息的锁竞争导致的性能问题，读写操作使用不同的缓冲区。读操作使用条带化的环形缓冲区，根据线程的哈希值选择条带，而不是元素的哈希值，避免热点元素导致的竞争问题。当检测到竞争时，会自动增加条带。当环形缓冲区已满时，触发异步批量处理（只需获取一次锁），此时会丢弃对该缓冲区的后续添加，直到空间可用。被丢弃的读操作依然会将缓存值返回给调用者，只是不会更新策略信息，部分策略信息的丢失不会对性能产生太大影响。

写操作使用单个并发队列，会逐个而不是批量处理，不允许丢失。读写缓冲区都是多生产者单消费者的模式。使用缓冲区异步更新策略，无法保证按照增删改查操作实际发生的顺序更新，可以会发生悬空引用，即哈希表中已经删除但是策略中却保留某个元素的信息，Caffeine 使用状态机定义元素的生命周期来解决该问题。

个人理解，缓冲区优化主要是异步批量处理策略信息的更新，避免阻塞读写哈希表，避免频繁获取锁。Caffeine 缓存的元素是可以随时淘汰的，而磁盘页面缓冲池还需要判断页面是否被 Pin。

源码分析

1
// TODO
发表更新语言 / Java4 分钟读完 (大约665个字)

Guava RateLimiter

参考 RateLimiter 代码。

基本使用

1
2
3
4
<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
</dependency>
1
2
RateLimiter rateLimiter = RateLimiter.create(1);
rateLimiter.acquire();

代码实现

抽取 SmoothBursty 限流器的关键代码，梳理基本的实现流程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
class RateLimiter {

    /**
     * 最多可以存储多少秒的许可来应对突发流量
     */
    private final double maxBurstSeconds;

    /**
     * 允许存储的最大许可数量
     */
    private final double maxPermits;

    /**
     * 生成许可的间隔时间
     */
    private final double stableIntervalMicros;

    /**
     * 当前存储的许可数量
     */
    private double storedPermits;

    /**
     * 允许下一个请求获取许可的时间
     */
    private long nextFreeTicketMicros = 0L;

    /**
     * 每秒生成的许可数量
     */
    RateLimiter(double permitsPerSecond) {
        this.maxBurstSeconds = 1.0;
        maxPermits = maxBurstSeconds * permitsPerSecond;
        stableIntervalMicros = TimeUnit.SECONDS.toMicros(1L) / permitsPerSecond;
    }

    /**
     * 获取指定数量的许可，阻塞请求知道可以获取，返回等待的时间（秒）
     */
    public double acquire(int permits) {
        // 参数范围检查
        if (permits <= 0) {
            throw new IllegalArgumentException(String.format("Requested permits (%s) must be positive", permits));
        }
        long microsToWait;
        // 加锁保证线程安全
        synchronized (this) {
            Instant instant = Instant.now();
            long nowMicros = instant.getEpochSecond() * 1_000_000 + instant.getNano() / 1000;
            long momentAvailable = reserveEarliestAvailable(permits, nowMicros);
            microsToWait = max(momentAvailable - nowMicros, 0);
        }
        LockSupport.parkNanos(microsToWait * 1000);
        return 1.0 * microsToWait / SECONDS.toMicros(1L);
    }

    /**
     * 返回当前请求允许获取许可的时间，设置当前存储的许可数量，以及下一个请求允许获取许可的时间
     */
    final long reserveEarliestAvailable(int requiredPermits, long nowMicros) {
        // 如果当前时间大于 nextFreeTicket，则重新生成当前时间存储的许可数量，以及当前请求允许获取许可的时间
        if (nowMicros > nextFreeTicketMicros) {
            double newPermits = (nowMicros - nextFreeTicketMicros) / stableIntervalMicros;
            storedPermits = min(maxPermits, storedPermits + newPermits);
            nextFreeTicketMicros = nowMicros;
        }
        // 存储当前请求允许获取许可的时间作为返回值
        long returnValue = nextFreeTicketMicros;
        // 消耗已有的许可数量，然后根据需要新获取的许可数量，生成下一次请求的等待时间
        double storedPermitsToSpend = min(requiredPermits, this.storedPermits);
        double freshPermits = requiredPermits - storedPermitsToSpend;
        long waitMicros = (long) (freshPermits * stableIntervalMicros);
        // 将等待时间添加到 nextFreeTicketMicros 中，如果溢出则设置为 Long.MAX_VALUE
        try {
            nextFreeTicketMicros = Math.addExact(nextFreeTicketMicros, waitMicros);
        } catch (ArithmeticException e) {
            nextFreeTicketMicros = Long.MAX_VALUE;
        }
        storedPermits -= storedPermitsToSpend;
        return returnValue;
    }

    public static void main(String[] args) {
        RateLimiter rateLimiter = new RateLimiter(1);
        for (int i = 0; i < 10; i++) {
            double wait = rateLimiter.acquire(2);
            System.out.printf("等待时间: %fs, 剩余许可: %f\n", wait, rateLimiter.storedPermits);
        }
    }
}
1
2
3
4
5
6
7
8
// 当前时间大于 nextFreeTicket，生成 maxPermits 个许可
// 请求 2 个许可，当前只有 1 个许可，等待 0 s，下一个请求的等待时间是 1 s
等待时间: 0.000000s, 剩余许可: 0.000000
// 请求 2 个许可，当前只有 0 个许可，等待 1 s，下一个请求的等待时间是 2 s
等待时间: 0.967138s, 剩余许可: 0.000000
// 请求 2 个许可，当前只有 0 个许可，等待 2 s，下一个请求的等待时间是 2 s
等待时间: 1.981604s, 剩余许可: 0.000000
等待时间: 1.989831s, 剩余许可: 0.000000
发表更新语言 / Java1 分钟读完 (大约179个字)

性能测试

服务器硬件配置是 2 核 2 GB 内存，对 Redis Get 命令进行基准测试的 RPS 是 7w+，而应用程序接口会将数据缓存到 Redis，即使每次都命中缓存 RPS 却只有 1k+。

1
2
3
4
5
6
7
8
9
$ lscpu
Architecture:        x86_64
CPU(s):              2
CPU MHz:             2499.998

$ free -h
              total        used        free      shared  buff/cache   available
Mem:          1.8Gi       1.3Gi       140Mi       1.0Mi       551Mi       545Mi
Swap:            0B          0B          0B
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
$ redis-benchmark -t get -c 50 -n 100000 -d 8 -P 1
====== GET ======                                     
  100000 requests completed in 1.41 seconds           
  50 parallel clients                                 
  8 bytes payload                                     
  keep alive: 1                                       
  host configuration "save": 3600 1 300 100 60 10000  
  host configuration "appendonly": no                  
  multi-thread: no

Summary:                                              
  throughput summary: 70972.32 requests per second    
  latency summary (msec):                             
          avg       min       p50       p95       p99       max
        0.478     0.144     0.407     0.863     1.183    10.327
1
2
3
4
5
6
7
8
9
10
11
12
13
14
$ wrk -t4 -c100 -d30s --latency http://127.0.0.1:8080/predict/biweekly-contest-152/1/25
Running 30s test @ http://127.0.0.1:8080/predict/biweekly-contest-152/1/25
  4 threads and 100 connections
  Thread Stats   Avg      Stdev     Max   +/- Stdev
    Latency    75.57ms   32.14ms 490.57ms   85.10%
    Req/Sec   337.43     69.15   530.00     76.79%
  Latency Distribution
     50%   71.32ms
     75%   85.89ms
     90%  103.88ms
     99%  201.92ms
  40414 requests in 30.11s, 269.38MB read
Requests/sec:   1342.26
Transfer/sec:      8.95MB
关注我

链接

分类

最新文章

归档

标签

Debugging2
Draft1
Hexo1

链接

×