神经网络图像输入的 resize 问题

这个标题在我的博客后台躺了快一年了,但一直没想好该怎么写。主要是没有深入地去研究这里面的问题,就随便谈谈一点粗浅的认知吧。这些认知可能不对,仅供参考,并且欢迎批评。

一、不同的 resize 方式对最终的结果有一定的影响,尤其是用随机图片评估时会更加明显。

看似用的是同一个神经网络,同一个训练集,但在输入的处理上仍然会有各种不同。比如 Inception 要求 299x299,你可以直接用 ImageMagick 将原始图片处理成 299x299 再输入,也可以用 OpenCV 读入图片后再转成 299x299,还可以直接用深度学习框架(TensorFlow/Caffe)进行 resize。甚至同一种方法也可能有各种不同的参数控制,比如最邻近插值、双线性插值、双立方插值等。通过不同的 resize 方法训练出来的网络参数,或者同一张图片不同方法 resize 后预测的输出,数值是存在差异的。如果使用的是质量较低的大规模数据集,差异可能会非常明显。

二、不同的 resize 方式对最终结果的影响无法确定。

换种说法,这可能是个玄学。这算是一个经验总结,就不多讲了。也就是说,某种 resize 方式有时可能让结果变好,有时也可能让结果变差。

三、训练、评估和线上预测时统一图片处理方式有一些好处。

有的公司在训练神经网络时使用一种框架,上线时使用另一种框架;或者训练时采取一种输入,上线时采取另一种输入。都会导致线上服务的预测结果跟评估结果不一致,导致排查问题较为复杂。

有时候为了性能考虑,必须在客户端完成图片处理,resize 成较小图片后再传给服务端。而客户端往往使用的不同的库,比如 iOS 可以使用 Core Graphics 库或者 UIKit 库,Android 的 Bitmap 库,这些库在服务端是基本上无法使用的。这时候就需要知道这可能会导致线上效果与评估结果有不一致的可能,并且采取一定的措施来消减这样的不同。

react-native-navigation 简单分析和跨页跳转

虽然 react-native-navigation 是 Facebook React Native 官方文档推荐的导航库之一 ,但我也不得不说使用它做 APP 导航主框架的体验简直糟糕透了。当然,这本身可能就是 React Native 自身的问题。

1 react-native-navigation 简单分析

使用 react-native-navigation 首先得理解下它的实现。它独立于 RN Component 的 componentWillMount/componentWillUnmount 接口实现了一套自己的事件机制,最重要的可能是 willAppear/willDisappear。它提供了一套页面堆栈操作和切换动画, push 可以将目标页面切换到最上方,pop 可以返回上一页。

可能是为了性能或者设计使然,push 的时候不会销毁当前页。也就是说,在 A 页面里 push 跳转到B 页面,不会 Unmount A 页面的Component。 不过在 B 页面 pop 回 A 页面时,的确会 Unmount B 页面的Component。这也意味着,整个导航路径是一个页面堆栈,只要在堆栈里页面的 Component,都不会被 Unmount。

2 页面堆栈的问题

这有时候会导致一些很严重的问题。有些情况下,特定的 Component 可能会占用唯一的系统资源,比如:麦克风、照相机等。这些 Component 在实现的时候往往只考虑了 React Native 的接口,在 componentWillUnmount 的时候释放占用的资源。它们不会预料到与 react-native-navigation 的结合,专门提供一个 willDisappear 时释放资源的接口,而且有些情况下也未必能这样做。

如果 A 页面在使用这些 Component 已经占用了麦克风或者相机,B 页面也要使用这些 Component,那么从 A push 跳转到 B 时,A 页面的资源不会被释放,B 页面就可能会遇到麦克风不可用,或者相机无法初始化等问题。

解决这个问题,最简单的办法是调整页面交互顺序,保证使用这些独占系统资源的页面永远在堆栈的最顶端,或者使用 Modal Stack,把独占资源的 Component 放到 Modal 里去 present 然后 dismiss。

3 跨页跳转实现

react-native-navigation 只能支持页面堆栈,而且看起来只能支持 push/pop 一个页面,也就是说整个切换过程是串行的,push 顺序是 A->B->A->D ,那么 pop 顺序也只能是 D->A->B->A。

但很可惜地是,在产品经理眼中,是不存在串行页面切换这种限制的。TA 们有时候要求跳转的过程中没 A,但返回的时候要有 A;或者要求跳转的过程中有 A,但返回的时候可以跳过 A,或者甚至直接返回到堆栈最底端。

直接返回栈底很容易,react-native-navigation 提供了 popToRoot 接口,但它没有提供一下子 push 多个页面,或者一下子 pop 多个页面的功能。它也没有类似于 HTML5 的 history API,我们直接对堆栈进行操作,是不太可能的。只能通过它现有的接口想办法。

3.1 跨页 push

跳转的过程没有 A,但返回的时候要有 A,这只是一个产品需求。在实现上,是可以变成跳转过程中有 A,但是 A 被快速跳过,返回的时候才会被真正渲染。这样从用户体验上来看,并没有看到 A。代码实现上,可以考虑两种方法:

willAppear 结合 didDisappear 做状态控制

在 A 的 state 里放一个 isFirstEntry 状态,默认是 truewillAppear 里判断 isFirstEntry 则直接跳转到下个页面,render 里判断 isFirstEntry 则只渲染一个背景 View ,否则才渲染正常页面。这样就实现了在页面切换过程中跳过 A。在 的 didDisappear 里将 isFirstEntry 置为 false 。这样在返回的时候 willAppearrender 表现就和正常返回一样了。

  willAppear = () => {
    if (this.state.isFirstEntry) {
      this.props.navigator.push(...);
      return;
    }
    ...
  };
  render() {
    if (this.state.isFirstEntry) {
      // 返回背景 View
    } else {
      // 返回正常 View
    }
  }
  didDisappear = () => {
    this.setState({isFirstEntry: false});
  };

willAppear 页面计数

在需要更复杂逻辑的地方,可以在 state 里放一个 appearTimes 计数器。在 willAppear 里给计数器加一,这样每次进入页面都会增加计数。通过判断计数器的值,来决定如何 render 或者跳转。

  willAppear = () => {
    this.setState({appearTimes: this.state.appearTimes + 1});
    if (this.state.appearTimes === 1) {
      this.props.navigator.push(...);
      return;
    }
    ...
  };
  render() {
    if (this.state.appearTimes === 1) {
      // 返回背景 View
    } else {
      // 返回正常 View
    }
  }

3.2 跨页 pop

跳转的过程中有 A,但返回的时候要跳过 A,相当于可以自己操作 pop 的步长。很遗憾,react-native-navigation 没有提供这样的接口。不过我们可以采用一个 trick 的手段,来实现这个逻辑。

假设从 Root->A->B,在 A 的 state 里放一个 relayPop ,默认是 false。 在 A 跳转到 B 时,通过 props 传入一个回调:setParentRelayPop,B 可以通过这个回调修改 A 的 state relayPoptrue; 在 A 的 willAppear 中,首先判断 relayPop 是否为真,如果是真的话,代表是从 B 返回且 B 要求接力返回,那么 A 就直接 pop 返回到 A 的上级。 B 在返回时,首先通过回调设置 relayPoptrue,然后再调用 pop 接口,就实现了跨页返回。

// Screen A
  willAppear = () => {
    if (this.state.relayPop) {
      this.props.navigator.pop();  // 接力返回
      return;
    }
    ...
  };
  ...
    // 跳转逻辑某处
    this.props.navigator.push({..., passProps: {
                                  setParentRelayPop: () => this.setState({relayPop: true}) 
                                }});
// Screen B
    // 返回逻辑某处
    this.props.setParentRelayPop();
    this.props.navigator.pop();

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 上了,希望能对同样需求的朋友也有所帮助:

手机 APP 应该选用哪个加密算法 - 兼吐槽 TEA

很多 APP 产品都有通信加密的需求,一部分出于市场的要求,比如苹果对于“ATS”的强制性规定,一部分出于自身安全的考虑,比如对账号和密码的保护。这些需求大部分都可以用简单的 HTTP -> HTTPS 升级来搞定,而且几乎不用付出什么成本(除加解密的计算开支外),例如使用我之前文章介绍到的 Let's Encrypt 免费证书

但还有一类特殊的需求,HTTPS 解决不了,也就是防协议分析的需求。很多 APP 开发者应该知道,只要在手机里安装一个代理 CA 证书,就可以实现中间人攻击,通过代理软件抓到 HTTPS 包的明文内容。虽然这样的攻击很难在公开网络上进行,但对自己的手机进行抓包分析,作为 APP 和服务端通信的调试手段是被广泛使用的。

协议分析能做什么呢?可以猜想到一定的 APP 内部逻辑,可以对产品数据进行作弊攻击。举个例子:你的 APP 通过某个渠道进行推广,为了统计渠道安装、注册或者日活,你往往会在 APP 中埋一个点,当 APP 启动时,发送一些信息到服务器。如果这个协议被破解了,渠道商根本不需要真正进行推广,只需要构造一些假消息发送到你的服务器就行了。仅看数据你可能会以为这个渠道推广效果特别好,其实只是骗局而已。

这类情况下,就要求对敏感协议内容进行额外的数据保护。最常用的做法,就是对协议内容进行一次额外的加密,为了性能,往往选用对称加密算法。那么问题来了,手机 APP 开发时,应该选用哪个加密算法?

关于这个选型,国内互联网圈有个怪现状值得谈一下,那就是 TEA 算法。因为该算法在腾讯有着广泛的应用,因而被很多客户端开发人员推崇。典型推荐理由往往是:“TEA加密算法不但比较简单,而且有很强的抗差分分析能力,加密速度也比较快,还可以根据需求设置加密轮数来增加加密强度”。这是真的吗?算法安全性可以直接看维基百科上 TEA 算法的介绍,我的理解是不够安全。但其实大部分用户也不那么地在乎它的安全强度,那么性能呢?加密速度真的很快吗?

这就要从历史的角度去看了。作为曾经手撸过 “DES 差分密码攻击” 代码的程序员,表示 TEA 算法的确足够简单。在 QQ 诞生的那个年代,TEA 在计算上的确有着不小的优势。但 QQ 已经 18 岁了啊同学们,18 年来中国发生了多大的变化,世界发生了多大的变化啊!

2008 年,Intel 就发布了 x86 的 AES 指令集扩展,近几年的服务器 CPU 应该都支持,不相信你
grep aes /proc/cpuinfo 就能看到 ;2011 年 ARM 也在 ARMv8 架构下直接提供了 AES 和 SHA-1/SHA-256 指令 。这意味着什么?意味着服务端和客户端在硬件上直接支持 AES,意味着原来 N 条汇编指令只需要一条 AES 指令就完成了。其实也意味着,在绝大多数情况下 AES 才应该是你的首选

口说无凭,咱们可以看一下测试数据,x86 服务器 CPU 测试可以直接看 Crypto++ 的 benchmark 。可以看到 AES/CTR (128-bit key) 与 TEA/CTR (128-bit key) 的加密速度比是:4499 MB/s 比 72 MB/s,62 倍的差异!这就是硬件实现的威力。

ARM 手机 CPU 加密算法的 Benchmark,我没有找到。但为了更有说服力,我自己实现了两个测试 APP,一个 Android 版,一个 iOS 版。写技术文章多不容易啊,写博客之前先写三个晚上代码,泪目!!!代码在 https://github.com/solrex/cipher-speedAndroid 版可以直接在 Release 里扫码安装

首先介绍一下目前的旗舰 CPU,骁龙 835 (MSM8998) 的表现,测试机型是小米 6:

# Speed Test of 10MB Data Enc/Decryption #
# AES: 
* [AES/CBC/PKCS5Padding] ENC: 1146.9 KB/ms
* [AES/CBC/PKCS5Padding] DEC: 692.4 KB/ms
* [AES/CBC/NoPadding] ENC: 1118.8 KB/ms
* [AES/CBC/NoPadding] DEC: 1343.5 KB/ms
* [AES/ECB/PKCS5Padding] ENC: 990.4 KB/ms
* [AES/ECB/PKCS5Padding] DEC: 703.2 KB/ms
* [AES/ECB/NoPadding] ENC: 973.4 KB/ms
* [AES/ECB/NoPadding] DEC: 988.9 KB/ms
* [AES/GCM/NOPADDING] ENC: 13.9 KB/ms
* [AES/GCM/NOPADDING] DEC: 14.7 KB/ms
# DES: 
* [DES/CBC/PKCS5Padding] ENC: 20.1 KB/ms
* [DES/CBC/PKCS5Padding] DEC: 20.7 KB/ms
* [DES/CBC/NoPadding] ENC: 21.3 KB/ms
* [DES/CBC/NoPadding] DEC: 21.6 KB/ms
* [DES/ECB/PKCS5Padding] ENC: 26.3 KB/ms
* [DES/ECB/PKCS5Padding] DEC: 26.2 KB/ms
* [DES/ECB/NoPadding] ENC: 25.9 KB/ms
* [DES/ECB/NoPadding] DEC: 26.8 KB/ms
# 3DES: 
* [DESede/CBC/PKCS5Padding] ENC: 23.6 KB/ms
* [DESede/CBC/PKCS5Padding] DEC: 23.2 KB/ms
* [DESede/CBC/NoPadding] ENC: 23.6 KB/ms
* [DESede/CBC/NoPadding] DEC: 23.5 KB/ms
* [DESede/ECB/PKCS5Padding] ENC: 8.5 KB/ms
* [DESede/ECB/PKCS5Padding] DEC: 8.5 KB/ms
* [DESede/ECB/NoPadding] ENC: 8.5 KB/ms
* [DESede/ECB/NoPadding] DEC: 8.6 KB/ms
# TEA: 
* [TEA] ENC: 16.0 KB/ms
* [TEA] DEC: 18.1 KB/ms

可以看到,TEA:AES=16:990,这是多少倍?我都懒得算了。然后是 2 年前的中低端 CPU,联发科 Helio P10 (MT6755),测试机型是魅蓝 Note 3:

# Speed Test of 10MB Data Enc/Decryption #
# AES: 
* [AES/CBC/PKCS5Padding] ENC: 358.8 KB/ms
* [AES/CBC/PKCS5Padding] DEC: 267.9 KB/ms
* [AES/CBC/NoPadding] ENC: 438.8 KB/ms
* [AES/CBC/NoPadding] DEC: 515.0 KB/ms
* [AES/ECB/PKCS5Padding] ENC: 310.6 KB/ms
* [AES/ECB/PKCS5Padding] DEC: 222.1 KB/ms
* [AES/ECB/NoPadding] ENC: 312.4 KB/ms
* [AES/ECB/NoPadding] DEC: 319.5 KB/ms
* [AES/GCM/NOPADDING] ENC: 5.1 KB/ms
* [AES/GCM/NOPADDING] DEC: 5.7 KB/ms
# DES: 
* [DES/CBC/PKCS5Padding] ENC: 7.5 KB/ms
* [DES/CBC/PKCS5Padding] DEC: 7.7 KB/ms
* [DES/CBC/NoPadding] ENC: 7.7 KB/ms
* [DES/CBC/NoPadding] DEC: 7.8 KB/ms
* [DES/ECB/PKCS5Padding] ENC: 9.3 KB/ms
* [DES/ECB/PKCS5Padding] DEC: 9.2 KB/ms
* [DES/ECB/NoPadding] ENC: 9.3 KB/ms
* [DES/ECB/NoPadding] DEC: 9.5 KB/ms
# 3DES: 
* [DESede/CBC/PKCS5Padding] ENC: 12.5 KB/ms
* [DESede/CBC/PKCS5Padding] DEC: 12.3 KB/ms
* [DESede/CBC/NoPadding] ENC: 12.3 KB/ms
* [DESede/CBC/NoPadding] DEC: 12.5 KB/ms
* [DESede/ECB/PKCS5Padding] ENC: 3.1 KB/ms
* [DESede/ECB/PKCS5Padding] DEC: 3.1 KB/ms
* [DESede/ECB/NoPadding] ENC: 3.1 KB/ms
* [DESede/ECB/NoPadding] DEC: 3.1 KB/ms
# TEA: 
* [TEA] ENC: 6.2 KB/ms
* [TEA] DEC: 8.0 KB/ms

然后是 3 年前的旗舰 CPU,Apple A8,测试机型是 iPhone6。别问我为啥不用今年的苹果旗舰 CPU...

