首先是五分钟法则的问题.
The Five-Minute Rule 20 Years Later: and How Flash Memory Changes the Rules

文章本身是很有意思的, 两年又过去了, 可以算一算现在的机械硬盘与 SSD 的价钱.

BreakEvenIntervalinSeconds = (PagesPerMBofRAM / AccessesPerSecondPerDisk) × (Price-PerDiskDrive / PricePerMBofRAM).
(另一个相对的公式不列了)

慢. 这个公式有个问题. 当然对缓存来说这基本是对的.
如果查询 item 存储位置的算法复杂度不是 O(1), 这个公式就要重新考虑了.

当然, 准确来说, O(logn), 这个 n 在一段时间内不会发生数量级的变化. 可以认为是常数.
但它既然不是 O(1), 那就应该把它算出来.
这里特别拿 B-Tree 来说, 要看这个树有几层. 有多少层已经被缓存到内存里了.
长期使用有 split 的问题. 空间利用率也不会到 100%.

此外 B-Tree 还有 Page Size 的问题. 原文说的很详细. 不提.

需要注意的一点是, B-Tree 的(随机)插入复杂度不可忽略.
B-Tree 不适于高 IOPS 的场合, 即便是 SSD.

—

CSDN TUP 的问题.

实时搜索.
P6 的中间, 加上 P8-9 的描述, 就是个 BigTable 的简化版.
如果有必要的话可以谈一谈 Bigtable 和 Cassandra.

内存 snapshot db 如果是可用性考虑的话好像有点道理,
这就相当于 memtable 大小设成内存一半略少.
如何平衡 bigtable 的几个 tuning 参数也是个小问题.

Feed 系统.
序列化, 压缩: Protobuf, QuickLZ
模板用 CTemplate 并不奇怪. memcached, tokyo tyrant 比较常见.
值得注意的是 Boost multi-index container 和 Flyweight.

以下摘自 http://flustar.javaeye.com/blog/160829

一、FlyWeight模式定义:
运用共享技术有效地支持大量细粒度对象。
二、模式解说
也就是说在一个系统中如果有多个相同的对象，那么只共享一份就可以了，不必每个都去实例化一个对象。在Flyweight模式中，由于要产生各种各样的对象，所以在Flyweight(享元)模式中常出现Factory模式。Flyweight的内部状态是用来共享的,Flyweight factory负责维护一个对象存储池（Flyweight Pool）来存放内部状态的对象。Flyweight模式是一个提高程序效率和性能的模式,会大大加快程序的运行速度。

对于 multi-index container 没有什么可评论的. 内存里怎么搞都行.

需要解决的问题方面, 数万每秒写入, 几千随机读都不是什么大问题. 不用 B-Tree 是第一步?

Direct IO 有人喜欢有人烦. 偶属于不喜欢也不排斥 Direct IO 的那种.
个人认为只有碰到 Double Caching 的情况再用.

关于用 Tokyo Tyrant 存 user-server 的做法, 越看越像 riak’s bitcask.

留一个算法复杂度分析当作业好了, 当然这里要考虑磁盘输出和 IOPS 的问题. 上面都说了一半了.

微博架构.

首先是 Push / Pull 的问题.
偶考虑到的是,
1 在线用户数量?
2 是否应该为非注册用户提供这么多实时服务?
3 用户分组带来了哪些影响?
4 服务利用率? 能否利用运营/用户监控数据? —那些不活跃的用户就不用…

要是偶会做两步.
1 hover 到推送 item 上的时候返回一个 beacon 回服务器. 分析这些结果.
2 偶要从应用上做监控, 看究竟有多少人真正得到了推送数据. 这个利用率如何. 比较哪种方式开销小.

关于 memcached 分组/库的问题没什么意见.
但 memcached 内存利用率低是众所周知的? 浪费一点也是浪费, 对吧.
这里有一个平衡问题(要容量还是要吞吐量). 还要注意前面提到的五分钟法则. 这是对普通场景来说的.
但这种 Cache 使用方式决定, 法则不适用于这种场景.
新浪这种发展模式本身注定就是自找事, 偶说把僵尸用户处理一下(加个 flag 不考虑对它们的推送), 问题说不准就可以再推迟上半年.

