Home avatar

主题的晦涩 人生的短暂

[Paper Note] F4 Facebook’s Warm BLOB Storage System

背景

Facebook 的 BLOB(Binary Large OBject)工作负载有以下特征:

  • Write Once Read Many
  • 冷热分区
  • 不可变数据

Finding a needle in haystack Facebook’s photo storage 的目标是高 IOPS,但存储成本高。面对冷热分区的工作负载,Facebook 设计了暖存储系统 f4,专为第存储成本和高容错设计,填补 Facebook BLOB 存储系统的最后一块拼图。

【论文阅读】f4 Facebook’s Warm BLOB Storage System

背景

Facebook 的 BLOB(Binary Large OBject)工作负载有以下特征:

  • Write Once Read Many
  • 冷热分区
  • 不可变数据

Finding a needle in haystack Facebook’s photo storage 的目标是高 IOPS,但存储成本高。面对冷热分区的工作负载,Facebook 设计了暖存储系统 f4,专为第存储成本和高容错设计,填补 Facebook BLOB 存储系统的最后一块拼图。

[Paper Note] Skip Lists a Probabilistic Alternative to Balanced Trees

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

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

继续增大步长,在 b 的基础上,每隔 3 个节点,该节点同时指向它后面 3 个位置后的节点。这样,搜索只需要$N/3+2$步。
不断增大步长,每隔 i 个节点,该节点同时指向它后面 i 个位置后的节点。最终,搜索只需要$O(logN)$步。
这种设计虽然实现了$O(logN)$复制度的搜索,但插入删除却十分低效。为了维护“每隔 i 个节点,该节点同时指向它后面 i 个位置后的节点”的不变量,插入删除节点后都要修改所有后继的指针。这种情况下,相当于通过增大步长,用链表实现了有序数组($O(logN)$的搜索,$O(N)$的插入删除)。

【译】无锁算法导论

译者序

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 语义究竟是什么,并介绍五种相对简单的能够覆盖无锁原语大多数用例的模式。

使用 Yadm 管理点文件

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

点文件管理的痛点

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

0%