技术手记

爆流量记

缘起

过年回家那几天发现此博客垃圾评论暴涨, 从一周几条涨到一天一千多, 当时懒, 人肉删了就没管. 回北京后发现还是这样, 删是删不及了, 只能把 Akismet 打开, 拦的效果还不错, 再要求访客第一次发表评论的用户要过审核, 这下好了, 基本上能拦住, 偶尔一两条漏的人看一下也就砍掉.

这个空间买的就很便宜, 一个月 5G 流量对纯文本的 blog 来说完全够用. 在搞垃圾评论期间发现流量暴涨, 在一月还剩下没几天的时候收到邮件说流量达到 90%, 当时想了下估计是发垃圾评论的在抓站把流量搞的, 等我把垃圾评论处理了应该就没事, 看后台监控好像没怎么涨了就没继续关心. 第二天收到邮件说流量爆了, 而且登空间后台都登不上去. 没办法只能联系空间提供商 flyssh.net, 说我是被垃圾评论搞挂的, 让帮看看能不能处理, 那边很快回复说看我爆的还挺厉害, 但是因为我也是受害者, 免费给我加了 5G 流量, 但是垃圾评论这事他们搞不了, 祝我尽快搞定.

解决

我观察了下空间后台的流量监控, 发现不是实时更新, 而是一天一次. 另外由于服务器在美国, 上面的时区是 -5:00, 所以是每天下午一点结算, 我搞定了垃圾评论后每天流量还是非常夸张, 之前正常时一天不到 100M, 现在却一天 1.5G+. 想不清楚到底哪里有问题, 看了下后台有 Apache 的日志, 就抓下来分析了下, 这一看不要紧, 怎么 404 的次数这么多而且流量都这么大?

HTML 返回 次数 总字节 平均长度
200 4219 103,647,235.00 24,566.80
301 2597 1,750,723.00 674.13
500 4 13,882.00 3,470.50
302 62 49,992.00 806.32
403 4596 15,855,133.00 3,449.77
304 274 57,134.00 208.52
404 10555 1,488,782,649.00 141,050.00

从大到小挨个分析, 最大的是 404. 看错误绝大部分都是因为下 win7 未遂. 想起来 yewen.us 这个域名曾经在度娘内部提供过下载, 放的是度娘发的 X200/X201 可激活的 Win7 Pro, 估计有人用迅雷或旋风下载过, 结果被他们记住这个链接了. 但是我都返回 404 了居然还不停的请求, 真坑爹. 拦不了迅雷旋风就从自己这改变, 将那个 win7 的链接, 以及下载主入口都添加 301 跳转, 让去找正确的 ourfcr.info 下. 另一个 404 来源的大头是最近被搜索引擎抓站, 因为我没显式提供 robots.txt 也返回 404, 应对办法就是加了个空的 robots.txt 到根目录.

404 的另外一个问题是返回页怎么也都这么大? 本来应该跳转到 /404.shtml, 一个不到 1k 的文件, 实际却跳到了 /blog/404.php. 中间换过一次主题, 新主题的 404 页面包括了整个主题框架, 就因为这所以数据大? 在弄不明白为什么 404 不是跳到 /404.shtml 的情况下, 果断将 /blog/404.php 先改成了一个纯 html 的:

<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML 2.0//EN">
<HTML><HEAD>
<TITLE>404 Not Found</TITLE>
</HEAD><BODY>
<H1>404 Not Found</H1>
</BODY></HTML>

其次是 200 正常返回, 看了下 Agent, 不少还是垃圾评论发送者和搜索引擎的爬虫, 这没办法, 只能希望搜索引擎爬完后不再爬那些过期页面, 垃圾评论被 ban 掉后不再骚扰.

再一个大头 403, 看记录似乎是某些搜索引擎或垃圾评论发送者的爬虫逻辑写的有问题, 每访问我 blog 的一个页面都会再去访问一个受限的链接, 从而引起大量的 403 错误. 这个不知道怎么写 robots.txt, 就放那吧, 等他抓完了应该就好了.

上面的所有所有修改都完成后, 单天总流量下降到 77.0MB, 算下来是绝对不会超过每月 5000M 的限额了.

其他问题

搞定流量问题后, 还有剩下几个不紧急的问题:
1) 404 为啥是由 /blog/404.php 返回?
2) 开 Akismet 防垃圾评论是不是靠谱?
3) 垃圾评论和爆流量都是换主题后导致的, 中间有联系么?

对 404 那个检查实验了半天, 应该是在 WordPress 开启固定链接时, 在根目录的 .htaccess 里加的 rewrite 参数将不存在的访问默认的都导向 /blog/ 来处理, 所以空间后台的错误页面管理失效, 我那个改动是正确的, 丑点就丑点吧, 反正正常人类浏览遇到 404 点下后退好了, 发垃圾评论什么的我才不管呢.

Akismet 固然是有效的, 但是很多时候也担心是否有性能和流量的问题, 搜了下果然还有更 ws 的解决方案, 那就是中文验证. 之前发到我 blog 的垃圾评论都是英文的, 而考虑到我的 blog 应该不会有全文非中文的评论, 所以只要限制评论必须带中文就行了. 修改主题的 functions.php, 在最前面加上这么一段

function scp_comment_post( $incoming_comment ) {
    $pattern = '/[一-龥]/u';

    // 禁止全英文评论
    if(!preg_match($pattern, $incoming_comment['comment_content'])) {
        wp_die("You should type some Chinese word (like "你好") in your comment to pass the spam-check, thanks for your patience! 您的评论中必须包含汉字!");
    }
    return( $incoming_comment );
}
add_filter('preprocess_comment', 'scp_comment_post');

