0%

Prometheus 是当下最流行的监控平台之一,它的主要职责是从各个目标节点中采集监控数据,后持久化到本地的时序数据库中,并向外部提供便捷的查询接口。本文尝试探讨 Prometheus 存储层的演进过程,信息源主要来自于 Prometheus 团队在历届 PromConf 上的分享。

时序数据库是 Promtheus 监控平台的一部分,在了解其存储层的演化过程之前,我们需要先了解时序数据库及其要解决的根本问题。

TSDB

时序数据库 (Time Series Database, TSDB) 是数据库大家庭中的一员,专门存储随时间变化的数据,如股票价格、传感器数据、机器状态监控等等。时序 (Time Series) 指的是某个变量随时间变化的所有历史,而样本 (Sample) 指的是历史中该变量的瞬时值:

每个样本由时序标识时间戳数值 3 部分构成,其所属的时序就由一系列样本构成。由于时间是连续的,我们不可能、也没有必要记录时序在每个时刻的数值,因此采样间隔 (Interval) 也是时序的重要组成部分。采样间隔越小、样本总量越大、捕获细节越多;采样间隔越大、样本总量越小、遗漏细节越多。以服务器机器监控为例,通常采样间隔为 15 秒。

数据的高效查询离不开索引,对于时序数据而言,唯一的、天然的索引就是时间 (戳)。因此通常时序数据库的存储层相比于关系型数据库要简单得多。仔细思考,你可能会发现时序数据在某种程度上就是键值数据的一个子集,因此键值数据库天然地可以作为时序数据的载体。通常一个时序数据库能容纳百万量级以上的时序数据,要从其中搜索到其中少量的几个时序也非易事,因此对时序本身建立高效的索引也很重要。

The Fundamental Problem of TSDBs

TSDB 要解决的基本问题,可以概括为下图:

阅读全文 »

本文转自我个人的 gitbook

Background

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

总结如下表:

Memory Disk
byte-addressable block-addressable
fast slow
expensive cheap

当数据库中的数据无法一次性装入内存时,数据的读写就可能需要从内存穿透到磁盘。在 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 的方法:

阅读全文 »

摘要

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。

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

Why & Design Goals

云原生环境中,一次请求的处理可能途径多个服务的任意实例,彻底理解系统就需要理解各服务内部的逻辑,理清这些服务之间的关系,甚至有时候还需要了解服务所在物理机的当时状态。系统出现异常时,如果其行为无法被追踪、被理解,就无法为解决异常快速提供线索。

通常这些异常会被监控捕捉,如时延异常、错误日志、程序崩溃,在紧急处理之后,就需要调查案发现场,彻底解决问题。这时候就需要了解每个请求在整个微服务集群内部的行踪。

这就向分布式追踪系统提出了两点要求:

  • 处处部署 (ubiquitous deployment)
  • 持续监控 (continuous monitoring)

如果部署不完全或者监控有间断,就可能有一小部分历史无法被追踪到,从而影响到问题定位的准确度,使得追踪效果大打折扣。

据此,我们提出追踪系统的 3 个主要设计目标:

  1. 低成本 (Low overhead):对服务的性能影响应该能够忽略不计
  2. 对应用透明 (Application-level transparency):应用开发者对追踪系统无感知
  3. 扩展性好 (Scalability):支持部署到所有服务的所有实例上
阅读全文 »

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 保证也并不是时序数据库的核心要求,即便在极端情况下,丢弃少量数据也不会影响核心用途。

阅读全文 »