ARTS 打卡第 4 周

1. Algorithm

题目的来源于 leetcode:https://leetcode.cn/problems/lru-cache/description/。考察的知识点是 LRU 的实现，代码实现如下：

class LRUCache {public:
    LRUCache(int capacity) : max(capacity){            }        int get(int key) {                int ret = -1;
        if (M.count(key) > 0)        {            pair<int,int> p = *M[key];            ret = p.second;
            /**            * 移动表头,并更新位置            **/            cache.erase(M[key]);            cache.push_front(p);            M[key] = cache.begin();        }
        return ret;    }        void put(int key, int value) {                if (M.count(key) > 0)        {            cache.erase(M[key]);            cache.push_front(make_pair(key, value));            M[key] = cache.begin();        }        else        {            if (cache.size() == max) {
                pair<int,int> p = cache.back();                int remove = p.first;                M.erase(remove);                cache.pop_back();            }            cache.push_front(make_pair(key, value));            M[key] = cache.begin();        }    }
private:
    int max;        /**    * 双端链表存储[key,value]    **/    list<pair<int,int>> cache;    unordered_map<int, list<pair<int,int>>::iterator> M;};
/** * Your LRUCache object will be instantiated and called as such: * LRUCache* obj = new LRUCache(capacity); * int param_1 = obj->get(key); * obj->put(key,value); */

2. Review

本周将会对 redis 中的内存淘汰算法（eviction）的实现进行翻译，我将会结合源码和我的理解进行解读.原文链接参考：Key eviction

Key eviction

键淘汰

Overview of Redis key eviction policies (LRU, LFU, etc.)

Redis 键淘汰策略概述（LRU、LFU 等）

When Redis is used as a cache, it is often convenient to let it automatically evict old data as you add new data. This behavior is well known in the developer community, since it is the default behavior for the popular memcached system.

当 Redis 作为缓存时，通常可以简便地让它在添加新数据时自动淘汰旧数据。这种行为在开发者社区中非常常见，因为它是流行的内存缓存系统的默认行为。

This page covers the more general topic of the Redis maxmemory directive used to limit the memory usage to a fixed amount. It also extensively covers the LRU eviction algorithm used by Redis, which is actually an approximation of the exact LRU.

这个页面涵盖了 Redis 中的更一般性主题，即 Redis 的maxmemory指令，它是用于限制内存的最大使用量的一个固定值。它还详细介绍了 Redis 使用的 LRU（最近最少使用）淘汰算法，实际上是对精确 LRU 的一种近似实现。

Maxmemory configuration directive

Maxmemory 配置指令

The maxmemory configuration directive configures Redis to use a specified amount of memory for the data set. You can set the configuration directive using the redis.conf file, or later using the CONFIG SET command at runtime.

"maxmemory 配置指令" 用于配置 Redis 使用指定数量的内存来存储数据集。您可以通过 redis.conf 文件或在运行时使用 CONFIG SET 命令来设置此配置指令。

For example, to configure a memory limit of 100 megabytes, you can use the following directive inside the redis.conf file:

例如，要配置一个 100Mb 的内存限制，您可以在 redis.conf 文件中使用以下指令：

maxmemory 100mb

Setting maxmemory to zero results into no memory limits. This is the default behavior for 64 bit systems, while 32 bit systems use an implicit memory limit of 3GB.

将 maxmemory 设置为零会导致没有内存限制。这是 64 位系统的默认行为，而 32 位系统使用隐式内存限制为 3GB。

When the specified amount of memory is reached, how eviction policies are configured determines the default behavior. Redis can return errors for commands that could result in more memory being used, or it can evict some old data to return back to the specified limit every time new data is added.

当达到指定的内存限制时，配置的淘汰策略将决定默认行为。Redis 可以对可能导致更多内存使用的命令返回错误，或者可以在每次添加新数据时淘汰一些旧数据以恢复到指定的限制。

Eviction policies

淘汰策略

The exact behavior Redis follows when the maxmemory limit is reached is configured using the maxmemory-policy configuration directive.

