本文来自于 2017 年 PWL NYC Meetup，作者的简介如下：

William E. Byrd (@webyrd) is a Research Assistant Professor in the School of Computing at the University of Utah. He is co-author of 'The Reasoned Schemer', and is co-designer of the miniKanren relational programming language. He loves StarCraft (BW & SC2). Ask him about the scanning tunneling microscope (STM) he is building.

先假设你已经对 Scheme (Lisp 的一门方言) 的基本语法有一些了解。我们直奔主题，来看这个 "The Most Beautiful Program Ever Written" 究竟是什么程序。

简介

本文介绍伴鱼内部服务报警平台中匹配器模块的演进，及其利用 Lex 和 Yacc 同类工具构建 DSL 编译器的过程。是我和团队成员在伴鱼的质量工程小组的一小部分工作。

背景

报警平台是伴鱼内部各端、应用、基础设施等服务异常状态信息的集散中心。整体流程如下图所示：

信息源将信息投递给报警平台，后者将这些信息最终通过邮件、即时消息、电话呼叫的形式路由给理应关心它的人。总体而言，路由的需求可以分为以下几种：

• 路由给服务的负责人及其团队
• 路由给服务依赖方人员及其团队
• 路由给所有值班人员所在的即时消息群

为了满足这样的需求，报警平台采用树状结构组织路由信息，如下图所示：

每个节点是一个路由节点，节点上可以挂载不同的规则，如抑制规则、通知规则；也可以存放不同的配置信息，如触发报警的阈值，以及相关负责人及其团队的联系方式。

在进入文章之前，应该先介绍两位重量级作者：Andrew Pavlo 和 Matthew Aslett。Andrew 在 CMU 的计算机科学学院任教，主攻方向包括内存数据库、自动驾驶系统架构、事务处理系统和海量数据分析，他是 CMU Database Group 的核心成员，在 CMU 开设的两门课程 Database Systems (15-445/645) 和 Advanced Database System (15-721) 全是干货；Matthew 是 451 research: Data, AI & Analytics channel 的 VP，他在 2011 年的一篇 论文 中第一次用 NewSQL 指代提供类似 NoSQL 高吞吐、高可用支持，同时仍然保持 ACID 特性的新一代数据库系统。

提到分布式锁，很多人也许会脱口而出 "redis"，可见利用 redis 实现分布式锁已被认为是最佳实践。这两天有个同事问我一个问题：“如果某个服务拿着分布式锁的时候，redis 实例挂了怎么办？重启以后锁丢了怎么办？利用主从可以吗？加 fsync 可以吗？”

因此我决定深究这个话题。

论文引用量：744 (截止至 2020-03-15)

Kafka 是开发者耳熟能详的开源项目，它已经成为近年来互联网公司必不可少的基础组件。Kafka 得名于作家 Franz Kafka，大概是因为二者都比较擅长写日志 : )。它孵化于 LinkedIn 内部，在 2011 年被捐赠给 Apache 基金会，2012 年末正式从 Apache Incubator 中毕业。本文于 2011 年发表于 NetDB workshop，如今原文的三位作者，Jay Kreps、Neha Narkhede 以及 Jun Rao 一同离开 LinkedIn，创立 Confluent.io，提供基于 Kafka 的企业级 Event Streaming Platform 服务。

除了翻译论文原文的核心内容之外，本文也会补充一些论文发表当时还未问世的话题，如 replication，exactly-once delivery 等。

Introduction

在规模较大的互联网公司中，每天都会产生大量的日志数据，如：

• 用户事件：登录、访问、点击、分享、评论、搜索
• 性能指标：时延、错误、QPS
• 机器指标：CPU、Memory、Network、Disk Utilication

这些日志数据常常被用于离线分析，帮助公司了解用户、产品，帮助开发者了解系统、服务。在初期，每当 LinkedIn 内部有服务需要使用这些日志数据时，研发人员就需要写新的数据传输脚本或在线传输逻辑，久而久之，内部服务的拓扑图就出现了类似完全图的形状：

这种拓扑图对分布式系统很不友好，不仅可能造成网络资源浪费，维护成本也极高。有 DRY 精神的工程师肯定无法忍受这样的架构，这时就需要有一个服务能将日志数据的消费和生产隔离：

本文介绍 FB 基于 memcached 构建统一缓存层的最佳实践。全文递进式地讲述 单集群 (Single Front-end Cluster)、多集群 (Multiple Front-end Clusters)、多区域 (Multiple Regions) 环境下遇到的问题和相应的解决方案。尽管整个解决方案以 memcached 为基本单元，但我们可以任意地将 memcached 替换成 redis、boltDB、levelDB 等其它服务作为缓存单元。

在下文中，需要注意两个词语的区别：

• memcached：指 memcached 源码或运行时，即单机版
• memcache：指基于 memcached 构建的分布式缓存系统，即分布式版

Background

与大部分互联网公司的读写流量特点类似，FB 的整体业务呈现出明显读多写少的特点，其读请求量比写请求量高出若 2 个数量级 (数据来自于 slides)，因此增加缓存层可以显著提高业务稳定性，保护 DB。

Pre-memcache

在使用缓存层之前，FB 的 Web Server 直接访问数据库，通过 数据分片 和 一主多从 的方式来扛住读写流量：

