惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

cs.AI updates on arXiv.org
cs.AI updates on arXiv.org
P
Palo Alto Networks Blog
S
Securelist
Threat Intelligence Blog | Flashpoint
Threat Intelligence Blog | Flashpoint
NISL@THU
NISL@THU
L
Lohrmann on Cybersecurity
有赞技术团队
有赞技术团队
The GitHub Blog
The GitHub Blog
C
Cisco Blogs
B
Blog
Microsoft Azure Blog
Microsoft Azure Blog
Recent Announcements
Recent Announcements
Simon Willison's Weblog
Simon Willison's Weblog
T
Tenable Blog
Know Your Adversary
Know Your Adversary
Spread Privacy
Spread Privacy
WordPress大学
WordPress大学
月光博客
月光博客
Latest news
Latest news
C
CXSECURITY Database RSS Feed - CXSecurity.com
T
Threat Research - Cisco Blogs
Cisco Talos Blog
Cisco Talos Blog
I
InfoQ
D
Darknet – Hacking Tools, Hacker News & Cyber Security
W
WeLiveSecurity
Hacker News - Newest:
Hacker News - Newest: "LLM"
酷 壳 – CoolShell
酷 壳 – CoolShell
U
Unit 42
C
Cybersecurity and Infrastructure Security Agency CISA
博客园 - 聂微东
人人都是产品经理
人人都是产品经理
Google DeepMind News
Google DeepMind News
Apple Machine Learning Research
Apple Machine Learning Research
Attack and Defense Labs
Attack and Defense Labs
罗磊的独立博客
T
The Exploit Database - CXSecurity.com
I
Intezer
GbyAI
GbyAI
Jina AI
Jina AI
www.infosecurity-magazine.com
www.infosecurity-magazine.com
Blog — PlanetScale
Blog — PlanetScale
博客园 - 司徒正美
Google Online Security Blog
Google Online Security Blog
Engineering at Meta
Engineering at Meta
D
Docker
Recent Commits to openclaw:main
Recent Commits to openclaw:main
小众软件
小众软件
云风的 BLOG
云风的 BLOG
爱范儿
爱范儿
Project Zero
Project Zero

土法炼钢兴趣小组的算法知识备份

