#683 Linux-libre

Linux 2021-10-29

内核需要和硬件打交道，中间少不了硬件厂商的支持，可是有些厂商不愿提供相关的资料，只提供了一些二进制文件，无法审查，无法修改。
Linux 内核中一直包含着很多这样的二进制 blob。

#682 转载：Redis LRU 策略

Redis 2021-10-26

这篇文章讨论的是 Reids 数据到期之后发生了什么。
Redis 并不会立即删除过期数据，而是根据配置的策略来处理。

config get maxmemory-policy
# maxmemory-policy
# volatile-ttl

原文

When Redis is used as a cache, often it is handy to let it automatically evict old data as you add new data. This behavior is very well known in the community of developers, since it is the default behavior of the popular memcached system.
Redis 和 Memcached 一样会自动清除旧数据。

LRU is actually only one of the supported eviction methods. This page covers the more general topic of the Redis maxmemory directive that is used in order to limit the memory usage to a fixed amount, and it also covers in depth the LRU algorithm used by Redis, that is actually an approximation of the exact LRU.

Starting with Redis version 4.0, a new LFU (Least Frequently Used) eviction policy was introduced. This is covered in a separated section of this documentation.

Maxmemory configuration directive 最大内存配置指令

The maxmemory configuration directive is used in order to configure Redis to use a specified amount of memory for the data set. It is possible to set the configuration directive using the redis.conf file, or later using the CONFIG SET command at runtime.

For example in order to configure a memory limit of 100 megabytes, the following directive can be used inside the redis.conf file.

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.
Markjour 注释：设置成 0 的话，64 位系统上表示没有限制，32 位系统则隐式地使用 3GB 内存限制。

When the specified amount of memory is reached, it is possible to select among different behaviors, called policies. Redis can just return errors for commands that could result in more memory being used, or it can evict some old data in order to return back to the specified limit every time new data is added.

Eviction policies 清理策略

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

The following policies are available:

  • noeviction: return errors when the memory limit was reached and the client is trying to execute commands that could result in more memory to be used (most write commands, but DEL and a few more exceptions).
    Markjour 注释：内存占用超过限制之后，执行写命令报错，除了 DEL 和其他少数命令。
  • allkeys-lru: evict keys by trying to remove the less recently used (LRU) keys first, in order to make space for the new data added.
    Markjour 注释：常规的 LRU 策略。
  • volatile-lru: evict keys by trying to remove the less recently used (LRU) keys first, but only among keys that have an expire set, in order to make space for the new data added.
    Markjour 注释：只对设置了 TTL 的 key 进行 LRU 策略。
  • allkeys-random: evict keys randomly in order to make space for the new data added.
    Markjour 注释：随机删除。
  • volatile-random: evict keys randomly in order to make space for the new data added, but only evict keys with an expire set.
    Markjour 注释：只对设置了 TTL 的 key 进行随机删除。
  • volatile-ttl: evict keys with an expire set, and try to evict keys with a shorter time to live (TTL) first, in order to make space for the new data added.
    Markjour 注释：按照 TTL 升序依次删除。

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

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 in order to tune your setup.

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 that a subset of elements will be accessed far more often than the rest. This is a good pick if you are unsure.
  • 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 (all elements likely accessed with the same probability).
  • 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.

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.

It is also worth noting that setting an expire to a key costs memory, so using a policy like allkeys-lru is more memory efficient since there is no need to set an expire for the key to be evicted under memory pressure.
Markjour 注释：TTL 的处理需要占用额外的内存，如果是用 allkeys-lru 策略则可以不需要设置 TTL，可以节约内存。

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.
  • 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.

Markjour 注释: 常用的 LRU 过期删除策略：定时，Lazy Expire，LFU，FIFO，RANDOM，TTL。

Approximated LRU algorithm 近似 LRU 算法

Markjour 注释: 出于节约资源（内存）的考虑，Redis LRU 算法并非精确的 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 access that was accessed the most 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.

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.

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:

maxmemory-samples 5

The reason why Redis does not use a true LRU implementation is because it costs more memory. However the approximation is virtually equivalent for the application using Redis. The following is a graphical comparison of how the LRU approximation used by Redis compares with true LRU.

LRU comparison

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, so that 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.

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.

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.

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 that the LRU approximated algorithm will be able to handle well.

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

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

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

Markjour 注释：1. 在 Redis 3.0 中，LRU 算法的精确度提高了。2. 按照默认的 5 个样本就足够了。

The new LFU mode 频率计数模式

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

If you think at LRU, an item that was recently accessed but is actually almost never requested, will not get expired, so the risk is to evict a key that has an higher chance to be requested in the future. LFU does not have this problem, and in general should adapt better to different access patterns.

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

  • volatile-lfu Evict using approximated LFU among the keys with an expire set.
    Markjour 注释：对配置了 TTL 的键执行 LFU 清理。
  • allkeys-lfu Evict any key using approximated LFU.
    Markjour 注释：对所有键执行 LFU 清理。