这下整个世界清静了, 连偶尔一两条 Akismet 放过去, 但因为访客第一次发言进入审核队列的垃圾评论都没有了. (上面那段代码很好理解, 就是把汉字在 utf-8 里的编码位置开头结尾过一遍, 看评论中是否有文字在其中, 不在就报错)

对于换主题导致的问题, 不知道垃圾评论是否有关系, 这个主题用的人挺多, 作者还有几个其他主题也在被很多人用, 应该不至于在主题中嵌代码通报垃圾评论发送者, 只能说是个巧合, 或者说垃圾评论发送者对这个主题有匹配模板, 能快速从搜索引擎那搜到且自动发垃圾评论. 爆流量则是有一定关系了, 一是主题允许换色, 导致多个 css 加载, 二是 404.php 等处理页面太大, 换色的问题想了下让大家忍受下我的审美观, 不准换就行了, 404 的问题前面解决过了.

附小广告
flyssh.net 提供的 ssh/vpn 都挺靠谱, 推荐下, 要折扣优惠码的可以私聊我. 他家虚拟主机如果最便宜那几档还有卖的话也非常划算, 可惜现在最便宜的也是 100RMB/年. 管理员都很 nice, 出问题时都很快很友好的帮助, 都是搞技术的, 沟通特别舒畅.

搜索和推荐的需求猜测

最近去围观了几场年会, 刨开文化的差异, 从不同公司里领导层和员工更关注更强调的点也是可以看出来不同产品的差异. 把自己看过做过的一些东西揉进去连起来看, 有一些关于 “需求满足” 的想法, 抛砖引玉, 请大家提供更多的观察角度和建议.

搜索和推荐, 以及计算广告

我不知道业界对 “搜索” 和 “推荐” 的定义分别是什么, 我自己的定义是
推荐: 对一个特定的用户, 根据其历史行为, 推测其可能的需求, 推送满足潜在需求的内容给用户
搜索: 对一次特定的请求, 推送满足该请求的内容给用户

这么一分, 搜索就可以看成是推荐的一个真子集. 搜索相对发展的比较成熟一些, 个人觉得现在的发展重点更多在 “理解需求本身”, “内容丰富度” 以及 “内容时效性” 几个方向上. 而推荐, 现在更多的问题应该都在 “推测需求” 这个环节.

计算广告, 则是在搜索和推荐的内容中加入商业结果, 本质是一样的, 只是需要额外考虑商业收益和可持续性. 任意一家商业公司都需要收入来维持整个公司运作和发展, 在资源受限的情况下, 一般都会先考虑商业结果接入, 毕竟活下去才是王道, 死了就啥都没得搞了.

搜索中的需求

搜索的需求都更直接, 而且相对独立, 比如我搜 “西二旗地铁站附近的饭馆” 或 “北京到上海的机票代理”, 直接给结果就行了. 而一些比较复杂的搜索, 因为事件本身需要更多考虑, 或是因为需求比较难用文字表达, 则会引起一系列的搜索, 但是这一堆搜索请求也都是可以比较容易将其黏合在一起成立一个系列事件. (各搜索引擎的个性化搜索中的短期行为个性化)

因为搜索需求是如此的直接暴力, 用户就是需要某物品或服务, 所以广告也可以直接暴力的给出, 效果还很好 (稍微好点的广告应该都可以做到百分之几的点击率, 转化率也不低)

也因为搜索需求的独立性, 偏搜索的产品在考核时更多都用 PV (Page View, 页面访问数) 说话, 用户黏度不大, 流失风险也不低 (甚至压根就没有用户概念, 只有请求的定义). 个人感觉这就是百度推新首页, 阿拉丁, 开放平台等产品的目的, 留住用户, PV 至上向 UV (User View, 独立用户访问数) 转换, 而且还能降低系统消耗并提升效率 (变现/搜索结果满足需求等效率)

推荐的需求猜测

和推荐有关的东西很多, Netflix 的影片推荐, douban 的读书推荐, 各种个性电台的音乐喜好推荐, 电商网站的商品推荐, Web 2.0/SNS 的内容推荐. 其中有一些是能比较直接带来收入的, 比如影片推荐, 商品推荐, 做的人很多且深入, 而另一些变现能力不明朗的产品, 比如个性化电台, 大部分都还只是玩票, 公司有人的情况下做着玩玩, 攒点技术.

Web 2.0/SNS 的内容推荐在推荐中的位置比较尴尬, 一方面用户需要更多更好的内容推荐 (用户需求强烈), 另一方面变现比较难 (公司投入回报比低). 为了留住用户显然要做推荐, 从中能挤出点商业需求弄点钱让自己活下去也是很多推荐团队要考虑的事.

回到推荐的需求判断, 一般推荐系统都是在根据历史行为猜用户的未来需求 (实时的直接需求那都是搜索, 不管是通用搜索还是站内搜索), 所以最朴素的想法就是用户过去看过啥, 喜欢啥, 关注啥, 买过啥, 就给 TA 推荐类似的东西. 这种简单粗暴的方法在影片推荐什么的会比较有用, 效率高, 相关性也好, 用户的个人喜好一般不会变化太快, 而且会一直有相关需求, 如果需要维持内容丰富度, 可以做一些随机化, 或用用户的朋友的喜好来推荐.

但是其他行业中, 就会有是否是 “持续性需求” 的差异. 电影我看了这部还会看别的, 吃饭我吃过这家店还会考虑别的类似的店, 但是有一些需求一次完成很久不会变, 比如我买了个路由器, 只要不坏或脑子抽了要骚包下, 一般不会去买第二个 (帮别人买这种行为应该分开考虑, 或者现在这种行为也很多?), 再比如学英语我报了个老罗英语后, 至少短时间内我不会再考虑去报个新东方或别的.

