Google Search 淘气三千问:Q1~Q5

前言

两个多月前(2024年5月27日),Google 的一份名为 GoogleApi.ContentWarehouse 的 API 文档受到 SEO 圈的关注,由于这份文档的内容和 Google Search 副总裁 Pandu Nayak 在 2023 年美国司法部(DOJ)起诉 Google 的案件中的证词和 Google 的一些专利高度一致,因此其真实性被广泛认可。

后续有媒体称 Google 发言人回应了文档泄露的问题(没有承认、也没有否认):

A Google spokesperson sent us the following statement:

“We would caution against making inaccurate assumptions about Search based on out-of-context, outdated, or incomplete information. We’ve shared extensive information about how Search works and the types of factors that our systems weigh, while also working to protect the integrity of our results from manipulation.”

此前大部分讨论仅限于猜测 API 文档中的各种信号在排名算法中的作用,以及对谷歌是否在排名算法上欺骗了大家。很少人意识到,这篇 2500 页的文档可以作为以往 Google 公开论文的补充,一本叫做《如何构建一个世界级(成功的)搜索引擎》的武功秘籍撕下来的几页。

而偏偏我对这本武功秘籍非常好奇,试图在这几页上再加一些批注,就有了 《Google Search 淘气三千问》这个系列。这个系列会有几篇文章,我不知道,主要看我能想到多少问题。

为什么叫“淘气三千问”这个名字?可以把它看成是一种传承吧,懂的都懂,不懂的也不影响阅读。

为避免误导读者,这个系列所有的回答里,来自公开信息的我都会标注来源,没有标注来源的,你可以认为是 inaccurate assumptions about Search based on out-of-context, outdated, or incomplete information。当未来有了更新的信息,我有可能回到博客来更新这些 assumptions(公众号文章无法更新)。

如果你有新信息可以给我,或者纠正文中的错误,欢迎评论或者到公众号“边际效应”私信,谢谢!

Q1: Google 的索引分了几层(Tier)?依据什么?

Google 在 2012 年的论文《Indexing the World Wide Web: The Journey So Far 》中提到产业实践中大规模索引都是会分成多个桶(tier),一般按照更新频率来分:

The way we have described search indices so far makes a huge assumption: there will be a single unified index of the entire web. If this assumption was to be held, every single time we re-crawled and re-indexed a small set of fast-changing pages, we would have to re-compress every posting list for the web and push out a new web index. Re-compressing the entire index is not only time consuming, it is downright wasteful. Why can we not have multiple indices -- bucketed by rate of refreshing? We can and that is what is standard industry practice. Three commonly used buckets are:

1. The large, rarely-refreshing pages index
2. The small, ever-refreshing pages index
3. The dynamic real-time/news pages index

...

Another feature that can be built into such a multi-tiered index structure is a waterfall approach. Pages discovered in one tier can be passed down to the next tier over time.

在 Google ContentWarehouse API 里有这样一段 :

GoogleApi.ContentWarehouse.V1.Model.PerDocData

* scaledSelectionTierRank (type: integer(), default: nil) - Selection tier rank is a language normalized score ranging from 0-32767 over the serving tier (Base, Zeppelins, Landfills) for this document. This is converted back to fractional position within the index tier by scaled_selection_tier_rank/32767.

可以看到,Google 仍然是把索引分了 3 层,现在我们有了它们的名字,分别是:Base(基础)、Zeppelins(飞艇) 和 Landfills(垃圾填埋场)。在每一层之内,scaledSelectionTierRank 这一归一化分数决定了它所在位置的分位数。分位数最大值是 32767,猜测也许是 Google 在索引存储里只给它留了 15 bits(2^15=32768)。

但从索引分层的名字来看,这三层并不(全)是按照时效性分的,至少第三层,看着是按照文档质量分的。因为你把文档放到“垃圾填埋场”中,大概率因为它的质量较差而不是不再更新。那么 scaledSelectionTierRank 也许就代表了层内的文档质量等级。

网友 avanua 对这三层的命名提供了一个解读,我觉得非常合理,因为我一直困惑第二层为什么叫做 Zeppelins:

我觉得 Tier 命名和质量无关,可能只是用来描绘更新频率:
​Zeppelins 在气流中起起伏伏
Base
​Landfills 几乎不会再翻动,上下层叠关系是固定的

Q2: Tier 内的 scaledSelectionTierRank 有什么作用?

在 《Indexing the World Wide Web: The Journey So Far》中提到,在倒排拉链中最好按照文档实际的影响力对文档列表进行排序。如果仅仅是这样,那么只需要知道文档 0 比文档 10000 更重要即可,那么额外记录一个打分的目的,其实是可以让这个分数参与排序过程。文档在某个 Query 下的得分,是文档影响力得分乘以文档在 Query-term 下的权重。