但随着用户数数量飙升，单纯靠数据库来抗压成本高，效率低。

Design Requirements

注：如果只想了解 Prometheus TSDB 的存储层现状，可以直接移步Ganesh Vernekar 的博客，他写了 7 篇系列文章介绍这个主题。

Prometheus 无疑是时下最流行的监控平台，它负责定期从不同的采集目标拉取样本数据，然后持久化到内建的时序数据库中，向外部提供便捷的查询接口。本文主要探讨的是 Prometheus 存储层的演进过程，整理自 Prometheus 团队在历届 PromConf 上的分享以及相应的文档。

Background

数据库中的各种奇技淫巧，实际上都来自于内存与磁盘的读写模式和性能区别。

总结如下表：

当数据库中的数据无法一次性装入内存时，数据的读写就可能需要从内存穿透到磁盘。在 OLTP 场景下，每次事务写入和读取的数据数量都不大。但因为磁盘是块存储设备，无论是否需要，写入和读取都以块 (block) 为单位：

这就导致许多不必要的数据传输。除此之外，在磁盘中连续读取或写入相邻的数据块比随机的数据块效率高。因此数据库在组织数据、索引时，为了减少不必要的 I/O，同时提高 I/O 的效率，就需要尽可能做到：

• 让具有局部性的数据、索引在磁盘上相邻存储
• 让具有局部性的数据、索引批量写入到磁盘中

从而达到两个目的：

在计算机系统设计实践中，我们常常会遇到下图所示架构：

为了解决单个存储器读吞吐无法满足要求的问题，常常需要在存储器上面增加一个或多个缓存。但由于相同的数据被复制到一个或多个地方，就容易引发数据一致性问题。不一致的数据可能出现在同级 Cache 之间 (Cache Coherence) 和上下级 Cache 之间。解决这些数据一致性问题的方案可以统称为 Cache Policies。从本质上看，所有 Cache Policies 的设计目的都可以概括为：在增加一级缓存之后，系统看起来和没加缓存的行为一致，但得益于局部性原理，系统的读吞吐量提高、时延减少。

本文将探讨四个场景：

1. Cache Policy In Single-core Processor
2. Cache Coherence in Multi-core Processor
3. Cache Policy in Cache/DB Architecture
4. Cache Policy in Distributed DBMS Architecture

Cache Policy in Single-core Processor

在单核 CPU 中，只有一套 Cache，因此只要确保写入 Cache 中的数据也写入到 Memory 即可。

补充一些概念定义：数据在 Cache 与 Memory 之间移动的最小单位通常在 32 - 128 字节之间，Memory 中对应的最小单位数据称为 Cache Block，Cache 中与单个 Cache Block 对应的存储空间称为 Cache Line，在 Cache 中除了存储 Block 数据，还需要存储 Block 对应的唯一标识 (Tag)，以及一个用于标记 Cache Line 是否有数据的有效位 。完整对应关系如下图所示：

论文作者的贡献主要包含两部分：Consistent Hashing 和 Random Trees。Consistent Hashing 主要用于解决分布式哈希表 (Distributed Hash Table, DHT) 的桶增减带来的重新哈希问题；Random Trees 主要用于分布式缓存中的热点问题，它利用了 Consistent Hashing。下文主要关注 Consistent Hashing。

Contribution

在分布式环境下，单台机器的负载有限，我们需要将请求散列到不同的机器上，利用更多的机器实现服务的横向扩容。这时候就需要 Hash Function，好的 Hash Function 能够帮我们均匀地分布到不同的机器上。但传统的 Hash Function 通常是静态的，桶的数量固定。在多台机器组成的服务中，每台机器就是一个桶，但机器在运行的过程中很可能出现崩溃，在请求数量波动较大时，需要动态地增减机器。如果每次桶的数量发生变化时都需要重新散列所有请求，可能造成多方面影响：

• 来自于同一个用户的请求在桶发生变化时将被打到不同的节点，可能导致数据不一致 (考虑 monotonic consistency)
• 所有的 Client 都需要知道当前最新的 Hash Function 配置，在网络中传播这个配置需要时间

Consistent Hashing 的提出就是希望能够缓解/解决这个问题，使得每次桶数量发生变化时不需要重新散列桶内的所有元素，而是将受影响的数量控制在很小的范围内。

Definitions

作者从四个方面讨论了好的 Consistent Hash Function 应该满足的性质：

• Balance：元素应当尽量均匀地分布到不同的桶内 (with high probability)
• Monotonicity：当增加新的桶时，元素只可能从旧桶移动到新桶，而不可能从旧桶移动到其它旧桶
• Spread：在不同的用户眼里，相同的元素可能被散列到不同的桶中，我们称之为不同的观点。Spread 要求总的观点数量必须有一个上限。好的 Consistent Hash Function 应当让 spread 尽量小。
• Load：类似 spread，Load 性质是针对不同的用户，但它规定的是单个桶中不同元素数量的上限，即每个桶中的，至少有一个用户认为其中含有的，元素数量存在上限。好的 Consitent Hash Function 应当让这个上限尽量小。

Construction

作者提出一种构建好的 Consistent Hash Function 的方法：