摘要

Linear Hashing 和 Spiral Storage 是两种动态哈希算法。这两种算法最初都是为了优化外部存储 (secondary/external storage) 数据访问而设计的。本文将这两种算法引入到内存中，即键值数据可以一次性读入内存的场景，对比、分析二者之间，以及与其它动态哈希算法的性能。实验结果表明：Linear Hashing 的性能上要优于 Spiral Storage，实现难度上要小于 Spiral Storage。其它纳入对比范围的动态哈希算法包括 Unbalanced Binary Tree 以及支持周期性 rehashing 版本的 Double Hashing。Linear Hashing 的查询时间与 Double Hashing 相当，同时远远优于 Unbalanced Binary Tree，即使在 tree 很小的场景上也如此；在载入键值数据的表现上，三者相当。总体而言，Linear Hashing 是一个简单、高效的动态哈希算法，非常适用于键空间未知的场景。

简介

许多为外部文件存储而设计的动态哈希算法在过去的若干年中被提出，这些算法允许外部文件根据内部存储的纪录数量而优雅地扩大和缩小。在外部文件存储场景中，外部存储比内存读写慢很多，它的特点总结如下：

• 按块读写数据，如 4096 字节为 1 块
• 倾向于读写连续块
• 倾向于批量读写
• 在每一层都设有缓存来优化性能
• 根据磁盘中数据块的读写次数来衡量程序的性能

Linear Hashing 和 Spiral Storage 在上述场景中都已被验证有效。本文将介绍如何将二者引入到 Internal Hash Table 场景中，在数学上分析其预期性能，并通过实验验证预期。从实验结论上看，两种方法对于 Internal Hash Table 、键 (key) 空间未知的场景同样有效。其中 Linear Hashing 更快且更容易实现。

所有 Hashing 技术都有一个特点：当负载提高时，基本操作的复杂度，如插入、查询、删除，也将提高。如果希望 Hash Table 的性能维持在一个可接受的下限之上，我们必须通过某种方式为其分配新的空间。传统的方案是创建一个新的、更大的哈希表，然后将所有数据重新哈希到新的哈希表上。动态哈希算法的不同之处在于，它允许哈希表逐渐扩大，每次增加一个桶。当新桶加入到寻址空间时，只需要重新哈希原来的一个桶即可，而不需要将所有数据全部重新哈希。

Linear Hashing

通常在 Hash 算法中需要一个 Hash Function，将输入参数转化成一个整数：

Abstract

缓存置换算法 (Cache Eviction Algorithm) 在操作系统、数据库以及其它系统中被广泛用于缓存置换模块，当缓存空间不足时，它利用局部性原理 (Principle of Locality) 预测未来数据的使用模式，将最不可能被访问的数据清出从而提高缓存命中率。目前已经存在的缓存置换算法包括 MRU (Most Recently Used)、MFU (Most Frequently Used)、LRU (Least Recently Used) 以及 LFU (Least Frequently Used) 等。每个算法都有其各自的适用场景。到目前为止，应用范围最广的是 LRU，主要原因在于 LRU 贴近大多数应用的实际负载模式 (workloads)，同时 LRU 拥有 时间复杂度的成熟实现方案。与 LRU 类似，LFU 同样与大多数应用的负载模式相近，但目前 LFU 最佳实现方案的时间复杂度是 ，不如 LRU。本文，我们提出一种同样达到 时间复杂度的 LFU 实现方案，它支持的操作包括插入、访问以及删除。

Introduction

本文将按顺序介绍：

• LFU 的典型使用场景
• LFU 的接口说明
• 目前 LFU 的最佳实现方案
• 时间复杂度为 的 LFU 实现方案

Uses of LFU

LFU 的一个典型使用场景就是 HTTP 的缓存代理应用 (caching network proxy application)。它位于网络服务与用户之间，如下图所示：

它通过将大多数用户可能请求的静态文件放入缓存中，来优化网络利用率，提高服务的响应速度。这种缓存代理需要满足：

1. 在有限的存储资源中缓存尽可能多的、更可能被重复使用的数据
2. 实现的成本应该尽可能小，保证代理在高负荷下也能正常工作

简介

本文是分布式系统理论的开山鼻祖、2013 年图灵奖获得者 Lamport 的成名作，也是分布式计算领域杰出论文最佳影响力奖 Dijkstra Prize 的第一篇论文，高达 11692 的引用量（截至 2019/12/08）足以证明其广泛的影响力：

本文主要讨论 3 个话题：

• 分布式系统中的事件偏序
• 利用逻辑时钟实现事件偏序
• 利用逻辑时钟实现事件全序

事件顺序

生活中的事件顺序

生活中，当两个事件 A 和 B 发生时，我们可以利用其发生的时刻来确定它们的先后关系，如：

A：2019-12-08T00:00:00+00:00

B：2019-12-07T08:00:00+00:00

早在 2008 年，Google 就已开始分布式调用链追踪的工作，经过两年的打磨后，Dapper 系统问世，并通过这篇文章将其设计公之于众。遗憾的是，Dapper 并不是开源项目，但它的设计理念依然深刻影响到后来的 Jaeger、Zipkin 等开源分布式追踪项目，以及相关的标准 Opentracing、OpenTelemetry。

本文不是原文的精准翻译，而是一次重述和简述，旨在记录分布式调用链追踪要解决的核心问题和潜在解决方案。

Abstract

在大型微服务架构中，服务监控和实时分析需要大量的时序数据。存储这些时序数据最高效的方案就是使用时序数据库 (TSDB)。设计时序数据库的重要挑战之一便是在效率、扩展性和可靠性中找到平衡。这篇论文介绍的是 Facebook 内部孵化的内存时序数据库，Gorilla。Facebook 团队发现：

1. 监控系统的用户主要关注的是数据的聚合分析，而不是单个数据点
2. 对于线上问题的根源分析来说，最近的数据比过去的数据更有价值

Gorilla 以可能抛弃少量数据为代价，在读写高可用方面做了优化。为了改进查询效率，开发团队使用了激进的压缩技术：

1. delta-of-delta timestamps
2. XOR's floating point values

相比基于 HBase 的方案，Gorilla 将内存消耗缩小 10 倍，并使得数据得以存放在内存中，进而将查询时延减少 73 倍，查询吞吐量提高了 14 倍。 这样的性能改进也解锁了更多的监控、调试工具，如相关性分析、密集可视化。Gorilla 甚至能够优雅的解决单点到整个可用区域故障的问题。

Introduction

以下是 FB 内部对时序数据库的要求：

Write Dominate

对时序数据库的首要限制就是必须一直能够写入数据，即写数据的高可用。因为 FB 内部的服务集群每秒将产生 1 千万个采样数据点。相较之下，读数据比写数据要求通常要低好几个数量级，因为数据的消费者是一些运维、开发使用的控制面板以及自动化报警系统，它们的请求频率低且通常只关注部分时序数据。由于用户关注的往往是整组时序数据的聚合结果，而不是单个数据点，因此传统数据库中的 ACID 保证也并不是时序数据库的核心要求，即便在极端情况下，丢弃少量数据也不会影响核心用途。