Since it made sense to order the posting lists by decreasing term frequency, it makes even more sense to order them by their actual impact. Then all that remains is to multiply each posting value by the respective query term weight, and then rank the documents. Storing pre-computed floating-point document scores is not a good idea, however, since they cannot be compressed as well as integers. Also, unlike repeated frequencies, we can no longer cluster exact scores together. In order to retain compression, the impact scores are quantized instead, storing one of a small number of distinct values in the index.

从上文中有理由认为,scaledSelectionTierRank 就是文中提到的量化以后的文档影响力得分,量化就是将其归一化到 32768 个分档之中。

Q3: Google 搜索系统主要分成几个部分?

通过 API 和其它公开文档,目前我能够分析出来的搜索系统组成部分有以下这些。随着阅读的深入,可能还会有新的部分加进来。

爬虫系统:Trawler

在 Google ContentWarehouse API 中有一系列 API 以 Trawler 为前缀,并且从上下文中看出来 Trawler 是一个实体系统并且有一个研发团队。

GoogleApi.ContentWarehouse.V1.Model.TrawlerCrawlTimes
GoogleApi.ContentWarehouse.V1.Model.TrawlerFetchReplyData
GoogleApi.ContentWarehouse.V1.Model.TrawlerHostBucketData

* TotalCapacityQps (type: number(), default: nil) - The following four fields attempt to make things simpler for clients to estimate available capacity. They are not populated yet as of 2013/08/21. Even after they are populated, they may change. So talk to trawler-dev@ before you use the fields. Total qps for this hostid

去重系统:WebMirror

在 Google ContentWarehouse API 里有这样一段:

GoogleApi.ContentWarehouse.V1.Model.CompositeDocAlternateName

Alternate names are some urls that we would like to associate with documents in addition to canonicals. Sometimes we may want to serve these alternatenames instead of canonicals. Alternames in CompositeDoc should come from WebMirror pipeline.

每个 CompositeDoc 都有一些替代的 URL,这些 URL 来自 WebMirror 流水线,那么 WebMirror 应该是识别重复文档的一套系统。

离线索引构建系统:Segindexer + Alexandria

在 Google ContentWarehouse API 里有这样一段:

GoogleApi.ContentWarehouse.V1.Model.AnchorsAnchor

* sourceType (type: integer(), default: nil) - ... In the docjoins built by the indexing pipeline (Alexandria), ...

所以 Alexandria 应该是建库系统。而 Segindexer 和 Alexandria 曾经并行出现过:

GoogleApi.ContentWarehouse.V1.Model.ClassifierPornClassifierData

* imageBasedDetectionDone (type: boolean(), default: nil) - Records whether the image linker is run already. This is only used for Alexandria but NOT for Segindexer.

考虑到关键的表示原始文档内容的 compositedoc.proto 在 Segindexer 目录下:

GoogleApi.ContentWarehouse.V1.Model.NlpSaftDocument

* bylineDate (type: String.t, default: nil) - Document's byline date, if available: this is the date that will be shown in the snippets in web search results. It is stored as the number of seconds since epoch. See segindexer/compositedoc.proto

从名字和上述信息有理由怀疑 Segindexer 是在 Alexandria 之前,决定了索引分层,或者分 vertical 的一个分类模块。

在线索引服务系统:Mustang 和 TeraGoogle

在 《Indexing the World Wide Web: The Journey So Far》中我们知道,TeraGoogle 是 Google 在 2005 年实现的一套 large disk-based index 服务系统。而在 Google ContentWarehouse API 里有这样一段:

GoogleApi.ContentWarehouse.V1.Model.CompressedQualitySignals

A message containing per doc signals that are compressed and included in Mustang and TeraGoogle.

这里将 Mustang 和 TeraGoogle 并列,有理由认为 Mustang 是 2005 年之后 Google 开发的一套替代或者部分替代 TeraGoogle 的在线索引服务系统。

实时索引服务系统:Hivemind(muppet)

Realtime Boost 这篇文档中有一张图,揭示了一个新网页进入索引的过程,其中实时索引的系统叫做 Hivemind。但 Hivemind 应该是个集群名,实际的索引系统方案可能是叫做 muppet。因为在 RealtimeBoost Events - DesignDoc 这篇文档中也提到了一个用 muppet 支持的系统,叫做 ModelT,这是一个索引实时事件的索引系统。

实时索引的建库系统可能与非实时索引不同,叫做 Union。

查询汇聚系统:SuperRoot

在 Google ContentWarehouse API 中多次出现 SuperRoot 这一模块,而在 Jeff Dean 2009 年 WSDM 的 《Challenges in Building Large-Scale Information Retrieval Systems》 分享第 64 页,SuperRoot 被描述为聚合 Web、Images、Local、News、Video、Blogs 和 Books 所有检索子系统的汇聚模块,这个定位也许没有变。

