0%

引言

最近因为工作的关系接触 ElasticSearch,发现搜索引擎也是计算机应用的一个有意思的分支。于是通过 Freiburg 的 Information Retrieval 公开课开始系统地了解信息检索这个领域,感觉收获颇丰。周末一时兴起,上 Google Research 找到了 Google 的开山之作,近距离地感受一下 19800+ 引用量、造就如今 Google 万亿市值的这篇文章。

本文介绍会尽可能地忠于原文,但不是完全逐字逐句的翻译。

1. 简介

近年来,网络中的信息量和非专业的用户都在快速增长,为信息检索领域带来了新的挑战。从行为上看,人们更倾向于以门户网站,如 Yahoo,或搜索引擎为起点,利用网页间的链接来浏览所需信息。门户网站的索引来自于人工维护,聚合效果好、主观性高、维护成本高、改进速度慢,且通常不会覆盖小众话题。自动化的搜索引擎则相反,其它都满足,但聚合效果差,依赖于关键词匹配的检索方式返回的匹配项质量过低。一些广告商为了获取更多的流量,通过逆向工程来误导搜索引擎,使其结果靠前,进一步加剧问题的严重性。我们搭建了一个大型搜索引擎来当前系统的这些已知问题,它通过重度利用网页文本中的特殊结构来提供更高质量的检索结果。我们为这个系统取名为 Google,因为它是 googol (即 ) 的常用拼写,后者的含义恰好与构建大型搜索引擎的目标体量相契合

网络搜索引擎的扩张:1994 - 2000

为了跟上网络信息扩张的速度,搜索引擎技术也必须加速规模化。1994 年,World Wide Web Worm (WWWW),第一代网络搜索引擎 (web search engine) 之一,对 11 万网页或文件建立了索引;到了 1997 年末,行业领先的网络搜索引擎建立索引的数量已达到 200 万 (WebCrawler),甚至 1 亿 (Search Engine Watch)。可以预见这个数量在 2000 年将超过 10 亿。与此同时,网络上的搜索引擎处理的查询也在飞速增长。在 1994 年初,WWWW 大约每日需要处理 1500 次查询,到了 1997 年末,Altavista 已经声称自己每日处理的请求量达到 2 千万。同样可以预见,这个数量在 2000 年也将达到亿级。Google 的目标就是要提供相应规模、高质量的网络搜索服务。

Google: 与网络一同扩张

即便是搭建一个满足当前规模的网络搜索引擎也需要面对许多挑战,如:

  • 高性能的网页抓取技术保证原始数据全而新
  • 充足的存储空间用以存放索引和网页本身 (如果需要的话)
  • 索引系统必须能够高效地处理百 G 级别的数据
  • 查询必须能被快速处理,QPS 过千
阅读全文 »

I ❤ Logs 出版于 2014 年,是一本很短小的书,100 页不到,利用这周的零散时间就看完了。作者 Jay Kreps,是前 LinkedIn 的 Principal Staff Engineer,也是 LinkedIn 许多著名开源项目的负责人及联合作者,如 Kafka、Voldemort 等。他是现任 Confluent 的 CEO,主要工作在于围绕实时数据提供企业级服务支持。这本书算是 Jay Kreps 过去多年实践的思考结晶。

本文主要是对书中的一些看法、观点的个人化梳理,有兴趣可以阅读原著

日志即数据

在讨论日志之前,首先要明确日志的含义。这里的日志并非指我们常用的非结构化或半结构化的服务日志,而更接近数据库中常见的结构化的提交日志 (commit log/journal/WAL),这些日志通常是只往后追加数据,这里的序号暗含着逻辑时间,标识着连续日志产生的逻辑先后顺序:

a-structured-log

数据库中的日志

日志在数据库中常常被用来实现故障恢复、数据复制、最终一致性等。一个事务提交成功与否在日志提交成功时就可以确定,只要 WAL 落盘,便可告诉客户端提交成功,即便数据库发生故障,也能从 WAL 日志中恢复数据;日志 (如 BinLog) 的 pub/sub 机制可以用来在主节点与复制节点之间同步数据,通过同步的进度可以知道不同复制节点的同步进度,此外日志的逻辑顺序保证了主节点与复制节点之间数据的一致性。

