A programmer's site

半年小结

blog有些时间没有更新，最近工作比较有意思，把精力都投入到了工作，更新blog的事情给耽搁了些。

时间过得真快，掐指一算，距离5月14日加入美团，一晃快也有半年了。半年多前，由于某些原因，离开了服务了近3年的一个初创公司。到云南吸了10天好空气后，承蒙朋友介绍，收到6，7个互联网公司的offer，最后加入美团。半年已经过去，庆幸选择了美团，也非常感谢现在的领导秦亚飞当初说服我加入美团：这半年，有机会干了很多以前没有干过的事，体会了未曾有机会体会过的感受，感觉成长了很多。说来也是缘分，美团是唯一一个自己投简历得到的offer。

在上家公司，专注于web开发，在web技术积累较多：从一个form的生成，到浏览器通过HTTP协议发送请求，Ngnix接到请求，forward给后台程序，到用户验证，到查询数据库，调用服务，生成结果，展示给用户等都涉猎。来到美团，职位为后台服务开发工程师，改变还是蛮大的，从一个全端工程师变成一个专注于后台服务的工程师。

第一件摆在面前的任务：搞定deal排序服务的稳定性。

Deal排序服务的稳定性问题

首页排序服务是一个Thrift服务，由Python编写。负责对首页和筛选页面的deal进行排序。历时近3年，几易维护者。它是一个很重要的服务，因为在首页，很多人盯着。两个问题，期望被解决：

1. (CPU)流量高峰服务失败率偏高, latency偏高
2. (RAM)与日剧增的在线单导致它的内存占用变得不可控

对我也是不小的挑战：初来乍到，不熟悉情况；这个程序有点历史，有不少的业务逻辑（水深）；Thrift不熟悉，仅仅听说而已；Python也不是很熟。

第一个月在融入新的团队，熟悉业务，学习Python，学习go语言，熟悉Thrift中度过；给Thrift官方提了2个patch，改进它的go代码。

水深浅摸得差不多后，提出通过实现一个透明的proxy，来cache Python的计算结果。于是用go在TCP上实现了一个Thrift的代理，cache结果。3天左右，程序ready。小流量测试，3周后全流量接入。于此同时，挑了2-3个点，协助原程序负责人改了几段代码，内存占用省掉一半。问题解决的同时，还使老code简化了一些。收获最佳新人奖。

比组织预期提前2个月搞定Deal排序服务的稳定性问题。我开始加入推荐team。这时的推荐分流量测试需要别的部门配合，数据训练是定时hive跑，预算结果存Redis，效果观察需要等第二天的报表。在初创公司干了几年的我，对这种节奏不是很习惯。想改变这个事情，用程序员的方式：code。遂提出

1. 写一个流量分配程序（Router），使我们自己可以控制分发流量
2. 每个Response，打一个算法tag，主站的同事记到日志里面，并且把日志实时推给我们，方便统计。

流量分发程序：Router

Go语言，在TCP层实现的根据Thrift请求内容，分发流量的服务。主要的功能为流量分配，和负载均衡。它也会”修改”请求，比如查redis，补上用户最近几十天的点击，浏览，购买，消费等行为。由于有些推荐算法不能cover所有请求，也干按配置，调用多个后台服务，揉合为一个结果的事情。配置通过HTTP页面修改，点一个按钮生效，HTTP页面dump运行状态，比如QPS，lantency，出错率等，方便监控。

由于切流量方便，有负载均衡，容错等功能，其它流量也陆续接入：几乎已经支撑了美团主站后台的全部流量：EDM，搜索，搜索suggest，推荐，Deal排序等

实时日志解析，CTR监控，debug工具

实时的CTR，流量，点击等数据，对理解复杂系统的运行状况很有帮助。

