有序链表无法在$O(logN)$时间复杂度内搜索的根源在于：链表不支持随机访问。既然不支持随机访问，可以通过增大步长降低搜索次数。 每个隔 2 个节点，该节点同时指向它 2 个位置后的节点。这样，搜索只需要$N/2+1$步。 继续增大步长，在 b 的基础上，每隔 3 个节点，该节点同时指向它后面 3 个位置后的节点。这样，搜索只需要$N/3+2$步。 不断增大步长，每隔 i 个节点，该节

译者序 An introduction to lockless algorithms是 Paolo Bonzini 在 LWN.net 上发布的无锁编程系列文章的第一篇，清楚明了地阐述了内存模型中的 acquire/release 语义。 当传统的锁定原语（locking primitives）无法使用或性能不足时，无锁算法就会引起 Linux 内核的兴趣。因此，无锁算法时不时出现在 LWN 上。LWN 最近一次提及无锁算法是在七月，这促使我写下了这一系列文章。更频繁出现的话题是 read-copy-upd

背景 Facebook 存储 2600 亿张照片，数据量超过 20 PB，且处于迅速增长中。Facebook 照片的工作流有以下特征： 单次写，多次读，很少删除。 长尾：用户会访问旧照片，这些照片不在 CDN 中。 Facebook 一开始直接将照片存储在文件系统中，并通过 NFS 导出，但存在以下问题： 存储空间浪费严重：每个照片（文件）一个 metadata 且大部分 metadata 无用（如用户权限。） 大量与读取照片数据无关的 IO 操作：读取 metadata 需要多次 IO，造成瓶

When you live in a command line, configurations are a deeply personal thing. They are often crafted over years of experience, battles lost, lessons learned, advice followed, and ingenuity rewarded. When you are away from your own configurations, you are an orphaned refugee in unfamiliar and hostile surroundings. You feel clumsy and out of sorts. You are filled with a sense of longing to be back in a place you know. A place you built. A place where all the short-cuts have been worn bare by your own travels. A place you proudly call… $HOME. -- yadm website 点文件管理的痛点 管理点文件主要有两个目的： 方便拷贝配置到新机器 方便地查看对配置的更改 对于软件项目，Git 结合 Github 可以很好的满足这两点需求。但点文件不像软件代码

原理 许多情况下，对象的构造和析构成本原大于内存的分配和回收。因此，既要优化内存分配，也要降低对象的构造/析构成本。 通过缓存对象维持对象的基本结构，在多次“使用”间复用此基本结构。对象在第一次分配时构造(初始化基本结构），回收时不析构（不毁坏此基本结构），下次分配直接返回缓存的对象。slab allocator 缓存的对象生命周期从“构造-使用-析构-构造-使用-析构……”变为“

k&R allocator 是Brain Kernighan和 Dennis Ritchie 的名著 The C Programming Language 第 8.7 节中介绍的一个简单 malloc 实现。因为该书被称为 K&R C，这个 malloc 实现也被称为 K&C allocator。 K&R allocator 的实现非常简洁，Linux 内核基于 K&R allocator 实现了用于嵌入式系统 slob allocator。见 slob: introduce the SLOB allocator，邮件摘要如下： SLOB is a traditional K&R/UNIX allocator with a SLAB emulation layer, similar to the original Linux kmalloc allocator that SLAB replaced. It's signicantly smaller code and is more memory efficient. But like all similar allocators, it scales poorly and suffers from fragmentation more than