Query 改写模块:QRewrite

RealtimeBoost Events - DesignDoc 这篇文档中说:

Currently in production RealtimeBoostServlet runs in QRewrite detects spikes on news documents published that match the SQuery (including syns). It does so by issuing one or two RPCs to Realtime-Hivemind.

The RealtimeBoostResponse containing the Spike is sent down to Superroot in the QRewrite response and it is currently used by a few Search features (such as TopStories) to trigger faster and rank fresher documents for queries that are spiking for a given news event.

所以 QRewrite 是会被 SuperRoot 调用的一个 Query 改写模块,它会将用户实际发起的搜索 Query 改写成 SQuery,S 可能是代表 Superroot。而到真正发起检索时,会进一步转成检索 Query,比如发给 muppet 的 Query 叫做 MQuery。

摘要模块:SnippetBrain

在 Google ContentWarehouse API 里有这样一段:

GoogleApi.ContentWarehouse.V1.Model.MustangReposWwwSnippetsSnippetsRanklabFeatures

* displaySnippet (type: GoogleApi.ContentWarehouse.V1.Model.QualityPreviewRanklabSnippet.t, default: nil) - Snippet features for the final chosen snippet. This field is firstly populated by Muppet, and then overwriten by Superroot if SnippetBrain is triggered.
  • 看起来 SnippetBrain 是一个可选的摘要生成模块。

入口服务:GWS

Google Web Server,这个大家都知道,还有 Wikipedia 词条

Q4: TeraGoogle 是怎样一套系统?

根据论文《Indexing the World Wide Web: The Journey So Far》和专利《US7536408B2: Phrase-based indexing in an information retrieval system》,TeraGoogle 应该有以下几个属性:

  • Disk-based Index:索引存储在磁盘上,在需要的时候读入到内存中,而且往往不需要全部读入,针对重要的文档有一些优化;
  • Phrase-based Indexing:构建索引的时候不仅仅有 term 索引,还会建设多 term 的短语索引,这样索引库里会有更多的倒排链;
  • Document-Partitioned Index:将索引分 Shard 的时候,按照文档进行分片,即同一批文档的所有拉链放在同一个 Shard 上,这样每个 Shard 上有所有的拉链,查询在一个节点内即可完成。在论文中只对比了 Document-Partitioned 和 Term-Partitioned 二者的差异,在 Jeff Dean 2009 年 WSDM 的 《Challenges in Building Large-Scale Information Retrieval Systems》 分享第 17 页确认了 Google 的选择。

Q5: Google 的文档是什么概念?

从 Google ContentWarehouse API 里:

GoogleApi.ContentWarehouse.V1.Model.CompositeDoc
Protocol record used for collecting together all information about a document. 

可以看到 CompositeDoc 是在系统里非常重要的概念,它定义了一个文档的所有信息。在它的所有字段中我们发现,url 又是一个可选的字段,这也就是说,文档并不一定需要是一个网页。像 localinfo,看起来就像是一个 POI 信息。也就是说在 Google 的系统里,不一定只有网页索引,可能每个 POI 点、图片、商品也是一种文档,所以它使用 CompositeDoc (复合文档) 而不是 WebPage 作为整个系统里对文档的刻画。

ABTest 平台设计 - 流量分布问题

通过前三篇文章,大家可以了解到一个基本的 ABTest 平台架构建设的要点,看起来构建起一个生产环境可用的 ABTest 平台难度不大。但如果想把这个平台做得更强大,还有很多细节地方要注意。下面举两个常见的细节问题。

跨层分桶不完全正交

理论上来讲,如果每层分桶都是采取的独立不相关的 hash 算法,那么层和层之间的流量应该是完全正交且服从均匀分布的。举个例子:如果每层分 10 个桶,那么第二层的 1 号桶内,应该有第一层每个桶里的 1/10 的用户。

但从实际上来讲,很多情况下我们使用的 hash 算法没有那么地“强”,会导致分桶没那么地随机和均匀。比如几年前非常流行的 MurmurHash,也被 SipHash 的作者找到了攻击的方法,他们更推荐使用更强的 SipHash / HighwayHash

还有就是均匀分布仅仅是统计意义上的期望,而不是实际的效果。比如我们有 1-10 十个数,用 hash 算法一定能保证把它们分到 10 个桶里,每个桶里 1 个数吗?

只不过大多时候,在统计意义上能保证基本的均匀,对大部分产品来说也够用了。

对于一些强迫症公司,或者用户数还没有达到统计意义上可分又开始早早做 ABTest 的公司,或者从数据观察的确存在较大的实验间干涉的公司,可能会做这样的一个事,人工构造层间正交分桶