1. 推动日志团队推送实时日志给我的code。他们用Flume，通过Thrift发给来。由于缺少文档，dump binary发现原来用的是Framed CompactProtocol
2. 解析日志（原来有code，但我想单进程做到能实时解析，并且在未来一段时间不想担心它的性能问题，自己动手，Python也能每秒搞定100k行日志）
3. 计数（展示，点击等）到Redis，通过HINCRBY。另外一个Python程序提供HTTP服务，读取并处理数据，Javascript可视化
4. 预处理后，记下有用的字段，dump到硬盘，分时间保存为文件。做为离线计算<用户，行为>矩阵程序的输入
5. 统计<用户，行为>，放到Redis。Router会读取这部分数据，补在请求里面，这样其它程序接到的请求里面，就有用户的实时行为数据了。

推荐：基于用户的collaborative filtering

这是我第一次做推荐，挑战很大，摸着石头过河，数据和工具也都需要自己去建设。我一边写一些基础的服务和工具，比如日志解析，监控工具，流量分配程序（AB测试），debug工具等，一边不断完善推荐程序。这部分耗消耗了我大部分精力。由于很有意思，下班回家，周末在家都在写这部分code，天天想着这事。大部分code都是我在家完成，在公司的时候主要是线上测试，观察。

我好像摇身一变，从后台服务开发，变成了数据挖掘。不过用的却是优化程序的路子：整体考虑，做实验，找瓶颈，抓大放小，拒绝主观猜测，数据驱动。

推荐程序分为两个部分：1. 离线用户－行为, 行为－用户矩阵生成（Python为主）；2. 在线计算（C++)

离线部分由python，shell，C++完成，程序分5步：

1. 按行解析日志，生成 (user-id, action)对，写到硬盘。user-id为对用户的重编号，1，2，3，4….，重编号可以把用户id映射到int上，并可以节约内存，加快计算速度 (Python)
2. 按照user-id排序生成的文件。由于生成的文件巨大，需要用到外排，Linux的sort命令很好的搞定了这个问题
3. 读入排序好的文件，group by user-id，把action编号为int，写入硬盘（binary)，格式为（user-id, action-cnt, actions），生成用户到对应的行为的矩阵 (Python)
4. 把用户行为矩阵倒转，生成行为＝>用户ids的矩阵 (C++)。同样存为自定义的binary格式。
5. Query DB，通过Thrift的BianryProtocol Dump Deal数据到文件。这样在线程序可以以非常快的速度加载他们到内存。

生成的数据规模：6M用户，3M行为，116M <用户，行为>对。耗时25分钟。

在线部分由C++完成

1. load生成的两个文件：mmap到内存，在上面用自己实现的hashmap建Index。自己实现hashmap可以做到比std::unordered_map快2到5倍。耗时1.5s
2. load Deal息，商圈等其它数据到内存，建好索引，耗时1.5s
3. 3s后，开始在线服务。来一个请求，用户近期行为已经被Router补全，它就专心计算。通过（行为，用户）索引快速找出有和他有至少一个相同行为的用户们，计算和他之间的相似度，找出top n个最相似用户
4. 计算出top n用户的行为，按照相似性加权排序。按照业务规则，去掉不靠谱的(如过期单)，过一遍多样性规则，取出前n个，返回给用户，总耗时20ms左右

依靠C++强悍的性能和我的精心设计，完成了能对用户行为做出实时反应的基于用户的协同过滤。很多论文在比我数据量小不少的情况下，说UserCF计算量太大。还好我没有听他们的。应用到首页排序，CTR显示，用户是买账的。

这个程序，可能还会折腾我一段时间。

小结

这半年，过得很充实，以较高的效率，干了不少事情，学习了很多东西。