当达到 maxmemory 限制时，Redis 遵循的确切行为是通过 maxmemory-policy 配置指令进行配置的。

The following policies are available:

可用的策略如下(译者注：除了 noeviction 策略不进行内存淘汰，其他都是是根据淘汰候选数据集的范围进行划分的)：

• noeviction: New values aren’t saved when memory limit is reached. When a database uses replication, this applies to the primary databases

• noeviction:：当达到内存限制时，不保存新的值。对于使用复制的数据库，这适用于主数据库。

• allkeys-lru: Keeps most recently used keys; removes least recently used (LRU) keys

• allkeys-lru: 保留最近使用的键；删除最不常使用的（LRU）键。

• allkeys-lfu: Keeps frequently used keys; removes least frequently used (LFU) keys

• allkeys-lfu：保留频繁使用的键；删除最不频繁使用的（LFU）键。

• volatile-lru: Removes least recently used keys with the expire field set to true.

• volatile-lru：删除带有设置为 true 的到期字段的最近不常用的键。

• volatile-lfu: Removes least frequently used keys with the expire field set to true.

• volatile-lfu：删除带有设置为 true 的到期字段的最不常用的键。

• allkeys-random: Randomly removes keys to make space for the new data added.

• allkeys-random：随机删除键为新添加的数据腾出空间。

• volatile-random: Randomly removes keys with expire field set to true.

• volatile-random: 随机删除带有设置为 true 的 expire 字段的键。

• volatile-ttl: Removes keys with expire field set to true and the shortest remaining time-to-live (TTL) value.

• volatile-ttl：删除设置为 true 且剩余生存时间（TTL）值最短的键。

The policies volatile-lru, volatile-lfu, volatile-random, and volatile-ttl behave like noeviction if there are no keys to evict matching the prerequisites.

如果没有符合条件的键需要淘汰，那么volatile-lru、volatile-lfu、volatile-random和volatile-ttl这些策略的行为与noeviction相似。

Picking the right eviction policy is important depending on the access pattern of your application, however you can reconfigure the policy at runtime while the application is running, and monitor the number of cache misses and hits using the Redis INFO output to tune your setup.

选择适合你应用访问模式的淘汰策略非常重要，不过你可以在应用运行时重新配置策略，并使用 Redis 的 INFO 输出来监控缓存的未命中和命中次数，以便调整你的设置。

In general as a rule of thumb:

总的来说，作为一个经验法则：

• Use the allkeys-lru policy when you expect a power-law distribution in the popularity of your requests. That is, you expect a subset of elements will be accessed far more often than the rest. This is a good pick if you are unsure.

• 如果你预期请求的热门程度符合幂律分布，也就是说，你预期会有一部分元素的访问频率远高于其他元素，那么可以使用 allkeys-lru 策略。如果你不确定，这通常是一个不错的选择。

• Use the allkeys-random if you have a cyclic access where all the keys are scanned continuously, or when you expect the distribution to be uniform.

• 如果你的访问模式是循环的，也就是说所有的键都会被连续扫描，或者你期望分布是均匀的，那么可以使用 allkeys-random。

• Use the volatile-ttl if you want to be able to provide hints to Redis about what are good candidate for expiration by using different TTL values when you create your cache objects.

• 如果你想要在创建缓存对象时使用不同的 TTL 值，以向 Redis 提供关于哪些对象适合过期的提示，可以使用 volatile-ttl 策略。

The volatile-lru and volatile-random policies are mainly useful when you want to use a single instance for both caching and to have a set of persistent keys. However it is usually a better idea to run two Redis instances to solve such a problem.

volatile-lru 和 volatile-random 策略主要在你希望在单个实例中同时进行缓存和保留一组持久性键时有用。但通常更好的做法是运行两个 Redis 实例来解决这个问题。

It is also worth noting that setting an expire value to a key costs memory, so using a policy like allkeys-lru is more memory efficient since there is no need for an expire configuration for the key to be evicted under memory pressure.