以下摘自 关于新浪离职

这中间有个问题是，确定需求的人基本不关心技术架构，都是在需求确定之后，讨论实现方案。

hotkey & mutex. 加一层 proxy 是可以了.
用 gearman + uniq 的方法看起来像 RPC. 那这个事情就应当作为 RPC 来看.
直说来还是技术上有问题. 对同一个请求你敢让多少台机器帮着处理? 数据的缺漏对这个应用来说并不关键.

回到 memcached 的话题. 如果都这么穿透到 db 的话, 是不是对 db 的保护不够呢?
还要加 db proxy layer 吗? 还是干脆只允许专门的机器处理数据库访问?

ps:
更尖锐一点说, 为什么数据库那么脆弱 ?

ps2:
“明白运作原理是部署应用的前提” 这句话对吗?

0.99.9 这个版本接近于这个 Code Base 下偶能做到的极限.
仍然有几个小问题做的并不够好. 不过这些问题完全不影响使用就是了. 最近也没有修掉这些问题的计划.

1 第一次超时, 第二次 (Range) 请求成功问题
如果这个文件并没有超过文件大小的限制, Range 反而是多了一步.
而且 Range 的处理也不够恰当.

如果未来能做重构的话, 偶直接会去掉 urlfetch limit 方面的判断.
把 Range 请求和普通请求用同一种方法解决.

此外要说, 偶虽然会用 Python, 但仍然没有用到语言独有的特点.

2 Range = 下载软件?
这种事情偶只遇上过一次. 就是明明写着 0-1023 却返回了 1023 bytes.
代码中有专门的判断以修复这个问题. 代码倒是很烂的感觉.
判断应来多少 bytes, 实际来了多少 bytes, 本次来了多少 bytes.
就别管它是否是 206 了.

3 加密与提交问题
WallProxy 用了一种简单的异或加密法. 还自己写了一个类似 urlencode 一样的函数.
偶觉得这种方法实在太朴素, 太奇怪.

首先如果要符合正常的 http 模式的话, 大号 POST 请求肯定要用 multipart/form-data.
直接的 POST 是 application/octet-stream 类型, 但从来没有浏览器会直接用这种 Mine Type 提交.
稍微注意一点的就会发现这个请求有问题, 完全不是浏览器发出的.

最初, 在原版 GAppProxy 基础上用了 Base64 以避免 encoding 的问题, 但要损失 1/4 的上传限制.
后来有了这种方法:
request = cgi.parse_qs(self.request.body) for k in request: request[k] = request[k][-1]
(thanks to @hexieshe)

最终还是用 multipart 解决了这个问题.

关于异或加密的问题. 偶说, 按照 block 来做几次循环移位或者是交换, 然后再用一次 xor 效果都比现在这种好的多.
当然确实是因为条件所限无法在这一层上用强加密.

真的要加密, 那就 SSL. 这没什么可争的. 只是验证 SSL 证书的任务只能靠自己.
当然 GAE Python SDK 上传的时候有验证证书, 这块代码可以考虑拿来.

既然说到这里, 不生成自签名证书的原因也就清楚了. 还有一个 CNNIC ROOT / SSL 的问题, 这里不提.

—

GAppProxy2 的推荐用法.

Google 系列服务, 靠 hosts + HTTPS 绝对没问题.
无论是 ipv4 还是 ipv6 都是这样的, 没有 https 支持的, 再用, 偶不反对.
前两天有人说 encrypted.google.com 不行了. 你出去看一看, 它的 SSL 证书的主机名是 *.google.com.
只要再找一个同样的出来, 这事情就解决了.

如果你有留心的话, 会注意到 proxy 可以设置成 google 主站, 甚至是 ipv6.google.com.
同样的方法… 加上 pac 文件, 也算是一种可以用的方法.

Facebook 有 ipv6 了, 好不好使是另一回事, 偶暂时不管.
上篇文章写了一种用 ipv6 上 twitter 的方法. 这里不重提了. 原有的 ipv6 文章也更新过了, 可以去看.
dabr 什么的也不是不能用. 所以这个事情没必要说太多.

gappproxy2-0_99_9.tar.gz