1. 熟悉了Python，搞定一个Python程序的性能，还用它写了几个工具。哈哈，在此之前，主要以写Java，Clojure，Javascript为生的。
2. 学习go，并写了几个线上服务，支撑了美团主站后台流量。嗯，组里另一个同事也开始用go做一些数据挖掘的模型训练，体验还不错。
3. 由以前的全端工程师，转为后台服务开发工程师，后又尝试做个“外行”的数据挖掘。oh，yeah
4. 用C++写线上服务，写起来是麻烦了点，跑起来那是杠杠的快
5. 到了一个很有活力的公司，公司的交易额月月涨，而我做的事情，也会影响交易额，虽然基本上一个人单干，这必须感谢Leader吴瑜华的信任和支持。
6. 熟悉了Thrift，一个非常好的工具；给官方提交了Patch
7. 教老婆学习Web Development，她硬是把udacity的《Web Development》听了一遍，做了一遍
8. 读了几本书，技术类的《推荐系统实践》，《数学之美》，还有其它非技术类的。
9. 每天晚，和老婆一边吃饭一边听《财经郎眼》，或者《晓说》，《杨澜访谈录》，《罗辑思维》,etc
10. 仰望大师，听了Peter Norvig的《Design of Computer Programs》
11. 周末开始跑步；买了个空气净化器，24小时全开。
12. 从Emacs转到Vim了。没办法，线上写code，还是Vim比较好
13. http-kit，在github上有600多个星星了，多了300多个吧，merge了几个pull request，有17个Contributors了

python求解算式迷cryptarithmetic

这周末两天都在听 Peter Norvig 在udacity的公开课《Design of Computer Programs》，，很有意思，很受启发。Peter Norvig一把年纪了（1956年生，今年56岁了），很有激情，非常佩服

庆幸大学时期便坚持完整读厚厚的英文原版图书，坚持听英文的公开课，使得听Peter Norvig视频，没有障碍。如此才能受教于Peter Norvig，虽仅视频观摩，仍觉三生有幸，受益匪浅。

在第二讲“Back of the Envelope”里面，他一步一步的设计程序，来解算式迷（cryptarithmetic），并优化性能。算式迷也是我小学时期做的题目，长大了，发现居然还能用计算机程序轻松的解决，觉得很有意思，记录下来，权当备忘：

什么是算式迷（cryptarithmetic）

例如:

图片来自维基百科 Verbal arithmetic

1. 字母代表0-9之间的数字.
2. 不同的字母代表不同的数字.
3. 相同的字母代表相同的数字.

那么各个字母分别代表什么数字，才能使等式成立？

程序解法

程序列举出所有可能，挑出满足条件的，便是答案。问题变为：

1. 如何列举出所有可能

2. 如何判断满足条件

用排列列举出所有可能

itertools.permutations可以列出排列，比如

# 1， 2， 3的全排列
list(itertools.permutations((1, 2, 3)))
=>
[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]

# 1， 2， 3的全排列，仅取前面2位
list(itertools.permutations((1, 2, 3), 2))
=>
[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]

def fill_in(formula):
    # 找出所有的大写字母（替换为数字）
    letters = ''.join(set([s for s in formula if s in string.uppercase]))
    # 列出所有的可能
    for i in itertools.permutations('0123456789', len(letters)):
        trans = string.maketrans(letters, ''.join(i))
        # 变换。 比如"A+A==B" => "2+2==3"
        yield string.translate(formula, trans)

如何判断满足条件

eval 可以用来帮忙：

eval('123 + 345 == 567') => False
eval('123 + 345 == 468') => True

def valid(f):
    "Return True iff the statement eval to True, eg: 1+1==2"
    try:
        return not re.search(r'\b0[0-9]', f) and eval(f) is True
    except ArithmeticError:
        return False

解决问题

def solve(formula):
    return (f for f in fill_in(formula) if valid(f))

for s in solve('SEND+MORE==MONEY'):
    print s

=> 9567+1085==10652

但解决的过程比较漫长，我的电脑需要需要花掉17.5s，才能找出解。profile发现eval花了大部分时间(14.3s)：

python -m cProfile code.py

  1814400    0.920    0.000    4.042    0.000 re.py:139(search)
  1814400    1.136    0.000    1.472    0.000 re.py:226(_compile)
  1451520   13.955    0.000   14.334    0.000 {eval}

优化性能

Peter Norvig说，优化它有两种做法：使eval变得更快，或者减少调用次数。他选择了第二种方式： eval一个string，需要经历parse，compile为bytecode，执行的三个阶段，前两个阶段是可以复用的： 比如可以把表达式变成下面的函数：