LFU is approximated like LRU: it uses a probabilistic counter, called a Morris counter in order 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.
Markjour 注释：概率计数器（莫里斯计数器）。
近似计数算法允许使用少量内存计算大量事件。1977年由贝尔实验室的罗伯特·莫里斯（密码学家）发明，它使用概率技术来增加计数器。

Those informations are sampled similarly to what happens for LRU (as explained in the previous section of this documentation) in order to select a candidate for eviction.

However unlike LRU, LFU has certain tunable parameters: for instance, 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 in order to better adapt the algorithm to specific use cases.

By default Redis 4.0 is configured to:

  • Saturate the counter at, around, one million requests. Markjour 注释：饱和计数器，一百万请求。
  • Decay the counter every one minute. Markjour 注释：每分钟衰减一次。

Markjour 注释: LFU 有可调节参数，上面是 Redis 4.0 的两个默认配置。

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

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

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: always decay the counter every time is scanned, and is rarely useful.

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

factor 100 hits 1000 hits 100K hits 1M hits 10M hits
0 104 255 255 255 255
1 18 49 255 255 255
10 10 18 142 255 255
100 8 11 49 143 255

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

Since LFU is a new feature, we'll appreciate any feedback about how it performs in your use case compared to LRU.

总结

TTL (过期时间) 相关命令：

SET key value [EX seconds|PX milliseconds|EXAT timestamp|PXAT milliseconds-timestamp|KEEPTTL] [NX|XX] [GET]
SETEX key seconds value
PSETEX key milliseconds value
GETEX key [EX seconds|PX milliseconds|EXAT timestamp|PXAT milliseconds-timestamp|PERSIST]

TTL key
PTTL key
EXPIRETIME key  # 获取过期时间戳，单位为秒
PEXPIRETIME key # 获取过期时间戳，单位为毫秒

EXPIRE key seconds
PEXPIRE key milliseconds
EXPIREAT key timestamp
PEXPIREAT key milliseconds-timestamp

相对于 LRU (Least Recently Used), Redis 采用 LFU (Least Frequently Used) 算法对于其应用场景来说确实是个不错的选择。

一共八种策略：

  • noeviction 拒绝新值写入，不自动删除
  • volatile-ttl 按 TTL 值删除
  • volatile-lru / allkeys-lru LRU
  • volatile-lfu / allkeys-lfu LFU
  • volatile-random / allkeys-random 随机删除
evict [ɪˈvɪkt] vt. 驱逐；逐出
eviction [ɪˈvɪkʃn] n. 逐出；赶出；收回
volatile [ˈvɒlətaɪl]
    adj. [化学] 挥发性的；不稳定的；爆炸性的；反复无常的
    n. 挥发物；有翅的动物
    n. (Volatile)人名；(意)沃拉蒂莱

#681 开源协议

开源 法律 2021-10-26

常见协议

如何选择开源协议

  • GPL: 有 v2 和 v3 两个常见版本。
  • LGPL: 有 v2.1 和 v3 两个常见版本。
  • AGPL
  • Apache 2.0
  • BSD: 又分成两句和三句两种版本
  • MIT: 等于 BSD 2-clause
  • WTFPL:

国产的两个协议：

  • 木兰: 国家队，分成：木兰宽松许可证 MulanPSL / 木兰公共许可证 MulanPubL, 分别对应 Apache 和 GPL
  • 提供中文版本，解决互诉漏洞，不要求列出每个修改文件（Apache 的约束太繁琐）
  • MulanPSL v2 已经得到 OSI 批准。MulanPSL v2 相对于 v1 的主要变化是修改英文版措辞以及确定中英文有冲突时以中文版本为准。
  • ZPL 禅道公司设计的。主要要求保留所有产品相关标识。
  • 反 996 协议, 在 MIT 的基础上加了保护劳动者合法权益的条款。

    个人或法人不得以任何方式诱导或强迫其全职或兼职员工或其独立承包人以口头或书面形式同意直接或间接限制、削弱或放弃其所拥有的，受相关与劳动和就业有关的法律、法规、规则和标准保护的权利或补救措施，无论该等书面或口头协议是否被该司法管辖区的法律所承认，该等个人或法人实体也不得以任何方法限制其雇员或独立承包人向版权持有人或监督许可证合规情况的有关当局报告或投诉上述违反许可证的行为的权利。

Unlicense

https://unlicense.org/

最近听说的一个协议。

只有三点：

  1. 传染性
  2. 关于专利
  3. 关于隐私

区别