分布式系统中的日志

数据库利用日志来解决的问题,也是所有分布式系统需要解决的根本问题,如刚才提到的故障恢复、数据同步、数据一致性等等,可以称之为以日志为中心 (log-centric) 的解决方案。更严谨地说:

如果两个相同的 (identical)、确定 (deterministic) 的进程以相同的状态启动,按相同的顺序获取相同的输入,它们将最终达到相同的状态。

阅读全文 »

Jaeger Walkthrough 系列文章之一,旨在深入理解 Jaeger 项目内部的实现细节。本文介绍的是 Jaeger 的 Go 客户端,jaeger-client-go

简介

jaeger-client-go 是 Jaeger 对 opentracing-go 标准接口的实现,主要解决的是两个问题:

  • 如何在进程内部管理调用链追踪信息 (tracer, span)
  • 如何在进程间传递调用链追踪信息 (span context, propagation)

但在调用链追踪实践中,jaeger-client-go 仅仅解决上述两个问题还不够,它还需要考虑的问题包括:

  • 如何将数据上报到存储中心
  • 如何对数据抽样,支持不同的抽样策略
  • 需要收集哪些统计指标

接下来,我们就着源码对这些问题一一分析。

进程内调用链追踪信息管理

Tracer

Tracer 是 opentracing.Tracer 的实现,它负责与应用程序沟通,接收应用程序的请求,协调 jaeger-client-go 中各个模块完成相应工作。

阅读全文 »

Alertmanager 是 Prometheus 提供的报警分发平台,它主要满足的是报警的路由、分组、抑制、去重等常见需求。

整体报警控制逻辑

Alertmanager 将报警路由组织成树状结构:

route-tree

每条报警信息进入 Alertmanager 后,都会被流转给根路由,然后根据每个路由的配置决定是否递归地继续往下传播。每条报警信息最终都会匹配到一棵路由子树,如下图所示:

route-tree-matched

这棵子树上的路由就是可能发出报警信息的路由。那么报警信息在单个路由内部是如何处理的?

routed

每个路由内部会有一组匹配器 (Matcher) 负责匹配报警信息,匹配成功则表示路由命中。进入路由内部后,会根据报警信息的一些特征将其分配到某个特定的组 (Group),每个组内拥有独立的通知 (Notify) 处理逻辑,如抑制、冷却、去重,最终满足一定条件后,路由会根据接收人 (Receiver) 配置,将报警信息通过通知媒介传递给相应的负责人。

项目架构

阅读全文 »

本文来自于 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" 究竟是什么程序。

A Lisp interpreter written in Lisp

这个 List interpreter 的核心代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
(define eval-expr
(lambda (expr env)
(pmatch expr
[,x (guard (symbol? x))
(env x)]
[(lambda (,x) ,body)
(lambda (arg)
(eval-expr body (lambda (y)
(if (eq? x y)
arg
(env y)))))]
[(,rator ,rand)
((eval-expr rator env)
(eval-expr rand env))])))

pmatch 中仅用短短 3 行代码,就实现了 List interpreter 核心流程,它是如何做到的?

pmatch

pmatch 是一个 pattern match 工具包,用于匹配输入的文本,如:

1
[(,rator ,rand)]
阅读全文 »

简介

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

背景

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

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

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

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

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

阅读全文 »

在进入文章之前,应该先介绍两位重量级作者:Andrew PavloMatthew 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 特性的新一代数据库系统。

相比于已经问世 40 多年的关系型数据库 (relational DBMS) ,我们不禁会问:"新兴的 NewSQL 究竟是一种市场营销还是确有其创新之处?" 如果 NewSQL 确实能够在多方面达到更高的性能,那么下一个问题就是:"它的性能是来自于硬件的升级还是其系统设计有着科学上的创新?"

要回答这两个问题,我们先讨论数据库系统的历史以及 NewSQL 的诞生,再讨论 NewSQL 在数据库系统各个重要设计方面的细节。

注:本文基本上会是原文的一个完整翻译,如果你愿意,大可直接点击文末链接翻看原文 :)

A Brief History of DBMSS