sha1sum:
702531d5ed38852471a6849f3155c9fe68b93ae4 gappproxy2-0_99_9.tar.gz

感谢 Wallproxy 作者 @hexieshe 的大力支持…

Changelog 很长, 不写了. 压缩包里有.
请务必配套使用 client 和 server. 不配套使用后果自负…

为了方便大家部署, 这次提供了 app.yaml. 并开启了 precompile 的支持.
(需要较新的 App Engine Python SDK 支持)

撒花庆祝吧. hohoho. (第一次用这个词, 不习惯呢)

—

ps:
Q: WallProxy 有自动签名的证书, 这个为什么没有?
A: 在 CNNIC ROOT 当道的时候手动验证证书还来不及呢. 这种安全性真是令人担忧哪.

ps2:
这次的断点续传达到了下载软件的水平. Content-Range 头都给你造好了.
有的论坛有 bug 的也都发现了. (当然承认由于 GAE 的原因下不了那也没办法)
想下大文件的这次真的可以拼命去下了.

ps3:
欢迎大家测试 ipv6… ipv6 上有 youtube, 有 google, 有 facebook, 有 GAE …
可以借代理 [2001:470:1f0e:456::X]:80 上 twitter… (故意的马赛克).

ps4:
配置文件 proxy.conf, 去掉 # 就不是注释了… 也就是说… 自己理解吧…

最后一篇. 预定是 4 篇就能结束的.
只是因为突然发现自己 2008 年就写了一篇很有意思的文章(搜索搜到自己了… ), 于是决定继续写.

—

网站分析师(前端技术方向), 培养方法是极其简单的.
Noscript 会用不? 会导出黑名单列表不? (这一步会卡住一些人)
导出列表之后去找一个又一个 js 文件, 分析. 分析 30 个就没有任何问题了.
(前提: 不能是同一个统计平台, 必须包括几个功能强劲的大号产品, 要知道 mousetracking 这类玩意是怎么实做的).

—

统计系统本身也存在一些细节上的问题.
2008 年年中的时候就写过这样的文章, 现在看只有偶自己做了这一点.
当时写这篇文章是为了只用统计代码实现日志分析的功能.

简单说, 偶用两条一样长的腿走路.
也就是统计代码的实力和日志分析的能力比较接近. 虽然这种比较本来就没什么意义.
过期文章解密: fcicq 的不满, 统计

偶虽然不能把自己统计系统整个拿出来,
不过, 偶可以把偶走过的路简单的总结出来. 整个流程对有基础的同学来说是很快的.
1 用 GA 和 国内的 51.la. (重点: 要像小站长一样看用户访问的页面.)
2 用 GA 学 Action Tracking 和前端技术.
3 用 51.la 学习从页面/关键词级别理解用户, 理解国内的复杂网络环境.
—可以用看 Raw Log 代替, 可是这太枯燥了…
4 写自己的统计代码, 不断修正优化统计代码, 增加(有用的)功能. (参见上面的培养方法)
—服务器端可以暂时用文本文件收集, 可以考虑用修正服务器端的方法提高用户分辨精度(见第一部分).
5 用 awk 分析文本文件 (文本文件的格式?). 生成文本报告.
—这一步就会出现指标问题了.
—既然能生成 CSV, 做图还难吗?
6 改写 awk 代码为 MapReduce. 实际上用什么都可以…
—什么 MR, 这是一般人用的东西吗… (画外音: 用 awk 模拟模拟行不 … )
7 分析报告(对产品)产生实质性影响.
—A/B Test? 转化率分析? 别忘了还有行为统计的问题.
8 增加高级数据挖掘和统计算法. 实现网站日志与统计代码的协同分析.
—许多人会挖关键词, 如果做到这里不愿意做统计了, 可以转做 Adwords, 当然 SEO 也可以…
—可以继续做其它的方向, 比如商业智能, 运维(安全, 性能优化, 监控…).
—就说商业智能吧. 把 uri 映射成具体产品(无关的扔掉), 这个肯定比真实的业务数据库还要大上一两个的数量级. 先不看推荐的效果, 就这个经验你要还是不要?

—