不同的持续性, 也应该有不一样的做法. 电影, 音乐等已经有良好分类标签的持续性需求, 可以直接提关键属性来做推荐 (主演, 主唱, 导演, 词曲作者, 风格等), 还会有一些影评乐评等用来辅助标记, 还有排行榜, 感觉相对比较容易, 至少做个原型出来要容易, 同时, 用户兴趣的相似度也是可以考虑的, 比如看了电影 A 的人都看了电影 B, 那现在有一个人说他看了电影 A, 我们也可以推荐他去看电影 B. 视频等没有明确分类标签的持续性需求, 计算被推荐条目和用户的相关性比较麻烦, 也不够准确, 这时候用户之间以及被推荐条目之间的相似度似乎是一个更可以考虑的点, YouTube 曾经发过两篇 paper, 其中 08 年的 paper 有很多很炫的方法, 但是同样的那批人在 10 年发的 paper 就回归到最朴素的相关浏览算法了, 而且还特别说了, 数据量大是一个非常明显的优势, 另外展示位置和展现样式的影响因子也非常非常大 (除非算法有天翻地覆的差异, 位置和样式才是最大的影响因子吧 :P). 而像衣服等 “有搭配的持续性需求”, 除了用户购买的相似度, 是否可以考虑从搭配需求上去做? 比如有 MM 买过一件大衣, 除了继续推荐类似的大衣 (通过所有用户的查看/收藏序列), 其实更应该去推荐可搭配的帽子/围巾/靴子什么的才对? 比如笨狗前年脑抽买了个大显示器, 过了一段就攒了台电脑主机, 然后还买了一个音箱… 这就是典型的可搭配持续性需求. 有关搭配性的持续性需求还没去找相关的 paper, 如果有麻烦告诉我一下.

人人的推荐需求

回到人人或其他生活平台级的推荐系统, 因为信息源过多且不集中, 所以简单的文本提取关键词然后按这些关键词推荐的方式绝对不会工作的很好. 在 NLP/IR/DM 支持下, 我们可以识别出用户讨论的内容, 如果能再识别出 TA 是在说需求还是在提供反馈评论, 那接下来需要一个需求转换图, 按这个有向图的下游节点来推荐就好了. 一个已经买了智能机的用户你给他看无线路由的评测或购买信息是顺理成章的 (当然前提是他还没买路由), 一个正在找留学信息的用户你除了推荐留学中介, 外语培训应该也是可以的, 甚至一些出国教程, 必需品购买等都是可以的 (教人打包行李的日志视频等等)

一个好的推荐系统最大的问题在于怎么识别或预判出一个合理的需求. 大概流程如下

1. 提取用户目前的兴趣点或兴趣方向
2. 判断用户是在 seek 阶段还是 review 阶段
-a. 如果还在 seek, 直接按搜索的方法做推荐, END
-b. 如果是在做 review, 转 3
3. 判断 review 的内容是否有重复性
-a. 如果有重复性, 直接按经典相似度的方法做推荐, END
-b. 如果没有重复性, 但是有搭配延续性, 转 4
4. 离线挖掘有搭配延续性需求的转换图, 按图指导推荐方向, END

在一个信息充分度足够的平台上, 应该更容易做 4 中的那个转换图, 否则平台太过垂直, 就只能做到 2.a 或 3.a 那个地步. 比如京东如果没有商品评论, 他只能知道我现在在京东上找什么, 买过什么, 然后在同类别内做推荐. 但是如果换到一个非常大的平台上, 可以根据一些蛛丝马迹来推荐更多相关的东西 (当然因为信息量更大, 推荐的准确度会下降, 但是整体来最后的成功数应该会接近或更高). 比如知道我买了机票后, 除了可以向我推荐相关酒店, 旅游等资源 (目前 qunar, kuxun 等已经做到的), 当地的纪念品 (以前在百度, 有出差回来带当地小吃给大家分享的传统), 甚至旅行用的拉杆箱 (今天在电梯里看到一个实际案例), 这些都谁可以推荐?

如果推荐靠谱, 而且有更多的信息提交渠道, 用户可以继续提供更丰富的信息, 形成良性循环. (说提交是从数据的角度来看, 产品上包装下可能就是用户非常愿意做的分享, 比如人气之星, 分享送礼等)

CSDN 这个杯具带倒了整个茶几

最近几天要是哪个 IT 民工没有关注 csdn 密码这个事情, 估计要么是被抓去封闭开发了, 要么是死了. 如果还需要回顾下, 具体的事情经过可以参考 http://csdn.aspx2.com/, 按我能统计到的资料, wooyun 的 http://www.wooyun.org/bugs/wooyun-2010-03523 应该是最早的公开信息源, 具体的下载链接我还是不发了, 自己找吧.

csdn 那个库的真实性还是挺高的, 至少周围有不少人能验证上, ACRush 和 Matrix67 都被爆了, 而且被爆的很难看. 但根据网络消息和 scat 等人的人肉分析, 那个库的泄漏时间应该在 09 年. 其他库的真实性存疑, 至少传闻的人人库应该也是 08 或 09 年的数据, 那时候人人还叫校内吧? (刚查了下, 改名是 09 年 8 月的事) 而且密码有效率比较低, 很多能登陆的帐号也都是僵尸号, 没什么内容, 倒是有可能就是以前恶意注册的一堆水号资料被注册的人不小心弄丢了. 而且今天继续流出的新浪微博那个文件 (weibo.com_12160.dbh) 和人人库 (xh-2.txt) 几乎是一样的.