国密算法与国密 TLS 系列索引 【系统架构设计】架构质量属性:不只是"高可用高性能" 【系统架构设计百科】告警策略:如何避免"狼来了" 【系统架构设计】CQRS:读写分离的架构哲学 【系统架构设计】空间架构:极端扩展场景的解法 【系统架构设计】微服务架构深度审视:优势、代价与适用边界 【系统架构设计】扩展性原理:水平、垂直与对角扩展 【系统架构设计】无状态设计:扩展的第一步也是最难的一步 【系统架构设计】缓存架构:从本地到分布式的多级缓存体系 【系统架构设计】管道与过滤器:Unix 哲学的架构表达 【系统架构设计】复杂性管理:架构的核心战场 【系统架构设计】消息队列架构:异步解耦的设计与陷阱 【系统架构设计】CDN 架构:全球加速的设计原理 【系统架构设计】连接池设计:被忽视的性能杀手 【系统架构设计】弹性设计模式:熔断器、舱壁与超时 【系统架构设计】高可用设计模式:冗余、故障转移与仲裁 【系统架构设计】容量规划:从拍脑袋到数据驱动 【系统架构设计】数据库扩展:分库分表的工程实践与替代方案 【系统架构设计】SLO 工程:可靠性的量化管理 【系统架构设计】性能建模:用数学思维分析系统瓶颈 【系统架构设计】混沌工程:主动验证系统的韧性 【系统架构设计】零拷贝与内存映射:数据搬运的极致优化 【系统架构设计】线程模型:从 thread-per-request 到协程 【系统架构设计】容灾架构:多活与灾备设计 【系统架构设计】数据库性能模式:索引、查询与连接管理 【系统架构设计】数据建模:从关系范式到文档模型的真实权衡 【系统架构设计】吞吐量优化:批处理、流水线与并发模型 【系统架构设计】流处理架构:从批处理到实时的范式迁移 【系统架构设计】搜索引擎架构:倒排索引之上的系统设计 【系统架构设计】时序数据架构:监控与 IoT 的存储设计 【系统架构设计】数据迁移与版本化:在线不停机的数据演进 【系统架构设计】数据湖与数据仓库:分析架构的演进路线 【系统架构设计】API 网关设计:入口层的职责边界 【系统架构设计】应用层数据一致性模式:在正确性与性能之间走钢丝 【系统架构设计】多模数据库选型:Polyglot Persistence 的工程实践 【系统架构设计】服务发现与注册:动态拓扑的基础设施 【系统架构设计】配置管理架构:从配置文件到配置中心 【系统架构设计】全链路压测:大规模系统的性能验证 【系统架构设计】幂等性设计:分布式环境下的安全重试 【系统架构设计】契约测试与 Schema 演进:服务间的信任协议 【系统架构设计】长连接与推送架构:WebSocket、SSE 与 MQTT 【系统架构设计】延迟分析:从 P50 到 P999 的全链路追踪 【系统架构设计百科】DDD 战术模式:聚合、实体与值对象 【系统架构设计百科】防腐层与开放主机服务:系统集成的 DDD 方案 【系统架构设计百科】领域事件与事件风暴:从业务到架构的桥梁 【系统架构设计百科】CQRS + Event Sourcing 完整实战:从领域建模到部署 【系统架构设计百科】DDD 与微服务:用领域模型划分服务边界 【系统架构设计】DDD 战略设计:限界上下文与上下文映射 【系统架构设计百科】认证架构:从 Session 到 JWT 到 OIDC 【系统架构设计】API 设计哲学:REST vs GraphQL vs gRPC 的真实权衡 排序算法专题:从 TimSort 到并行排序 【密码学百科】国密算法体系:SM2/SM3/SM4/SM9 全景解读 【密码学百科】承诺方案:Pedersen 承诺、向量承诺与多项式承诺 【密码学百科】不经意传输与隐私信息检索:OT、OT 扩展与 PIR 【密码学百科】门限密码学:门限签名、门限解密与分布式密钥生成 完美哈希:从理论到 gperf 实践 【密码学百科】安全多方计算:从 Yao 的混淆电路到实用 MPC 【密码学百科】同态加密:从 Paillier 到全同态加密(FHE) 【密码学百科】零知识证明系统:zk-SNARKs、zk-STARKs 与 Bulletproofs 【密码学百科】概率论与密码分析:生日攻击、差分分析与线性分析 【密码学百科】计算复杂性与归约:密码安全性证明的基石 【密码学百科】秘密共享:Shamir 方案、VSS 与安全多方计算入口 【密码学百科】椭圆曲线代数:Weierstrass 方程、点群运算与曲线选择 【密码学百科】离散对数与配对密码学:从 DLP 到 BLS 签名 【密码学百科】格密码数学基础:SVP、LWE 与格基约化 【密码学百科】抽象代数:群、环、域的密码学视角 【密码学百科】有限域算术:GF(2^n) 运算与在 AES/ECC 中的应用 【密码学百科】数论进阶:二次剩余、椭圆曲线上的 Weil 配对 【密码学百科】密码学简史:从凯撒密码到量子时代 【密码学百科】威胁模型与安全目标:CIA 三要素之外 【密码学百科】Kerckhoffs 原则与现代密码设计哲学 【密码学百科】随机性:密码学的基石 【密码学百科】信息论入门:熵、完美保密与 Shannon 定理 【密码学百科】分组密码原理:Feistel 网络与 SPN 结构 【密码学百科】AES 逐步拆解:SubBytes 到 MixColumns 的数学 【密码学百科】分组密码工作模式全览:ECB/CBC/CTR/OFB/CFB 【密码学百科】流密码:RC4 的兴衰与 ChaCha20 的崛起 【密码学百科】密码学哈希函数:MD5→SHA-2→SHA-3 的进化之路 【密码学百科】MAC 与 HMAC:消息认证的正确姿势 【密码学百科】认证加密(AEAD):GCM、ChaCha20-Poly1305 与 OCB 【密码学百科】密钥派生函数:HKDF、PBKDF2、Argon2 与密码存储 【密码学百科】公钥密码的数论基础:模运算、群、原根 【密码学百科】RSA 从原理到攻击:教科书 RSA 为什么不安全 【密码学百科】Diffie-Hellman 密钥交换与离散对数问题 【密码学百科】椭圆曲线密码学(ECC):从几何直觉到点群运算 【密码学百科】数字签名:ECDSA、EdDSA 与 Schnorr 签名 【密码学百科】现代密钥交换:X25519、ECDHE 与前向保密 【密码学百科】混合加密与 KEM/DEM 范式:ECIES 与 HPKE 【密码学百科】填充方案:PKCS#1 v1.5、OAEP 与 PSS 【密码学百科】TLS 协议全解析:从握手到 0-RTT 【密码学百科】PKI 与数字证书:信任链的构建与崩塌 【密码学百科】密码认证协议:从 SRP 到 OPAQUE 【密码学百科】零知识证明入门:如何证明你知道而不泄露 【密码学百科】安全信道构造:Noise 协议框架与 Signal 协议 【密码学百科】密钥管理工程:HSM、KMS 与密钥生命周期 【密码学百科】侧信道攻击:从时序攻击到功耗分析 【密码学百科】密码学实现陷阱:三层漏洞分类、审计工具链与系统性预防 密码敏捷性:如何设计可升级的密码系统 【密码学百科】OpenSSL/BoringSSL 架构剖析:ENGINE、Provider 与 FIPS 模块 排序基准测试:用数据说话
【操作系统百科】内存回收
2026-04-27 · via 土法炼钢兴趣小组的算法知识备份