这一个系列综合了许多方面的内容. 意思上基本上都表达出来了.
使用偶的描述加上一些其它统计的经验, 就能够复制一个出来.
偶不知道有多少人在看. 不过从 2008 年那篇文章没有引起任何重视来看, 偶还是可以继续在前面找个椅子坐坐歇歇.

最后一句话结束: 白送你的数据仓库, 你要不要?

ps:
这话是什么意思呢?
1 数据是白送的.
2 练习的机会是白送的.
3 它既然是数据仓库, 就值得用专业级工具.
(但没鼓励你去烧钱. 你能复制 SPSS 也不错. 有些人靠一个算法的实现就能打天下)
4 如何利用数据仓库? 这个问题留给你自己吧.

小剧场:
仓库里躲着的都是用户, 一个一个揪出来, 给发糖吃 … 有不要的吗…

—

Web Analytics 浅谈系列文章列表:
Web Analytics 浅谈 (1)
Web Analytics 浅谈 (2)
Web Analytics 浅谈 (3)
Web Analytics 浅谈 (4)
Web Analytics 浅谈 (5) – 最终回

2006.7.13 – 2010.7.13

去年这个时间没有发类似的文章, 也许是因为忘了吧…
下一步要写文章讨论的话题, 大概会有不少吧.

要做的事情不少:

要结束 Web Analytics 系列.
(等待定时发布, 但好像还有没涉及到的地方. 不过不出意外的话暂时不改了.)

写一些关于 Oracle 的文章. 因为 Oracle 现在是新开源巨头嘛.
—不仅要说 Oracle Database, 还要说 Oracle 收购的 Sun, InnoBase, Sleepycat 等公司及其产品.
—2010.4, 就连 Apache Software Foundation 也被买了.

写一些关于 Mac 的文章. 之前没接触过.

写一些书评. 没记错的话以前没怎么做过. 可以考虑用豆列替代.

整理以前的文章. 有必要的话换 Blog 程序, 没必要的话就继续先这么用着.

扩大交流范围. 之前很少和海外的同学们接触, 这是另类的小圈子.
希望中国大陆之外的同学们多提意见.
这个交流障碍的根本原因在 ps2 里面有一定的描述.

ps:
之前有篇文章 不搞架构了.
可偶没说的是, 等偶做到这一点的时候, 说不准又两三年过去了.
所以该写的还是要写下去.

ps2:
偶可怜的小朋友最近考试, 有道题的答案的其中一句是这样的:
“XXXXX 中国化就是把 XXXXX 植根于中国的优秀文化之中”
党国不分, ()和()文化不分. 这就没有交流基础了, 不是吗?

关于分析指标的定义.
偶当然知道有介绍相关知识的 blog.
有会日语的同学请看:
アクセス解析の集計と用語定義ガイドライン
(粗译: 网站分析统计用语定义指南. 有想翻译的须要联系原作者.)

但这个问题偶并不这么看.
既然有 MapReduce, 有 Pig 语言, 这事还有什么难的?

有几个指标偶不是太喜欢, 做了一些修改 (但如果你的程序改不了, 你就别照做了 ).
1 Page View.
综合判断为非 Bot 的访客访问的动态页面数. 另外参见下面的 Visit.
(注1: 静态页面分离, 白名单制. 注2: 访客的判定与页面统计代码有关.
注3: 页面统计代码触发数量与日志记录数在统计上方差不大于特定数值.
注4: 会专门处理非名单上的地址列表, 供产品和运营/安全分析)

2 Visit.
Visit 的问题在第一篇里就说过了.
所以对偶来说的 Daily User PV = “本日来的 visitor 总共贡献了多少 PV”.
甚至是本日新来的 Visitor … 当然这个指标不如这个有用: “从某地(这属于 Campaign Tracking)来的新用户, 今天贡献了多少 PV”.
都能长期监控一个订单的起源是谁的推荐, 这个, 不难.

偶说的这个 Daily User PV 指标在 0:00 的时候是无法得到精确结果的. 但你多做几天就大致能够得到与真实日志的比例.
从这个描述就可以看出, 这个 Visit 没有跨日问题. 但 PV 跨日了.
旧有的指标又不是求不出来, 对照看看就可以了.