问了人人安全组的人, 以及和人人网黄晶的一些状态互动, 我还是相信人人应该不至于干明文存密码这么弱的事情. 不过从 wooyun 上 http://www.wooyun.org/bugs/wooyun-2010-03337 这个漏洞的回复, 和今天人人上某好友用 HttpFox 检查的结果来看, 这个漏洞很可能是真实存在的, 但是我把这个 bug @黄晶 的时候被否定了, 求有时间的人去验证下. 这种浏览器明文传输密码的事情在 KO 和 littleken 他们做 WOJ 第一版 (Noah) 的时候就被人搞过, 后来通过 SHA1+salt 加密密码, 并在浏览器提交数据前就加密, 才搞定这事.

更多的跟进消息可以见 aspx2 的那个页面, 分析上我个人比较赞同 http://www.36kr.com/p/71020.html 里面的说法, 主要的问题是 1) 新人不懂; 2) 脑残需求; 3) 历史遗留; 4) 政府要求; 5) 站点私心. 问题一个比一个严重, 而且越来越难修复. 一般来说新人不懂还是可以很快学习到, 脑残的需求还是可以被有理想的程序员拍回去, 这两个还算简单, 解决起来也容易. 历史遗留的问题一般大家都不敢动, 能用的系统你没事去改什么改? 又不算 KPI, 再说了, 改挂了谁负责? 而且很多程序员对公司并没有那么大的认同感, 都抱着 “反正过多久我就不在这了, 只要不在我手上出事” 的念头干活, 也难怪现在的很多产品烂成那样. 政府要求这种真的是一朵奇葩, 不过我倒是觉得与其明文存密码, 还不如给政府提供超级通道, 让他可以直接进来, 这样虽然都是被强奸, 好歹也算戴了个套, 痛是必然的, 好歹不会得病和怀孕啊. 站点私心这种完全就是流氓行径了, 小站还有这样可能, 做大了的站应该就不用靠这个赚钱了吧, 还是说这样来钱还是要快很多, 大家还是想赚快钱? 话说开个色情网站用来收密码好像是个挺不错的想法?

目前我看到对此事件的阴谋论包括: 1) robbinfan (csdn 那个头) 得罪了人; 2) csdn 和黑帽价格没谈拢; 3) 反抗政府实名制. 前两个都是就是论事, 听起来也很有道理, 09 年的库现在才爆发, 中间应该在黑市上已经流通很久了, 事实上这么一想, 很可能还有别的新库正在黑帽们手里流通着呢, 而我们还傻乎乎的说还好这次没被爆掉. 反抗政府实名制, 其实也有道理, 让大家看看网络到底多不安全, 还实名个腿, 下次漏的可能就是身份证号和家庭住址了, 再愚昧的民众也会起来反对的. 我个人对反抗实名制这个阴谋论还是挺满意的, 让民众开化最好的方式就是革命, 而革命必然会很痛, 这次痛的人多了点.