具体做法是这样的:先用 hash 算法(或其它抽样算法)将用户分成桶数的平方个最小流量单元,然后再选取这些流量单元组成每个分层。比如要构造 2 层,每层 3 个分桶的用户分层,先将用户分为 3*3 个流量单元,那么两层就可以这样构造:

Layer 1: [1, 2, 3] [4, 5, 6] [7, 8, 9]
Layer 2: [1, 4, 7] [2, 5, 8] [3, 6, 9]

可以看到第二层的每一个桶,都包含第一层里所有桶的 1/3 用户。通过精巧地构造来实现层间的正交分桶,可以有效地降低层间实验互相干涉的情况。

发版造成指标波动

当实验本身受到 APP 版本一定影响的时候,AB 分组可能会由于升级节奏不同,导致 AB 指标波动完全不可比。

举一个例子:如果新版本使用时长会上升 10%,正常情况下实验分组 A 比分组 B 使用时长上升 3%。那么如果分组 A 用户升级新版本占比 30%,分组 B 用户升级新版本占比 70%,结果会是怎样呢?

分组 A:70*1.03 + 30*1.1*1.03 = 106.09
分组 B:30 + 70*1.1 = 107

分组 A 反而比分组 B 的数据更差!当然,这里为了效果,举的例子比较极端。实际的情况可能是在发版收敛期间,ABTest 的指标波动较大。

而且升级动作本身对活跃用户和非活跃用户有一定的筛选作用,产生的行为和数据也是有偏的,很难有完美的解决办法。避开发版收敛时段,或者对数据进行多维的分析和组织,也许有一定帮助。

结语

按照我以前的风格,这本应是一篇文章。但在信息快消时代,我发现自己也没耐心读长文了,所以就拆成一个系列发布了。

这篇文章主要从平台建设的角度出发,讨论了一些平台设计中要考虑到的关键功能点,希望能对读者有所助益。至于如何科学地进行 ABTest 实验设计和效果分析,不是我擅长的部分,就不再后续展开了。

ABTest 平台设计 - 灰度发布和早鸟用户

上篇《ABTest 平台设计 - 实验开关和分组信息传递》简单介绍了 ABTest 实验开关和数据收集的一些实现,从流量划分、到实验开关、到数据收集,基本实现了 ABTest 的主要功能。下面则扩展谈一下 ABTest 的衍生功能:

基于 ABTest 的灰度发布

与 ABTest 一样,灰度发布也是圈出来一部分流量进行新功能的线上验证,验证基本能力没有问题之后再逐渐扩大覆盖面,支持扩展到全流量。

灰度发布本身也有很多种机制,例如最常用的:上线时先上单副本,再扩展到多副本,再扩展到单机房,再扩展到其它机房。这种方式非常自然,逐步扩量观察保证了服务稳定性。

但这样在上线的中间过程中,总不可避免地会出现一些用户体验问题。比如用户相邻的多次刷新请求被路由到版本不同的副本上,导致请求结果的跳变

既然 ABTest 同样具备划分流量的能力,而且这种划分对于单个用户来说是稳定的,其实在很多情况下可以利用 ABTest 能力来实现灰度发布。

但基于 ABTest 的灰度发布,要求在架构上提供一些支持

比如要发布新版本的网站静态文件(css/js 等),可以全量发布多个版本,然后通过 ABTest 圈定部分用户路由到新版本的静态文件,其余则路由到原版本的静态文件。

比如要发布新版本的服务程序,可以用新的 Docker 部署新版本程序,通过 ABTest 圈定部分用户请求路由到新的 Docker 上,其余则路由到线上的 Docker 上。

基于 ABTest 的灰度发布,很多情况下可以简化服务的部署和回滚操作,也保证了用户在灰度上线期间的体验稳定性。

服务好早鸟用户

在很多时候,企业的内外部总存在着一些早鸟用户,他们对灰度 / AB 新功能有着非常迫切的需求。

最典型的早鸟用户,就是公司的老板。当你开发了一个新功能,向上汇报了一下这功能多好多好。老板会问:

“为什么我没有看到这个新功能?”

你可能不得不解释说:

“老板你的 ID 没有被随机分到实验组里。”,

或者:

“老板这个功能只上了广州机房,北京访问不了。”

还有一种早鸟用户,是产品经理、测试人员,甚至可能包括提交 BUG 的外部用户。他们需要去回归新功能的线上效果是否达到预期,而且甚至他们需要一直不停地在不同的 AB 分支上切来切去比较效果。

这时候就需要一种灵活的机制,让这些早鸟用户有办法切换 AB 功能。

很多人最直接想到的方法,是在随机分桶之外搞一个 ID 分桶,收集上来早鸟用户的 ID,手动配置实验分组。这能在一定程度上解决问题,但设想这样的场景:

“老板,把你 UserID 发来一下,我给你配一下小流量实验。”

老板心里肯定在嘀咕,我要给了你 UserID,岂不是我看过啥发过啥你都能查出来了?这以后还能有隐私么?

而且配置 ID 的方式会增加运维的工作量,尤其是用户需要切来切去的时候。所以这时候不如提供一些强制命中灰度 / AB 的后门功能,能够大幅度降低沟通和维护的复杂度。

这种给早鸟用户的后门可以有很多种做法:

写 Cookie 机制。提供一个特殊的 URL,访问该 URL 就会种下一个强制命中的实验分组 Cookie,此后带着这个分组 Cookie 的访问都会中这个实验。这种适用于 WEB 端产品。APP 端使用的话,需要做一些 Cookie 同步工作。

配置注入机制。提供一个二维码,二维码内容是一段特殊的代码,APP 扫描到该二维码,就会被注入实验分组配置。这种适用于 APP 端产品。

隐藏功能机制。在某些内容上连续点 N 下,就会弹出一个配置面板,可以用来查看和调整当前所中的实验分组。

ABTest 平台如果能够提供这样的后门机制,将会大大方便与早鸟用户的沟通和合作。

下篇,我们聊一下流量分布问题。

ABTest 平台设计 - 实验开关和分组信息传递

通过上文《ABTest 平台设计 - 如何进行流量分桶》可以知道如何把用户流量科学地分配到不同的实验分组中,下面就面临一个问题:如何根据分组信息控制产品功能?

一种直观做法

最显而易见的做法,是直接在系统中传递分组信息,同时使用分组信息作为实验功能的开关

比如说在服务端系统的接入层,通常是 Nginx 或者其它入口模块,对流量进行分组,为每个请求添加一个抽样分组字段,字段内容类似于 “Exp1Group1,Exp3Group2,...”。然后所有对下游的请求,都带着这个分组字段。那么下游的各个模块,都可以根据这个分组字段来决定程序逻辑。用伪码表示就是:

if 抽样分组字段 包含 Exp1Group1:
do 实验1 的 A逻辑
elif 抽样分组字段 包含 Exp1Group2:
do 实验1 的 B逻辑
else
do 全流量逻辑

上面的伪码有些缺点,就是抽样分组信息 Exp*Group* 写死在了代码里,这样灵活性太差。所以,即使直接使用分组字段,通常也是将分组字段作为配置项写到代码里,这样更方便测试和部署。

客户端带来的挑战

在服务端直接使用抽样分组信息作为实验功能开关尚且可以忍受,因为一旦有问题调整下重新上线并不困难,但是在客户端 APP 中这样做就行不通了。客户端版本一旦发布,再想改动就面临着诸多的问题,比如发布审核周期问题,用户拒绝升级问题等等。

还有一个问题就是冗余代码和数据控制的问题。服务端功能 ABTest 转全以后,可以同时删除实验分组和对应的实验功能代码。客户端的实验代码是很难删除的,而且无法预判哪个分支会转全,所以没法直接删除实验分组。这会导致线上的实验越来越多,无法控制。

功能配置和分组配置分离的设计

回过头来思考这个需求:用户中了实验分组 A ,就走实验 A 逻辑。 其实可以加一层抽象:用户中了实验分组 A,就下发 A 对应的功能配置,实现走实验 A 逻辑

就拿客户端 ABTest 来说,大实验可能是换一下 APP 版式,增加或者减少一个新功能;小实验可能是调整一下字体和字号,调整一下背景颜色或者图片等。其实本质上是控制一些功能的配置项。ABTest 可能会下线,但这些配置项会一直在产品中存在。

功能配置和分组配置分离还能带来很大的灵活性,也就是说云端可以创建新的 ABTest 尝试不同的功能配置组合,而不需要硬编码固定的 ABTest。

假设你本来有两个实验,标题大小实验和内容大图实验。如果硬编码情况下,你只能做原始实验方案的对比。如果用功能配置的话,等这两个实验完了,你还可以实验不同标题和内容大小图的结合实验,这是不需要再开发和发版的。

当然,动态配置在工程上如何更合理地实现,也是一个值得探讨的话题,这个留待以后再说。

实验分组信息记录

做 ABTest 的目的,主要是为了收集用户对实验的反馈,方法则是查看不同分组下用户数据指标和用户行为的对比和变化。这些数据的记录,往往是靠各种系统日志。

一种比较原始的办法,是用系统日志跟用户中实验分组的时间信息去 join,来区分 AB 分组。比如用户 A 在 1 号到 10 号分到了 A 分组,那么可以认为该用户 1 号到 10 号的日志都属于 A 分组,用来统计 A 分组指标。