# SEND+MORE==MONEY
lambda E, D, M, O, N, S, R, Y: (1*D+10*N+100*E+1000*S)+(1*E+10*R+100*O+1000*M)==(1*Y+10*E+100*N+1000*O+10000*M)

# E, D, M, O, N, S, R, Y 是参数

变成函数的过程，可以用eval，并且仅仅调用一次，其它的仅是调用生成的函数

def compile_word(word):
    if word.isupper():
        terms = ['%d*%s' % (10**i, d)
                for i, d in enumerate(word[::-1])]
        return '(' + '+'.join(terms) + ')'
    else:
        return word

def compile_formula(formula, verbose=False):
    letters = set(re.findall('[A-Z]', formula))
    terms = re.split('([A-Z]+)', formula)
    params = ', '.join(letters)
    expr = ''.join(map(compile_word, terms))
    f = 'lambda %s: %s' % (params, expr)
    if verbose: print f
    return eval(f), ''.join(letters)

def faster_solve(formula):
    f, letters = compile_formula(formula, True)

    for digits in itertools.permutations(range(10), len(letters)):
        try:
            if f(*digits) is True:
                table = string.maketrans(letters, ''.join(map(str, digits)))
                r = string.translate(formula, table)
                # 数字的首位不能是0
                if not re.search(r'\b0[0-9]', r):
                    yield r
        except ArithmeticError:
            pass

在我的机器上，faster_solve 仅需要1.2s，比未优化的solve快10几倍

Google后发现，还有用prolog解决此问题的，速度比这个快上千倍（花的CPU时间在ms一下）Cryptarithmetic Puzzle Solver，以后有时间再研究一下，应该比较有意思。

设计和实现一个高性能的redis go client之实际性能上限

这几天有打算写一个redis的go的客户端：

1. redis是一个非常好用的k/v存储，广泛应用
2. 在负责的一个项目中，使用了redis做缓存，虽然redis本身很快，但client可能比较慢，看了几个开源的实现，发现有改进的空间
3. redis协议比较简单，实现一个客户端时间可控：可能一个周末可实现一个可用版本
4. 可以促进对redis的了解

我比较偏好把程序写得简单，高效。为了高效，需要知道一个天花板：最快可以做到多快，所以写了下面的go代码：

func BenchmarkRawUpperLimit(b *testing.B) {
        c, err := net.Dial("tcp", "localhost:6379")
        if err != nil {
                b.Error(err)
        } else {
                buffer := make([]byte, 1024)
                ping := []byte("*1\r\n$4\r\nPING\r\n")
                b.ResetTimer()
                for i := 0; i < b.N; i++ {
                        c.Write(ping)
                        c.Read(buffer)  // receive PONG
                }
        }
        c.Close()
}

go test -bench .

BenchmarkRawUpperLimit    200000             13313 ns/op

发送ping，等待redis返回，需要13313ns，也就是每秒75k次 （测试机器为Intel(R) Core(TM) i7-2600 CPU @ 3.40GHz)

下面是相应的python版本, 作为一个简单的计较

import socket, time

sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
sock.connect(("localhost", 6379))

buffer = bytearray(1024)
loop = 0
start = time.time()
LOOP = 1000000
while loop < LOOP:
    sock.send("*1\r\n$4\r\nPING\r\n")
    sock.recv_into(buffer)
    #  sock.recv(1024)  76k/s, a little slower than above, which is 78k per second
    loop += 1

t = time.time() - start
# about 78k per second on my computer
print t, 1 / (t / LOOP)

python版本的稍微快一点，一个可能的解释是，go语言的socket是在epoll等的基础上封装的，由runtime调度。但它与python的性能差别不大，可见go语言的runtime非常的高效

图文详解8皇后，python实现

在给女朋友讲8皇后时，用python画了一些图，还做了个gif帮助理解，记录下来，可能对在学习8皇后的朋友有用

8皇后是一个很有意思的问题，经典的回溯算法教给我们怎么系统的搜索：从一条路往前走，能进则进，不能进则退回来，换条路再试。