一些趣闻八卦

  • CSDN 杯我最喜欢的密码, CSDN 杯程序员最喜欢的邮箱等活动真是大大锻炼了大家的脚本处理能力, 挺好的技术普及活动. (话说为什么我的角度总这么奇怪?) 今天上午面别人就顺手拿这中间的活动所需技术当面试题给出去了, 不过结果不太让我满意 :(
  • 很多爱情段子, 算是本次惨痛的茶几颠覆 (一地杯具) 事件为数不多让人感到温暖的地方.
  • csdn 有两个比较难理解的高频密码, 一个是 dearbook, 这个我猜到都是 “第二书店”, 就是 csdn 的一个业务; 另一个 xiazhili, http://www.guokr.com/ask/item/81227/ 的 12 楼真的太牛逼了…  (正解答案: xiazhili 是 csdn 下载频道 09 年上传比较多的一 MM 会员, 众多程序员意淫的对象, 故 xiazhili 作为密码不足为奇)
  • 类似 “ppnn13%dkstFeb.1st” (娉娉袅袅十三余,豆蔻梢头二月初) 的密码, 果然是文艺到家, 其实我猜这是某百度员工的杰作? 因为百度的很多密码就是唐诗宋词中的某一段变换而来, 连内网给的好密码样例都是 “Hhzstsla!” (黄河之水天上来啊!), 而用过的类似密码更是不计其数. 话说 MySQL 好像也是个好密码? (明月三千里, 好冷…)

有关密码安全机制, 我自己的密码一直是分级的, 目前来看还算安全. 数字密码有一个纯 6 位数字应对脑残的只能用数字做密码的场合 (比如某些电信业务), 有一个好点的 6 位数字密码拿来给银行卡用. 网络密码有一个 6 位弱密码用来注册那些我不甚信任或无所谓的网站, 丢就丢吧, 反正也不是多大个事, 有一个 8 位的大小写字母加数字做一般强密码 (有些地方不然用特殊字符), 最后有 8-12 位的强密码来把关最后的核心业务 (gmail, 网银, 支付等, 且跟钱有关的都分开设定).

设定密码的方式其实用中文拼音转换就挺好的, 很多字符做下变化就模糊掉了, 比如 {数字 1, 大写字母 I, 小写字母 l, 特殊字符 !} 就是个很好的互换集合, 类似的还有 {数字 0, 大写字母 O, 小写字母 o} 等等. 做个样例: “不怕猪一样的对手” -> “bpzyydds” -> “bPz!yDd5”, 这样就又安全又好记了.

我个人建议密码还是学我那么去保存, 或用一个开源的密码管理器来管理, 开源的意思是至少自己信得过这个东西, 不然这一丢更惨, 所有的都没了.

解答随机抽数系列问题并说明 bug

十月份的时候写了一篇 面试题, 随机抽样问题及扩展, 当时这个 blog 没整好, 发在了好几个地方

前几天跟 Lee.Mars 聊, 又把这堆问题解答了一遍, 并指出其中一个问题的 bug.

原始版, 数据流 n 选 1. 构建一个可容纳一个数的 buffer, 数据流中第 i 个数过来时做一次 [0, 1] 的 random, 如果小于 1/i, 则更新 buffer. (证明过程略, 很简单的)

buf = 0
cnt = 0
for i in sys.stdin:
  cnt += 1
  if random.random() < 1.0/cnt:
    buf = int(i)

print buf

加强版, 数据流 n 选 k. 同上, 构建的 buffer 大小变为 k, 每次 rand 小于 k/i 时, 将 rand*i 对应的 buffer 更新

k = 3 
buf = []
cnt = 0 
for i in sys.stdin:
  cnt += 1
  rd = int(random.random()*cnt)
  if rd < k:
    if cnt <= k:
      buf.append(int(i))
      buf[cnt-1] = buf[rd]
    buf[rd] = int(i)

print buf 

带权版, 带权数据流 n 选 1. 同原始版, 只是对权重为 w[i] 的第 i 个数, rand 时判断是否小于 w[i]/SUM(w)

sum = 0
buf = 0
cnt = 0 
for i in sys.stdin:
  cnt += 1
  sum += int(i)
  if random.random() < float(i)/sum:
    buf = int(i)

print buf 

带权选 k 版. 这个有 bug, 无解, 因为无法保证最后选出来的 k 个数, 其 SUM(w[k1..kk])/sum(w[1..n]) = k/n, 那个概率无法算

分布式版, m 个序列最后选 k. 每个序列先按加强版选 k 个, 然后将 m*k 个数放到一起, 做带权版的 n 选 k. 由于带权选 k 版有 bug, 所以这里会有一定误差. 而实际上一般的分布式框架是可以保证每个序列数据规模分布都比较均匀, 所以最后的 m*k 个数可以当无权版直接选 k, 这样的误差在工业应用是可以接受的

注: 从 n 选 k 那个就可以很容易看出来, 这其实就是那个把一个序列打乱成随机状态的算法简化, n 选 1 只是 n 选 k 的一个特例

乱弹 EdgeRank

EdgeRank 是今年 Facebook 在 F8 开发者大会上提出的对 fb 新鲜事 (Feeds) 排序的新算法, 用于区别默认的按时间逆序的 timeline. 不像 PageRank 还有很多论文或学术界的资料, 目前没有什么官方资料讨论 EdgeRank, 搜到的资料大部分来自在线广告代理公司或优化团队.

EdgeRank

EdgeRank 用于当某个用户查看他的新鲜事时, 决定这些新鲜事先后顺序的一个排序算法. 算法核心是每个事件对这个用户而言的权重 E, 其计算公式是 E = u*w*d, 其中

  1. u, 事件生产者和观察者之间的亲密度
    • 亲密度主要指的是互动情况, 互动越频繁亲密度越高
    • 互动可以是单向的, 比如 A 经常关注 B, 而 B 不怎么关注 A, 那 u(a,b) 和 u(b, a) 的权重不一样
  2. w, 边权重 (主要是事件的类型)
    • 边权重主要受事件类型影响, edgerankchecker 给的关于点击跟其他事件的关系可以大概说明
      • i. Avg Clicks Per Like: 3.103
      • ii. Avg Clicks Per Comment: 14.678
      • iii. Avg Clicks Per Impression: 0.005
  3. d, 时间衰减因子
    • 比较少见到讨论时间衰减因子怎么做的, 猜测是类 log 变化
    • 如果将 EdgeRank 公式只保留 d, 则 EdgeRank 退化到经典 timeline 模式

GraphRank

EdgeRank 用于描述某事件对某观察者而言的重要性, 考虑了事件生产者和观察者的亲密度, 事件类型以及时间衰减因子. 而对于一些还不是好友关系的事件需要 push 时 (比如一些公共信息), 或是来自好友的分享, 还要考虑分享是否需要被关注, 则引入 GraphRank 的概念.

GraphRank 跟 EdgeRank 的区别主要是在 u*w*d 之外, 再加了一层事件生产者和观察者之间的相关度, 变为 u*w*d*r.

其中相关度 r 是一个和亲密度无关的影响因子, 亲密度更多受最近的互动频度影响, 相关度则是一个时间无关的特征, 描述两者相似度

EdgeRank 的意义

Timeline 模式对大多数人来说其实已经够用, 而 EdgeRank 排序后的 Feeds, 并不能有一个很好的效果评判标准. 看用户在 Feeds 模式下是否有比 Timeline 模式更好的体验怎么看? 用 item 的先后顺序和点击序列做比较? 很难, 而且因为面对的是有感情的人 难保今天我心情好愿意什么都看看, 明天心情不好就只看所谓的感兴趣内容, 那怎么判断某天的效果好坏? 难不成 fb 还能预测我心情?

从大部分广告相关的资料来看, 受 EdgeRank 影响最大的应该是那些企业用户. 以前企业用户可以花比较低的价格建立一个公共主页 (Page), 然后以比常规广告便宜得多的方式获得大量粉丝 (Fans/Follower), 对于这些成为粉丝用户, 企业的新广告就可以以几乎免费的价格推送到这些人的 timeline 中. 显然这样的结果不是 Facebook 乐于见到的, 你们都可以不花钱做广告了, 那我们喝西北风么? 而且, Facebook 也想通过 EdgeRank 让企业知道, 他的多少粉丝是僵尸粉, 都是没意义的.

回到 EdgeRank 的定义, 相比较 timeline 模式的, 区别就在多出来那两个参数 u 和 w, w 没什么好说的, 可以认为就是简单加权, 或者考虑事件对用户的重要度, u 才是 EdgeRank 的核心所在. 如果 a 跟 b 互动少, 那么 u(a,b) 值变低, 则导致 b 发布的东西在 a 那的排名就会很低, 如果把 a 看成一个粉丝, 而 b 是某企业的主页, 则这个主页发布的消息在这个粉丝这可能就完全看不见了.

所以, 为了保持现有粉丝的有效性, 企业必须经常发布一些互动活动来保持现有粉丝的活跃度, 否则千辛万苦弄来的粉丝都没意义了. 而同时为了把那些已经僵尸掉的粉丝挽救回来, 以及扩展新粉丝, 企业还是需要投放大量广告, 这样 Facebook 的广告业务就不会因为公共主页粉丝数变多而衰落, 整个公司也就能一直维持很好的盈利状况了. (最后这段有点阴谋论和职业敏感在里面, 大家看看就好)

参考资料

  1. http://techcrunch.com/2010/04/22/facebook-edgerank/
  2. http://edgerankchecker.com/edgerank/learn
  3. http://edgerankchecker.com/blog/
  4. http://www.socialmediaexaminer.com/6-tips-to-increase-your-facebook-edgerank-and-exposure/
  5. http://qing.weibo.com/2282115205/88065085330003gq.html

Hadoop Streaming 的奇怪问题

之前一直在百度用内部改过的 hadoop 版本, streaming 接口下, 一直将 map command 写成 “sh mapper.sh | sort | sh combiner.sh” 来做人肉 combiner, 相安无事. 到人人后, 发现这个做法有问题, 今天测试了下, 果然很奇怪, 求 hadoop 大拿解答.

当前实验的版本是 hadoop 社区 0.21.0

实验 1. 跟经验不符的情况

mapper.sh

awk '{print $$}'

reducer.sh

wc -l

map command

sh mapper.sh | sort | sh reducer.sh

这时候, 单个 map 并不只输出一行信息, 而是一行输入会导致一行输出

实验 2. 符合预期, 但很别扭的写法

修改 mapper.sh 如下

awk '{print $$}' | sort | wc -l

修改 map command 如下

sh mapper.sh

这时候, 单个 map task 输出就只有一行了

实验 3. 不得已再封一层的方法

基于实验 1 新增一个脚本 xp.sh 如下

sh mapper.sh | sort | sh reducer.sh

并修改 map command 如下

sh xp.sh

这时候的效果和实验 2 结果一致

结论

至少在 Hadoop Streaming 0.21.0 这个版本里, 其执行方式并不是 cat input_data | map_command 这样, 其中 map_command 必须是一个单指令时才符合这个假设

讨论下密保, 找回密码和申诉

想起来写这么一篇完全是因为最近在酷壳 (CoolShell) 上看到这么一篇 http://coolshell.cn/articles/5987.html 并在后面跟人口水战了一把, 有一些想法提出来.

首先, 密保. 密保应该是在密码外, 多出来的一层或多层安全措施, 可以是另外一套校验码 (比如以前 WoW 的充值卡背面的阵列数字), 也可以是短信或类似的动态口令, 还能是硬件 (比如 U 盾). 其目的都是为了使得帐户更安全, 当密码过于简单被人破解, 或被不该知道的人知道密码后并不能进入帐户. 这个东西很赞, 很多时候也很烦, 所以一般不是特别要紧的东西, 相信大多数人都会尽量放弃密保. 今天我去尝试了下 Gmail 的两步登陆, 发现把整个工作量增加了很多, 而且如果手机丢了, 登陆帐户将非常麻烦, 没补过手机卡, 不知道这个纠结的时间会持续多久, 所以最后还是取消掉了. 之前 QQ 的异地登陆密保卡也因为宽带动态 IP 经常被识别成邻省而烦不胜烦, 最终取消. WoW 的密保卡也是经常忘了在哪, 电脑里保存的电子版要切出来看一下再切进去输一次, 巨烦无比, 最终也放弃. 倒是银行的一直不敢动, 还有以前公司的 Token, 一是这俩用起来比较简单, 二是实在关系要紧事, 不敢怠慢.

然后是找回密码. 顾名思义这个功能应该是密码忘记, 或被他人恶意篡改后需要找回来的时候需要. 一般密码找回无非是用备用邮箱重置密码, 或用绑定过的手机接收一个校验码来重置密码. 但是, 如果比较悲剧的是备用邮箱压根没绑定, 或一起被盗, 手机也丢了的情况下, 只能各种叫天不应叫地不灵, 这时候就需要走到下一个功能的流程里去. 顺便说下, Facebook 有一个非常好玩的找回密码功能, 他把你经常联系的好友照片展示给你, 让你选这是谁, 或者给你个名字让你选哪张照片是他, 连续若干次, 如果对了就让你重置密码.

申诉, 个人感觉这又是企鹅家非常有特点的一个服务 (或者说过度设计的一个坑爹功能). 其他服务的帐号, 丢了总有办法找回来, 邮箱也好手机也好, 重置下就行. 如果没绑邮箱又没绑手机, 这时候找不回来只能说明这个东西并不重要, 只能算了, 或者通过一些诡异的私人渠道去联系帐号所在服务的所有人去进行重置, 但是这种方式的可行性实在太差 (我只在 BBS 上帮人干过这事 -___-), 而 QQ 号就是这么个神奇的东西, 他对很多人很重要, 但是很多人又没有绑邮箱/手机的意识, 特别是早些年, 有手机的人都不多, 怎么绑? 而且好多人唯一的一个邮箱就是 QQ 邮箱… 这时候, 只能上土办法, 人工申诉. 当然, 腾讯做的稍微自动化了一点, 提供一些以前的密码, 或注册时的一些个人信息, 以及一些好友信息, 就可以进入申诉流程处理. (我不了解后面的具体流程, 我猜是机器做大部分数据判断, 如果明显符合可能不用触发人工审核, 比较含糊的将数据准确性交由人工最终审核)

原帖中争论的几个焦点和我的看法是

1. 腾讯是否有权收集用户信息?
狗: 我个人觉得腾讯压根犯不着在这个地方收集身份证号等信息, 要想弄, QQ 整个游戏产品线都非常容易收集, 而手机号这些, 本来如果要办密保就该提供吧, 只是如果没有这些信息, 实在想不出申诉怎么申

2. 腾讯为啥把找回密码这么简单一事就弄成这么复杂的申诉流程? 直接找回不就完了?
狗: 要知道腾讯活了多少年了, 之前的多少用户的信息是不全的, 压根没法按常规方式找回密码. 比如原帖楼主, 一个多年不用的号突然要用, 密码被盗或自己忘了, 当时没绑手机, 邮箱不知道是否就是自己现在在用的, 那只能进入申诉流程. 我自己最早的 QQ 号是 01 年开始用的, 而我 05 年才拥有自己的手机, 而且随着上学, 实习, 工作, 这些年已经换了好几个号, 不是每次切换都会记得把这些号都转一次的, 有时候也没法转 (我去香港呆过半年, 手机号换香港的, 则大陆的号可以取消绑定, 而香港号无法绑定上密保, 你让我怎么办? 绑老爸的?), 而邮箱, 因为 Gmail 太好用, 我以前留的那个 Yahoo 邮箱早被删号了, 而如果 QQ 密码不丢, 估计我也会忘记有这么回事. 而更多的群众用户的情况是, 压根不用邮箱, QQ + 百度就是他们的网络入口, 手机号非常勤快的说换就换, 都不在乎后面会有什么关系. 所以, 除去少部分精英, 大部分人并没有常规找回密码的意识和能力

3. 不能引导教育用户跟精英一样可以享受密码保护功能么?
狗: 这个… 如果大家愿意去调查下, 这个还真的很难… 当然, 做还是要努力去做的, 拉动一部分是一部分. 而在提示安全信息上, 老实说腾讯做的还比较好了, 提示加入密码保护, 威逼利诱绑定手机等信息, 聊天里随便说点和钱有关的就会弹信息提示注意资金安全, 应该有些用, 但是还是架不住更多的人是小白这个事实. 最重要的, 这些小白你没法抛弃, 3Q 大战已经很好的揭示了强制等手段是无效的, 还可能起到反作用

4. 那申诉流程能靠谱点么?
狗: 我记得我曾经申诉过一回, 感觉还算合理, 要求提供以前用过的几次密码, 注册时间地点, 一些好友信息 (QQ 号, 备注名什么的) 等, 相信这些资料不可能 100% 对上, 那就只能触发人工审核看有多少的匹配度, 或者机器也可以设个阈值直接判. 除了这些, 真想不出有啥靠谱的方法. 比如 Facebook 那个非常赞的功能, 放 QQ 上就未必适用, 一个是实名真实网络的延伸, 一个更多的是虚拟关系, 我 QQ 上很多人我未必就记得他们的很多细节, 经常联系的人, 可能也会忽视他们的一些变化 (比如头像等)

5. 别人可以恶意申诉, 然后自己又要申诉回来
狗: 这个没遇到过, 不好评价, 不过考虑到本来申诉的适用场景, 如果有人通过社会工程学获得一些个人信息, 然后去恶意申诉抢帐号, 那似乎也是无解? 不然如果自己帐号真丢了去申诉时, 怎么判断哪个真那个假?

总结
这个事情在腾讯那 (在人人上很可能也一样) 就是无解的, 而目前这个解决方案已经是比较好的妥协各方利益了. 我 BS 小白和喷子, 但更 BS 那些只活在理想国里干着喷子事的所谓 “精英”, 就跟最近微信启动页上引用的 M.J. 的那句话: “如果你说我是错的, 那最好证明你是对的”. 有能力去调研下实际情况, 然后给出有效解决方案, 比建立在自己假设上提出一堆看似牛逼实则无用的方案要踏实的多.

P.S. 当然, 我也没有提出更优的解决方案, 所以, 我同意被划到小白和喷子的行列, 不过, 那些 “精英” 请不要站在道德制高点, 显得好像你就高人一等, 同时还是一样的乱喷.

面试题, 随机抽样问题及扩展

今天看到张栋在新浪微博上说一个他当时被 Google 面试时碰到的一个问题 (其实我也碰到过), 觉得这个问题很有意思, 我自己也在工作中碰到过该问题的实际应用, 扩展一下, 大家一起活动下脑子玩玩 :) (答案我就不说了, 不然多没意思)