这种方式存在着明显的缺点:一是实验的开启和关闭点不会是整点,而进行精确到秒的日志时间 join 成本太高,很多时候不得不抛弃首尾两天不足整天的用户日志;二是用户中实验分组在产品上的生效往往不是实时的。尤其是在客户端上,用户正在用一个功能的时候,很难瞬间将该功能切换成另一种样式,往往是在用户在下一次重入初始化的时候才开启实验样式,否则很容易引起崩溃。

对统计更友好的分组信息记录,是在每条关键的系统/客户端日志中都添加分组信息字段。这样虽然增加了一些冗余信息,但会使所有的关键数据记录都有实验分组这一列,用它做筛选即可进行指标的对比和用户行为序列的分析。

小细节:分组编码

上面谈到每条日志中都要记录用户所属的实验分组信息,这种冗余程度要求分组信息有着非常集约的编码设计,才能尽量减少传输和存储的数据量。可能的选择有以下几种:

  • 奔放派 :直接使用实验名+分组名作为分组信息。比如一个用户中了两个实验的不同分组,那就是:“ExpTitle_GroupA|ExpImage_GroupC”。奔放派的好处是日志可读性很高。
  • 婉约派:将实验名和/或分组名精简为两个 ID,形如:“10010_1|10080_3”。好处是虽然可读性低了些,但毕竟直观。
  • 理工派:将实验名和分组名精简为一个ID,形如:“12345|14523”。对于理工科思维来说,只要 ID 不重复就行,为啥要分成俩字段?
  • 极客派:将 ID 用 62 进制表示,形如:“3d7|3Mf”。这个世界上,只有麻瓜才用 10 进制。
  • 抠门派:将 ID 数组用 protobuf (varint)表示,有时候需要 base64 一下,形如:“算了举例太费劲”。好处就是一般人看不懂。

当然,可能还有其它的组合,大家意会就好了。

下篇,我们聊一下灰度发布和早鸟用户

ABTest 平台设计 - 如何进行流量分桶

在 2018 年,我相信 ABTest 这个名词已经不用过多地解释了。但我发现很多公司,尤其是初创企业,虽然能理解这件事是什么,却不知道这件事该怎么做,以及该怎么做好。

这一系列文章,就是想讲清楚在设计具体的 A/B 测试平台这种基础架构时,要考虑哪些问题,以及有哪些推荐的做法。

今天先谈一谈:

如何进行用户分桶

我们都知道互联网产品的 ABTest 主要是围绕用户进行的实验,从统计意义上观察用户对不同的产品设计、交互体验、业务流程的反馈,从而指导产品的改进方向。

那么很重要的一点就是,怎么圈定哪些用户进行 A 实验,哪些用户进行 B 实验。

一种错误做法

在我工作过的一家公司,他们是这样做的:

“使用用户的 UserID 对 1000 取模分成 1000 个桶,然后选择不同的桶分配给 A 或者 B。”

我问研发人员为什么这么做?他们给的理由是:

“UserID 是自增 ID,跟用户注册顺序有关,有一定的随机性。可以保证用户随机地分到 A 或者 B 中。”

A/B 的流量圈定的一个重要原则就是无偏,不然无法进行对比评估。上面的做法看起来倒也有一定的道理。(还常见的一种做法是,用手机尾号最后一位来进行分桶,优惠多少就看你手机尾号是否运气好了 ^_^ )

单单考虑孤立实验,这样做也无可厚非。但如果考虑到长期交叉、连续的实验,这样做有很大的问题。

首先,这种设计只能进行单层实验,也就是说一份流量只能通过一个实验。

如果实验人员选择了在任意一个桶中同时进行 X, Y 两个实验的话,那两个实验的结果就会相互干涉,导致最终结果不可信。例如:在尾号为 001 的桶里进行了两个促销活动“降价10%”和“满100减10块”的实验,最终 001 桶的用户订单数比其它桶高,那到底是哪个促销更有效果呢?

其次,这种设计在长期会造成桶间用户行为有偏

也许刚开始因为其随机性,桶间用户行为差异很小。但第一个实验过后,桶间就开始有了行为差异——这也是 ABTest 的目标。N 个实验过后,桶间行为的差异可能就变得非常大了。

比如你总是在 001 桶的用户上实验幅度较大的促销活动,那么 001 桶的用户留存就会显著高于其它桶。那实验人员为了让实验效果更好看,可能会偷偷地继续选择 001 桶进行实验。

最后,这种设计的实验效率太低。因为一份流量只能通过一个实验,无法对流量进行充分的利用。

那该如何设计用户分桶,才能满足 ABTest 的需求呢?

一种正确方法

目前业界应用最多的,是可重叠分层分桶方法。

具体来说,就是将流量分成可重叠的多个层。因为很多类实验从修改的系统参数到观察的产品指标都是不相关的,完全可以将实验分成互相独立的多个层。例如 UI 层、推荐算法层、广告算法层,或者开屏、首页、购物车、结算页等。

