Archive for September, 2008
Saturday, September 27th, 2008
本博客所有原创文章采用知识共享署名-非商业性使用-相同方式共享，转载请保留链接http://chaoqun.17348.com/2008/09/7-stages-scaling-of-web-apps/
几天前看到The 7 Stages of Scaling Web Apps，觉得很是不错，想写点什么，奈何一直很忙，整天忙着那些quick&dirty的项目，让人也堕落了许多。
今天找到报告的原文看了一下，内容丰满了许多。
要构建一个可扩展的网络应用,大多是数据库分表分库、分布式缓存、负载均衡、统一存储，诸如此类，前面我也翻译了一些国外网站架构文章，John Engales的文章高明之处是分7个步骤阐述了一个网络应用从简单到高度可扩展的构建过程。对比这七个步骤，想想我们的应用处在第几步呢？
报告的一开始解释了Performance（性能）和Scalability（扩展性）的区别，里面有两幅图片很好的诠释了，高性能就是买个好车（高配服务器）在高速公路（充足带宽）跑，高扩展性是一堆车跑在立交桥N通道上，不一定跑的很快，至少不会堵车。
第一步：开始阶段
简单的结构：防火墙＋负载均衡、一对服务器、数据库服务器、内部存储，结构简单，没有冗余，维护成本低，很是适合开始阶段。
这样的应用结构应该撑个50W～100W的访问没问题吧，一般的应用话。
很多的应用可能还不到这个水平，一台服务器扔在托管机房里，应用和数据库跑在同一台服务器上，这样的应该是“第零步”吧，如果要扩展这样的应用，升级到第一步吧，应该对程序和数据库不需要怎么修改，效果可能还会不错（如果你的应用不是特别大的话）。
第二步：和第一步一样，只是规模大了些
应用很成功，加更多防火墙、负载均衡，增加更多的应用服务器，找个DBA来优化一下数据库，增加数据库存储备份，把数据库存到SAN或者DAS（这个不太赞同，有几个有这个钱的啊），仍然是个简单的应用。
第二步也很有用，估计能撑到300W左右。如果钱能解决的问题，都不是问题，访问量大了，有钱了，多买点服务器能解决问题何乐而不为？
第三步：痛苦的开始
访问量大了，加个Squid或者Varnish做反向代理吧，或者更高级的负载均衡，以缓存静态内容。加更多的应用服务器，数据库做个Master-Slave，一台Master负责写操作，N台Slave负责读操作，可能会需要做一些代码修改。
到这一步就有点像模像样了，这应该是硬件方面能做到的极限吧，估计撑了500W左右问题不大。
第四步：更加痛苦了
访问量更大了，做个memcache分布式缓存吧，数据库主从复制出现问题了，大量的写堆积到一台服务器上，复制时间过长（数据库从服务器不能即时同步），然后可以做做数据库分区（或者分表），内容统一存储，需要大量重构应用和数据库结构。
终于引入memcache了，可以大大减轻服务器硬盘读取的负载，当数据库（数据库表）变的过大的时候，再多服务器都不管用，想想你的一个数据表有100G，索引有10个G，服务器内存才4个G，光放索引都放不下。这个时候分表会是一个不错的选择，简单的分表可以自定义一个hash函数或者按照ID主键分表，只是这种固定的分表方法将来数据迁移会费事很多，还是推荐Flickr的中心数据库做法，后面会讲到。
到第四步的规模，估计1000W问题不大了
第五步：真正的痛苦开始了
开始恐慌了，开始考虑整个应用模式了，仅仅是通过业务分区还不够，可以通过地理位置啊（比如北方的用户都用北京的服务器），用户ID啊什么的分服务器分区，建立服务器集群，对于每个集群，所有功能都是可用的（这样可以很好的做数据迁移以及冗余），使用一个hash结构或者主服务器来判断用户属于哪个服务器集群（^_^中心数据库）
第五步？估计很多应用都到不了这一步，已经分完善了，估计5000W左右都没问题。
第六步：一点点痛苦
扩展应用和数据库架构，提高性能，增加新功能，优化代码，访问还在增长，但是可控。
比较惬意的阶段了，1个亿的访问量轻松应对吧。
第七步：进入未知的领域
开始找系统的瓶颈了，电源、存储、CDN什么的，更多的数据中心，可能难题是夸地区的数据复制。
呵呵，这个应该是Google考虑的问题了.
想想我们的应用瓶颈在那里，不要一下子什么都想想全了，一步到位的做法是不存在的，知道那里不足，解决它，发现其他的不足，再解决，无休止的循环，直到你失业（什么问题都没有，还要你做什么啊）或者退休（该歇歇了）。
Posted in Arch, 默认分类 | No Comments »
Friday, September 12th, 2008
About OpenSlopeOne
OpenSlopeOne is an implementation of Slope One based on PHP&MySQL, it's an open source project under GPL V3.
It aims to a fast way to use Slope One with PHP&MySQL, and it can handle tons of data.
It's localed on Google Code:
http://code.google.com/p/openslopeone/
You can get the latest code here:
svn checkout ...
Posted in Data Mining, Mysql, Open Source, PHP | No Comments »
Wednesday, September 3rd, 2008
本博客所有原创文章采用知识共享署名-非商业性使用-相同方式共享，转载请保留链接http://chaoqun.17348.com/2008/09/slope_one/
推荐系统最早在亚马逊的网站上应用，根据以往用户的购买行为，推荐出购买某种产品同时可能购买的其他产品，国内做的不错的当当网,有时候买书，它总能给我推荐出我感兴趣的其他书来，也算是技术极大的促进了销售。
一般的协同过滤算法，首先是收集用户对事物（产品）的评分情况，一种直接对某本书，或者某个歌曲打分，另种是隐性的打分，比如商务系统中，购买了表示打2分，浏览了打1分，其他的0分。我比较看好隐性打分，因为直接打分需要用户的参与程度比较高，很多网站都在内容页中留一个打分的按钮，从1～5选一个，我可能喜欢这篇文章，可我哪里知道我喜欢的程度是几分啊，还要我去思考，而网站设计中一条很重要的原则是:Do not let me think!，于是我就胡打一个分数或者不打，而隐性的打分则不同，只有你喜欢的图书你才会购买，只有你喜欢的歌曲才会听多次。
收集好用户的打分之后，通过最近邻搜索到和某个事物或者某个人特征或者兴趣相近的其他事物或者人，最近邻搜索算法一般是皮尔森相关系数（Person Correlation Coefficient）、余弦相似性（Cosine-based Similarity）以及调整余弦相似性（Adjusted Cosine Similarity）。关于余弦定理在数据挖掘中的应用，google黑白报有过介绍，可以参考数学之美 系列 12 - 余弦定理和新闻的分类。
剩下的工作就是根据最近邻集进行推荐了。
最近邻集的运算相对来说成本比较高，尤其是大量数据的时候，今天和大家分享的是一种简单高效的协同过滤算法：Slope one
基本原理
用户
对事物A打分
对事物B打分
X
3
4
Y
2
4
Z
4
?
用户Z对事物B的打分可能是多少呢？股票上有个说法是平均值可以掩盖一切异常波动，所以股票上的各个技术指标收拾不同时间段的平均值的曲线图或者柱状图等。同样的，Slope one算法也认为：平均值也可以代替某两个未知个体之间的打分差异，事物A对事物B的平均很差是：((3 - 4) + (2 - 4)) / 2 = -1.5，也就是说人们对事物B的打分一般比事物A的打分要高1.5，于是Slope one算法就猜测Z对事物B的打分是4 + 1.5 = 5.5
是不是非常的简单？
加权算法
有n个人对事物A和事物B打分了，R(A->B)表示这n个人对A和对B打分的平均差（A-B）,有m个人对事物B和事物C打分了，R（C->B）表示这m个人对C和对B打分的平均差（C-B），注意都是平均差而不是平方差，现在某个用户对A的打分是ra，对C的打分是rc，那么A对B的打分可能是：
rb = (n * (ra - R(A->B)) + m * (rc - R(C->B)))/(m+n)
开源的Slope one的程序包
Python
http://www.serpentine.com/blog/2006/12/12/collaborative-filtering-made-easy/
Java
http://taste.sourceforge.net/
http://www.daniel-lemire.com/fr/documents/publications/SlopeOne.java
http://www.nongnu.org/cofi/
PHP
http://sourceforge.net/projects/vogoo
http://www.drupal.org/project/cre
http://www.daniel-lemire.com/fr/documents/publications/webpaper.txt Slope one算法作者写的，简单明了，强烈推荐。
Erlang
http://chlorophil.blogspot.com/2007/06/collaborative-filtering-weighted-slope.html
C#
http://www.cnblogs.com/kuber/articles/SlopeOne_CSharp.html 国人写的C#版本
T-SQL
http://blog.charliezhu.com/2008/07/21/implementing-slope-one-in-t-sql/
还有一些其他语言的版本，请参考http://en.wikipedia.org/wiki/Slope_One，即将面世的，居于PHP & Mysql的Slope one算法实现将会在http://code.google.com/p/openslopeone/开源出来，主要优化的是海量数据以及分布式处理，目前在我的笔记本上（迅驰＋1.5G内存），对440W打分记录进行测试，单一线程，3小时47分处理完。速度还算是不错了，最近工作实在太忙了，等我整理好会开源出来放在上面的地址。过几天会有一篇我的算法的详细介绍，盼诸位批评指正，共同学习，共同进步。
Posted in Data Mining, Open Source, PHP | 1 Comment »