这也值得注意的是，为一个键设置过期时间会占用内存，因此使用像 allkeys-lru 这样的策略更节省内存，因为无需为键配置过期时间，它可以在内存不足时被淘汰。（译者注：）

How the eviction process works

淘汰过程的工作原理

It is important to understand that the eviction process works like this:

重要的是要理解，淘汰过程的工作方式如下：

• A client runs a new command, resulting in more data added.

• 客户端运行新的命令，导致添加了更多的数据

• Redis checks the memory usage, and if it is greater than the maxmemory limit , it evicts keys according to the policy.

• Redis 检测内存使用情况，如果大于了 maxmemory的阈值，则通过指定的策略进行键的淘汰

• A new command is executed, and so forth.

• 新的命令被执行，以此类推

So we continuously cross the boundaries of the memory limit, by going over it, and then by evicting keys to return back under the limits.

因此，我们不断地越过内存限制，然后通过淘汰键来将内存降低到限制之下。

If a command results in a lot of memory being used (like a big set intersection stored into a new key) for some time, the memory limit can be surpassed by a noticeable amount.

如果某个命令在一段时间内导致大量内存的使用（比如将大的集合交集存储到新键中），那么内存限制可能会超出相当大的数量。

Approximated LRU algorithm

近似 LRU 算法

Redis LRU algorithm is not an exact implementation. This means that Redis is not able to pick the best candidate for eviction, that is, the key that was accessed the furthest in the past. Instead it will try to run an approximation of the LRU algorithm, by sampling a small number of keys, and evicting the one that is the best (with the oldest access time) among the sampled keys.

Redis 的 LRU（最近最少使用）算法不是一个精确的实现。这意味着 Redis 不能选择最佳的淘汰候选项，即最久未访问的键。相反，它会尝试运行 LRU 算法的近似实现，通过对一小部分键进行采样，并淘汰在采样键中访问时间最早（最久未访问）的那个键。这个近似 LRU 算法的目的是在减少计算成本的同时，尽可能接近精确的 LRU 淘汰策略。

However, since Redis 3.0 the algorithm was improved to also take a pool of good candidates for eviction. This improved the performance of the algorithm, making it able to approximate more closely the behavior of a real LRU algorithm.

然而，自 Redis 3.0 以来，该算法已经得到改进，以便还考虑到了淘汰的优秀候选项池。这一改进提高了算法的性能，使其能够更接近真正的 LRU 算法的行为。这意味着它能够更准确地确定哪些键应该被淘汰，以便更好地管理内存。

What is important about the Redis LRU algorithm is that you are able to tune the precision of the algorithm by changing the number of samples to check for every eviction. This parameter is controlled by the following configuration directive:

Redis 的 LRU 算法的一个重要特点是，您可以通过更改每次淘汰检查的样本数量来调整算法的精度。这个参数由以下配置指令控制：

maxmemory-samples 5

The reason Redis does not use a true LRU implementation is because it costs more memory. However, the approximation is virtually equivalent for an application using Redis. This figure compares the LRU approximation used by Redis with true LRU.

Redis 不使用真正的 LRU 实现的原因是因为它会消耗更多的内存。然而，对于使用 Redis 的应用程序来说，这种近似方法几乎是等效的。下图比较了 Redis 使用的 LRU 近似方法与真正的 LRU。

The test to generate the above graphs filled a Redis server with a given number of keys. The keys were accessed from the first to the last. The first keys are the best candidates for eviction using an LRU algorithm. Later more 50% of keys are added, in order to force half of the old keys to be evicted.

生成上述图表的测试向 Redis 服务器填充了一定数量的键。这些键从第一个到最后一个依次访问。最初的（被访问的）键是使用 LRU 算法的最佳驱逐候选项。然后添加了 50%以上的键，以强制驱逐旧键的一半。

You can see three kind of dots in the graphs, forming three distinct bands.

在图表中，您可以看到三种不同类型的点，它们形成了三个明显的带状区域。

• The light gray band are objects that were evicted.

• 浅灰色带表示被驱逐的对象。

• The gray band are objects that were not evicted.