单单分层还不够,在每个层中需要使用不同的随机分桶算法,保证流量在不同层中是正交的。也就是说,一个用户在每个层中应该分到哪个桶里,是独立不相关的。具体来说,在上一层 001 桶的所有用户,理论上应该均匀地随机分布在下一层的 1000 个桶中。

通过可重叠的分层分桶方法,一份流量通过 N 个层可以同时中 N 个实验,而且实验之间相互不干扰,能显著提升流量利用率。

从实操上来说,我们通常采取下面的方法:

首先,确定 Layer,确定请求 Tag。例如从 UserID,DeviceID、CookieID、手机号 中选一个,支持匿名流量的,一般会选用 DeviceID 或者 IMSI 等作为请求 Tag。

然后,选一个你喜欢的 Hash 函数,尽量选个使用方便、随机性更强的;

最后,通过 Hash(Layer, Tag) % 1000 确定每层分桶。如果 Hash 函数支持 seed,那么使用 Layer 作为 seed,否则作为 SALT,即将 "Layer+Tag" 作为输入参数。

在完成分桶以后,还可以进行一定的流量筛选。例如来自北京和上海的用户,可以允许分别进行不同的实验。

可重叠分层分桶方法的系统性介绍,可以参见 Google 在 KDD 2010 发表的论文 《Overlapping Experiment Infrastructure: More, Better, Faster Experimentation》,感兴趣的同学可以延伸阅读一下。

更多样的选择

但分层方法并不能让所有人满意,尤其是对并行实验非常多的大公司来说。因为同一层可能有不同份额的其它小流量实验在线上,新实验能够拿到的流量非常有限,需要等待同层其它实验结束,会非常影响迭代效率。而新实验未必一定会修改其它实验的参数,或者影响其它实验的效果。

所以一些公司也逐渐开始探索无分层,也可以称为无限分层的方法。具体的做法是,每个实验都可以看成独立的层,只保证层间流量分桶的正交性,所有的实验都可能存在重叠情况。

这样做用户就有大概率同时中同一类实验,例如两个实验人员同时在实验 UI 布局,实际上用户只能看到一种布局(因为代码分支有先后逻辑),那么实验结果就不可信了。

由于系统上无法保证实验间不冲突,那么只能从组织上来避免冲突,或者从数据上尽早观察到冲突的存在来解决冲突。这对组织的管理能力和企业的数据能力提出了更高的要求。

下篇,我们聊一下实验的开关和分组信息传递

ES/Redis/SSDB/BRPC 的 Open-Falcon 监控脚本

前些天想监控不同机房的多个 ElasticSearch 集群,结果网上找到的监控脚本都不太好用。我希望这个脚本能够并发获取多个 ES 集群的状态,而且监控的目标和上报的地址可以通过配置文件修改,不需要去脚本中查找修改位置。

了解到 Open-Falcon 的上报接口非常简单,于是就自己写了一个同时查询多个 ES 集群信息并上传到 Open-Facon Agent 的监控脚本。能够将多个集群的索引文档数、查询请求数、查询时间等关键信息收集到 Open-Falcon 中。

用了一段时间,感觉还挺不错的。后来又头疼 Redis 内存占用太高,分析困难等问题,又以同样的思路写了 Redis 的监控脚本,都是通过 info 命令获取集群的状态,把 KEY 数量,内存占用,命令数,过期的 KEY 数量等等相关的信息都收集到了 Open-Falcon 里。这样就能通过 Open-Falcon 的报表看到 Redis 使用情况的变化。

SSDB 虽然兼容 Redis 命令,但 info 命令的返回跟 Redis 差异实在是太……大了点儿。内容不一样也就算了,格式也太随意了,用纯文本画了几个表格,真让人无力吐槽。没法复用 Redis 的监控,只能自己给 info 写个 parser,将信息提取成可用的字典。

最后说一下 BRPC。BRPC 内建了一个 HTTP 服务,把内部的各种状态用 WEB 页面的形式展示出来。关键的是又提供了一套 BVAR 机制,可以用于统计内部的各种指标,自动显示到页面上。最有意思的是,它这个内建服务会识别 User-Agent,如果请求是通过 curl 发起的,返回的是一个完全不包含任何 HTML 标签的纯文本界面,可以用 yaml 解析成字典。这样就可以用跟监控 ES 完全类似的方式,通过外部请求 BVAR 页面,获取所有状态上报监控系统了。

这四种系统的监控脚本,我已经整理放到 GitHub 上了,希望能对同样需求的朋友也有所帮助:

VirtualBox 还能这样玩