问题定义

8皇后问题：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上

结果表示：

由于一个皇后只能在一行，因此可以使用一个数组来记录，数组数字表示皇后在棋牌的列，数组的下标则表示行。python数组下标以0开始，故棋牌横0-7，纵着0-7，例如：

[0, 4, 7, 5, 2, 6, 1, 3]

表示的棋盘为：

搜索皇后在n行的位置

前n-1行皇后的位置，存在arr数组里。需要在第n行找一列，使皇后放在那里，不与前面n-1个皇后冲突。 如果back_tracing 为True，则是在回溯状态，在第n行的result[n_row]列有个皇后，需要看可不可以把她往右边移动

def find_legal_position(arr, n_row, n_queens, trace_back=False):
    start = 0
    if trace_back:
        start = arr[n_row] + 1
    for col in range(start, n_queens):
        ok = True
        for row in range(n_row):  # [0, n_row)
            if arr[row] == col:  # two queens share the same column
                ok = False
                break
            if n_row - row == abs(col - arr[row]): # two queens share the same diagonal
                ok = False
                break
        if ok:
            return col
    return None  # no position we can place a queen on the n_row

回溯解8皇后

从一条路往前走，能进则进，不能进则退回来，换条路再试

def solve_queen_puzzle(n_queens):
    result = [0] * n_queens
    n_row = 0  # 从0行开始，一行一行安置皇后
    while n_row < n_queens:
        pos = find_legal_position(result, n_row, n_queens)
        if pos is not None: # 往前走
            result[n_row] = pos
            if n_row == n_queens - 1:
                yield result[:] # 找到一个结果，返回
        if pos is None or n_row == n_queens - 1:
            while 1:
                n_row -= 1
                if n_row < 0:
                    return # 所有路已经穷尽
                pos = find_legal_position(result, n_row, n_queens, back_tracing=True)
                if pos:  # 换条路试一下
                    result[n_row] = pos
                    break
        n_row += 1

动画演示搜索过程

红色表示无路可走时进行回溯

coursera-dl, youtube-dl,视频下载利器

coursera-dl

Coursera是个好网站，上面有很多课程，课程列表，涵盖多个学科，并且免费。学习充电的好地方。近段时间，我在上面学习：

1. Andrew Ng的 Machine Learning，毕业这3年，断断续续在看Machine Learning的东西，但没有系统的学习，Andrew Ng正好系统的讲解，可以弥补一下。
2. Alex Aiken的 Compilers, 前段时间，寻找新的工作机会，到阿里面试时，被问到compiler。但我的大学本科是信息与计算科学，学了一大堆数学，编译原理学校给省掉了，自己也没有自学。无奈承认不会，虽他们没有因此拒掉我，但确实不会，念念不忘，Coursera正好有这个课程，正好可以系统学习一下

但家里面的网速，在线看，卡，影响心情。正好遇到coursera-dl，可以完整的把video下载下来，比如Compiler

# 需要注册Coursera，并且enroll
# 它支持wget，python等下载。wget是久经考研的，相信，比起相信同志，更相信它
coursera-dl -u "" -p "" -w `which wget` compilers-003

youtube-dl

Youtube上更是有很多好的视频，比如Google IO等，有的还有1080p源。在线看1080p，需要的是耐心，离线下载能搞定。比如下载 Google I/O 2013: Keynote， :

# -f 后面的是视频质量，这几个数字分别代表 1080p/720p/480p/360p
#    详细参看http://en.wikipedia.org/wiki/YouTube#Quality_and_codecs
youtube-dl "" -f 37/22/35/34

一个小脚本，下载我感兴趣的Google IO的视频：

#! /bin/bash

lists=(
   
);

for l in "${lists[@]}"
do
    echo "downloading $l"
    # http://en.wikipedia.org/wiki/YouTube#Quality_and_codecs
    youtube-dl "$l" -f 37/22/35/34
done

端午节时，三天假期，五台山远足。脚本跑着。回来时，已经搞定。