• 灰色带表示未被驱逐的对象。

• The green band are objects that were added.

• 绿色带表示已添加的对象。

In a theoretical LRU implementation we expect that, among the old keys, the first half will be expired. The Redis LRU algorithm will instead only probabilistically expire the older keys.

在理论上的 LRU 实现中，我们预计在旧的键中，前半部分将会过期。而 Redis LRU 算法将只在旧键中进行概率性的过期处理。

As you can see Redis 3.0 does a better job with 5 samples compared to Redis 2.8, however most objects that are among the latest accessed are still retained by Redis 2.8. Using a sample size of 10 in Redis 3.0 the approximation is very close to the theoretical performance of Redis 3.0.

正如您所看到的，Redis 3.0 在使用 5 个样本的情况下相比 Redis 2.8 做得更好，然而，Redis 2.8 仍然保留了大多数最近访问的对象。在 Redis 3.0 中使用 10 个样本，逼近了 Redis 3.0 的理论性能。

Note that LRU is just a model to predict how likely a given key will be accessed in the future. Moreover, if your data access pattern closely resembles the power law, most of the accesses will be in the set of keys the LRU approximated algorithm can handle well.

请注意，LRU 只是一个模型，用来预测将来访问给定键的可能性有多大。此外，如果您的数据访问模式与幂律密切相关，那么大多数访问将在 LRU 近似算法能够很好处理的键集合中。

In simulations we found that using a power law access pattern, the difference between true LRU and Redis approximation were minimal or non-existent.

在模拟中，我们发现使用幂律访问模式时，真正的 LRU 和 Redis 近似之间的差异微乎其微，甚至不存在。

However you can raise the sample size to 10 at the cost of some additional CPU usage to closely approximate true LRU, and check if this makes a difference in your cache misses rate.

您可以将采样大小提高到 10，代价是额外的 CPU 使用，以更接近真正的 LRU，然后检查这是否会影响缓存的未命中率。

To experiment in production with different values for the sample size by using the CONFIG SET maxmemory-samples <count> command, is very simple.

在生产环境中尝试不同的采样大小非常简单，只需使用CONFIG SET maxmemory-samples <count>命令即可。

The new LFU mode

新的 LFU 模式

Starting with Redis 4.0, the Least Frequently Used eviction mode is available. This mode may work better (provide a better hits/misses ratio) in certain cases. In LFU mode, Redis will try to track the frequency of access of items, so the ones used rarely are evicted. This means the keys used often have a higher chance of remaining in memory.

从 Redis 4.0 版本开始，引入了最不经常使用（LFU）的驱逐模式。在某些情况下，LFU 模式可能表现更好（提供更好的命中/失误比）。在 LFU 模式下，Redis 会尝试跟踪条目的访问频率，以便很少使用的条目被驱逐出去。这意味着经常使用的键有更高的机会保留在内存中。

To configure the LFU mode, the following policies are available:

要配置 LFU 模式，可以使用以下策略：

• volatile-lfu Evict using approximated LFU among the keys with an expire set.

• 使用带有过期设置的键中的近似 LFU 进行驱逐。

• allkeys-lfu Evict any key using approximated LFU.

• 使用近似 LFU 来驱逐任何键。

LFU is approximated like LRU: it uses a probabilistic counter, called a Morris counter to estimate the object access frequency using just a few bits per object, combined with a decay period so that the counter is reduced over time. At some point we no longer want to consider keys as frequently accessed, even if they were in the past, so that the algorithm can adapt to a shift in the access pattern.

LFU 是通过使用概率计数器（称为 Morris 计数器）来估计对象访问频率的方式来近似的，每个对象只使用几位比特，结合衰减周期以使计数器随时间降低。在某些时刻，即使过去访问频率较高的键，我们也不再希望将其视为频繁访问的，以便算法可以适应访问模式的变化。

That information is sampled similarly to what happens for LRU (as explained in the previous section of this documentation) to select a candidate for eviction.

这些信息的采样方式类似于 LRU（如本文档的前一节所解释的），以选择要淘汰的候选项。