3 Bounce Rate
这个不根据日志不行. 想提高正确率就要这么干.
已经见过非常多的案例说第一页统计没记录到, 第二页带着第一页的 Referer 当作新 Visit 了. 解法就是使用日志修正统计.
这个定义和实际情况有关: 以日志中记录为准, 判定为非 Bot 用户产生的 Bounce 算 Bounce. 这样就可以算 Bounce Rate 了.

—

DNS 服务器日志别扔了. 有用. 可以分析从 DNS Response 到 HTTP Request 之间的时间. 这个数值有什么用那就自己想了.
这种分析需要考虑阻塞问题, 预抓取问题, DNS 中转(及地域)等问题.

思考题: 如果给你较长的时间(考虑到延时), 但只允许在 A 记录中返回 k (k 肯定大于等于 2 ) 个 IP 中的其中一个, 你能否定位一个具体用户使用的是哪个 DNS 服务器? 假定用户每小时访问该站一次, 并在访问时用 (本地的) DNS 解析域名.

—

关于技术细节.
图片里也能传数据. 参见 网页统计与 35 Bytes GIF
简单说就是图片的长宽可以做很多事. 也有人喜欢用 HTTP 204 返回一个空文件.
如何使自己的统计图片躲过 Adblock? Privoxy 也有一定的防监控功能.
这个问题自己研究, 篇幅所限, 不写了.

不过具体是否需要这种 hacks 要看情况的. 有些人就会匹配 1×1 .
不传数据的话就不需要太重视这个方法.

未完待续. Part 5 为最终回. 预计发布日期未定.

非常不幸, 因为 btrfs 上出现了一个坏块 (这还是 SSD 呢), 文件系统被部分破坏以至于不能修复.
备份了 /etc 和 debfoster keepers 就开始重装了. 2 h 不到就重新回到了正常的工作状态.
系统也升级成了白鼠专用的 Ubuntu 10.10 Alpha. 内核是 2.6.35-6-generic.
安装使用了 netinst iso (提取安装用的内核和 initrd 即可).
debian installer 暂不支持 ipv6 安装, 看起来也没有要支持的样子.

—

一定要准备另外的启动盘.
默认安装的是 grub. 升级到 grub2 可能会有意想不到的问题.
/etc/default/grub 应该是需要修改的.

如果使用 netinst 安装, 要把 /etc/network/interfaces 中关于 eth0 的部分去掉, 以使用 network-manager.

把 /proc/cmdline 的一部分写上, 以免再丢.
acpi_osi=Linux force-hpet pciehp.pciehp_force=1 pciehp.pciehp_poll_mode=1 usbcore.autosuspend=1

—

在 en_US.UTF-8 环境下启用 ibus (不要用 root 权限!)
im-switch -z all_ALL -s ibus

DHCP 获取地址时启用 dnsmasq. (dhcp3-client, a.k.a dhclient)
sudo sed 's/#prepend/prepend/' /etc/dhcp3/dhclient.conf --in-place

Aria2 多线程 ipv6 下载 (重点是 async-dns 参数). 可以考虑 alias 一下.
aria2c --check-certificate=false --async-dns=false FILE
Aria2 下 Torrent. 上传限速 50k. 监听端口最好改一改.
aria2c --listen-port=6881 --dht-listen-port=6882 -u 50K TORRENTFILE

省几个 Request 这不是命令.
APT::Acquire::Translation "none"; (/etc/apt/apt.conf.d/99translation)

使 OpenSSH Server 不做反向解析. 注意 tee 的参数.
echo "UseDNS no" | sudo tee -a /etc/ssh/sshd_config
(话说实际上偶喜欢用 sudo sh -c 一套. 只是害怕漏掉参数)

命令行添加 ppa. (需要 python-software-properties)
add-apt-repository ppa:user/repository

/etc/ntp.conf 设置服务器 server time.buptnet.edu.cn
选择它的原因有两个. v4/v6 双栈, 单 IP, 不会造成大的负担 (从 Wireshark 看重试次数少).
大规模应用还是应该部署自己的 NTP 服务器, 很容易的. 替代品可以选择 ntp.sixxs.org.

用 pavuk 抓站. 相当于多线程的 wget -m -np URI
pavuk URI -progress -dont_ave_dir -nthreads 10