传染性

  1. GPL, LGPL, MPL 要求衍生品采用相同的许可协议。Copyleft
    其中，LGPL，MPL 不要求新增代码采用相同许可协议。Weak Copyleft
  2. MulanPSL, Apache, BSD, MIT 这几种就相对宽松了。Permissive

专利问题

隐私问题

只有 Unlicense 解决了这个问题。

推广

  1. 除了 Unlicense 和 WTFPL 之外, 其他协议都要求不得使用作者推广

MulanPSL-2.0
评分 100 2. 许可协议类型: Permissive 3. 司法管辖区: Not specified
4.a 授予专利权: Yes
4.b 专利报复条款: Yes 5. 指定“增强型归属”: No 6. 解决“隐私漏洞”: No 7. 指定“不推广”功能: Yes
Apache-2.0
评分 100 2. 许可协议类型: Permissive 3. 司法管辖区: Not specified
4.a 授予专利权: Yes
4.b 专利报复条款: Yes 5. 指定“增强型归属”: No 6. 解决“隐私漏洞”: No 7. 指定“不推广”功能: Yes
BSD-3-Clause
评分 100 2. 许可协议类型: Permissive 3. 司法管辖区: Not specified
4.a 授予专利权: No
4.b 专利报复条款: No 5. 指定“增强型归属”: No 6. 解决“隐私漏洞”: No 7. 指定“不推广”功能: Yes
EPL-1.0
评分 100 2. 许可协议类型: Weak copyleft 3. 司法管辖区: Specified: State of New York, US
4.a 授予专利权: Yes
4.b 专利报复条款: Yes 5. 指定“增强型归属”: No 6. 解决“隐私漏洞”: No 7. 指定“不推广”功能: Yes
GPL-2.0
评分 100 2. 许可协议类型: Strong copyleft 3. 司法管辖区: Not specified
4.a 授予专利权: No
4.b 专利报复条款: No 5. 指定“增强型归属”: No 6. 解决“隐私漏洞”: No 7. 指定“不推广”功能: Yes
LGPL-2.1
评分 100 2. 许可协议类型: Weak copyleft 3. 司法管辖区: Not specified
4.a 授予专利权: No
4.b 专利报复条款: No 5. 指定“增强型归属”: No 6. 解决“隐私漏洞”: No 7. 指定“不推广”功能: Yes
LGPL-3.0
评分 100 2. 许可协议类型: Weak copyleft 3. 司法管辖区: Not specified
4.a 授予专利权: Yes
4.b 专利报复条款: Yes 5. 指定“增强型归属”: No 6. 解决“隐私漏洞”: No 7. 指定“不推广”功能: Yes
MIT
评分 100 2. 许可协议类型: Permissive 3. 司法管辖区: Not specified
4.a 授予专利权: No
4.b 专利报复条款: No 5. 指定“增强型归属”: No 6. 解决“隐私漏洞”: No 7. 指定“不推广”功能: Yes
MPL-2.0
评分 100 2. 许可协议类型: Weak copyleft 3. 司法管辖区: Not specified
4.a 授予专利权: Yes
4.b 专利报复条款: Yes 5. 指定“增强型归属”: Yes 6. 解决“隐私漏洞”: No 7. 指定“不推广”功能: Yes
Unlicense
评分 100 2. 许可协议类型: Weak copyleft 3. 司法管辖区: Not specified
4.a 授予专利权: Yes
4.b 专利报复条款: No 5. 指定“增强型归属”: No 6. 解决“隐私漏洞”: Yes 7. 指定“不推广”功能: No

WTFPL
评分 100 2. 许可协议类型: Permissive 3. 司法管辖区: Not specified
4.a 授予专利权: Yes
4.b 专利报复条款: Yes 5. 指定“增强型归属”: No 6. 解决“隐私漏洞”: No 7. 指定“不推广”功能: No

参考资料与拓展阅读

#679 Thunderbolt

计算机硬件 接口技术 2021-10-24

Thunderbolt（又称“雷电”，苹果中国译为“雷雳”[4]）是由英特尔发表的连接器标准，目的在于当作电脑与其他设备之间的通用总线，第一代与第二代接口是与 Mini DisplayPort 集成，较新的第三代开始改为与 USB Type-C 结合，并能提供电源。

早期由英特尔独立研发，使用光纤传输；后来在一次科技展示会场上，苹果公司看到了早期光纤传输的原型后，主动对英特尔表示兴趣并给予开发上的建议，致使正式发表的第一代从光纤改用铜线和苹果的 Mini DisplayPort 外形。

第三代改为使用 USB Type-C 接口。由于二合一的集成特点，因此它既能以双向 40 Gbit/s 传输数据（40 Gbit/s + 40 Gbit/s，特别是针对外置高速网络时），既能兼容 Mini DisplayPort 设备直接连接 Thunderbolt 接口传输视频与声音信号，也可连接 Apple Thunderbolt Display 直接同时输出视频、声音与数据，且不用如传统使用多条连接线。