However unlike LRU, LFU has certain tunable parameters: for example, how fast should a frequent item lower in rank if it gets no longer accessed? It is also possible to tune the Morris counters range to better adapt the algorithm to specific use cases.

与 LRU 不同，LFU 具有某些可调参数：例如，如果不再访问频繁的项目，频繁项目应降低排名的速度有多快？还可以调整 Morris 计数器的范围，以更好地适应特定的使用情况。

By default Redis is configured to:

默认情况下，Redis 被配置为：

• Saturate the counter at, around, one million requests.

• 数器饱和在大约一百万个请求左右（这意味着当某个键的访问计数达到一百万时，Redis 不再增加计数，即使该键继续被访问。这是 LFU 算法的默认行为，但您可以根据需要调整这个饱和度。）

• Decay the counter every one minute.

• 每隔一分钟减小计数器的值。

Those should be reasonable values and were tested experimental, but the user may want to play with these configuration settings to pick optimal values.

这些值应该是合理的，并经过实验测试，但用户可能希望调整这些配置设置以选择最佳值。

Instructions about how to tune these parameters can be found inside the example redis.conf file in the source distribution. Briefly, they are:

关于如何调整这些参数的说明可以在源码中的示例 redis.conf 文件中找到。简而言之，它们是：

lfu-log-factor 10 lfu-decay-time 1

The decay time is the obvious one, it is the amount of minutes a counter should be decayed, when sampled and found to be older than that value. A special value of 0 means: we will never decay the counter.

衰减时间是比较明显的一个参数，它表示当一个计数器被采样并发现其年龄超过该值时，应该经过的分钟数。特殊值 0 意味着：我们永远不会对计数器进行衰减。

The counter logarithm factor changes how many hits are needed to saturate the frequency counter, which is just in the range 0-255. The higher the factor, the more accesses are needed to reach the maximum. The lower the factor, the better is the resolution of the counter for low accesses, according to the following table:

计数器的对数因子改变了饱和频率计数器所需的命中次数，它在范围 0-255 内。因子越高，需要更多的访问次数才能达到最大值。因子越低，计数器对低访问率的分辨率越好，如下表所示：

So basically the factor is a trade off between better distinguishing items with low accesses VS distinguishing items with high accesses. More information is available in the example redis.conf file.

因此，这个因子基本上是在更好地区分低访问率项与高访问率项之间进行权衡的。更多信息可以在示例 redis.conf 文件中找到。

3. Technique/Tips

这周在进行 HTML/CSS/JS/Jquery 相关技术的开发，由于一直做的是后端，这是第一次接触前端，因此在这个过程遇到了很多不会的用法，这周简单的整理一下：

• CSS 的 lable 组件内容的换行的相关属性：

white-space: normal; //文本内的空白字符会被合并，并且文本会在需要时换行。white-space: nowrap; //文本内的空白字符会被合并，但文本不会换行，会在容器边缘发生溢出。white-space: pre;    // 文本内的空白字符会被保留，但只有在遇到换行符或 <br> 标签时才会换行。white-space: pre-wrap;  // 文本内的空白字符会被保留，文本会在需要时换行，但也会在遇到换行符或 <br> 标签时换行。white-space: pre-line;  //文本内的空白字符会被保留，文本会在需要时换行，同时也会在遇到换行符或 <br> 标签时换行。white-space: break-spaces; //与 pre-wrap 类似，但在换行时会尽量保留连续的空白字符。

• 删除指定文本组件中内容的一行：

// 找到标签元素var label = $("#yourLabelId");
// 获取标签的文本内容var text = label.html();
// 指定要删除的字符串var stringToRemove = "包含指定字符串的行";
// 使用正则表达式删除包含指定字符串的行var updatedText = text.replace(new RegExp(".*" + stringToRemove + ".*<br>"), "");
// 更新标签的文本内容label.html(updatedText);

4. Share

• 不要拒绝生活给你的会让你继续进步的挑战，即使万事开头难。但是终究会柳暗花明