# Speed Test of 10MB Data Enc/Decryption #
# AES
* [AES/CBC/PKC7Padding] ENC: 76.0 KB/ms
* [AES/CBC/PKC7Padding] DEC: 111.3 KB/ms
* [AES/CBC/NoPadding] ENC: 138.2 KB/ms
* [AES/CBC/NoPadding] DEC: 450.7 KB/ms
* [AES/ECB/PKC7Padding] ENC: 305.6 KB/ms
* [AES/ECB/PKC7Padding] DEC: 735.9 KB/ms
* [AES/ECB/NoPadding] ENC: 330.0 KB/ms
* [AES/ECB/NoPadding] DEC: 673.6 KB/ms
# DES
* [DES/CBC/PKC7Padding] ENC: 23.1 KB/ms
* [DES/CBC/PKC7Padding] DEC: 24.5 KB/ms
* [DES/CBCPadding] ENC: 23.1 KB/ms
* [DES/CBCPadding] DEC: 22.8 KB/ms
* [DES/ECB/PKC7Padding] ENC: 19.4 KB/ms
* [DES/ECB/PKC7Padding] DEC: 20.8 KB/ms
* [DES/ECBPadding] ENC: 22.2 KB/ms
* [DES/ECBPadding] DEC: 22.2 KB/ms
# 3DES
* [3DES/CBC/PKC7Padding] ENC: 9.7 KB/ms
* [3DES/CBC/PKC7Padding] DEC: 9.8 KB/ms
* [3DES/CBC/NoPadding] ENC: 9.8 KB/ms
* [3DES/CBC/NoPadding] DEC: 9.8 KB/ms
* [3DES/ECB/PKC7Padding] ENC: 9.4 KB/ms
* [3DES/ECB/PKC7Padding] DEC: 9.1 KB/ms
* [3DES/ECB/NoPadding] ENC: 9.2 KB/ms
* [3DES/ECB/NoPadding] DEC: 9.4 KB/ms
# TEA
* [TEA] ENC: 10.9 KB/ms
* [TEA] DEC: 11.1 KB/ms

关于 Apple A8 的测试多说两句。我上面的 AES 性能,离 GeekBench 发布的 A8 AES Single Core 还有不少差距,不知道是不是测试方法差异导致。但总的来说,不影响结论,那就是 TEA 跟 AES 差距巨大

看到这里,可能大部分人心里已经做出选择了。即使还没做出选择的读者,我想你也可以考虑看看我的代码实现是否存在问题。不过最后还是回答一下开头提出的问题吧:

  • 如果你使用平台语言来实现对称加密,也就是 Android 上用 Java,iOS 上用 OC 或者 Swift,AES 是不二选择。这样能充分利用硬件提供的能力,安全性+性能肯定是最优,不要再想其他选项了。
  • 如果你使用 Native 语言来实现对称加密,在 Android 上使用 JNI 调用 C 编译的代码,的确不少人认为原生指令更难逆向。可能要在 ARM 架构上做个取舍,是取悦 v8 用户,还是取悦 v7 以下的用户,这可能影响到选型。不过我认为 AES 依然是一个好的选项,起码在服务器端,你肯定会节省成本。

如何实现高效的 URL 过滤算法

在上一篇文章《那么,屏蔽词系统到底该怎么做?》中,我简单讲了一下屏蔽词系统的实现思路。这篇就讲一讲另一个类似的话题,那就是如何实现高效的 URL 过滤算法。

通过某些字面特征,筛选出符合条件的 URL,对其执行特定的操作。虽然看起来像是很遥远专业的技术,但其实早就根植在你手机里的各类浏览器相关 app,以及你使用的各类互联网服务中了。举一个最简单的例子:你在微信里打开淘宝链接,背后就是一个 URL 过滤算法的实现。

还有,很多浏览器 APP 设置项里有一个开关,叫做“广告过滤”,其中很大一部分也是通过 URL 过滤实现的。那如何做到高效的 URL 过滤呢

如果拿这个问题来面试,大概率候选人会回答用正则表达式实现。其实这一点不令人惊讶,因为我曾经亲眼见过一个日活惊人的 APP 也是用正则表达式做的(真不敢相信自己的眼睛)。用正则表达式本身来实现 URL 匹配不是很大的问题,但在“广告过滤”这样的场合,意味着有成千上万的 URL 规则,很难有人能用这些规则写出来高效的正则表达式

关于这点,展开说一下。理论上来讲,把所有 URL 规则融合到一条正则表达式里,也不是不可能。比如:"http[s]{0,1}://..{0,1}(taobao|tmall).com/.",可以融合两条淘宝和天猫的 url 规则。但如果让你融合一千个不同的 url 规则到一条正则表达式里,我想很难有人有信心把它完全做对,更不敢保证后续维护这个规则库的人能做对。所以很多情况下,他们只是用几千个正则表达式实现了几千条 url 规则,想想这个匹配效率有多低!!

