背景

Ceph 是一个高性能、可靠的、可拓展的分布式文件系统。Ceph 最主要的目标是可拓展性，即如何使得文件系统支持任意多的数据量。

Ceph 面临以下难题：

• 如何高效地管理元数据？
  • 如何确保一致性？
  • 如何服务热点？
  • 如何服务动态的工作负载？
• 如何高效地管理数据？
  • 数据容错
  • 复制

设计

元数据管理是实现高性能分布式文件系统的一大难点，元数据操作甚至占典型工作负载的 50。由于元数据存在较多的依赖，导致无法像文件 IO 一样水平拓展。此外，POSIX 的 per-file metadata 在小文件场景下海限制了存储利用率。Finding a needle in haystack Facebook’s photo storage使用小文件聚合的方式减少元数据带来的磁盘 IO。The Google file system虽然提供了命名空间的抽象，但实现上改为了 key，这极大地减少了锁争用，而且简化了垃圾回收。

有序链表无法在$O(logN)$时间复杂度内搜索的根源在于：链表不支持随机访问。既然不支持随机访问，可以通过增大步长降低搜索次数。

每个隔 2 个节点，该节点同时指向它 2 个位置后的节点。这样，搜索只需要$N/2+1$步。

译者序

An introduction to lockless algorithms是 Paolo Bonzini 在 LWN.net 上发布的无锁编程系列文章的第一篇，清楚明了地阐述了内存模型中的 acquire/release 语义。

当传统的锁定原语（locking primitives）无法使用或性能不足时，无锁算法就会引起 Linux 内核的兴趣。因此，无锁算法时不时出现在 LWN 上。LWN 最近一次提及无锁算法是在七月，这促使我写下了这一系列文章。更频繁出现的话题是 read-copy-update（RCU——这些2007 年的文章 仍未过时），引用计数，以及种种将无锁原语（lockless primitives）包装成更高级、更理解的 API 的技术。这些文章深入到了无锁编程背后的概念以及如何在内核中运用。内存模型的底层知识通常被认为是连经验丰富的黑客都感到害怕的高级东西，我们的编辑在七月的文章中写道：“需要不一样的脑子才能真正理解内存模型。”他说 Linux kernel 内存模型（尤其是 Documentation/memory-barriers.txt）能把小孩吓哭，acquire 和 release 这样的词语可能也同样吓人。与此同时，像 RCU 和 seqlocks 一类的机制在内核中运用的如此广泛，以至于几乎每个开发者早晚会遇到无锁编程接口。因此，你最好能对无锁原语有基本的理解。通过这一系列文章，我会说明 acquire 和 release 语义究竟是什么，并介绍五种相对简单的能够覆盖无锁原语大多数用例的模式。

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

点文件管理的痛点

管理点文件主要有两个目的：

原理

许多情况下，对象的构造和析构成本原大于内存的分配和回收。因此，既要优化内存分配，也要降低对象的构造/析构成本。

通过缓存对象维持对象的基本结构，在多次“使用”间复用此基本结构。对象在第一次分配时构造(初始化基本结构），回收时不析构（不毁坏此基本结构），下次分配直接返回缓存的对象。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 SLAB, so it's only appropriate for small
systems.

本文的代码摘抄自 The C Programming Language 并修改了 C99 语法错误，你可以在这里获取完整代码 malloc.c。