原始版
有一个店老板, 他决定从每天光顾他的店的顾客中随机选出一个人, 在当天打烊时给这位顾客发去一份小礼品, 问怎样选才能保证随机 (我表达能力太弱, 没看懂的请直接看抽象版. 关键点, 顾客不是同时来, 所以没法让这一堆人站好随机挑, 而且每天会来多少人你不知道, 可能打烊前突然来一大拨人, 老板比较呆, 只能记住一两个人, 没法把所有人的信息都记录下来)

抽象版
有一个数据流输入过来, 请在数据流停止时, 返回数据流中的随机的一个数. 注意, 数据是流, 只能一次读, 而且数据流很大, 本机无法完整存储 (最多也就很少几条)

实际应用
从每天的日志中, 对符合条件的日志, 随机抽出一条来做校验, 数据太大只能一次读过去, 要保证是随机的

加强版
如果店老板每天不是送一个人礼品, 而是送 k 个人礼品, 怎么办?

加强版的抽象
从数据流中返回随机的 k 个数

加强版的实际应用
从每天的日志中随机挑出 k 条来做校验

带权版
每个顾客有一个会员级别, 级别越高的人获奖概率越大, 怎么办?

带权版的抽象
数据流中每个数有权重 w[i], 对数字 i, 返回他的概率从 1/n 变为 w[i] / SUM(w[j], j from 1 to n). k 个数的情况类推