在工作中经常遇到这样的情况:忽然发现开源界有了个新玩意儿,但是下载到自己电脑上一看,不支持我的操作系统,或者不支持这个版本的操作系统。只能老老实实下载某个版本的 Linux 安装镜像,然后开始安装配置虚拟机,等把环境都折腾得差不多了,已经忘了自己装系统来干什么了。

我曾经想过直接从网上寻找构建好的虚拟机镜像,最终发现并不容易。但我很遗憾没有早些遇见 Vagrant,因为它更进一步地满足了上述的需求。

Vagrant 能做什么呢?一句话来说,就是它用简单的命令封装了虚拟机创建、分发和配置的过程。如果把 VirtualBox 比作 dpkg、rpm,Vagrant 就是 apt-get、yum。用 Vagrant 可以非常简单地下载网上封装好的虚拟机镜像(叫做 box),然后启动起来,并且登录进去。配置虚拟机的端口转发等功能也变得非常容易,并且可以脚本化。

当然,Vagrant 也可以将配置好的虚拟机打包成 box 分发给别人。这就带来很大一个好处,那就是用它可以非常简单地实现团队开发环境的统一。创建一个 Linux 虚拟机,安装好必要的开发工具、运行环境,配置好代码仓库,打包成 box,然后再分发一个 Vagrantfile 支持启动虚拟机后执行一个脚本更新代码。新人只需要下载 Vagrantfile,然后 vagrant up。Bingo! 就可以 ssh 上去开发了。

当开发环境出现各种问题时,非常简单地用 vagrant 重新配置下即可。这大大避免了追查『在我的环境里执行没错啊!』这种问题的麻烦发生。

对于团队来说,开发环境的 box 还是自己打包更为合适,能够尽可能避免从网上下载的 box 带来的安全问题。不过对于普通用户来说,最酷的就是有各种来自官方或非官方现成的 box 可玩,不用痛苦地自己去一遍遍重装操作系统。比如以下几个:

虽然事实上 Vagrant 已经支持了 VMware 和 KVM,不过资源上就没有 VirtualBox 那么丰富了,大家有兴趣也可以尝试一下。

TCP Fast Open by Google 浅析

Google 将在今年 12 月的 ACM CoNEXT 会议上发表他们在改善 Web 应用响应时延方面的一个工作,通过修改 TCP 协议利用三次握手时进行数据交换的“TCP Fast Open”。虽然 paper 是两天前才释出,但相关的 RFC 草案则早在 2011 年 3 月份就提交到了 IETF,并且在两周前进行了一次 UPDATE,这里是 DIFF

对于 TCP Fast Open 方案的内容,淘宝的一个朋友已经根据 RFC 草案进行了解读。我就不再赘述,感兴趣的朋友可以去看 paper 或者 RFC。我这里只是想讨论一下这个东西的应用前景。

由于对背景并没有做深入了解,我相信已经有很多人尝试去做过类似的工作,但我想类似的工作应该没有得到过大规模的应用。对于已经成型很久很久的 TCP 协议,让人很难有修改它的欲望,因为改那么底层的东西意味着很多很多的麻烦。

但是是否愿意付出代价,有一个前提是有没有足够的好处。TFO 给出的好处是:在 RTT (Round Trip Time) 比较低时,客户端页面加载时间优化大约在 4%~5%;RTT 越长,好处越大,平均大约在 25%。

Google TCP Fast Open Evaluation
Google TCP Fast Open Evaluation

除了页面加载变快改善了用户体验之外,TFO 给服务器端也带来了一些好处。由于每个请求都节省了一个 RTT,相应地也减少了服务器端的 CPU 消耗。paper 中给出的数据是每秒事务数由 2876.4 上升到 3548.7。

虽然 paper 中大部分时间在强调 TFO 对 web 页面加载的显著加速作用,但我认为即使 TFO 能成为互联网标准,它目前的状态离成为标准还有很长一段距离,因而在短期内它是无法影响到主流互联网世界的。但这并不意味着它没有机会,依小弟的愚见,目前它的推广应用可能有两个方向:

1. 移动互联网。移动互联网的 RTT 目前远大于传统互联网(常理推测,需数据支撑),因而一个 RTT 节省的效果无法被忽视;另外移动互联网终端操作系统多样化,不像桌面终端系统那么单一。 Google 自己就掌握着其中一个很重要的 android,百度也计划推出自己的“易平台”。这些互联网公司有动力去改善移动用户访问自身网站的用户体验。

2. 互联网企业数据中心。虽然数据中心内部访问时延很低,但对于典型的请求/响应的服务而言,减少一次 RTT 带来的好处还是有吸引力的,最起码能减少计算能力浪费和增加吞吐吧。再加上很多企业内部使用的都是定制的开源操作系统和定制的网络库,升级的代价并不是那么高。如果我是企业基础设施的负责人,我想我会很慎重地考虑这个方案的。