所以,真正在乎 URL 匹配效率的人,不会使用正则表达式。举个最典型的例子,Adblock Plus 的过滤规则(https://adblockplus.org/filters),是完全自定义了一套匹配规则。不过,Adblock Plus 在早期也是用正则表达式,而且完全就是我上面讲的那种用法,不过后来他们改进了,还专门发了篇博客(https://adblockplus.org/blog/investigating-filter-matching-algorithms , 注意里面也用到了我上篇文章提到到 Rabin-Karp )。

可是在我看来,Adblock Plus 的实现只是够用,却还不够高效。我上一篇文章提到的 Trie 树,更合适做这种事情,可能也更高效(未比较),至少更简洁。Adblock 最核心的地方,是 URL 匹配。从 Adblock Plus 定义的规则也能看出,URL 匹配其实比正则表达式匹配简单很多,无非是在普通字符串匹配之上加了一些通配符而已。

那以 Adblock Plus 的通配符为例,我来讲一下如何用 Trie 树来实现含通配符的字符串匹配

  • "*" 通配符匹配任意长的字符串
    • 包含匹配时模式串前后的 "*" 没有意义,可以直接丢掉;
    • 以中间的 "*" 做划分,原串 * 位置后面的部分进行递归子树匹配;
  • "|" 匹配网址开头结尾:对 url 预处理,扔掉 scheme 部分 "http://",头尾都加上 "|",这样自然就能匹配上模式串中的 "|" 了。
  • "^" 标记分隔符:这就更简单了,遇到 ^ 规则时,不是比较原串中字符是否与其相等,而是是否包含在某个符号表中即可。

在这些匹配规则的基础上,结合 Double Array Trie 数据结构,可以实现一个内存占用超级小但效率又非常高的 URL 过滤器了。而且 Trie 树的结构对规则的条数非常不敏感,耗时并不会随着过滤规则的增多而显著增加。

不过还得多说一句,算法是效率核心,但真正解决问题还得花很多心思在算法外。比如例外规则,规则库的动态更新等等,这里就不继续展开了。

以上只是本人的一点拙见,对 Adblock Plus 的评论也没有评测数据验证,只是希望对读者能够有些用处。此外,也欢迎大家用更好的算法来打脸

那么,屏蔽词系统到底该怎么做?

caoz 在最近一篇公众号文章《企业面试需要几轮》中提到一个面试问题:

大家都知道做互联网有很多屏蔽词要处理,那么需要对用户发布的内容,做屏蔽词过滤,先不考虑一些正则组合的情况,假设我有一个屏蔽词库,里面有几万条屏蔽词信息,然后我有个非常火爆的社区,每天用户产生海量内容,比如上百万篇文章或评论,现在我要求每篇文章都能快速通过屏蔽词库去检索,而且要求服务器可以支撑尽可能多的处理请求,毕竟这是成本啊。那么请设计一个屏蔽词过滤的算法逻辑。

碰巧我在面试中也喜欢问这个问题,可惜的是能答上来的的确不多。

单单从算法层面论,大概有 50% 的人能回答出来逐个进行 KMP 匹配(另外 50% 不知道什么是 KMP)。让他更进一步优化的话,20% 的人能想到一些粗糙的优化技巧,10% 的人能说出前缀树匹配。大部分能答出前缀树匹配的人会提到 AC 自动机,但只有一半能大概答出 AC 自动机的大概算法。到目前为止,还没有人回答过其它算法,比如 Rabin-Karp 或者 Commentz-Walter。

即使在算法层面上能回答出来 AC 自动机,在实现上候选人也只能形象地描述一下 Trie 树和失败指针,Trie 树的每一层使用一个 Set 或者哈希表数据结构。到目前为止,还没有人回答过用 Double Array 来实现 Trie,甚至连用前缀做 key 的一个大哈希表来模拟 Trie 树的优化也没有。虽然构造 Double Array Trie 的代价非常高,但内存占用非常小,检索效率也很高,特别适用于屏蔽词的场合。离线建好 Double Array Trie,推送到线上仅仅需要读入两个内存块就能完成更新,加载过程到了极简。

哪怕是回答出了高效的算法和实现,离一个真正有效的屏蔽词系统还相差很远。首先要清楚一件事,道高一尺,魔高一丈。你平时想过什么办法绕过屏蔽词系统,现在就得想办法对抗你曾经开过的脑洞。下面举几个最常见的例子:

  1. 简繁体混用,大小写混用,全半角混用。首先得做归一化,繁体转简体,大写转小写,全角转半角。
  2. 在屏蔽词中间加特殊字符。原串先过一遍,去掉特殊字符再过一遍。
  3. 字形相近,读音相似。积累相近字典,替换为常用字再过一遍,将所有的字转为拼音再过一遍。
  4. 同义词替换。加屏蔽词时考虑替换场景,或者挖掘替换词库用来替代。

上面这几种方法,说起来简单,做起来都是坑。一不小心,就把正常的内容当成包含屏蔽词干掉了。这就是为啥大家老吐槽在某些网站发帖,动不动就被屏蔽,关键就在于坏招太多,规则多了就有误伤啊!所以一个优秀的屏蔽词系统,还得尽量避免误伤情况,也有一些办法。

  • 先切词,如果命中屏蔽词的范围不在切词的边缘,应该是误伤。最简单的例子是:24口交换机。
  • 添加屏蔽词的例外规则,比如“成人牙刷”需要是“成人”的例外规则。

最近几年机器学习特别火,其实机器学习也特别适合这种场景,就是一个二分类问题嘛。只是超出了简单算法的范畴,这里就不展开了。

所以你看,就一个“屏蔽词过滤的算法逻辑”,就有那么多要探讨的东西。而且以目前国内大部分互联网产品的实现上来看,可能考虑的还没我这篇文章全面。这可真不是一个能轻松就回答完美的问题。

Caffe 神经网络配置 - All in one network

很多人使用 Caffe 配置神经网络的时候,习惯于撰写两个配置文件,一个叫 train_val.prototxt,在训练的时候使用;一个叫 deploy.prototxt,在预测的时候使用。这两个文件的本质区别,往往在输入、输出层不同。train_val.prototxt 里包含 train/test 的输入数据和标签,但出于效率考虑,train/test 都是分 batch 进行的,而输出的往往是 acc/loss;deploy.prototxt 里只包含 test 的输入,而且一般是每次输入一个数据(没有标签),输出的也不是 acc/loss,而是预测值(Top N 类别或者预测概率)。可以把 deploy.prototxt 看成可以往线上部署的网络配置文件,来一个用户请求,执行 network 的 forward,预测返回给用户结果。

这样做没什么不可以,而且很多开源的例子都是这么做的。但实际操作中,有一个很麻烦的地方是,当你在频繁调整模型的时候,每次修改隐层都要同时修改两个 .prototxt 让人很烦恼。Caffe 的配置文件不像 Keras 那样,每层就是简单的一行代码,而是一个 Protobuf 的 txt message,有很多行,这样电脑的一屏显示不全,就需要花精力去仔细 diff 两个文件。

其实我们有更好的办法,使用 Caffe 的 proto 协议实现 All in one network。那就是充分利用 NetStateRule 这个结构,结合 phase 和 stage/not_stage,实现不同场合下 layer 的过滤。

message NetStateRule {
  // Set phase to require the NetState have a particular phase (TRAIN or TEST)
  // to meet this rule.
  optional Phase phase = 1;

  // Set the minimum and/or maximum levels in which the layer should be used.
  // Leave undefined to meet the rule regardless of level.
  optional int32 min_level = 2;
  optional int32 max_level = 3;

  // Customizable sets of stages to include or exclude.
  // The net must have ALL of the specified stages and NONE of the specified
  // "not_stage"s to meet the rule.
  // (Use multiple NetStateRules to specify conjunctions of stages.)
  repeated string stage = 4;
  repeated string not_stage = 5;
}

以 Caffe 里的 example/minist/lenet_train_test.prototxt 为例 ,那怎么把它改成 all in one 的 prototxt 呢?

name: "LeNet"
layer {
  name: "mnist"
  type: "Data"
  top: "data"
  top: "label"
  include {
    phase: TRAIN
  }
  transform_param {
    scale: 0.00390625
  }
  data_param {
    source: "examples/mnist/mnist_train_lmdb"
    batch_size: 64
    backend: LMDB
  }
}
layer {
  name: "mnist"
  type: "Data"
  top: "data"
  top: "label"
  include {
    phase: TEST
  }
  transform_param {
    scale: 0.00390625
  }
  data_param {
    source: "examples/mnist/mnist_test_lmdb"
    batch_size: 100
    backend: LMDB
  }
}

首先,我们要明确解决的是 TEST phase 的冲突(验证集和测试集的 input/output 不同),不用去管 TRAIN phase。而为了解决 TEST phase 的冲突,就需要通过为 NetStateRule 增加参数来实现。min_level/max_level 和 stage/not_stage 都可以做这个事情,但我习惯用 stage,因为文字看起来比数字更直观一些。所以我会在原来的 train_val.prototxt 里再增加一个 TEST 输入层,通过 stage 区分不同的应用场景,如下所示:

layer {
  name: "mnist"
  type: "Data"
  top: "data"
  top: "label"
  include {
    phase: TEST
    not_stage: "predict"    # 在 predict 时过滤掉这一层
  }
  transform_param {
    scale: 0.00390625
  }
  data_param {
    source: "examples/mnist/mnist_test_lmdb"
    batch_size: 100
    backend: LMDB
  }
}
# 增加 deploy 的输入层
layer {
  name: "data"
  type: "Input"
  top: "data"
  input_param { shape: { dim: 1 dim: 1 dim: 28 dim: 28 } }
  include {
    phase: TEST
    stage: "predict"    # 在 predict 时加上这一层
  }
}

在 caffe.bin train 时,由于 solver.prototxt 没有提供特殊的参数,所以只包含 batch_size 100 的 TEST 输入层;在预测的时候,设置 stage='predict' 参数(设置方式下文有介绍),网络的输入层就变成了 dim: 1 的 TEST 输入层了。

同理,对输出层也是一样,在 loss layer 加上 exclude stage: "predict" 的参数,预测时就无需提供 label 和计算 loss 了,如下所示:

layer {
  name: "accuracy"
  type: "Accuracy"
  bottom: "ip2"
  bottom: "label"
  top: "accuracy"
  include {               #
    phase: TEST           #
    not_stage: "predict"  # 在 predict 时过滤掉 accuracy 层
  }                       #
}
layer {
  name: "loss"
  type: "SoftmaxWithLoss"
  bottom: "ip2"
  bottom: "label"
  top: "loss"
  exclude {           # 注意是 exclude
    phase: TEST       #
    stage: "predict"  # 在 predict 时过滤掉 loss 层
  }                   #
}

这样,你就能得到一个 all in one 的网络配置 lenet_train_val_deploy.prototxt,可以统一用它进行训练和预测,修改隐层再也不用拷贝来拷贝去了。其实使用 NetStateRule 可以进行各种组合,其它的参数组合也能实现 all in one 的网络设置,但我上面介绍的这种配置方法有个好处是完全不用修改原来的 solver.prototxt。也就是 default 走 non-predict,显式走 predict。

那怎样显式提供 stage='predict' 参数呢?在 caffe.bin 命令行可以使用:

$ caffe.bin test --stage="predict" --model="train_val_deploy.prototxt" \
--weights="iter_N.caffemodel"

当然,这时候输入层可能要换成其它的类型,不能是 Input 类型,不然 caffe 没法读取数据。使用 Input 类型时,就得用 Python/C++ 来加载数据。使用 stage="predict" 初始化 Python 和 C++ 的方法如下:

Python:
net = caffe.Net("train_val_deploy.prototxt", caffe.TEST, stages=['predict'],
                weights="iter_N.caffemodel")
C++:
caffe::vector<caffe::string> stages;
stages.push_back("predict");
caffe::Net *net = new caffe::Net("train_val_deploy.prototxt", caffe::TEST, 0, &stages);

手机上的 AI - 在 Android/iOS 上运行 Caffe 深度学习框架

目前在云端基于各种深度学习框架的 AI 服务已经非常成熟,但最近的一些案例展示了在移动设备上直接运行深度神经网络模型能够带来很大的处理速度优势。比如 Facebook 在官方博客上发布的可在移动设备上进行实时视频风格转换的应用案例 “Delivering real-time AI in the palm of your hand”。其中提到 Caffe2go 框架加上优化后的网络模型,可以在 iPhone6S 上支持 20FPS 的视频风格转换。Google Tensorflow 也提供了 iOS 和 Android 的 example

Caffe 是一个知名的开源深度学习框架,在图像处理上有着非常广泛的应用。Caffe 本身基于 C++ 实现,有着非常简洁的代码结构,所以也有着很好的可移植性。早年也已经有了几个 github 项目实现了 Caffe 到 iOS/Android 平台的移植。但从我的角度来看,这些项目的编译依赖和编译过程都过于复杂,代码也不再更新,而且最终产出的产品包过大。caffe-compact 最接近我的思路,但是在两年前未完工就已经不更新了。

从我个人在 APP 产品上的经验来看,移植深度学习框架到 APP 中,不仅仅是能不能跑,跑不跑得快,还有个很重要的因素是包大小问题。因为一般用深度学习模型只是实现一个产品功能,不是整个产品。一个产品功能如果对 APP 包大小影响太大,很多 APP 产品都无法集成进去。我希望依赖库能尽量地精简,这样打包进 APP 的内容能尽量地少。所以我在春节期间在 github 上启动了一个 Caffe-Mobile 项目,将 Caffe 移植到 Android/iOS 上,并实现了以下目标:

NO_BACKWARD:手机的电量和计算能力都不允许进行模型训练,所以不如干脆移除所有的后向传播依赖代码,这样生成的库会更小,编译也更快。

最小的依赖。原始的 Caffe 依赖很多第三方库:protobuf, cblas, cuda, cudnn, gflags, glog, lmdb, leveldb, boost, opencv 等。但事实上很多依赖都是没必要的:cuda/cudnn 仅支持 GPU, gflags 仅为了支持命令行工具,lmdb/leveldb 是为了在训练时更高效地读写数据,opencv 是为了处理输入图片,很多 boost 库都可以用 c++0x 库来替换。经过精简和修改部分代码,Caffe-Mobile 的第三方库依赖缩减到两个:protobuf 和 cblas。其中在 iOS 平台上,cblas 用 Accelerate Framework 中的 vecLib 实现;在 Android 平台上, cblas 用交叉编译的 OpenBLAS 实现。

相同的代码基,相同的编译方式。两个平台都采取先用 cmake 编译 Caffe 库(.a or .so),然后再用对应平台的 IDE 集成到 app 中。编译脚本使用同一个 CMakeList.txt,无需将库的编译也放到复杂的 IDE 环境中去完成。

可随 Caffe 代码更新。为了保证开发者能追随最新 Caffe 代码更新,我在修改代码时使用了预编译宏进行分支控制。这样进行 diff/patch 时,如果 Caffe 源码改动较大,merge 时开发者可以清楚地看到哪些地方被修改,是如何改的,更方便 merge 最新更新。

除了 Caffe 库外,在 Caffe-Mobile 项目中还提供了 Android/iOS 两个平台上的最简单的 APP 实现示例 CaffeSimple,展示了在手机上使用 Caffe example 里的 MNIST 示例(深度学习领域的 Hello World)训练出来的 LeNet 模型预测一个手写字符 “8” 图片的过程和结果。 Caffe-Mobile 项目的地址在:https://github.com/solrex/caffe-mobile 欢迎体验,感兴趣的同学们也可以帮忙 Star 下 :)

700行代码帮你迈出打造专属Jarvis的第一步

前几天,Mark Zuckerberg 写了一篇博客《Building Jarvis》 ,立即风靡科技圈。智能家庭,Bill Gates 弄了一个,Zuckerberg 也搞了一个,科技圈的大佬们纷纷动手,让小民们看着很眼馋。

在《Building Jarvis》这篇文章中,Zuckerberg 写到:

These challenges always lead me to learn more than I expected, and this one also gave me a better sense of all the internal technology Facebook engineers get to use, as well as a thorough overview of home automation.

注意到这些酷炫的技术,都是 internal technology Facebook engineers get to use。那么到底有没有可能,使用公开领域的服务,构建一个类似于 Jarvis 的系统呢?

正好这段时间,我也在做一个基于人工智能技术的简单 APP:WhatIsWhat。这个 APP 目前很简单,甚至可以称得上简陋,但可能对你构建自己的 Jarvis 会有所帮助或启发。

什么是什么
什么是什么

背景

某天闲聊的时候,有个妈妈同事说,她家宝宝问她很多东西不懂,只好去搜索,发现百度百科的不少词条有个“秒懂百科”,用视频讲解百科词条,宝宝很爱看。只是可惜宝宝不认字,不会自己搜索。然后我就想,要是有个工具,能用语音问问题,语音或者视频回答问题,那挺不错啊,就有了这个 APP。

随着近几年语音识别准确率的大幅度提升,语音交互技术已经步入到非常成熟的阶段了。公开领域也有讯飞、百度等好几家免费服务可用,只是关注和使用这些的一般都是企业,个人开发者并不多。其实从我工作上的背景出发,语音交互背后的技术都是非常熟悉的。下面我就以我使用的百度语音开放平台为例,解释下能有哪些免费的语音交互服务可用。

语音识别

要想宝宝能使用语音问问题,首先需要有一个语音转文字的技术,我们一般称之为“语音识别”。从 20 世纪 70 年代 IBM 把 HMM 应用到语音识别技术上来以后,语音识别准确率一直在稳步提升。但到了 2000 年以后,语音识别的效果改进停滞了,而且一停就是 10 年。直到 2010年,Geoffrey Hinton、邓力和俞栋在微软研究院将深度学习引入语音识别技术后,平地一声惊雷,语音识别的准确率才又开始一次大跃进。

可以这样说,20 年前的语音识别和六七年前的语音识别,没有太大区别。但现在的语音识别技术,和六七年前的语音识别技术,是有革命性改进的。如果你还根据几年前的经验,认为语音识别是个 Tech Toy,识别结果充满了错漏。不妨试试最新的语音识别产品,比如讯飞语音输入法、百度语音搜索,结果会让你很吃惊的。

值得高兴的是,讯飞和百度都将最新的语音识别技术免费开放给所有人使用。比如百度的语音识别服务,单个应用每天可以免费调用 5 万次,而且可以通过申请提升这个免费上限。只需要到它的平台上注册成为开发者(不需要任何费用),申请新建一个应用,下载最新版的 SDK,参考文档集成到 APP 里就行了。

语音合成

如果想让手机使用语音回答问题,还需要一个文字转语音的技术,我们一般称之为“语音合成”或者“TTS”。语音合成在准确率方面的问题上,没有语音识别那么显著,但更大的困难来自于“怎么让机器发出的声音更像人声?”有很多个方面的考量,比如情绪、重音、停顿、语速、清晰度等等。现代的语音合成产品,一般都支持选择发声人(男声、女声、童声)和调整语速的功能。很多小说阅读器都配备的“语音朗读”,就是语音合成技术的典型应用。

讯飞和百度也都免费开放了自家的语音合成技术,也是类似于语音识别的SDK集成即可。值得一说的是,Google 在今年 9 月发表了自家的 WaveNets 语音合成模型,号称将 TTS 发声和人声的差距缩短了 50%(可以到这个页面体验一下),所以我们可以期待公开的语音合成服务效果有更进一步的改进。

WaveNets 效果
WaveNets 效果

语音唤醒

就像两个人交谈时你必须得称呼对方名字,他才知道你是在对他说话,机器也是一样。对着手机屏幕的时候,可以通过点击麦克风按钮来实现唤醒语音输入,但在远处或者不方便点击时(比如开车),需要用特定的指令唤醒它接收并处理你的输入。就像我们熟悉的“Hey,Siri”和“OK,Google”,我们一般称之为“语音唤醒”。

一般情况下,唤醒指令不依赖语音识别,也就是说,它纯粹是使用声学模型匹配你的声音。这样做也有好处,就是不依赖网络,待机功耗也更低。

讯飞的语音唤醒功能是收费的,但是百度的语音唤醒功能是免费的,可以定制自己的唤醒词,然后下载对应唤醒词的声学模型包,集成到语音识别 SDK 中即可。

如果希望打造一个专属的 Jarvis 的话,这个唤醒词声学模型最好是使用自己的语音训练出来的,这样召准率才能更高。但很遗憾,百度的免费语音唤醒还不支持这点,只能用百度语料库训练出来的模型。

自然语言理解

关于自然语言理解,Zuckerberg 的 《Building Jarvis》已经解释得非常充分了,这是一个非常复杂和困难的技术领域。讯飞和百度也都在自身语音识别能力基础上,开放了自然语言理解的能力。用户甚至可以在云端自定义自己的语义,这样识别后不仅能拿到一个纯文本识别结果,还可以获取结构化的分析后结果。

百度语义理解
百度语义理解

我对 WhatIsWhat 这个 APP 的要求很简单,只需要理解“什么是什么?”这个问题即可。我没有用到百度的语义理解能力,而是简单地写了一个正则表达式匹配,主要是希望后续能充分利用语音识别的 Partial Result 对性能进行优化。

问题回答

目前很多搜索引擎(比如谷歌、百度)对语音发起的搜索,在给出搜索结果的同时,往往附带着一句或者几句语音的回答。但搜索引擎针对的往往是开放领域的搜索词,所以语音回答的覆盖比例并不高。限定到“什么是什么”这个特定的领域,百度百科的满足比例就高了。尤其是秒懂百科,使用视频的方式讲解百科词条,样式非常新颖。

在这个最初的版本中,我只采取了秒懂百科的结果。也就是先抓取百科结果页,提取秒懂百科链接,然后打开秒懂百科结果页。为了让播放视频更方便,我用 WebView 执行了一个自动的点击事件,这样第一条视频结果在打开页面后会直接播放,不需要再点击。

演示视频

下面是“WhatIsWhat”这个 APP 的演示视频,请点击查看,因为录音设备的冲突,视频的后半部分没有声音,敬请谅解。

演示视频,点击查看

源代码地址

你可以到 https://github.com/solrex/WhatIsWhat 这个链接查看“WhatIsWhat”的全部源代码。代码总共 700 多行,不多,需要有一点儿 Android 和 Java 基础来理解。

总结

WhatIsWhat 是从一个朴素 idea 出发的非常简单的 APP,这个产品集成了“语音识别、语音合成、语音唤醒、自然语言理解”几类人工智能服务。想要实现 Jarvis,可能还需要人脸识别、智能对话、开放硬件 API 等几项能力,并且需要一定的工程能力将这些功能整合起来。

虽然 WhatIsWhat 与 Jarvis 的复杂度不可比,但它演示了如何使用公共领域已有的人工智能服务,构造一个落地可用的产品。更重要的是,它便宜到不需花一分钱,简单到只有 700 行代码。

就像 Zuckerberg 所说“In a way, AI is both closer and farther off than we imagine. ”虽然很多人并没有意识到语音交互这类 AI 技术能够那么地触手可及,但技术的开放对 AI 应用普及的影响是巨大的。在这一点上,国内的人工智能产业巨头们做得并不差。这篇文章,WhatIsWhat 这个 APP,只能帮你迈出第一步,希望不远的将来,我们能够有更多的开放 AI 服务,使得搭建自己的专属 Jarvis 变成一件轻而易举的事情。

Android HTTPUrlConnection EOFException 历史 BUG

这是一个影响 Android 4.1-4.3 版本的 HTTPUrlConnection 库 BUG,但只会在特定条件下触发。

我们有一个 Android App,通过多个并发 POST 连接上传数据到服务器,没有加入单个请求重试机制。在某些 Android 机型上发现一个诡异的 bug,在使用中频繁出现上传失败的情况,但是在其它机型上并不能复现。

经过较长时间的排查,我们找到了上传失败出现的规律,并认为它跟 HTTP Keepalive 持久化连接机制有关。具体的规律是:当 App 上传一轮数据后,等待超过服务端 Nginx keepalive_timeout 时间后,再次尝试上传数据,就会出现上传失败,抛出 EOFException 异常。

更准确的特征可以通过连上手机的 adb shell 观察 netstat:当 App 上传一轮数据后,可以观察到有 N 个到服务器的连接处于 ESTABLISHED 状态;当等待超过服务端 Nginx keepalive_timeout 时间后,可以观察到这 N 个到服务器的连接处于 CLOSE_WAIT 状态;当上传失败后,发现部分 CLOSE_WAIT 状态的连接消失。

Java 的 HTTP Keepalive 机制,一直是由底层实现的,理论上来讲,不需要应用层关心。但从上面的 BUG 来看,对于 stale connection 的复用,在部分 Android 机型上是有问题的。为此我稍微研究了一下 Android 的源代码,的确发现了一些问题。

在 2011年12月15日,Android 开发者提交了这样一个 Commit,Commit Message 这样写到:

Change the way we cope with stale pooled connections.

Previously we'd attempt to detect if a connection was stale by
probing it. This was expensive (it relied on catching a 1-millisecond
read timing out with a SocketTimeoutException), and racy. If the
recycled connection was stale, the application would have to catch
the failure and retry.

The new approach is to try the stale connection directly and to recover
if that connection fails. This is simpler and avoids the isStale
heuristics.

This fixes some flakiness in URLConnectionTest tests like
testServerShutdownOutput and testServerClosesOutput.

Bug: http://b/2974888
Change-Id: I1f1711c0a6855f99e6ff9c348790740117c7ffb9

简单来说,这次 commit 做了一件事:在修改前,是在 TCP 连接池获取连接时,做 connection isStale 的探测。Android 开发者认为这样会在获取每个 connection 时都有 1ms 的 overhead,所以改成了在应用层发生异常时,再重试请求。 但是这个重试有个前提,就是用户的请求不能是 ChunkedStreamingMode,不能是 FixedLengthStreamingMode,这两种模式下,底层无法重试。很不幸地是,我们正好使用到了 FixedLengthStreamingMode 带来的特性。

// Code snippet of: libcore.net.http.HttpURLConnectionImpl.java
while (true) {
  try {
    httpEngine.sendRequest();
    httpEngine.readResponse();
  } catch (IOException e) {
    /*
     * If the connection was recycled, its staleness may have caused
     * the failure. Silently retry with a different connection.
     */
    OutputStream requestBody = httpEngine.getRequestBody();
    // NOTE: FixedLengthOutputStream 和 ChunkedOutputStream
    // 不是 instance of RetryableOutputStream
    if (httpEngine.hasRecycledConnection()
        && (requestBody == null || requestBody instanceof RetryableOutputStream)) {
      httpEngine.release(false);
      httpEngine = newHttpEngine(method, rawRequestHeaders, null,
          (RetryableOutputStream) requestBody);
      continue;
    }
    httpEngineFailure = e;
    throw e;
}

由于 BUG 的根源在 Android 的核心库 libcore 中。这次改动影响了从 4.1 到 4.3 的所有 Android 版本, Android 4.4 网络库的 HTTP/HTTPS 从 libcore 切换到 okhttp,所以4.4以后的 Android 版本不受影响。

既然底层不重试,那么只有在应用层重试,所以我们在应用层增加了最多『http.maxConnections+1』次重试机制,以修复此问题。在重试的时候,尝试使用一个 stale connection 会导致 EOFException,底层也会自动关闭这个连接。『http.maxConnections+1』次重试保证即使连接池中全都是 stale connection,我们也能获得一个可用的连接。

网上应该也有人遇到过这个 BUG,所以我也在这个 StackOverflow 问题下做了回答

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 那么丰富了,大家有兴趣也可以尝试一下。

Google App API Protocol - Voice Search

Google 在移动平台(Android 和 iOS)上提供了独立的 Search App,但它不仅仅是用一个移动浏览器封装了 Google Web Search,而是做了很多移动应用相关的改进。这个系列文章,通过抓包对 Android Google App 与 Server 间通讯协议进行简单分析,管中窥豹,以见一斑。

  1. Google App API Protocol - Text Search
  2. Google App API Protocol - Voice Search
  3. Google App API Protocol - Search History

语音搜索

语音搜索与文本搜索不同,必须先进行语音识别(语音转文字),拿到识别结果后才能进行搜索,拿到搜索结果。语音识别过程是一个录音数据流上传过程,一般采取的都是流式分片上传。Google App 的语音搜索,仍然是沿袭 Google 一贯注重效率的风格,使用两个 HTTPS 请求,完成了录音数据的流式上传,以及识别结果、搜索结果和语音播报的流式下发。具体的做法是:

在用户发起语音请求时,Google App 与 Google 服务器同时建立两个 HTTPS POST 连接,以 URL 参数 "pair" 标识这是同一用户的一对连接:

https://www.google.com/m/voice-search/up?pair=4fc4d987-3f06-49d5-9f3a-986937a5e5fe
https://www.google.com/m/voice-search/down?pair=4fc4d987-3f06-49d5-9f3a-986937a5e5fe

Google App 基于 chunked 编码,在 up 连接中实现录音数据流式上传,在 down 连接中实现识别结果、搜索结果和语音播报的流式下发。

语音搜索 up 连接

在 up 连接中,Google App 仅利用了 POST 请求通路的 chunked 编码流式上传录音数据,直到所有数据上传完成,Google 服务器才会返回一个 Content-Length 为 0 的 200 响应消息。而且 POST 请求的 HTTP Header/Params 很简单,仅仅包含基本的信息。

Host	www.google.com
Connection	keep-alive
Transfer-Encoding	chunked
Cache-Control	no-cache, no-store
X-S3-Send-Compressible	1
User-Agent	Mozilla/5.0 (Linux; Android 4.4.4; HM 1S Build/KTU84P)
                AppleWebKit/537.36 (KHTML, like Gecko) Version/4.0 Chrome/33.0.0.0 
                Mobile Safari/537.36 GSA/5.9.33.19.arm
Content-Type	application/octet-stream
Accept-Encoding	gzip, deflate

这里要注意 Cotent-Type 是 application/octet-stream,这代表上传的是二进制数据流,需要用专门的协议才能 decode 到真正内容。这给解析协议带来了很大的困难。简单观察二进制数据流,发现部分内容是遵从 protobuf 协议格式,但直接使用 application/x-protobuffer 的 Dilimited List 封包格式进行 docode 并不成功。无奈之下,只好采取比较笨的方法,观察二进制数据流,跳过那些明显不符合 protobuf 协议格式的部分,尽最大努力把 protobuf 消息先解包出来。然后再根据已经解包出来的部分,逐步推测未解析部分的编码格式。经过较长时间的分析,拿到了 Google App 语音搜索 up 连接的请求消息封包格式大致如下:

(10 bytes Header)
(Big Endian Fixed32 of Msg Len)(Msg)
(Big Endian Fixed32 of Msg Len)(Msg)
......
(Big Endian Fixed32 of Msg Len)(Msg)

对于 Header 长度是否恒为 10 字节,我持怀疑态度,有待通过更多分析发现规律。做了很多二进制码的分析工作,到最后才发现消息结构如此简单,让人不得不抱怨:Google 你直接用和文本搜索一样的 application/x-protobuffer 格式不得了吗?还搞得那么复杂!不过也许有一定历史原因吧。

和文本搜索一样,先建立一个 Empty protobuf Message,逐步去推导流式协议里 Message 的结构,尽最大猜测推导出来的 Google 语音搜索请求消息的 .proto 可能是这样的:

$ more voicesearch.proto
package com.google.search.app;

message VoiceSearchRequest {
    optional int32 fin_stream = 3;
    optional UserInfo user_info = 293000;
    optional VoiceSampling voice_sampling = 293100;
    optional VoiceData voice_data = 293101;
    optional ClientInfo client_info = 294000;
    optional UserPreference user_preference = 294500;
    optional Empty VSR27301014 = 27301014;
    optional Empty VSR27423252 = 27423252;
    optional Double VSR27801516 = 27801516;
    optional GetMethod get_method = 34352150;
    optional Empty VSR61914024 = 61914024;
    optional Empty VSR77499489 = 77499489;
    optional Empty VSR82185720 = 82185720;
}

message UserInfo {
    optional Empty lang = 2;
    optional Empty locale = 3;
    optional string uid = 5;
    optional GoogleNow google_now = 9;
}

message GoogleNow {
	optional string auth_url = 1;
	optional string auth_key = 2;
}

message VoiceSampling {
    optional float sample_rate = 2;
}

message VoiceData {
    optional bytes amr_stream = 1;
}

message ClientInfo {
	optional string type = 2;
	optional string user_agent = 4;
	repeated string expids = 5;
	optional string os = 8;
	optional string model = 9;
	optional string brand = 11;
}

message UserPreference {
    optional Favorites favorites = 1;
    optional Empty UP4 = 4;
    optional Empty UP25 = 25;
}

message Favorites {
	optional string lang = 9;
	repeated Empty favorites_data = 22;
}

message GetMethod {
	optional Empty params = 1;
	optional HttpHeader headers = 2;
	optional string path = 3;
}

message HttpHeader {
    repeated string name = 1;
    repeated string text_value = 2;
    repeated bytes binary_value = 4;
}

基于这个 .proto,对语音输入『北京天气』的 POST 请求消息进行解码,最终的结果摘要如下:

$ more up.txt
######## Data block info: offset=0xa blockSize=3717
#### Proto: Voicesearch.VoiceSearchRequest Message with Size=3654
user_info {
  lang {
    1: "cmn-Hans-CN"
    2: 1
  }
  locale {
    1: "zh_CN"
    2: 2
  }
  uid: "******"
  google_now {
    auth_url: "https://www.googleapis.com/auth/googlenow"
    auth_key: "******"
    7: 1
  }
  8: "w "
}
voice_sampling {
  sample_rate: 16000.0
  3: 9
}
client_info {
  type: "voice-search"
  user_agent: "Mozilla/5.0 (Linux; Android 4.4.4; ......"
  expids: "p2016_01_27_20_58_17"
  expids: "8501679"
  expids: "8501680"
  expids: "8502094"
  expids: "8502157"
  expids: "8502159"
  expids: "8502312"
  expids: "8502347"
  expids: "8502369"
  expids: "8502376"
  expids: "8502490"
  expids: "8502491"
  expids: "8502618"
  expids: "8502679"
  expids: "8502705"
  expids: "8502947"
  expids: "8502986"
  expids: "8503012"
  expids: "8503037"
  expids: "8503109"
  expids: "8503110"
  expids: "8503132"
  expids: "8503133"
  expids: "8503157"
  expids: "8503158"
  expids: "8503208"
  expids: "8503212"
  expids: "8503214"
  expids: "8503303"
  expids: "8503306"
  expids: "8503367"
  expids: "8503368"
  expids: "8503404"
  expids: "8503512"
  expids: "8503559"
  expids: "8503585"
  expids: "8503604"
  expids: "8503606"
  expids: "8503729"
  expids: "8503730"
  expids: "8503751"
  expids: "8503752"
  expids: "8503755"
  expids: "8503805"
  expids: "8503815"
  expids: "8503832"
  expids: "8503835"
  expids: "8503844"
  expids: "8503853"
  expids: "8503855"
  expids: "8503907"
  expids: "8503925"
  expids: "8503927"
  expids: "8503994"
  expids: "8504022"
  expids: "8504059"
  os: "Android"
  model: "KTU84P"
  brand: "HM 1S"
  1: ""
  10: "300601416"
  12: 720
  13: 1280
  14: 320
  17: "assistant-query-entry"
}
user_preference {
  favorites {
    favorites_data {
      1: 2
      2: "fresh"
      9: "cmn-Hans-CN"
    }
    favorites_data {
      1: 2
      2: "favorite-phone"
      9: "cmn-Hans-CN"
    }
    favorites_data {
      1: 2
      2: "favorite-email"
      9: "cmn-Hans-CN"
    }
    favorites_data {
      1: 2
      2: "favorite-person"
      9: "cmn-Hans-CN"
    }
  }
  UP4 {
    1: 10
    2: 250
    3: 1
  }
  UP25 {
    1: 0
  }
  3: 5
  5: 1
  7: 0
  13: 1
  14: 1
  20: 1
  22: 0
}
VSR27301014 {
  1: 460
  2: 0
  3: 460
  4: 0
  5: 1
}
VSR27423252 {
  1: "rbshUd2M8t4"
}
VSR27801516 {
  d7: 0.6037593483924866
}
get_method {
  params {
    1: "noj"
    1: "tch"
    1: "spknlang"
    1: "ar"
    1: "br"
    1: "ttsm"
    1: "client"
    1: "hl"
    1: "oe"
    1: "safe"
    1: "gcc"
    1: "ctzn"
    1: "ctf"
    1: "v"
    1: "padt"
    1: "padb"
    1: "ntyp"
    1: "ram_mb"
    1: "qsubts"
    1: "wf"
    1: "inm"
    1: "source"
    1: "entrypoint"
    1: "action"
    2: "1"
    2: "6"
    2: "cmn-Hans-CN"
    2: "0"
    2: "0"
    2: "default"
    2: "ms-android-xiaomi"
    2: "zh-CN"
    2: "utf-8"
    2: "images"
    2: "cn"
    2: "Asia/Shanghai"
    2: "1"
    2: "5.9.33.19.arm"
    2: "200"
    2: "640"
    2: "1"
    2: "870"
    2: "1458289692542"
    2: "pp1"
    2: "vs-asst"
    2: "and/assist"
    2: "android-assistant-query-entry"
    2: "devloc"
  }
  headers {
    name: "User-Agent"
    name: "X-Speech-RequestId"
    name: "Cookie"
    name: "Host"
    name: "Date"
    name: "X-Client-Instance-Id"
    name: "X-Geo"
    name: "X-Client-Opt-In-Context"
    name: "X-Client-Data"
    text_value: "Mozilla/5.0 (Linux; Android 4.4.4; ......"
    text_value: "rbshUd2M8t4"
    text_value: "******"
    text_value: "www.google.com.hk"
    text_value: "Fri, 18 Mar 2016 08:28:13 GMT"
    text_value: "c6aef75ce70631e9518ae8e7011bb3d7957b24d59b62fd1b9d378262b3690cff"
    text_value: "w CAEQDKIBBTk6MTox"
    binary_value: "\037\213\b\000......"
    binary_value: "\b\257\363\206......gsa"
  }
  path: "/search"
  5: 0
}
VSR61914024 {
  1: 1
}
VSR77499489 {
  1: 1
}
VSR82185720 {
  1: "\b\001"
}
1: "voicesearch-web"
2: 1
4: 0

######## Data block info: offset=0xe93 blockSize=39
#### Proto: Voicesearch.VoiceSearchRequest Message with Size=39
get_method {
  headers {
    name: "X-Geo"
    text_value: "w CAEQDKIBBTE6MTox"
    3: 2
  }
}
2: 1

######## Data block info: offset=0xebe blockSize=309
#### Proto: Voicesearch.VoiceSearchRequest Message with Size=309
voice_data {
  amr_stream: "#!AMR-WB......"
}
2: 1

######## Data block info: offset=0xff7 blockSize=309
#### Proto: Voicesearch.VoiceSearchRequest Message with Size=309
voice_data {
  amr_stream: "......"
}
2: 1

......

######## Data block info: offset=0x4394 blockSize=309
#### Proto: Voicesearch.VoiceSearchRequest Message with Size=309
voice_data {
  amr_stream: "......"
}
2: 1

######## Data block info: offset=0x44cd blockSize=267
#### Proto: Voicesearch.VoiceSearchRequest Message with Size=267
voice_data {
  amr_stream: "......"
}
2: 1

######## Data block info: offset=0x45dc blockSize=4
#### Proto: Voicesearch.VoiceSearchRequest Message with Size=4
fin_stream: 1
2: 1

语音搜索 down 连接

在 down 连接中,Google App 仅利用了 POST 响应通路的 chunked 编码流式下发识别结果、搜索结果和语音播报数据。App 发起的虽然是一个 POST 请求,但在请求中并没有任何 POST Data,Content-Length 为 0。响应消息的 header 如下:

Content-Type	application/vnd.google.octet-stream-compressible
Content-Disposition	attachment
Cache-Control	no-transform
X-Content-Type-Options	nosniff
Pragma	no-cache
Content-Encoding	gzip
Date	Fri, 18 Mar 2016 08:28:14 GMT
Server	S3 v1.0
X-XSS-Protection	1; mode=block
X-Frame-Options	SAMEORIGIN
Alternate-Protocol	443:quic,p=1
Alt-Svc	quic=":443"; ma=2592000; v="31,30,29,28,27,26,25"
Transfer-Encoding	chunked

这里值得注意的,仍然是 Cotent-Type,这次是 application/vnd.google.octet-stream-compressible,又一个二进制私有协议数据流。通过与 up 流分析类似的方法,发现 Google App 语音搜索 down 连接的响应消息封包格式大致如下:

(4 bytes Header)
(Big Endian Fixed32 of Msg Len)(Msg)
(Big Endian Fixed32 of Msg Len)(Msg)
......
(Big Endian Fixed32 of Msg Len)(Msg)

可以看到,除了 Header 长度不同以外,基本与 up 连接的请求消息封包格式一样。采取同样的方式推测到 Google 语音搜索响应消息的 .proto 可能是这样的:

$ more voicesearch.proto
package com.google.search.app;
message VoiceSearchResponse {
    optional int32 fin_stream = 1;
    optional RecogBlock recog_block = 1253625;
    optional SearchResult search_result = 39442181;
    optional TtsSound tts_sound = 28599812;
}

message RecogBlock {
    optional RecogResult recog_result = 1;
    optional VoiceRecording voice_recording = 2;
    optional string inputLang = 3;
    optional string searchLang = 4;
}

message RecogResult {
    optional CandidateResults can = 3;
    repeated RecogSegment recog_segment = 4;
    optional CandidateResults embededi15 = 5;
}

message VoiceRecording {
    optional int32 record_interval = 3;
}

message RecogSegment {
    optional DisplayResult display = 1;
    optional int32 seg_time = 3;
}

message DisplayResult {
    optional string query = 1;
    optional double prob = 2;
}

message CandidateResults {
    optional CandidateResult can3 = 3;
    optional Empty can4 = 4;
}

message CandidateResult {
    repeated string query = 1; 
    repeated string queryWords = 12; 
    optional float res2 = 2;
    repeated CandidateInfo res7 = 7;
}

message CandidateInfo {
    optional CandidateInfoMore inf1 = 1;
}

message CandidateInfoMore {
    optional CandidateInfoMoreDetial more1 = 1;
    optional string more3 = 3;
}

message CandidateInfoMoreDetial {
    optional string type = 1;
    optional string detial2 = 2;
    optional float detial3 = 3;
    optional CandidateInfoMoreDetialSnip detial7 = 7;
    optional string detial8 = 8;
}

message CandidateInfoMoreDetialSnip {
    optional string query = 1;
}

message SearchResult {
    optional string header = 1;
    optional bytes bodyBytes = 3;
}

message TtsSound {
    optional bytes sound_data = 1;
    optional int32 fin_stream = 2;
    optional Empty code_rate = 3;
}

message Empty {
}

基于这个 .proto,对语音输入『北京天气』的 down 响应消息进行解码,最终的结果摘要如下:

$ more down.txt
######## Raw Data block info: offset=0x4 size=41
#### Proto: Voicesearch.VoiceSearchResponse Message with Size=41
recog_block {
  voice_recording {
    record_interval: 140000
    1: 0
    2: 0
  }
  inputLang: "cmn-hans-cn"
  searchLang: "cmn-Hans-CN"
}

######## Raw Data block info: offset=0x31 size=61
#### Proto: Voicesearch.VoiceSearchResponse Message with Size=61
recog_block {
  recog_result {
    recog_segment {
      display {
        query: "北"
        prob: 0.01
      }
      seg_time: 1500000
      2: 0
    }
    1: 0
    2: 0
  }
  inputLang: "cmn-hans-cn"
  searchLang: "cmn-Hans-CN"
}

######## Raw Data block info: offset=0x72 size=64
#### Proto: Voicesearch.VoiceSearchResponse Message with Size=64
recog_block {
  recog_result {
    recog_segment {
      display {
        query: "北京"
        prob: 0.01
      }
      seg_time: 1560000
      2: 0
    }
    1: 0
    2: 0
  }
  inputLang: "cmn-hans-cn"
  searchLang: "cmn-Hans-CN"
}

######## Raw Data block info: offset=0xb6 size=67
#### Proto: Voicesearch.VoiceSearchResponse Message with Size=67
recog_block {
  recog_result {
    recog_segment {
      display {
        query: "北京天"
        prob: 0.01
      }
      seg_time: 1980000
      2: 0
    }
    1: 0
    2: 0
  }
  inputLang: "cmn-hans-cn"
  searchLang: "cmn-Hans-CN"
}

######## Raw Data block info: offset=0xfd size=71
#### Proto: Voicesearch.VoiceSearchResponse Message with Size=71
recog_block {
  recog_result {
    recog_segment {
      display {
        query: "北京天气"
        prob: 0.01
      }
      seg_time: 2100000
      2: 0
    }
    1: 0
    2: 0
  }
  inputLang: "cmn-hans-cn"
  searchLang: "cmn-Hans-CN"
}

######## Raw Data block info: offset=0x148 size=71
#### Proto: Voicesearch.VoiceSearchResponse Message with Size=71
recog_block {
  recog_result {
    recog_segment {
      display {
        query: "北京天气"
        prob: 0.9
      }
      seg_time: 2700000
      2: 0
    }
    1: 0
    2: 0
  }
  inputLang: "cmn-hans-cn"
  searchLang: "cmn-Hans-CN"
}

######## Raw Data block info: offset=0x193 size=14
#### Proto: Voicesearch.VoiceSearchResponse Message with Size=14
recog_block {
  voice_recording {
    1: 1
    2: 2100000
  }
}

######## Raw Data block info: offset=0x1a5 size=40
#### Proto: Voicesearch.VoiceSearchResponse Message with Size=40
recog_block {
  voice_recording {
    1: 2
    2: 3570000
  }
  inputLang: "cmn-hans-cn"
  searchLang: "cmn-Hans-CN"
}

######## Raw Data block info: offset=0x1d1 size=491
#### Proto: Voicesearch.VoiceSearchResponse Message with Size=484
recog_block {
  recog_result {
    can {
      can3 {
        query: "北京天气"
        query: "北京天気"
        query: "北京天器"
        res2: 0.9156357
        queryWords: "北 京 天 气"
        queryWords: "北 京 天 気"
        queryWords: "北 京 天 器"
        6: "\020\n\030\001"
      }
      1: 0
      2: 3570000
    }
    embededi15 {
      can3 {
        query: "北京天气"
        query: "北京天気"
        query: "北京天器"
        res2: 0.9156357
        res7 {
          inf1 {
            more1 {
              type: "literal"
              detial2: "北京天气"
              detial3: 1.0
              detial7 {
                query: "北京天气"
                2: 0
                3: 75
              }
              detial8: "北 京 天 气"
            }
            more3: ""
          }
        }
        res7 {
          inf1 {
            more1 {
              type: "literal"
              detial2: "北京天気"
              detial3: 1.0
              detial7 {
                query: "北京天気"
                2: 0
                3: 75
              }
              detial8: "北 京 天 気"
            }
            more3: ""
          }
        }
        res7 {
          inf1 {
            more1 {
              type: "literal"
              detial2: "北京天器"
              detial3: 1.0
              detial7 {
                query: "北京天器"
                2: 0
                3: 75
              }
              detial8: "北 京 天 器"
            }
            more3: ""
          }
        }
        queryWords: "北 京 天 气"
        queryWords: "北 京 天 気"
        queryWords: "北 京 天 器"
      }
      1: 0
      2: 3570000
    }
    1: 1
    2: 0
  }
  inputLang: "cmn-hans-cn"
  searchLang: "cmn-Hans-CN"
}

######## Raw Data block info: offset=0x3c0 size=29759
#### Proto: Voicesearch.VoiceSearchResponse Message with Size=29759
search_result {
  header: "HTTP/1.1 200 OK
  Content-Type: application/x-protobuffer
  Date: Fri, 18 Mar 2016 08:28:17 GMT
  Expires: -1
  Cache-Control: no-store
  Set-Cookie: ******
  Trailer: X-Google-GFE-Current-Request-Cost-From-GWS
  Set-Cookie: ******
  Content-Disposition: attachment; filename=\"f.txt\"
  
  "
  bodyBytes: "\301R\n\026IbzrVsTgFsK0jwP1iY34CQ .... charset=UTF-8H\001"
  2: 1
  4: 0
}
## Bodybytes Proto: Textsearch.SearchResponse with Size=10561
search_id: "IbzrVsTgFsK0jwP1iY34CQ"
msg_type: 97000
result {
  fin_stream: 0
  text_data: "北京天气"
  html_data: "<!doctype html><html ......</script>"
  encoding: "text/html; charset=UTF-8"
  9: 1
}
## Bodybytes Proto: Textsearch.SearchResponse with Size=16951
search_id: "IbzrVsTgFsK0jwP1iY34CQ"
result {
  fin_stream: 0
  html_data: "<style data-jiis=\"cc\" ......</script>"
  encoding: "text/html; charset=UTF-8"
  9: 1
}
## Bodybytes Proto: Textsearch.SearchResponse with Size=1511
......

######## Raw Data block info: offset=0x7803 size=81
#### Proto: Voicesearch.VoiceSearchResponse Message with Size=81
search_result {
  bodyBytes: "D\n\026IbzrVsTgFsK0jwP1iY34CQ\......"
  2: 1
  4: 0
}
## Bodybytes Proto: Textsearch.SearchResponse with Size=68
......

######## Raw Data block info: offset=0x7858 size=107685
#### Proto: Voicesearch.VoiceSearchResponse Message with Size=107685
......

## Bodybytes Proto: Textsearch.SearchResponse with Size=103014
......
## Bodybytes Proto: Textsearch.SearchResponse with Size=2454
......
## Bodybytes Proto: Textsearch.SearchResponse with Size=2194
......

######## Raw Data block info: offset=0x21d01 size=8480
#### Proto: Voicesearch.VoiceSearchResponse Message with Size=8480
......
## Bodybytes Proto: Textsearch.SearchResponse with Size=7260
......
## Bodybytes Proto: Textsearch.SearchResponse with Size=1202
......

######## Raw Data block info: offset=0x23e25 size=1615
#### Proto: Voicesearch.VoiceSearchResponse Message with Size=1615
tts_sound {
  sound_data: "\377\363@\304\......"
  code_rate {
    1: 22050
  }
}

######## Raw Data block info: offset=0x24478 size=1609
#### Proto: Voicesearch.VoiceSearchResponse Message with Size=1609
tts_sound {
  sound_data: "k\224ed4= \213......"
}

######## Raw Data block info: offset=0x24ac5 size=1609
#### Proto: Voicesearch.VoiceSearchResponse Message with Size=1609
......

######## Raw Data block info: offset=0x25112 size=1609
#### Proto: Voicesearch.VoiceSearchResponse Message with Size=1609
......

######## Raw Data block info: offset=0x2575f size=1609
#### Proto: Voicesearch.VoiceSearchResponse Message with Size=1609
......

######## Raw Data block info: offset=0x25dac size=1518
#### Proto: Voicesearch.VoiceSearchResponse Message with Size=1518
......

######## Raw Data block info: offset=0x2639e size=7
#### Proto: Voicesearch.VoiceSearchResponse Message with Size=7
tts_sound {
  fin_stream: 1
}

######## Raw Data block info: offset=0x263a9 size=2
#### Proto: Voicesearch.VoiceSearchResponse Message with Size=2
fin_stream: 1

协议分析和启发

针对以上解码结果,对 Google App 语音搜索协议分析如下:

双向流式通信模式

上传音频采用流式方式,这个并不难想,但是识别结果、搜索结果和语音播报音频流全部在一个流里回传,需要做很多复杂的架构升级工作,带来的收益也是很明显的:

  1. 识别结果实时上屏。语音识别在解码时,需要收集到足够的语音流之后,才能识别出来文字,也就是说文字结果的出现时间比较随机。流式的识别结果下发能实现一旦有识别中间结果,就可以用最快的速度下发到 App 端展示给用户。
  2. 减少一次搜索请求开销。从逻辑上讲,应该先进行语音识别,再用识别出的 Query 发起搜索。但 Google 把这一步放在了服务端,不需要用户再发起一次搜索结果的 GET 请求。因为 Google Search 的域名和 locale 有关,新的 GET 请求可能需要发给 google.com.hk,这就需要 App 新建一个 HTTPS 连接,开销还是比较大的。而且服务器端还可以进一步优化,比如在识别出中间结果的同时请求即时搜索,不知道 Google 有没有做。
  3. 减少一次语音播报请求开销。原理同上
  4. 提升了 TCP 信道利用率。在同等传输数据量下,减少网络连接数,受 TCP 拥塞控制策略影响,TCP 信道的传输性能能得到一定提升。

录音小块回传

从 up 解码结果来看,Google App 音频流的是以固定每 300 字节一个封包,基于 AMR-WB 压缩这基本相当于 100ms 左右的录音。说明录音数据的上传还是很频繁的,这也能够让服务端尽早地识别出中间结果。还有就是,300字节的设计比较容易 fit in 1500 左右的以太网 MTU、576 的 3G、4G MTU。

搜索结果内置

搜索结果内置,其实相当于在服务器端『代理』App 发起一次内网搜索请求,那服务器端必须要知道正常的 App 请求参数是怎样的。所以在 App 端发起语音请求时,首先向服务器端传送了一些 App 端的配置信息,比如语言、地域、终端类型、用户偏好、搜索参数、搜索 Header 等。有了这些信息,服务器端就可以伪装成 App,通过内网发起搜索请求,获取搜索结果然后把结果内置到语音搜索结果里。但注意到中文语音搜索和文本搜索的域名不同,分别是 google.com 和 google.com.hk,在机房部署上如何高效地实现全球机房的高效内网访问,这仍然是个架构难题,这里无法窥知答案。

对文本搜索结果的分析我们了解到,Google App 的搜索结果是用 Protobuf Message 数组的方式下传的。但语音搜索并没有使用与文本搜索相同的数组元素 Message,所以文本搜索结果是以 bytes 方式,将序列化后的文本搜索 Message 放到语音搜索 Message 中的一个字段中。这也许是为了协议解耦,避免单方面协议改动带来的同步问题。但可能是基于效率考虑,多个文本搜索 Message 可能会被放到同一个语音搜索 Message 中,也是以 Dilimited List 的方式序列化后放入。语音搜索模块解码出来 bytes 之后,可以直接塞给文本搜索的渲染模块渲染,与文本搜索接收的协议格式完全相同。

语音播报

语音播报的音频也是以流式下传,这样可以边播边收,也有效率优势。

Google App API Protocol - Text Search

Google 在移动平台(Android 和 iOS)上提供了独立的 Search App,但它不仅仅是用一个移动浏览器封装了 Google Web Search,而是做了很多移动应用相关的改进。这个系列文章,通过抓包对 Android Google App 与 Server 间通讯协议进行简单分析,管中窥豹,以见一斑。

  1. Google App API Protocol - Text Search
  2. Google App API Protocol - Voice Search
  3. Google App API Protocol - Search History

HTTPS 抓包分析

Google Service 已经全面普及了 HTTPS 接入,所以想探索 Google 的通讯协议,首先必备的是 HTTPS 抓包能力。所谓的 HTTPS 抓包,实质上是通过代理服务器实现对测试手机上 HTTPS 连接的中间人攻击,所以必须在测试手机上安装代理服务器的 CA 证书,才能保证测试手机相信 HTTPS 连接是安全的。

有很多测试用代理服务器支持 HTTPS 抓包,例如 FiddlerCharles,HTTPS 配置具体可以参见它们的官方文档:Configure Fiddler to Decrypt HTTPS TrafficSSL CERTIFICATES.

文本 IS 请求

Google App 上的文本搜索请求,并不一定以用户按下搜索按钮才开始,而是在输入过程中就可能发生,类似于 Instant Search 即时搜索。这一切发生在输入文本过程中的 "/s?" 请求内。

Google 在接口上,已经将搜索推荐和即时搜索合二为一,通过发起对 "https://www.google.com[.hk]/s?" 的 GET 请求,根据用户已经输入的短语,获取搜索推荐词。如果 Google 认为用户已经完成输入,它会在这个请求的应答消息中直接返回搜索结果。

以小米手机上安装的 Google App 为例,当用户输入『上海』这个词时,GET 请求的参数,主要有以下这些:

noj	1
q	上海
tch	6
ar	0
br	0
client	ms-android-xiaomi
hl	zh-CN
oe	utf-8
safe	images
gcc	cn
ctzn	Asia/Shanghai
ctf	1
v	5.9.33.19.arm
biw	360
bih	615
padt	200
padb	640
ntyp	1
ram_mb	870
qsd	3670
qsubts	1458723210129
wf	pp1
action	devloc
pf	i
sclient	qsb-android-asbl
cp	2
psi	bLxzwaswPFc.1458723200693.3
ech	2
gl	us
sla	1

请求的 HTTP Header,主要有以下这些:

Connection	keep-alive
Cache-Control	no-cache, no-store
Date	Wed, 23 Mar 2016 08:53:26 GMT
X-Client-Instance-Id	c6aef75ce70631e9518ae8e7011bb3d7957b24d59b62f...
Cookie	******
X-Geo	w CAEQDKIBBTk6MTox
X-Client-Opt-In-Context	H4sIAAAAAAAAAONi4WAWYBD4DwOMUiwcj...
X-Client-Discourse-Context	H4sIAAAAAAAAAB1PS07DMBSUehe...
X-Client-Data	CM72hgQIjfeGBAiP94YECKj4hgQIy...
User-Agent	Mozilla/5.0 (Linux; Android 4.4.4; HM 1S Build/KTU84P)
 AppleWebKit/537.36 (KHTML, like Gecko) Version/4.0 Chrome/33.0.0.0 Mobile
 Safari/537.36 GSA/5.9.33.19.arm
Accept-Encoding	gzip, deflate, sdch

文本 IS 应答消息解码

文本 IS 应答消息的 HTTP Header 如下所示:

HTTP/1.1 200 OK
Content-Type	application/x-protobuffer
Date	Wed, 23 Mar 2016 08:56:47 GMT
Expires	-1
Cache-Control	no-store
Content-Disposition	attachment; filename="f.txt"
Content-Encoding	gzip
Server	gws
X-XSS-Protection	1; mode=block
X-Frame-Options	SAMEORIGIN
Alternate-Protocol	443:quic,p=1
Alt-Svc	quic=":443"; ma=2592000; v="31,30,29,28,27,26,25"
Transfer-Encoding	chunked

这里最值得关注的,是 Content-Type。application/x-protobuffer 不是一个常见的 Media Type,起初我以为它就是简单的 protobuffer message 序列化二进制内容,搜索到的一些信息也是这样说的,但用 protobuf 对其 Decode,并不能正确解析消息体。后来我还是在 Charles 的这篇文档中找到了思路,其实 application/x-protobuffer 在实现时区分单个消息和多个消息的格式(但 Content-Type 里并不显式说明)。多个消息,即 Dilimited List,的封包协议是这样的:

(Varint of Msg Len)(Msg)(Varint of Msg Len)(Msg)...(Varint of Msg Len)(Msg)EOF

解包时也很简单,Protobuf 的 Java 库提供了 Message.Builder.mergeDelimitedFrom(...) 来直接从 InputStream 里循环读取多个 Message 的封包数据。

但这时候我们还不知道应答消息里的 protobuf Message 格式,无法构建 Message 的 Builder。这时候有个简单的办法去逐步推导,也就是新建一个 Empty Message,如下所示:

$ more textsearch.proto
message Empty {}

用这个 Empty Message 构建 Builder,对 IS 的应答消息进行 Decode,将 Decode 结果打印出来时会发现所有的字段都是无名字段。然后根据对 protobuf wire data 的理解,逐步推导它的 Message 格式,尽最大的努力去猜测各个字段的作用,最终推导出来 IS 应答消息的 .proto 可能是这样的:

$ more textsearch.proto
package com.google.search.app;

message SearchResponse {
    required string search_id = 1;
    optional uint32 msg_type = 4;
    optional SearchResultPart sug = 100;
    optional SearchResultPart result = 101;
    optional Empty SR102 = 102;
}

message SearchResultPart {
    optional uint32 fin_stream = 1;
    optional string text_data = 2;
    optional string html_data = 7;
    optional string encoding = 8;
}

message Empty {
}

基于这个 .proto,对 Query 『上海天气』 IS 的应答消息进行 Decode,最终的结果摘要如下:

$ more s.txt
#### Proto: Textsearch.SearchResponse with Size=758
search_id: "iVnyVrChHsTAjwPdh4PwBA"
msg_type: 97000
sug {
  fin_stream: 1
  text_data: "[\"上海天气\",[[\"上海天气\",35,[39,70],......}]"
}

#### Proto: Textsearch.SearchResponse with Size=10561
search_id: "iVnyVsnMH8TAjwPdh4PwBA"
msg_type: 97000
result {
  fin_stream: 0
  text_data: "上海天气"
  html_data: "<!doctype html><html itemscope=\"\" ......</script>"
  encoding: "text/html; charset=UTF-8"
  9: 1
}
#### Proto: Textsearch.SearchResponse with Size=16951
search_id: "iVnyVsnMH8TAjwPdh4PwBA"
result {
  fin_stream: 0
  html_data: "<style data-jiis=\"cc\" id=\"gstyle\">......</script>"
  encoding: "text/html; charset=UTF-8"
  9: 1
}
#### Proto: Textsearch.SearchResponse with Size=1511
search_id: "iVnyVsnMH8TAjwPdh4PwBA"
result {
  fin_stream: 0
  html_data: "<title>上海天气 - Google 搜索</title></head><body ......</script>"
  encoding: "text/html; charset=UTF-8"
  9: 1
}
#### Proto: Textsearch.SearchResponse with Size=68
search_id: "iVnyVsnMH8TAjwPdh4PwBA"
result {
  fin_stream: 0
  html_data: ""
  encoding: "text/html; charset=UTF-8"
  3: 0
  9: 1
}
SR102 {
  1: 1
  4: ""
}
#### Proto: Textsearch.SearchResponse with Size=104557
search_id: "iVnyVsnMH8TAjwPdh4PwBA"
result {
  fin_stream: 0
  html_data: "<div data-jiis=\"cc\" id=\"doc-info\">......</script>"
  encoding: "text/html; charset=UTF-8"
  4: 8
  4: 10
  4: 6
  4: 13
  4: 12
  4: 2
  4: 21
  4: 20
  9: 1
  10: 1
}
#### Proto: Textsearch.SearchResponse with Size=2198
search_id: "iVnyVsnMH8TAjwPdh4PwBA"
result {
  fin_stream: 0
  html_data: "<script>google.y.first.push(function()......</script>"
  encoding: "text/html; charset=UTF-8"
  9: 1
}
#### Proto: Textsearch.SearchResponse with Size=2146
search_id: "iVnyVsnMH8TAjwPdh4PwBA"
result {
  fin_stream: 0
  html_data: "<script>......</script>"
  encoding: "text/html; charset=UTF-8"
  9: 1
}
#### Proto: Textsearch.SearchResponse with Size=7261
search_id: "iVnyVsnMH8TAjwPdh4PwBA"
result {
  fin_stream: 0
  html_data: "<script>......</script>"
  encoding: "text/html; charset=UTF-8"
  9: 1
}
#### Proto: Textsearch.SearchResponse with Size=1202
search_id: "iVnyVsnMH8TAjwPdh4PwBA"
result {
  fin_stream: 1
  html_data: " <div id=\"main-loading-icon\" ......</div></body></html>"
  encoding: "text/html; charset=UTF-8"
  9: 1
}

观察到 sug_data 看似是 JSON 格式的数据,专门对 sug_data 进行 JSON Decode,得到以下结果:

## JSONArray: sug_data ##
[
  "上海天气",
  [
    [
      "上海天气",
      35,
      [
        39,
        70
      ],
      {
        "ansc": "1458723207451",
        "ansb": "2338",
        "du": "/complete/deleteitems?client=qsb-android-asbl&delq=上海天气
               &deltok=AKtL3uTL0hK_EMlKCgutzvQvzXfh2VRAgg",
        "ansa": {"l": [
          {"il": {"t": [{
            "tt": 13,
            "t": "上海天气"
          }]}},
          {"il": {
            "at": {
              "tt": 12,
              "t": "周三"
            },
            "t": [
              {
                "tt": 1,
                "t": "54"
              },
              {
                "tt": 3,
                "t": "°F"
              }
            ],
            "i": {
              "d": "//ssl.gstatic.com/onebox/weather/128/partly_cloudy.png",
              "t": 3
            }
          }}
        ]},
        "zc": 602
      }
    ],
    [
      "上海天气<b>预报<\/b>",
      0,
      [],
      {"zc": 601}
    ],
    [
      "上海天气<b>预报10天<\/b>",
      0,
      [],
      {"zc": 600}
    ],
    [
      "上海天气<b>预报15天<\/b>",
      0,
      [],
      {"zc": 551}
    ]
  ],
  {
    "q": "W9D2ISTC-TXK4QauyTt2SFqJzvo",
    "n": 0
  }
]

非 IS 搜索请求和搜索应答解码

当 IS 应答消息里有搜索结果时,点击搜索按钮不会再发起一次搜索。但如果 IS 应答只有 SUG,没有搜索结果,Google App 就会发起一次非 IS 的正常搜索请求。这次请求除了请求的 URL path 从 "/s" 变成 "/search" 以外,主要的 GET 参数保持一致,会有部分附加参数的不同。以『上海天气』(有 IS 结果)和『上海天气好不好呢』(无 IS 结果)为例,GET 参数有以下区别:

-qsd	3670
-pf	i
-sclient	qsb-android-asbl
-cp	4
-psi	bLxzwaswPFc.1458723200693.3
-ech	3
-gl	us
-sla	1
+gs_lp	EhBxc2ItYW5kcm9pZC1h...
+source	and/assist
+entrypoint	android-assistant-query-entry

而非 IS 搜索应答和 IS 应答对比,区别主要在于非 IS 搜索应答消息中,没有搜索词 SUG Message 包。

协议分析和启发

请求消息协议

搜索请求是通过 GET 协议实现的,所以请求主要分为两部分:HTTP 头和 GET 参数。从请求上来看,Google 对 GET 参数的使用是非常节省的,很多字段都是极其精简的缩写。但它倒是在 HTTP 头里放了很多比较大的数据字段,从 Header 名来猜测,应该是跟设备、登录用户相关的一些加密字段。

因为搜索请求是 App 发出的,所以理论上 GET 请求和 POST 请求的实现难度是差不多的,POST 的时候可以进行数据压缩,Header 倒是不能压缩(HTTP 1.x)。那为什么 Google 反而选择把这么长的数据放在 HTTP Header 里呢?我的猜测是为了充分利用 HTTP/2 的特性。在 HTTP/2 里有个特性,叫做 Header Compression,在多次请求时,同一个 Header 原文仅需要压缩传输一次即可。但由于现在还没有 HTTP/2 的抓包工具,所以还无法判断 Google App 是已经用上了这个特性,还是为未来的使用做好准备。不过这至少给了我们一个启发,为了充分利用底层协议的特性,应用层约定可能也需要一些适配工作。

应答消息协议

Google App 的搜索结果,并没有像普通网站服务一样,直接用标准的 HTML 协议返回一个 Web Page。而是将渲染好的 Web Page 分段放到应答消息中,由 App 端提取、拼接成最终的搜索结果页。猜测有以下几点考虑:

  1. 便于与 SUG 服务集成。很多搜索框都提供 Sug 功能,但 Google 为了让用户感觉更快,在输入过程中不仅有 Sug,还会直接显示搜索结果,桌面版上叫做『即时搜索』。移动版 App 的做法跟桌面版类似,但实现上有不同的地方。移动 App 的输入框不是 HTML 的 <input> 标签,而是一个系统原生的输入框,所以无法依赖 Javascript 去响应事件,刷新结果页。而且网络请求是 App 发起的,为了充分利用网络连接,将搜索结果集成到 SUG 结果里也是顺理成章的事情。不过这还意味着在 App 上,不能仅返回数据通过 Ajax 技术无缝刷新结果页,必须得在消息里返回整个搜索结果页。
  2. 减少解码内存使用,改善性能。如果将整个搜索结果页放到一个 Protobuf Message 中,客户端为了解码这个消息,需要申请很大一块内存。而在移动设备上,内存是很 critical 的资源,尤其是在 Android 设备上,使用大块内存会导致频繁的 GC,性能很差。
  3. 模拟 Chunked 编码。Web 服务器可以通过 HTTP 1.1 引入的 Chunked transfer encoding 将网页分块传输给浏览器,浏览器无需等待网页传输结束,就能够开始页面渲染。当网页通过 Protobuf Message 传输时,无法利用浏览器的 chunked 处理技术,只好用分拆为多个 Message 的方式模拟 chunked 模式。虽然 Android 原生的 Webview 并没有支持 chunked 的 LoadData 接口,相信 Google 自己的 App 实现一个类似功能并不困难。

但 Google 这种直接下发网页数据的做法,也存在一个问题,就是没有合法的网页 URL。合法的网页 URL,有以下几个潜在的作用,Google App 做了一些额外的工作来处理:

  1. 刷新页面。Google App 没有提供页面刷新功能;
  2. 前进后退。Google App 没有提供前进后退功能,而是通过 Search History 来满足后退功能。
  3. 浏览历史。Google App 没有提供浏览历史,只提供了搜索历史。
  4. 页面分享。Google App 没有提供页面分享功能。

Android 版本的 Google App 连搜索结果都需要用第三方浏览器打开,结合上述功能处理,可以发现 Android 版本 Google App 只是想做一个精悍的搜索应用,无意于把自己变成一个完善的浏览器。但 iOS 版本 Google App 对上述问题的处理略有不同,iOS 版本内置了一个浏览器,搜索结果可以在 App 内打开。但主要的搜索结果页,仍然是采用类似于 Android 的方式处理。也就是说,iOS 版本的浏览器,可能仅仅是一个 UIWebview。

寻找更快的平方根倒数算法

机器学习的模型相关计算中,有很多诡异的运算。单个运算的开销很不起眼,但如果这些运算的量足够大,也会对性能产生一定的影响。这里谈的就是一个简单的运算:

a = b / sqrt(c);

对于 C/C++ 语言的程序员来说,sqrt 已经是非常基础的库函数,它的底层实现也仅仅是简单的一句 FSQRT (双精度是 SQRTSD) 指令,看起来没有什么优化的余地。但事实上 intel 提供了一个更快的指令,那就是 SQRTSS,利用这条指令,平方根倒数的计算速度可以达到 sqrt 版本的两倍(实测,与[1]相同)。你可以这样使用它:

#include <xmmintrin.h>
...
__m128 in = _mm_load_ss(&c);
__m128 out = _mm_sqrt_ss(in);
_mm_store_ss(&c, out);
a = b/c;
...

但这就是优化的尽头了么?不,单就求平方根倒数来说,还有一个神奇的近似算法,叫做 Fast Inverse Square Root平方根倒数速算法)。一个神人在 Quake III Arena 游戏中使用了一个神奇的数字 0x5f3759df,创造了这个神奇的算法,这个算法可以将平方根倒数的计算速度提升到 sqrt 的 3 倍多(实测,效果比[1]差)。

float Q_rsqrt( float number )
{
        long i;
        float x2, y;
        const float threehalfs = 1.5F;
 
        x2 = number * 0.5F;
        y  = number;
        i  = * ( long * ) &y;                       // evil floating point bit level hacking
        i  = 0x5f3759df - ( i >> 1 );               // what the fuck?
        y  = * ( float * ) &i;
        y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
//      y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed
 
        return y;
}

但 3 倍就是优化的尽头了么?很不幸,邪恶的 Intel 提供了这样一条指令 RSQRTSS,从硬件上支持了这个近似算法。利用这条指令,平方根倒数的计算速度能够达到 sqrt 版本的 6 倍以上!!!

#include <xmmintrin.h>
...
    __m128 in = _mm_load_ss(&c);
    __m128 out = _mm_rsqrt_ss(in);
    _mm_store_ss(&c, out);
    a = b*c;
...

虽然平方根倒数速算法只是一种近似算法,并且只有单精度版本,但是对 RSQRTSS 指令的简单测试发现大部分情况下误差在万分之一以下,指令说明书中给出的误差是 ±1.5*2^-12[2],在非精确数值计算的工程系统中已经足够用了。

它带来的一个更有趣的后果是:如果使用 RSQRTSS 计算出来 c 的平方根倒数,然后再乘以 c,就得到了 c 的平方根近似值。用它可以反过来加速 sqrt 的运算![1]

注1:编译相关程序时,需要打开优化开关,以实现函数的 inline
注2:RSQRTSS 和 SQRTSS 均有一个向量版本,如 RSQRTPS,可以同时计算 4 个 float 的平方根倒数;

[1] Timing square root
[2] RSQRTSS

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 带来的好处还是有吸引力的,最起码能减少计算能力浪费和增加吞吐吧。再加上很多企业内部使用的都是定制的开源操作系统和定制的网络库,升级的代价并不是那么高。如果我是企业基础设施的负责人,我想我会很慎重地考虑这个方案的。

Fastbit中的bitmap索引算法

摘要:bitmap 索引是一种典型的数据库索引方案,本文基于 Fastbit 软件包,使用实际用例对一些常用的 bitmap 索引算法进行了一个较为系统的介绍。

一、Fastbit是什么?

引用 Fastbit 的官方网站上的介绍:Fastbit是一个追随 NoSQL(Not Only SQL) 运动精神的开源的数据处理程序库,它提供了一系列的用压缩的 bitmap 索引支持的查询函数。在这里,我们关注的关键词是“bitmap 索引”。Fastbit 使用的是按列存储方式,其 bitmap 索引也是在按列存储的数据上建立起来的。

二、Fastbit 中的 bitmap 索引算法

Fastbit 的源代码有着非常清晰的结构。在 Fastbit 的源代码中,每个索引算法都用一个 C++ 类来实现,所有的索引算法类都是基类 index 的派生,并且在 fastbit 源代码中保存为以 i 开头的源文件。

下面是 Fastbit 中的索引类的派生关系图,从美观考虑,直接使用 xmind 思维导图而不是 UML 来展现了:

fastbit 索引算法派生关系图

下面我们将对其中部分算法进行简单的介绍。我们将这些索引算法分为几大类:基础算法、扩展算法、多层算法和多成分算法。

三、基础 bitmap 索引算法

基础的 bitmap 索引算法是最简单的 bitmap 索引算法,给出了 bitmap 索引的基本原理。

3.1 relic

relic (定义在 irelic.h 中,实现在 irelic.cpp ) 是最原始的 equality-encoded 算法,这个单词代表“遗迹”的意思。它可谓是最简单直观的 bitmap 索引算法。relic 为需要索引的每个值都建立一个 bitvector,在该 bitvector 中,只有等于该值的列才会被置 1,其它位都被置 0,如下表所示:

数据 索引(bitmap)
a b d e g
a 1 0 0 0 0
g 0 0 0 0 1
d 0 0 1 0 0
e 0 0 0 1 0
b 0 1 0 0 0
d 0 0 1 0 0
g 0 0 0 0 1
e 0 0 0 1 0
3.2 bin

bin (定义于 ibin.h,实现在 ibin.cpp)是 binned equality-encoded 算法,这里它代表“桶”的意思。它可以视为是 relic 的一种变形,它将值域分为几个不相交的区间,将原本是相等才置一的规则转变为值落在该区间内就置一,如下表所示。当然,relic 也可以视为 bin 的一个特例(将区间定义为 [a, a+ε)。bin 每个区间的范围由程序遵从某些规则设定,这些规则由命令行通过参数传入。

数据 索引(bitmap)
(…,b) [b,e) [e,…)
a 1 0 0
g 0 0 1
d 0 1 0
e 0 0 1
b 0 1 0
d 0 1 0
g 0 0 1
e 0 0 1
3.3 bin->range

range (定义于 ibin.h,实现于 irange.cpp)是 range-encoded 算法,这里它代表“范围”的意思。正如它字面所表达的意思,range 的每个 bitvector 标记着小于某边界值的值,如下表所示。因此,它可以视为是 bin 的一个累积表示,这也是 fastbit 软件包中所做的:首先构造 bin,然后累加转换成 range。值得注意的是,一般最后一列代表着小于无穷大,因此该 bitvector 全为 1,会被略去不写。

数据 索引(bitmap)
(…,b) (…,e) (…,g)
a 1 1 1
g 0 0 0
d 0 1 1
e 0 0 1
b 0 1 1
d 0 1 1
g 0 0 0
e 0 0 1
3.4 bin->mesa

mesa (定义于 ibin.h,实现于 imesa.cpp)是 interval-encoded 算法[1],它与 bin 类似,只不过它的区间之间有重叠部分。与 range 相同,在 fastbit 软件包中,它也是通过 bin 构造起来的。

数据 索引(bitmap)
(…,d) [a,e) [b,g) [d,…)
a 1 1 0 0
g 0 0 0 1
d 0 1 1 1
e 0 0 1 1
b 1 1 1 0
d 0 1 1 1
g 0 0 0 1
e 0 0 1 1

四、扩展 bitmap 索引算法

4.1 direkte

direkte (定义于 idirekte.h,实现于 idirekte.cpp)是丹麦语中的 direct,它与 relic 几乎是一样的,不同点只是它为小于最大值的所有值都建立了一个 bitvector(即使该值并不存在于列中)。

数据 索引(bitmap)
a b c d e f g
a 1 0 0 0 0 0 0
g 0 0 0 0 0 0 1
d 0 0 0 1 0 0 0
e 0 0 0 0 1 0 0
b 0 1 0 0 0 0 0
d 0 0 0 1 0 0 0
g 0 0 0 0 0 0 1
e 0 0 0 0 1 0 0
4.2 relic->slice

slice(定义于 irelic.h,实现于 islice.cpp)实现了 O'Neil'97 [2] 提出的 bit-slice 算法。它的基本思想就是首先将原始数据用二进制进行编码,bitmap 就是所有值的二进制编码表示的集合,bitvector 的个数由最大值的二进制表示决定,如下表所示:

数据 编码 索引(bitmap)
a 0 0 0 0
g 4 1 0 0
d 2 0 1 0
e 3 0 1 1
b 1 0 0 1
d 2 0 1 0
g 4 1 0 0
e 3 0 1 1
4.3 bin->bak

bak (定义于 ibin.h,实现于 idbak.cpp)是丹麦语中的 bin,因此它是 bin 的变形。它使用减精度来表示 bin 区间的中心,即它的每一个区间都是用一个更低精度的数来表示,具体来说就是四舍五入啦。下面是一个对 1-100 的数据列建立 bak 索引的输出,其中第一列表示区间的中心,第二三列代表区间最小最大值,第四列代表该区间内数据的个数:

index (equality encoding on reduced precision values) for data.a contains 19 bitvectors for 100 objects
1   1   1   1
2   2   2   1
3   3   3   1
4   4   4   1
5   5   5   1
6   6   6   1
7   7   7   1
8   8   8   1
9   9   9   1
10  10  14  5
20  15  24  10
30  25  34  10
40  35  44  10
50  45  54  10
60  55  65  11
70  66  74  9
80  75  84  10
90  85  94  10
100 95  100 6
4.4 bin->bak2

bak2 (定义于 ibin.h,实现于 idbak2.cpp)是 bak 的变形,也是以减精度来表示区间。但与 bak 不同的是,它将 bak 的每个区间区分为两个区间:小于减精度数的区间,和大于等于减精度数的区间。虽然注释中这样说,但实现时 bak2 是将 bak 的区间分为了三个:小于、等于和大于。下面是一个对 1-100 的数据列建立 bak2 索引的输出,每列的含义与 bak 中示例相同:

index (equality encoding on reduced precision values) for data.a contains 37 bitvectors for 100 objects
1   1   1   1
2   2   2   1
3   3   3   1
4   4   4   1
5   5   5   1
6   6   6   1
7   7   7   1
8   8   8   1
9   9   9   1
10  10  10  1   
10  11  14  4   
15  15  19  5
20  20  20  1
20  21  24  4
25  25  29  5
30  30  30  1
30  31  34  4
35  35  39  5
40  40  40  1
40  41  44  4
45  45  49  5
50  50  50  1
50  51  54  4
55  55  59  5
60  60  60  1
60  61  65  5
66  66  69  4
70  70  70  1
70  71  74  4
75  75  79  5
80  80  80  1
80  81  84  4
85  85  89  5
90  90  90  1
90  91  94  4
95  95  99  5
100 100 100 1

除了上面几个算法之外,扩展的算法还有 roster 和 keywords,这两种算法比较复杂,这里就不示例讲解了。

五、多层 bitmap 索引算法

有了几个基础的 bitmap 索引算法,我们就可以考虑将这些算法组合成一个层次的结构,构造出多层的 bitmap 索引算法。下面的几个算法,即是由前面的基础 bitmap 索引算法构造出来的二(多)层 bitmap 索引算法。

5.1 bin->ambit

ambit(定义于 ibin.h,实现于 ixambit.cpp)是 multilevel-range based算法,在这个算法中索引分为多层,每层索引都是基于 range 的索引。具体实现时,fastbit 首先构造 bin,然后对桶进行分组(调用 bin::divideBitmaps),然后构造 ambit。分组粒度可以由命令行传入参数 ncoarse=x 和/或 nrefine=n 指定,否则由一简单算法确定,确定分组个数的算法为(第一个桶不参与分组):

ixambit.cpp:
33     // the default number of coarse bins is determined based on a set
34     // of simplified assumptions about expected sizes of range encoded
35     // bitmaps and word size being 32 bits.
36     const uint32_t defaultJ = static_cast
37         (nbins < 100 ? sqrt((double)nbins) :
38          0.5*(31.0 + sqrt(31.0*(31 + 4.0*nbins))));

下面看一个实际的例子,左侧是对 1-100 的数据列构造的 bin,右侧是基于该 bin 构造的 ambit:

ambit 索引

5.2 bin->pale

pale(定义于 ibin.h,实现于 ixpale.cpp)是 two-level binned equality-range算法,它的索引分为两层,第一层为 binned equality(bin) 索引,第二层为 range 索引。在具体实现时,pale 首先构造 bin,然后对桶进行分组(调用 bin::divideBitmaps),然后构造 pale。与 ambit 相同,分组粒度可以由命令行传入参数 ncoarse=x 和/或 nrefine=n 指定,否则当 bin 桶数大于31时,默认第一层为16个组:

ixpale.cpp:
45     else { // default -- 16 coarse bins
46         if (nbins > 31) {
47         j = 16;
48         }
49         else {
50         j = nbins;
51         }
52     }

下面看一个实际的例子,左侧是对 1-100 的数据列构造的 bin,右侧是基于该 bin 构造的 pale:

pale 索引

5.3 bin->pack

pack(定义于 ibin.h,实现于 ixpack.cpp)是 two-level binned range-equality 算法。它的索引分两层,与 pale 相反,第一层为 range 索引,第二层为 binned equality(bin) 索引。具体实现时,fastbit 首先构造 bin,然后对桶进行分组(调用bin::divideBitmaps),然后构造 pack。分组粒度可以由命令行传入参数 ncoarse=x 和/或 nrefine=n 指定,否则当bin桶数大于63时,默认第一层为31个组:

ixpack.cpp:
44     else { // default -- 31 coarse bins
45         if (nbins > 63) {
46         j = 31;
47         }
48         else {
49         j = nbins;
50         }
51     }

下面看一个实际的例子,左侧是对 1-100 的数据列构造的 bin,右侧是基于该 bin 构造的 pack:

pack 索引

5.4 bin->zone

zone(定义于 ibin.h,实现于 ixzone.cpp)是 two-level binned equality-equality 算法,它的索引分两层,两层均为 binned equality(bin) 索引。它的实现方式也是首先构造 bin,然后对桶进行分组(调用 bin::divideBitmaps),然后构造 zone。其分组粒度可以由命令行传入参数 ncoarse=x 和/或 nrefine=n 指定,否则当bin桶数大于31时,默认第一层为14个组:

ixpack.cpp:
46     else { // default -- 14 coarse bins
47         if (nbins > 31) {
48         j = 14;
49         }
50         else {
51         j = nbins;
52         }
53     }

下面看一个实际的例子,左侧是对 1-100 的数据列构造的 bin,右侧是基于该 bin 构造的 zone:

zone 索引

5.5 bin->fuge

fuge(定义于 ibin.h,实现于 ixfuge.cpp)是 two-level binned interval-equality 算法,fuge 为德语中 interstice 的表述。fuge 的索引分两层,第一层为 interval(mesa) 索引,第二层为 binned equality(bin) 索引,它也是采用首先构造 bin,然后基于 bin 构造 fuge 的方式。其分组粒度由 ncoarse=x 指定,否则默认的分组个数由下面算法确定:

ixfuge.cpp:
887     // default size based on the size of fine level index sf: sf(w-1)/N/sqrt(2)
...
899     if (ncoarse < 5U && offset32.back() >
900     offset32[0]+static_cast(nrows/31)) {
901     ncoarse = sizeof(ibis::bitvector::word_t);
...
913     else {
914         ncoarse = ncmax;
915     }
916     }

下面看一个实际的例子,左侧是对 1-100 的数据列构造的 bin,右侧是基于该 bin 构造的 fuge:

fuge 索引

5.6 relic->bylt

bylt(定义于 irelic.h,实现于 ixrelic.cpp)是 two-level unbinned range-equality 算法,bylt 是丹麦语的 pack(binned 版本算法)。bylt 索引分两层,第一层为 range 索引,第二层为 unbinned equality(relic) 索引。在实现时首先构造 relic,然后对桶进行分组(调用bin::divideBitmaps),然后构造 bylt。分组粒度可以由 ncoarse=x 指定,bylt 保证每组中桶数是大致均匀的,否则由下面算法决定分组的个数:

ixbylt.cpp:
182     // default size based on the size of fine level index sf:
183     // (w-1) * sqrt(sf*(sf-N/(w-1))) / (2N)
184     if (ncoarse < 5U && offset64.back() > offset64[0]+(int32_t)(nrows/31U)) { 
185     ncoarse = sizeof(ibis::bitvector::word_t);
     const int wm1 = ncoarse*8-1;
...
199         ncoarse = ncmax;
200     }
201     }

下面看一个实际的例子,左侧是对 1-100 的数据列构造的 relic,右侧是基于该 relic 构造的 bylt:

bylt 索引

5.7 relic->fuzz

fuzz(定义于 irelic.h,实现于 ixfuzz.cpp)是two-level unbinned interval-equality 算法,即 fuge 的 unbinned 版本,名字起源于 fuzzy 聚类/分类。fuzz 索引分两层,第一层为 interval(mesa) 索引,第二层为 unbinned equality(relic) 索引,具体实现时 fastbit 也是采用首先构造 relic,然后构造 fuzz 的方式。其分组粒度可以由 ncoarse=x 指定,否则默认分组个数由下面算法确定:

ixfuzz.cpp:
168     // default size based on the size of fine level index sf: sf(w-1)/N/        sqrt(2) 
169     if (ncoarse < 5U && offset64.back() > offset64[0]+nrows/31U) {
170     ncoarse = sizeof(ibis::bitvector::word_t);
...
182     else {
183         ncoarse = ncmax;
184     }
185     }

下面看一个实际的例子,左侧是对 1-100 的数据列构造的 relic,右侧是基于该 relic 构造的 fuzz:

fuzz 索引

5.8 relic->zona

zona(定义于 irelic.h,实现于 ixzona.cpp)是 two-level unbinned equality-equality 算法,zona 是丹麦语的zone(binned 版本算法),其索引分两层,两层均为 unbinned equality(relic) 索引。首先构造 relic,然后对桶进行分组构造zona,分组个数默认为11个。下面看一个实际的例子,左侧是对 1-100 的数据列构造的 relic,右侧是基于该 relic 构造的 zona:

zona 索引

六、多成分 bitmap 索引

多成分(multi-component)bitmap 索引[3]是使用一组基数将数据值分解成多个部分,分别对每个部分进行 bitmap 索引的方案。原理描述如下:给定 n-1 个基数 { bn-1, bn-2, ..., b1},那么一个值 v 可以通过下式分解为 {vn, vn-1, ..., v1}:

数据值的分解

这和数的表示法类似,如果令 bi 都是 10,那么 vi 就是十进制表示法中第 i 位的值(大于等于0,小于10)。更准确的表述可以参考[3]。下面我们来看 fastbit 中的几个实现。

6.1 relic->fade

fade(定义于 irelic.h,实现于 ifade.cpp)是 multicomponent range-encoded 算法,即在每个部分中,是使用的 range 索引。下面来看一个 range-encoded 的例子:

fade 索引

在(b)图中,选择的基数是 9,那么索引就变成了一个单成分的 range 索引算法;在(c)图中,选择的基数是 <3, 3> 这样一个双成分编码,对分解出来的每个成分(大于等于0,小于3)生成 range 索引,就得出了 (c) 图中的结果。

6.2 relic->fade->sapid

sapid(定义于 irelic.h,实现于 isapid.cpp)是 multicomponent equality-encoded 算法,即在每个部分中是使用的 equality(relic) 索引。下面来看一个 equality-encoded 的例子:

sapid 索引

在(b)图中,选择的基数是 <3, 4> 这样一个双成分编码,对分解出来的每个成分生成 relic 索引,就得到了 (b) 图中的索引结果。

除了这两个索引算法之外,还有 sbiad(multicomponent interval-encoded),egale(multicomponent equality code on bins), entre(multicomponent interval code on bins), moins(multicomponent range code on bins)这几个索引算法。从括号中我们可以大致猜出这些索引的实现方式,但是由于我们现在没有一个很好的示例展现方式,用实际用例来展现这些索引算法的效果将会留给以后的文章进行。

七、总结

这篇文章基于 fastbit 软件包,加以实际的用例对常用的 bitmap 索引算法进行了一个较为系统的介绍。不过生成 bitmap 索引仅仅是第一步,bitmap 索引在存储时会有很大的开销,在不损害(较少损害)查询效率的情况下,对 bitmap 索引进行有效的压缩是一个非常有挑战性的课题。除了 bitmap 索引的生成和存储之外,在不同类型的 bitmap 索引上实现高效的各种类型的查询,也是一个值得进一步探讨的问题。我们很高兴地看到 fastbit 软件包实现了很多这些相关领域的算法,为我们提供了非常宝贵的资料。

参考文献

[1] C-Y. Chan and Y. E. Ioannidis, An efficient bitmap encoding scheme for selection queries, in Proceedings of the ACM international conference on Management of data (SIGMOD), 1999.
[2] P. O’Neil and DalIan Quass, Improved Query Performance with Variant Indexes, in Proceedings of the ACM international conference on Management of data (SIGMOD), 1997.
[3] C-Y. Chan and Y. E. Ioannidis, Bitmap Index Design and Evaluation, in Proceedings of the ACM international conference on Management of data (SIGMOD), 1998.

Math in CS:置换的轮换分解

随便一本《近世代数》或者《抽象代数》书上在讲到置换群的时候,应该都会讲到这样一个定理:
任何一个置换都可以表示为不相交轮换的乘积,若不计因子的顺序,其分解式是唯一的。

一、简单解释

没有数学背景的人,这句话很难读懂,下面我们来看一个简单的例子。假设我们有这样一个置换 P:

1, 2, 3, 4, 5
2, 5, 4, 3, 1

那么这个置换是什么样的轮换的乘积呢?我们先从 1 出发,1 被换到 2,2 被换到 5,5 又被换到 1,这就是一个轮换;然后再从 3 出发,3 被换到 4,4 又被换到 3,这又是一个轮换。也就是说 P 是两个不相交轮换 (1, 2, 5) 和 (3,4) 的乘积。

二、一个应用:全排列判断问题

下面我们来看这个定理有什么作用,考虑下面这道题目[1][2]:

给一个 n 长的数组,判断它是否为一个 1, 2, ..., n 的全排列,要求在线性时间,常数空间内实现。

我们可以容易看到,每个全排列都可以视为 1, 2, ..., n 上的一个置换。问题就转化为检测该数组是不是一个 1, 2, ..., n 的置换。由本文开头提到的定理可知,我们只需要检查该置换是不是由不相交的轮换构成的即可。

还是上面那个例子,怎么检查

1, 2, 3, 4, 5
2, 5, 4, 3, 1

是不是一个置换呢?首先从 1 开始,a[1]=2,那么再检查 a[a[1]]=a[2]=5,然后再检查a[a[a[1]]]=a[5]=1,这样就发现了一个轮换 (1, 2, 5)。然后接下来检测第二个,第三个轮换...

如何保证检查的高效以及所有轮换都不相交呢?我们每次检查完一个数,就将它置负,这样遇到负值,循环就终止了。如果终止前检查的那个数与起始的数相同,那么我们就发现了一个轮换,否则它就不是一个轮换,说明 P 不是一个置换。由于检查过的轮换中的数字都被置为负值,所以第二个轮换肯定不会与第一个轮换相交。如果到最后所有的数都被置为负值,且循环正常终止,那么说明它们都在不相交的轮换里,那么 P 就是一个置换。

如果想要查找过程不影响最终数组的值,到最后把所有置负的元素都重新置正即可。

代码实现如下[2]:

/* We use a n+1 elements array a[n+1] for convenience. a[0] is used to store
 * the return value, thus is not part of the permutation.  */
int test_perm(int *a, int n)
{
  int i, j;
  if (a == NULL)  return 0;     /* Test input */
  a[0] = 1;
  for (i = 1; i <= n; ++i)      /* Test input */
    if (a[i] < 1 || a[i] > n) { /* Is a[i] in the range 1~n? */
      a[0] = 0;
      return a[0];
    }

  for (i = 1; i <= n; ++i)
    if (a[i] > 0) {
      j = i;
      while (a[j] > 0) {        /* Follow the cycle */
        a[j] = -a[j];
        j = -a[j];
      }
      if (j != i)  a[0] = 0;    /* Test the cycle */
    }

  for (i = 1; i <= n; ++i)
    a[i] = a[i] > 0 ? a[i] : -a[i];

  return a[0];
}

三、另一个应用:100 囚徒碰运气问题

那么这个定理还有其它的用处没有呢?考虑下面这道题目[3][4]:

100 个囚犯,每人有一个从 1 到 100 的不重复不遗漏的号码,国王把这些号码收集起来,打乱放进 100 个箱子里,每个箱子里有且仅有一个号码。囚犯们一个一个地来到 100 个箱子面前,每人可以打开至多 50 个箱子来寻找自己的号码,可以一个一个打开(即可以根据之前箱子里看到的号码来决定后面要打开的箱子)。如果有一个囚犯没有找到自己的号码,那么这 100 个人一起被处死;只有当所有的囚犯都找到了自己的号码,他们才会被国王全部释放。

囚犯们可以在没开箱子前商量对策,但是一但打开了箱子,他就不能告诉别人箱子和号码的对应关系。问他们应该用什么样的策略以保证最大的存活概率?

显然,每个人随机选 50 个箱子打开,100 个人的存活概率会是 1/2 的 100 次方,即1/1267650600228229401496703205376,可以小到忽略不计。但是事实上有一种极简单的办法,其存活概率高达 30% 。至于有没有更好的办法?我不知道。

存活率达 30% 的策略就是:

囚犯打开自己号码对应的箱子,就按照箱子中的号码打开另一个箱子,一直到找到自己号码或者选50 次为止,这样就能保证整体有 30% 的存活概率。

这个策略背后的数学原理是什么呢?其实国王所作的事情,就是一个 1 到 100 元素集合的置换,囚犯所做的事情,就是顺着自己号码所在的轮换找自己号码。那么什么时候所有人都不用死呢?就是这个置换中所有的轮换长度都不大于 50,因为每个囚犯号码的轮换都不大于 50,那么他总能在 50 次以内找到自己的号码。

怎么计算这个概率 P 呢?{这个置换中所有的轮换长度都不大于 50 的概率},就是 1 - {存在轮换长度大于 50 的概率},进而 1 - {存在轮换长度为 51, 52, ..., 100 的概率},由此,我们可以得到下面的等式:

P=1-\frac{1}{100!}\sum_{k=51}^{100}\binom{100}{k}(k-1)!(100-k)!=1-\sum_{k=51}^{100}%20\frac{1}{k}=1-(H_{100}-H_{50})

其中,Hn 代表调和数(Harmonic Number)。虽然调和数没有精确的公式,但是我们知道调和数和自然对数有着密切的联系[5],那么我们就可以用自然对数来近似:

P\approx1-(ln(100)-ln(50))=1-ln(2)\approx0.30685281944005469059[6]

因此,我们可以得到,使用这种策略 100个囚犯的存活概率 P 约为 30%。

[1] http://yueweitang.org/bbs/topic/22
[2] http://fayaa.com/tiku/view/84/
[3] http://tydsh.spaces.live.com/Blog/cns!435F1A315756AD5D!833.entry
[4] http://fayaa.com/tiku/view/141/
[5] http://en.wikipedia.org/wiki/Harmonic_number#Calculation
[6] 求和得到的更精确的结果是:0.31182782068980479698,Bash 代码:

STR="1-("
for i in `seq 51 99`; do
  STR+="1/$i+"
done
STR+="1/100)"
echo $STR | bc -l

25 马问题

这是以前在 TopLanguage 讨论组讨论过的一道题目 ,题目描述为:

有 25 匹马和 1 个赛场,但赛场只有 5 条赛道,即一次只能给最多 5 匹马提供比赛机会,并且不能计时。请问如何设计比赛策略得到最快的 3/5 匹马,使得使用赛道的次数最少。

我想了一下,下面尝试给出我的分析,如果不对的话,还请指正。

一、决出前三名的策略

决出前 3 名网上有很多讨论,答案是 7 次,没有见过更少的,策略如下:

1. 将 25 匹马分成 5 组,分别赛一轮,得出一个先后顺序,共 5 轮。
2. 将每组的头马组成一组,再赛一轮,得出一个先后顺序。这第 6 轮能确定第一名。
3. 将最快一组的二三名,第二那组的一二名,以及第三那组的第一名五匹马放在一起,再赛一轮。这第 7 轮的前两名就是最终的二三名。总共赛 7 轮。

下面是分析。不失一般性,在赛 6 次之后,我们假设这 25 匹马的序号为:

A1 A2 A3 A4 A5  // 1 <-------
B1 B2 B3 B4 B5  // 2  |     |
C1 C2 C3 C4 C5  // 3 Main   |
D1 D2 D3 D4 D5  // 4  |  Extended
E1 E2 E3 E4 E5  // 5 <--    |
--------------  //          |
A1 B1 C1 D1 E1  // 6  {A1} <-

其中主矩阵列出了 25 匹马的序号,扩展矩阵的每行是每轮比赛的结果。我们可以看到主矩阵的行有序,第一列有序,那么现在我们知道第一名是 A1。

由于已知 A1 是第一名,第二名肯定是在每轮中紧挨在 A1 后面的,因此第二名的候选集为 {A2, B1}。

它们两个占不满 5 个赛道,我们再来看第三名的候选集。第三名在每轮中只可能是挨在第一或第二名的后面,也就是说在 {A1} U {A2, B1} 的后面,那么第三名的候选集就是 {A2, A3, B1, B2, C1},正好 5 匹马(第二名的候选集肯定包含在第三名候选集中)。那么第二三名只可能在这 5 匹马中,因此我们只需要让 {A2, A3, B1, B2, C1} 这 5 匹马再比一次,得到前两名,与 {A1} 合起来就是总的前三名。这样总共的比赛次数是 7 次。

2. 决出前五名的策略

决出前 5 名,就比较复杂了,我们按照同样策略再往下思考:

{A2, A3, B1, B2, C1} 决出前两名,有几种可能呢?如果它们没有比过,可能性就是从 5 个中取 2 个后的排列数,20 种可能。但是我们前面的比赛已经得到了一些快慢信息,我们就可以发现,第 7 轮 {A2, A3, B1, B2, C1} 决出前两名只有 5 种可能情况:

A2 A3 B1       B2/C1 * // 7  {A1, A2, A3}
B1 B2 A3/C1    *     * // 7  {A1, B1, B2}
B1 C1 A2/B2    *     * // 7  {A1, B1, C1}
A2 B1 A3/B2/C1 *     * // 7  {A1, A2, B1}
B1 A2 A3/B2/C1 *     *

去掉可交换的 A2 B1,其实只有 4 种情况。我们分别来考虑这 4 种情况:

1. {A1, A2, A3}

第四名肯定是 {A1, A2, A3} 之后的马,候选集为 {A4, B1};元素不足 5,再推一下第五名,即{A1, A2, A3} U {A4, B1} 之后的马,候选集为 {A4, B1, A5, B2, C1},只有 5 匹马。就是说第四、五名可以从这五匹马中产生,那么我们只需要再比一轮,取前两名,与 {A1, A2, A3} 并起来就能得到整个的前 5 匹马。那么最少的比赛次数是 8 次。

2. {A1, B1, B2}

这种情况下,同理,第四名候选集为 {A2, B3, C1} ,第五名候选集为 {A2, A3, B3, B4, C1, C2, D1},元素多于 5 个。因此我们必须先让 {A2, B3, C1} 比赛得到第 4 名,才能将第五名候选集的元素个数减少到 5 个以内。穷举:第 8 轮 A2 第一,可以消去 {C2, D1, B4, A2};B3 第一,可以消去 {B3, A3, C2, D1};C1 第一,可以消去 {C1, A3, B4},均能保证第五名的取值集合减少到 5 以内,因此只需要再一轮,就可以得到第五名。总的比赛次数是 9 次。

3. {A1, B1, C1}

同理,第四名候选集为 {A2, B2, C2, D1},第五名候选集为{A2, A3, B2, B3, C2, C3, D1, E1}。第四名无论取哪个,都会消去四个第五名候选集中的元素,总的比赛次数仍然是 9 次。

4. {A1, A2, B1}

同理,第四名候选集为{A3, B2, C1},第五名候选集为{A3, A4, B2, B3, C1, C2, D1}。第四名无论取哪个,至少消去第五名候选集中的 3 个元素,总的比赛次数也是 9 次。

穷举结束了,现在我们可以得出结论:最坏情况下该策略决出前 5 匹马的最少比赛次数是 9 次。

三、扩展问题

我有一个问题是:这种策略下取3, 5名比赛次数一定是最少的吗?有没有数学证明?

再扩展一点儿,如果需要求前 n 名,最少需要比赛几次?

在我们的这种策略下,因为主矩阵只有 5 行,每行还是有序的,那么求下一名的候选集最多有 5 个元素。也就是说多求一名,至多需要增加一轮比赛。什么情况下可以少于一轮呢?当已经确定第 n 名的情况时,第 n+2 名的候选集元素少于 5 个,我们就可以一轮比赛确定两个名次了。

我还比较好奇的是,如果需要决出所有 25 匹马的快慢顺序,最坏情况下至少需要比赛几次?

在我们这种策略下,假设 f(n) 是第 n 名最坏情况下的最少比赛次数,我们已知 f(1) = 6, f(2) = f (3) = 7, f(4) = 8, f(5) = 9,f(n) <= (n-5)+9 = n+4。那么 f(25) = f(20)+1 <= (20-5)+9 + 1 = 25 次,其上界应该是 25。但其准确值怎么确定?穷举就太困难了。 但是如果题目要求是确定 25 个的全部顺序,我们这种策略未必是最好的。这时候这题可以看成 n 路归并排序,并且可同时比较 n 个数的优化问题。过程中有很多可优化的可能。比如我们预处理时可以对每行和每列都排一下序,能否可以得到一些额外的信息?当主矩阵(去掉已确定顺序的元素)显得不那么平衡时,用扩展矩阵中的比较信息是否可以将主矩阵平衡一下,或者消去某些行列,这样做是否有帮助?

Cygwin GCC qsort 函数错误(续)

上一篇文章中提到我在为 qsort 写 compare 函数时犯了一个愚蠢的错误:我脑袋陷入了一个错误的逻辑,以为 compare 函数嘛,就是要 compare 一下,那么我用 '>' 或者 '< ' 这种比较算符就可以满足要求(潜意识里认为 > 会返回 1 或者 -1,显然是错的,上篇文章的评论者 Stephen 开始也犯了同样的直觉错误,不过他马上就醒悟过来了)。我当时脑袋里也犹豫了一下要不要处理相等的情况,后来想快排算法中没有判断相等的情况,那么我没必要加上等号。

这个错误直接导致了快排算法失效。

但是为什么在 Linux 下的 gcc 可以输出正确的排序结果呢?我想了很久,最终还是把 glibc 的代码看了一下,才发现,原来当数组规模比较小时时(数组大小小于物理内存的四分之一),glibc 的 qsort 其实不使用 quick sort(_quicksort),而是使用 merge sort(msort_with_tmp)。而且在 msort_with_tmp 中,对 compare 的处理是比较其返回值是否 <=0,这样排序的结果就是正确的了。[1]

事实上最简单的快排算法是只使用 '<' 号或者 '<='的,比如 Wikipedia 上给出的快排算法,那么我们的 compare 只返回 -1 和 0 行吗?这取决于实现,比如对快排算法的优化中有一个就是对数组中有大量相等元素情况下的优化,其中一种实现 Three-way partition, 就需要使用到三种情况:大于、小于或等于。原始的快排 partition 是将数组按照与 pivot 的比较分为两段,Three-way partition 则是将数组分为三段,中间增加一段与 pivot 值相等的子数组。C 玩具代码的实现如下:

void qsort_3way(int a[], int lo, int hi)
{
  if (hi <= lo) return;
  int lt = lo, gt = hi, i = lt;
  int v = a[lo], t;
  while (i <= gt) {
    if (a[i] < v) {
      t = a[i]; a[i] = a[lt]; a[lt] = t;
      ++i; ++lt;
    } else if (a[i] > v) {
      t = a[i]; a[i] = a[gt]; a[gt] = t;
      --gt;  
    } else i++;
  }
  qsort_3way(a, lo, lt - 1);
  qsort_3way(a, gt + 1, hi);
}

但是 '<' 和 '>' 真的都需要吗?理论上来讲,'>' 是不需要的,我们显然可以将 a[i] > v 改成 v < a[i]。这也是 C++ 里面做的,C++ 中的 sort 函数只需要类重载 '< ' 运算符。但是 C 中并没有这种约定,我们不能预设 qsort 如何拿 compare() 的返回值与 0 比较。因此让 compare() 按照 C 的约定,返回大于、小于和等于 0 的三种情况是绝对正确的而且必要的。

我了解了正确的结果怎么得来的,但是我仍然不知道错误的结果是怎么得来的。看起来 Cygwin 使用的 libc 中没有采取类似 Linux 下 gcc 的策略(比如无法取到物理内存大小?)。quick sort 算法有很多优化的技巧和实现:有的使用 '< ' 符号比较,有的在分支数组足够小时采用插入排序,有的同时使用 '<', '> 两个符号,有的随机取 pivot,有的取三点中值作为 pivot。[2] 没有看到代码和调试,很难判断 Cygwin 的 libc 使用了什么算法(当然,尝试分析不同的输入输出是可以得到规律的,比密码分析还是要简单一些)。

[1] glibc/stdlib/msort.c.
[2] Jon Bentley and M. Douglas McIlroy, "Engineering a sort function", Software - Practice and Experience, Vol. 23 (11), 1249-1265, 1993.

Cygwin GCC qsort 函数错误

我平时在 Windows 下写代码时,经常使用 Cygwin 的 gcc。但是今天我居然发现 Cygwin 下 gcc 的 qsort 函数是错误的!这种基本的函数出错,太让人惊讶了。为了验证是不是代码有错,我使用 tcc 和 Linux 下的 gcc 都编译了同样一段程序,它们两个都输出了期望的结果,只有 Cygwin 的 gcc 是错的。下面是示例代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void *p, const void *q)
{
  return *(const char *)p > *(const char *)q;
}