世界上第一个数据库系统,IBM IMS (Information Management System) 诞生于 1966 年,它被用于存储土星五号 (Saturn V) 和阿波罗 (Apollo) 空间探索项目所需的零件和供应商信息。IMS 的主要贡献在于展示了 "应用程序逻辑与数据操作逻辑应该分离" 的理念,应用程序开发者只需要关注数据的逻辑变化,而无需关心其具体实现。在 IMS 之后,出现了第一批关系型数据库,其主要代表就是 IBM 的 System R 系统以及加州大学的 INGRES,即 PostgreSQL 的前身。INGRES 迅速在其它大学的信息系统中流行起来,并于 70 年代末商业化。大约在相同的时期,Oracle 采用类似 System R 的设计,开发并发布其 DBMS 的第一个版本。在 80 年代初期又涌现了一批公司,它们也推出自己的商业化数据库产品,如 Sybase 和 Informix。在 System R 之后,IBM 在 1983 年发布了新的关系型数据库 DB2,后者复用了 System R 的部分代码,但二者至今未开源。

从 80 年代末到 90 年代初,面向对象的语言开始流行,这也催生了一批面向对象的 DBMS 诞生,以期磨平数据库模型与语言之间的隔阂。然而由于没有类似 SQL 一样的标准接口,这些面向对象的 DBMS 始终没有在市场上被广泛接受,不过它们的一些设计理念逐渐被融合进关系型数据库,许多流行的关系型数据库都增加了对 Object、XML 和 JSON 数据的支持。除此之外,面向文档 (document-oriented) 的 NoSQL 数据库也或多或少是面向对象的 DBMS 的延伸。

90 年代的一个大事件就是两个开源关系型数据库的发布,MySQL 和 PostgreSQL。MySQL 于 1995 年在瑞士诞生,主要基于 ISAM 的 mSQL 系统开发;PostgreSQL 于 1994 年启动,由两名伯克利的学生 fork Postgres 的源码二次开发,增加 SQL 查询语言的支持。

从 2000 年后,互联网应用如雨后春笋般出现,这些应用对各种资源的要求都远超传统的软件服务。互联网应用需要支持大量用户的并发访问,且对可用性要求极高,最好永远在线。在实践中,数据库开始成为互联网应用的瓶颈。许多厂商尝试纵向扩容,提高单机硬件性能,但这种方式换来的提升十分有限,表现出明显的边际收益递减。而且纵向扩容通常很不平滑,将数据从一台机器移动到另一台机器需要长时间下线服务,这对于互联网用户来说无法接受。为了解决这个问题,一些公司定制化开发中间件 (middleware),将数据分片到多个普通单机 DBMS 上:

阅读全文 »

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

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

备注:本文中,因为信息源使用的术语不同,Correctness 与 Safety 分别翻译成正确性和安全性,实际上二者在分布式锁话题的范畴中意思相同。

Efficiency & Correctness

如果想让单机/实例上的多个线程去执行同一组任务,为了避免任务被重复执行,使用本地环境提供的 Lock 原语即可实现;但如果想让单机/实例上,或多机/实例上的多个进程去抢同一组任务,就需要分布式锁。总体来说,对分布式锁的要求可以从两个角度来考虑:

  • 效率 (Efficiency):为了避免一个任务被执行多次,每个执行方在任务启动时先抢锁,在绝大多数情况下能避免重复工作。即便在极其偶然的情况下,分布式锁服务故障导致同一时刻有两个执行方抢到锁,使得某个任务被执行两次,总体看来依然无伤大雅。
  • 正确性 (Correctness):多个任务执行方仅能有一方成功获取锁,进而执行任务,否则系统的状态会被破坏。比如任务执行两次可能破坏文件结构、丢失数据、产生不一致数据或其它不可逆的问题。

以效率和正确性为横轴和纵轴,得到一个直角坐标系,那么任何一个 (分布式) 锁解决方案就可以认为是这个坐标系中的一个点:

Solutions

在进入分布式锁解决方案之前,必须要明确:分布式锁只是某个特定业务需求解决方案的一部分,业务功能的真正实现是业务服务分布式锁存储服务以及其它有关各方共同努力的结果。

阅读全文 »

论文引用量: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

阅读全文 »