整理 Firefox SQLite 数据库.
ls ~/.mozilla/firefox/*/*.sqlite | xargs -n1 -iabc sqlite3 abc "VACUUM;"

走到哪里 MAC 换到哪里. (需要安装 macchanger)
sudo sh -c "echo IyEvYmluL2Jhc2gKbWFjY2hhbmdlciAtYSBldGgwCg== | base64 -d > /etc/network/if-pre-up.d/eth0-macchanger"
sudo chmod +x /etc/network/if-pre-up.d/eth0-macchanger

Taobao Tair 是一个分布式 key-value store. 于 2010.6.29 正式开源.

Tair 支持内存 hash (MDB) 和文件存储引擎 (FDB).
(如果你熟悉 Tokyo Cabinet 的话, 对应 TCMDB 和 TCHDB)
存储引擎可以扩展 (但这个 API 个人觉得很难看).

Memcached 和 Redis 的一些特性也被搬到了这里.
比如原子计数器支持, Item 支持, 版本号支持.

可是压根它就不打算支持 Memcached 协议 (也许以后会有吧, 写个 Proxy?).

—

Tair 没有使用 Consistent Hashing (这个应该没看错).
但使用了 Dynamo 论文 Page 12 中的 Strategy 3 以保证节点分布与数据完整性.
(但就这个也不像! 因为没用 Consistent Hashing, 所以不符合论文, 见下 GFS 相关讨论)
并提供了两种节点分布方式: 负载平衡优先, 数据安全优先.
这种方式虽然偶不太喜欢, 不过倒是个可以接受的方案.
纯 Consistent Hashing + Buckets + 多 Hash Ring (每个 Ring 不能在同一网段以提高可用性) 也是一种做法, 不过缺点是复制份数不能随负载而调整了.

插嘴: Riak 和 Voldemort 应该是暂时最像 Dynamo 的实现了吧…

如果非要做个比较的话, Google File System (GFS) 的 Block 分配也是这样的, 有 Master 负责 Block 到机器的对应查询.
这个 Buckets 的数量是一定的 (这是没办法). 但 Buckets 太多, configserver 就要耗费更多的时间去同步对应表.
仔细考虑一下, 增加减少节点时重新平衡的行为, 和 GFS 确实太相似了.
区别只是 GFS Block 的数量是可变的, 这个是不可变的. 反着看的话, Blocksize 是不固定的.

整体上说, 如果数据完整性对你很重要, Tair 是不错的选择. (这话没说完就这么放着了… )

代码: 客户端直接取模就得到服务器了. (tair_client_api_impl.cpp)
if (my_server_list.size() > 0U) {
hash %= bucket_count;
for(uint32_t i=0;i < copy_count && i < my_server_list.size(); ++ i){
uint64_t server_id = my_server_list[hash] + i * bucket_count;
if(server_id != 0){
server.push_back(server_id);
}
}
}


—

关于 Tair 自带的 FDB, 自称树形存储引擎 (这个树实际上和排序没有太大关系, 仅用于索引查询).

如果没看错的话是这样的:
用 h(x) 计算出 bucket number (这属于前面的分布式部分), 找到 bucket 对应的(数据和索引)文件完成写入, 索引使用的是二叉树.

索引的定义:
typedef struct _item_index {
uint32_t left;
uint32_t right;
uint64_t size:24;
uint64_t offset:40;
uint64_t hashcode;
} item_index;

个人认为索引方面有缺陷. 应该引入 Cache-Oblivious 的树形数据结构 (二叉树需要的内存访问次数太多了), 即便它能够缓存在内存中.

FDB 具体实现很像 Facebook 的图片存储系统. 适合 Object 修改次数极少的情况.
使用了空间池 (free_blocks_manager) 以提高空间利用率.

关于 MDB 的实现偶没有评估的能力.

—

希望以上描述能够帮助大家更快的评估 Tair. 如有疑问请丢邮件过来.

ps:
那 Dynamo 的论文写 Consistent Hashing 干嘛?

ps2:
写网络应用程序不支持 IPv6 怎么行?

ps3:
四不像, 这个概括还是比较准确的. 你说它不像什么?