带权版的实际应用
从日志中按权重挑出一条或 k 条来做校验

分布式版
老板开了 m 家分店, 希望还能按平均概率给随机一位或 k 位顾客奖品, 怎么办?

分布式版的抽象
有 m 个数据流, 最后返回的是 m 个数据流合并后的随机数, 一个或 k 个

分布式版的实际应用
日志太大, 一台机器搞不定, 分布式抽取随机的一条或 k 条来做校验 (我下星期会做这个, 所以不要说面试题都是面试官蛋疼想出来坑爹的…)

nginx/php/检索折腾记

仅仅是想实现一个查询接口, 后台每天凌晨更新一份数据, 按存储. web 端可以查询所有 key1 对应的记录, 或者 key1 + key3 的记录, key2 不管, 但是也是个 key, 而且结果要按 key1, key2, key3 来排序. 这里有个问题是只按 key1+key3 查, value 有多个

只会很土鳖的 php 和 python, 于是考虑 php 做 web, 后面用 python 来做查询

机器上没有 web server 和 php, 于是先装. 没有 root 权限, 所以尽可能简单的搞, 把 nginx, pcre, php 都下到 /home/yewen/soft, 解压备用. pcre 是一个库, nginx 需要这个库的支持才能读取跟 php 连起来的部分配置