int main()
{
  char a[] = "1312515";
  printf("%sn", a);
  qsort(a, strlen(a), sizeof(char), compare);
  printf("%sn", a);
  return 0;
}

按说它应该输出:

1312515
1112355

但是我用 Cygwin gcc 编译后,它居然运行出这样的结果:

1312515
2111355

太诡异了。我尝试调试它,结果 gdb 无法步入 qsort 代码中。谁能告诉我是为什么?

附 Cygwin gcc 信息:

$ gcc -v
Using built-in specs.
Target: i686-pc-cygwin
Configured with: /gnu/gcc/package/gcc4-4.3.2-2/src/gcc-4.3.2/configure --srcdir=/gnu/gcc/package/gcc4-4.3.2-2/src/gcc-4.3.2 --prefix=/usr --exec-prefix=/usr --bindir=/usr/bin --sbindir=/usr/sbin --libexecdir=/usr/sbin --datadir=/usr/share --localstatedir=/var --sysconfdir=/etc --infodir=/usr/share/info --mandir=/usr/share/man --datadir=/usr/share --infodir=/usr/share/info --mandir=/usr/share/man -v --with-gmp=/usr --with-mpfr=/usr --enable-bootstrap --enable-version-specific-runtime-libs --with-slibdir=/usr/bin --libexecdir=/usr/lib --enable-static --enable-shared --enable-shared-libgcc --enable-__cxa_atexit --with-gnu-ld --with-gnu-as --with-dwarf2 --disable-sjlj-exceptions --enable-languages=ada,c,c++,fortran,java,objc,obj-c++ --disable-symvers --enable-libjava --program-suffix=-4 --enable-libgomp --enable-libssp --enable-libada --enable-threads=posix AS=/opt/gcc-tools/bin/as.exe AS_FOR_TARGET=/opt/gcc-tools/bin/as.exe LD=/opt/gcc-tools/bin/ld.exe LD_FOR_TARGET=/opt/gcc-tools/bin/ld.exe
Thread model: posix
gcc version 4.3.2 20080827 (beta) 2 (GCC)

我犯了一个愚蠢的错误,感谢来自 Stephen 的评论

你的compare函数有问题,你的compare函数不会返回负数。修改compare为:
int compare(const void *p, const void *q)
{
return *(const char *)p - *(const char *)q;
}
再编译运行就正确了。