物理内存有限;页缓存和匿名页不断增长。内核需要一套策略:谁先被回收、什么时候开始回收、回收多少。Linux 的回收子系统经历了 20 年演化,到今天 MGLRU 是新方向。

一、先看图

flowchart TD
    ALLOC[页分配请求] --> WM{watermark 检查}
    WM -->|> high| OK[直接分配]
    WM -->|< low| WAKEUP[唤醒 kswapd]
    WM -->|< min| DR[direct reclaim<br/>阻塞当前进程]
    WAKEUP --> KSWAPD[kswapd 扫描]
    DR --> SCAN[扫描 LRU / MGLRU]
    KSWAPD --> SCAN
    SCAN --> FILE{clean file page?}
    FILE -->|yes| DROP[直接丢弃]
    FILE -->|dirty| WB[writeback 后丢弃]
    SCAN --> ANON{anon page?}
    ANON -->|swappiness > 0| SWAP[swap out]
    ANON -->|swappiness = 0| SKIP[跳过]
    classDef ok fill:#3fb95022,stroke:#3fb950,color:#adbac7;
    classDef warn fill:#f0883e22,stroke:#f0883e,color:#adbac7;
    classDef crit fill:#f8514922,stroke:#f85149,color:#adbac7;
    class OK ok
    class WAKEUP,KSWAPD,WB warn
    class DR crit

二、Watermark 三线

每个 zone 有三个水位:

  • high:充裕,正常分配
  • low:kswapd 唤醒阈值
  • min:direct reclaim 阈值(分配者亲自回收)

还有 boost watermark(5.0+):sudden spike 时临时提高 low,让 kswapd 提前介入。

cat /proc/zoneinfo | grep -E 'min|low|high|managed'

三、经典 LRU

3.1 四条链表

每个 zone(实际按 lruvec / memcg)维护:

  • active anon
  • inactive anon
  • active file
  • inactive file

页首次分配进 inactive。被访问(PTE A bit)后提升到 active。

3.2 扫描

shrink_nodeshrink_lruvecshrink_list

  1. 扫描 inactive 链表尾部
  2. 检查 PTE A bit(page_referenced):有访问 → 回到 active
  3. 无访问 → 回收候选
  4. clean file → 直接丢
  5. dirty → writeback 后丢
  6. anon → swap out

3.3 swappiness

vm.swappiness = 60(默认)

控制扫描 anon vs file 的比例——不是”swap 概率”。

  • =0:几乎不回收匿名页(除非没有 file 页可回收了)
  • =100:同等对待 anon 和 file
  • =200(6.1+):更激进回收 anon(适合 zram)

容器内:memory.swap.max + memory.zswap.max 也影响。

四、MGLRU(Multi-Gen LRU)

4.1 经典 LRU 的问题

  • 只有 active/inactive 两代,粒度粗
  • A bit 扫描需要遍历 PTE(rmap),开销大
  • 工作集估计不准——新旧混杂

4.2 MGLRU 方案(6.1 合入)

引入多代(generation):

gen 0 (最老) → gen 1 → gen 2 → gen 3 (最新)

每代是一个 FIFO。页被访问时提升到最新代;回收时从最老代扫。

关键优化:

  • 页表扫描:直接 walk 页表而非 rmap,更高效
  • bloom filter:快速判断”这个 gen 里有没有热页”
  • 类型分离:anon 和 file 独立分代

4.3 效果

Google 在 Chromebook 和 Android 上实测:

  • 低内存抖动减少 40%
  • kswapd CPU 使用降低 35%
  • major fault 减少

启用:

cat /sys/kernel/mm/lru_gen/enabled     # 0x0007 = 全开
echo 7 > /sys/kernel/mm/lru_gen/enabled