版本 时间 厂商 代号 带宽 USB
Thunderbolt 开发版 2009 Intel Light Peak    
Thunderbolt 2011/02 Intel
Apple		 Light Peak 10 Gbit/s 与 USB 3.0 同时应用在未来的系统中，扮演互补角色。
具有这种接口的 MacBook Pro 及一根 29 美元的连接线。
苹果独享这技术专利权一年。
Thunderbolt 2 2013 Intel
Apple		 Falcon Ridge 20 Gbit/s  
Thunderbolt 3 2015/06/02 Intel Alpine Ridge 40 Gbit/s 连接端口更换为 USB Type-C
Thunderbolt 4 2020/07/08 Intel   40 Gbit/s  
  1. Thunderbolt 也叫雷电接口，Intel 公司开发。
  2. 最新的是今年发布的 4 代。
  3. 需要 CPU 支持：Thunderbolt 控制器
  4. 可以支持 USB, SD/TF, 网口 (), 视频接口（HDMI, VGA, DP）等接口, PCI-E 设备, 固态硬盘。
    注意：支持的接口和设备还需要看具体的实现，上面只是说理论上支持。
  5. 通常通过扩展坞的方式进行连接。

参考资料与拓展阅读

#678 我的开发机器

个人 开发者 2021-10-24

Notebook
我的主力开发环境是大概 14 年 4 月在 DELL 官方 (dell.com) 买的一台 Inspiron 14R (5437) 笔记本。
PS: 这台笔记本原本是我老婆办公用, 用了将近五年之后, 于 2019 年 1 月在换了一台 小米 Air 13.3, 然后我就有笔记本了...到现在我也用了两年多了。

#677 家庭教育促进法

个人 法律 育儿 2021-10-23

除了房产税的消息，这是新闻联播内容中最让我感兴趣的第二个点，主要是我有孩子，自然对教育两个字特别感兴趣。

不过我本以为是和 “双减” 有关，但仔细了解之后才知道，立法是为了明确监护人应该承担的教育义务，明确家庭和学校在教育方面的界限。

  1. 道德品质
  2. 身体素质
  3. 生活技能
  4. 文化修养
  5. 行为习惯

但也没有规定什么处罚措施，据说是删掉了，只是强调了国家对家庭教育的指导、支持和配套服务。

参考资料与拓展阅读

#676 房产税开始试点

个人 楼市 2021-10-23

今天的最重要新闻：

新华社10月23日消息，为积极稳妥推进房地产税立法与改革，引导住房合理消费和土地资源节约集约利用，促进房地产市场平稳健康发展，第十三届全国人民代表大会常务委员会第三十一次会议决定：授权国务院在部分地区开展房地产税改革试点工作。
———— 新华社：全国人大常委会授权国务院在部分地区开展房地产税改革试点工作

我不懂法律条文，但我之前听说，房产税将会很大程度改变中国楼市。观察ing...

#675 Python GIL 的最新动态

Python GIL 2021-10-22

开源中国上看到有人通过一些实验验证来视图说服 Python 核心团队移除 GIL，根据他的数据，移除 GIL 可以大幅提升多线程性能（19.8 倍）。

#674 Redis 版本历史

Redis 2021-10-20
版本 日期
6.2.8 October 2021
6.2.4 August 2021
6.0.20 April 2021
6.0.12 January 2021
6.0.8 September 2020
6.0 May 2020
5.6.0 April 2020
5.5 Preview April 2019
5.4.14 February 2020
5.4.10 December 2019
5.4.6 July 2019
5.4.4 June 2019
5.4.2 April 2019
5.4 December 2018
5.2.2 August 2018
5.3 beta July 2018
5.2 June 2018
5.0.2 2018 March
5.0 November 2017
4.5 May 2017
4.4 December 2016
4.3.0-230 August 2, 2016
4.2.1-30 October 18, 2015
4.0.0-49 June 18, 2015
0.99.5-24 February 15, 2015
0.99.5-11 January 5, 2015

Redis 4

  1. 模块系统，为后来的 RedisJSON，RedisSearch 打基础
  2. PSYNC 2.0（部分复制）
  3. LFU 优化
  4. 异步优化
  5. DEL -> UNLINK
  6. FLUSHDB, FLUSHALL 增加 ASYNC 参数
  7. RDB-AOF 混合持久化
  8. SWAPDB 命令
  9. MEMORY 命令

Redis 5

Redis 6

  • 多线程 IO
  • SSL
  • ACL 权限控制
  • RESP3
  • 客户端缓存

Redis 7

参见：2022/04/29，Redis 7 的变化

参考资料与拓展阅读