# 编译安装 nginx
cd ~/soft/nginx-1.1.1
./configure --prefix=/home/yewen/nginx --with-pcre=/home/yewen/soft/pcre-8.13
make
make install

# 改配置
cd ~/nginx
vim conf/nginx.conf

# 此处修改端口号 (http/server/listen)
# 修改 php 支持 (去掉 http/server/location ~.php 那一大段的注释, 不是 proxy)
# 修改 php 支持的路径fastcgi_param SCRIPT_FILENAME /home/yewen/nginx/html$fastcgi_script_name;
# 直接启动
./sbin/nginx

# 编译安装 php, 必须启用 fpm
cd ~/soft/php-5.3.8
./configure --prefix=/home/yewen/php --enable-fastcgi --enable-fpm
make
make install

# 改配置
cp php.ini-production ~/php/etc/php.ini
cd ~/php/etc
cp php-fpm.conf.default php-fpm.conf
vim etc/php-fpm.conf

# 将 user/group 改为本地用户
# 去掉 pm.min_spare_servers和 pm.max_spare_servers前面的注释并设置合理值

# 启动
cd ..
./sbin/php-fpm

写了个很简单的 php, 就是接受一个输入 key, 然后把这个 key 作为参数, system 调用 python 处理, 输出到某临时文件, 然后 php 再读这个文件输出, python 处理是用的最土鳖的扫描文件的方式, 而且由于文件里是按 key1, key2, key3 的顺序排序, 我们的查找有按 key1+key3 来的, 所以必须扫描整个文件, 后来发现这么搞实在不靠谱, 一次检索太慢了, 要数据规模稍微大点, 并发多点, 那就崩溃了

于是考虑把所有数据都加载到内存里来, 用 python 做一个 daemon, 然后 php 通过本机 socket 跟这个 daemon 互动. 不会搞 socket, 于是先学 php 和 python 的 socket 使用, 很简单, 只是因为我为了省事 php 编译的太简单, 居然不支持 socket 方法, 问了下 felix021, 改用fsockopen搞定.

这时候 python 是把所有数据 load 到内存, 用一个以 key1 为 key 的 dict 存储, dict 的每条记录是一个 list, 存储了所有 key1 对应的记录. 如果查询是只有 key1 的, 把这个 list 做下格式化返回就行了, 如果是 key1 + key3 的查询, 则把 key1 的 list 取出来, 做一次遍历, 看 key3 是否就是我们要的, 如果是, 加入结果 list, 最后把这个结果 list 做格式化返回. 因为每个 key1 对应的记录撑死也就几万条, 查询速度完全没有问题, 内存占用 3.2G.

后来发现这台机器没法提供对外服务 (这么坑爹的事情这么晚才得到确认), 换用一台台式机来处理, 这时候内存显然不能这么乱搞, 优化一下, 开始写人肉索引. 内存里还是一个以 key1 为 key 的 dict, 只是 value 改成 key1 在原始文件里的偏移量. 查询的时候, 打开文件跳到 key1 对应的偏移量挨条扫描, 直到到达 key1 结束的地方. 速度还是很好, 因为文件操作毕竟不算多, 至少人肉感觉不出来有迟钝, 内存占用 10M.

把这个问题泛化下, 貌似就可以做面试题了, 一个简单的查询系统. 只要按某个 key 有序, 一开始可以全内存搞, 扩大数据规模后就必须内存索引 + 磁盘文件, 再大就要多级索引, 再大就分库. (我决定今年面试我一定要问这个问题, 如果看过我 blog 的, 那就现场写实现, 如果不考虑做 list 格式化, 整个程序不超过 50 行)

Jeff Dean 对 G 的架构的串讲

原始来源: http://www.tektalk.org/2011/08/09/jeff-dean-%E8%B0%B7%E6%AD%8C%EF%BC%8C%E8%BD%AF%E4%BB%B6%E7%B3%BB%E7%BB%9F%EF%BC%8C%E7%BB%8F%E9%AA%8C%E6%95%99%E8%AE%AD/

很多资料外面都有, 不过听下串讲还是不错的

slides: http://www.tektalk.org/wp-content/uploads/2011/08/101110-slides4.pdf

youtube 的视频: http://www.youtube.com/watch?v=ulBalk7Od-Q