五、kswapd vs direct reclaim

  • kswapd:后台内核线程,每 zone 一个(kswapd0kswapd1…)。low watermark 触发,回收到 high
  • direct reclaim:分配者自己在 __alloc_pages_slowpath 里回收。min watermark 触发

direct reclaim 是延迟杀手——当前进程阻塞直到回收够页。

生产诊断:

sar -B 1
# pgscank/s = kswapd scan
# pgscand/s = direct reclaim scan → 越高越危险

六、memcg 回收

cgroup v2 memory.max 限制:memcg 内存超限时触发 memcg 级回收,不影响全局。

memory.current   # 当前使用
memory.max       # 硬限
memory.high      # 软限:超过开始 throttle
memory.low       # 保护:尽量不回收
memory.min       # 绝对保护

层级继承:子 cgroup 受父限制。

七、reclaim 调优

7.1 watermark

# 提高 watermark boost,让 kswapd 更早介入
sysctl vm.watermark_boost_factor=15000
sysctl vm.watermark_scale_factor=200    # 拉大 low-high 间距

7.2 swappiness

# DB 服务器(想保留文件缓存、少 swap)
sysctl vm.swappiness=10

# 桌面/Android(zram 有效)
sysctl vm.swappiness=100

7.3 PSI

Pressure Stall Information(4.20+)检测回收压力:

cat /proc/pressure/memory
# some avg10=0.50 avg60=0.30 avg300=0.20 total=12345
  • some:至少一个任务因内存等待
  • full:所有任务都在等

systemd-oomd 基于 PSI 触发 cgroup 级 OOM。

八、compact 与回收的关系

回收释放页后可能碎片化——高阶(order>0)分配仍失败。compaction 把散落的页搬到一起,腾出连续大块。

echo 1 > /proc/sys/vm/compact_memory   # 手动触发
cat /proc/buddyinfo                      # 看各 order 空闲页数

THP 分配失败 → 触发 compaction → 如果还失败 → fallback 4K。这个链条是 THP 抖动的根源。

九、观察

vmstat 1
# si/so = swap in/out
# free = 空闲页数

cat /proc/vmstat | grep -E 'pgsteal|pgscan|pgrefill|pgactivate'
# pgsteal_kswapd  pgsteal_direct

cat /proc/meminfo | grep -E 'Active|Inactive|Slab|SReclaimable'

十、小结

  • watermark 三线控制何时回收、谁来回收
  • 经典 LRU 四链表 + swappiness 控制 anon/file 比例
  • MGLRU 多代替代两代,减少扫描开销和抖动
  • direct reclaim 是延迟杀手——降 pgscand 是关键目标
  • PSI 是现代内存压力的标准度量

参考文献

  • Gorman, M. “Understanding the Linux Virtual Memory Manager.” §10 “Page Frame Reclaiming”
  • Yu Zhao, “Multi-Gen LRU Framework.” LWN.net 2022
  • mm/vmscan.c
  • Documentation/admin-guide/mm/multigen_lru.rst
  • Johannes Weiner, “PSI: Pressure Stall Information.” LPC 2018

工具

  • vmstatsar -B
  • /proc/vmstat/proc/meminfo/proc/zoneinfo
  • cgroup v2 memory.stat
  • bpftrace + vmscan tracepoints

延伸阅读


上一篇页缓存深入 下一篇交换

同主题继续阅读

把当前热点继续串成多页阅读,而不是停在单篇消费。

2026-04-28 · os

【操作系统百科】交换

swap 还值得开吗?本文讲 swap area 基础、swap cache、zram 压缩内存、zswap 前端压缩池、swappiness 的真实含义、容器里的 swap 策略,以及为什么现代 Android 全靠 zram 不靠磁盘。

2026-05-03 · os

【操作系统百科】Slab/SLUB 分配器

buddy 只管页粒度(4K+),内核大多数对象只有几十到几百字节。slab/SLUB 在 buddy 之上做对象级缓存。本文讲 slab 历史、SLUB 接手、SLOB 退场、kmem_cache、per-CPU cache、KASAN 集成。

2026-05-07 · os

【操作系统百科】用户态分配器

glibc malloc、tcmalloc、jemalloc、mimalloc 各有哲学。本文讲 arena、thread cache、size class、madvise 返还策略、碎片与 RSS 膨胀、如何根据负载选分配器。

2026-05-18 · os

【操作系统百科】io_uring 内核内部

io_uring 用共享内存 ring buffer 实现零 syscall 异步 I/O——SQ/CQ、SQPOLL、IOPOLL、注册 fd/buffer、multishot、安全模型演化。本文深入内核实现与工程实践。