• Archive by category "Dataguru作业"
  • (Page 2)

Blog Archives

RHadoop实验 – 统计邮箱出现次数

RHadoop实践系列文章,包含了R语言与Hadoop结合进行海量数据分析。Hadoop主要用来存储海量数据,R语言完成MapReduce 算法,用来替代Java的MapReduce实现。有了RHadoop可以让广大的R语言爱好者,有更强大的工具处理大数据1G, 10G, 100G, TB, PB。 由于大数据所带来的单机性能问题,可能会一去不复返了。

RHadoop实践是一套系列文章,主要包括”Hadoop环境搭建”,”RHadoop安装与使用”,R实现MapReduce的协同过滤算法”,”HBase和rhbase的安装与使用”。对于单独的R语言爱好者,Java爱好者,或者Hadoop爱好者来说,同时具备三种语言知识并不容 易。此文虽为入门文章,但R,Java,Hadoop基础知识还是需要大家提前掌握。

关于作者:

  • 张丹(Conan), 程序员Java,R,PHP,Javascript
  • weibo:@Conan_Z
  • blog: http://blog.fens.me
  • email: bsspirit@gmail.com

转载请注明出处:
http://blog.fens.me/rhadoop-demo-email/

rhadoop-demo-email

目录

  1. 需求描述
  2. 实验数据
  3. 算法实现

1. 需求描述

基于RHADOOP通过rmr包实现MapReduce算法

  • 1). 计算邮箱域出现了多少次
  • 2). 按次数从大到小排序

例如:
163.com,14
sohu.com,2

2. 实验数据

wolys@21cn.com
zss1984@126.com
294522652@qq.com
simulateboy@163.com
zhoushigang_123@163.com
sirenxing424@126.com
lixinyu23@qq.com
chenlei1201@gmail.com
370433835@qq.com
cxx0409@126.com
viv093@sina.com
q62148830@163.com
65993266@qq.com
summeredison@sohu.com
zhangbao-autumn@163.com
diduo_007@yahoo.com.cn
fxh852@163.com
weiyang1128@163.com
licaijun007@163.com
junhongshouji@126.com
wuxiaohong11111@163.com
fennal@sina.com
li_dao888@163.com
bokil.xu@163.com
362212053@qq.com
youloveyingying@yahoo.cn
boiny@126.com
linlixian200606@126.com
alex126126@126.com
654468252@qq.com
huangdaqiao@yahoo.com.cn
kitty12502@163.com
xl200811@sohu.com
ysjd8@163.com
851627938@qq.com
wubo_1225@163.com
kangtezc@163.com
xiao2018@126.com
121641873@qq.com
296489419@qq.com
beibeilong012@126.com

3. 算法实现

1). 计算邮箱域出现了多少次

把数据上传到HDFS


library(rmr2)
data<-read.table(file="hadoop15.txt")
d0<-to.dfs(keyval(1, data))
from.dfs(d0)

输出:


$key
[1] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
[39] 1 1 1
$val
V1
1 wolys@21cn.com
2 zss1984@126.com
3 294522652@qq.com
4 simulateboy@163.com
5 zhoushigang_123@163.com
6 sirenxing424@126.com
7 lixinyu23@qq.com
8 chenlei1201@gmail.com
9 370433835@qq.com
10 cxx0409@126.com
11 viv093@sina.com
12 q62148830@163.com
13 65993266@qq.com
14 summeredison@sohu.com
15 zhangbao-autumn@163.com
16 diduo_007@yahoo.com.cn
17 fxh852@163.com
18 weiyang1128@163.com
19 licaijun007@163.com
20 junhongshouji@126.com
21 wuxiaohong11111@163.com
22 fennal@sina.com
23 li_dao888@163.com
24 bokil.xu@163.com
25 362212053@qq.com
26 youloveyingying@yahoo.cn
27 boiny@126.com
28 linlixian200606@126.com
29 alex126126@126.com
30 654468252@qq.com
31 huangdaqiao@yahoo.com.cn
32 kitty12502@163.com
33 xl200811@sohu.com
34 ysjd8@163.com
35 851627938@qq.com
36 wubo_1225@163.com
37 kangtezc@163.com
38 xiao2018@126.com
39 121641873@qq.com
40 296489419@qq.com
41 beibeilong012@126.com

计算邮箱域出现了多少次


mr<-function(input=d0){
map<-function(k,v){
keyval(word(as.character(v$V1), 2, sep = fixed('@')),1)
}
reduce =function(k, v ) {
keyval(k, sum(v))
}
d1<-mapreduce(input=input,map=map,reduce=reduce,combine=TRUE)
}
d1<-mr(d0)
from.dfs(d1)

输出:

$key
[1] "126.com" "163.com" "21cn.com" "gmail.com" "qq.com"
[6] "sina.com" "sohu.com" "yahoo.cn" "yahoo.com.cn"
$val
[1] 9 14 1 1 9 2 2 1 2

2). 按次数从大到小排序


sort<-function(input=d1){
map<-function(k,v){
keyval(1,data.frame(k,v))
}
reduce<-function(k,v){
v2<-v[order(as.integer(v$v),decreasing=TRUE),]
keyval(1,v2)
}
d2<-mapreduce(input=input,map=map,reduce=reduce,combine=TRUE)
}
d2<-sort(d1)
result<-from.dfs(d2)
result$val

输出:


k v
2 163.com 14
1 126.com 9
5 qq.com 9
6 sina.com 2
7 sohu.com 2
9 yahoo.com.cn 2
3 21cn.com 1
4 gmail.com 1
8 yahoo.cn 1

转载请注明出处:
http://blog.fens.me/rhadoop-demo-email/

打赏作者

用R解析Mahout用户推荐协同过滤算法(UserCF)

RHadoop实践系列文章,包含了R语言与Hadoop结合进行海量数据分析。Hadoop主要用来存储海量数据,R语言完成MapReduce 算法,用来替代Java的MapReduce实现。有了RHadoop可以让广大的R语言爱好者,有更强大的工具处理大数据1G, 10G, 100G, TB, PB。 由于大数据所带来的单机性能问题,可能会一去不复返了。

RHadoop实践是一套系列文章,主要包括”Hadoop环境搭建”,”RHadoop安装与使用”,R实现MapReduce的协同过滤算法”,”HBase和rhbase的安装与使用”。对于单独的R语言爱好者,Java爱好者,或者Hadoop爱好者来说,同时具备三种语言知识并不容 易。此文虽为入门文章,但R,Java,Hadoop基础知识还是需要大家提前掌握。

关于作者

  • 张丹(Conan), 程序员Java,R,PHP,Javascript
  • weibo:@Conan_Z
  • blog: http://blog.fens.me
  • email: bsspirit@gmail.com

转载请注明出处:
http://blog.fens.me/r-mahout-usercf/

r-mahout

前言
用R全面解析Mahout的基于用户推荐协同过滤算法(UserCF),改进的采用欧氏距离,并用R语言实现,与Mahout的结果进行对比。

Mahout是Hahoop家族用于机器学习的一个框架,包括三个主要部分,推荐,聚类,分类!
我在这里做的是推荐部分。推荐系统在现在的互联网应用中很常见,比如,亚马逊会推荐你买书,豆瓣会给你一个书评,影评。

由于时间仓促,欢迎大家一起讨论。

目录

  1. Mahout的模型介绍
  2. R语言模型实现
  3. 算法实现的原理–矩阵变换
  4. 算法总结
  5. 参考资料

1. Mahout的模型介绍

mahout-recommendation-process

Mahout版本

 
<dependency>
<groupId>org.apache.mahout</groupId>
<artifactId>mahout-core</artifactId>
<version>0.5</version>
</dependency>

Mahout程序写法


public class UserBaseCFMain {

    final static int NEIGHBORHOOD_NUM = 2;
    final static int RECOMMENDER_NUM = 3;

    public static void main(String[] args) throws IOException, TasteException {
        String file = "metadata/data/testCF.csv";
        DataModel model = new FileDataModel(new File(file));
        UserSimilarity user = new EuclideanDistanceSimilarity(model);
        NearestNUserNeighborhood neighbor = new NearestNUserNeighborhood(NEIGHBORHOOD_NUM, user, model);
        Recommender r = new GenericUserBasedRecommender(model, neighbor, user);
        LongPrimitiveIterator iter = model.getUserIDs();

        while (iter.hasNext()) {
            long uid = iter.nextLong();
            List list = r.recommend(uid, RECOMMENDER_NUM);
            System.out.printf("uid:%s", uid);
            for (RecommendedItem ritem : list) {
                System.out.printf("(%s,%f)", ritem.getItemID(), ritem.getValue());
            }
            System.out.println();
        }
    }
} 

推荐结果:


uid:1(104,4.250000)(106,4.000000)
uid:2(105,3.956999)
uid:3(103,3.185407)(102,2.802432)
uid:4(102,3.000000)
uid:5 

2. R语言模型实现

  • 1). 建立数据模型
  • 2). 欧氏距离相似度算法
  • 3). 最紧邻算法
  • 4). 推荐算法
  • 5). 运行程序

由于时间仓促,R的代码中,有不少for循环影响性能,请暂时跳过!

1). 建立数据模型


FileDataModel<-function(file){
data<-read.csv(file,header=FALSE)
names(data)<-c("uid","iid","pref")

user <- unique(data$uid)
item <- unique(sort(data$iid))
uidx <- match(data$uid, user)
iidx <- match(data$iid, item)
M <- matrix(0, length(user), length(item))
i <- cbind(uidx, iidx, pref=data$pref)
for(n in 1:nrow(i)){
M[i[n,][1],i[n,][2]]<-i[n,][3]
}
dimnames(M)[[2]]<-item
M
}

2). 欧氏距离相似度算法


EuclideanDistanceSimilarity<-function(M){
row<-nrow(M)
s<-matrix(0, row, row)
for(z1 in 1:row){
for(z2 in 1:row){
if(z1<z2){< span="">
num<-intersect(which(M[z1,]!=0),which(M[z2,]!=0)) #可计算的列

sum<-0
for(z3 in num){
sum<-sum+(M[z1,][z3]-M[z2,][z3])^2
}

s[z2,z1]<-length(num)/(1+sqrt(sum))

if(s[z2,z1]>1) s[z2,z1]<-1 #标准化
if(s[z2,z1]< -1) s[z2,z1]<- -1 #标准化

#print(paste(z1,z2));print(num);print(sum)
}
}
}
#补全三角矩阵
ts<-t(s)
w<-which(upper.tri(ts))
s[w]<-ts[w]
s
}

3). 最紧邻算法

NearestNUserNeighborhood<-function(S,n){ row<-nrow(S) neighbor<-matrix(0, row, n) for(z1 in 1:row){ for(z2 in 1:n){ m<-which.max(S[,z1]) #       print(paste(z1,z2,m,'\n')) neighbor[z1,][z2]<-m S[,z1][m]=0 } } neighbor }

4). 推荐算法


UserBasedRecommender<-function(uid,n,M,S,N){
row<-ncol(N)
col<-ncol(M)
r<-matrix(0, row, col)
N1<-N[uid,]
for(z1 in 1:length(N1)){
num<-intersect(which(M[uid,]==0),which(M[N1[z1],]!=0)) #可计算的列
#     print(num)

for(z2 in num){
#       print(paste("for:",z1,N1[z1],z2,M[N1[z1],z2],S[uid,N1[z1]]))
r[z1,z2]=M[N1[z1],z2]*S[uid,N1[z1]]
}
}

sum<-colSums(r)
s2<-matrix(0, 2, col)
for(z1 in 1:length(N1)){
num<-intersect(which(colSums(r)!=0),which(M[N1[z1],]!=0))
for(z2 in num){
s2[1,][z2]<-s2[1,][z2]+S[uid,N1[z1]]
s2[2,][z2]<-s2[2,][z2]+1
}
}

s2[,which(s2[2,]==1)]=10000
s2<-s2[-2,]

r2<-matrix(0, n, 2)
rr<-sum/s2
item <-dimnames(M)[[2]]
for(z1 in 1:n){
w<-which.max(rr)
if(rr[w]>0.5){
r2[z1,1]<-item[which.max(rr)]
r2[z1,2]<-as.double(rr[w])
rr[w]=0
}
}
r2
}

5). 运行程序


FILE<-"testCF.csv"
NEIGHBORHOOD_NUM<-2
RECOMMENDER_NUM<-3

M<-FileDataModel(FILE)
S<-EuclideanDistanceSimilarity(M)
N<-NearestNUserNeighborhood(S,NEIGHBORHOOD_NUM)

R1<-UserBasedRecommender(1,RECOMMENDER_NUM,M,S,N);R1
##      [,1]  [,2]  
## [1,] "104" "4.25"
## [2,] "106" "4"   
## [3,] "0"   "0" 

R2<-UserBasedRecommender(2,RECOMMENDER_NUM,M,S,N);R2
##      [,1]  [,2]
## [1,] "105" "3.95699903407931"
## [2,] "0"   "0"
## [3,] "0"   "0"

R3<-UserBasedRecommender(3,RECOMMENDER_NUM,M,S,N);R3
##      [,1]  [,2]
## [1,] "103" "3.18540697329411"
## [2,] "102" "2.80243217111765"
## [3,] "0"   "0"

R4<-UserBasedRecommender(4,RECOMMENDER_NUM,M,S,N);R4
##      [,1]  [,2]
## [1,] "102" "3" 
## [2,] "0"   "0" 
## [3,] "0"   "0"

R5<-UserBasedRecommender(5,RECOMMENDER_NUM,M,S,N);R5
##      [,1] [,2]
## [1,]    0    0
## [2,]    0    0
## [3,]    0    0

3. 算法实现的原理–矩阵变换

所谓协同过滤算法,其实就是矩阵变换的结果!!请大家下面留意矩阵操作!
1). 原始数据

 1,101,5.0
  1,102,3.0
  1,103,2.5
  2,101,2.0
  2,102,2.5
  2,103,5.0
  2,104,2.0
  3,101,2.5
  3,104,4.0
  3,105,4.5
  3,107,5.0
  4,101,5.0
  4,103,3.0
  4,104,4.5
  4,106,4.0
  5,101,4.0
  5,102,3.0
  5,103,2.0
  5,104,4.0
  5,105,3.5
  5,106,4.0 

2). 矩阵转换

 101 102 103 104 105 106 107
[1,] 5.0 3.0 2.5 0.0 0.0   0   0
[2,] 2.0 2.5 5.0 2.0 0.0   0   0
[3,] 2.5 0.0 0.0 4.0 4.5   0   5
[4,] 5.0 0.0 3.0 4.5 0.0   4   0
[5,] 4.0 3.0 2.0 4.0 3.5   4   0 

3). 欧氏相似矩阵转换

 [,1]      [,2]      [,3]      [,4]      [,5]
[1,] 0.0000000 0.6076560 0.2857143 1.0000000 1.0000000
[2,] 0.6076560 0.0000000 0.6532633 0.5568464 0.7761999
[3,] 0.2857143 0.6532633 0.0000000 0.5634581 1.0000000
[4,] 1.0000000 0.5568464 0.5634581 0.0000000 1.0000000
[5,] 1.0000000 0.7761999 1.0000000 1.0000000 0.0000000 

4). 最近邻矩阵

 top1 top2
[1,]    4    5
[2,]    5    3
[3,]    5    2
[4,]    1    5
[5,]    1    3 

5). 以R1为例的推荐矩阵

 101  102  103  104  105  106  107
   4    0    0    0  4.5  0.0    4    0
   5    0    0    0  4.0  3.5    4    0 

6). 以R1为例的推荐结果

 推荐物品  物品得分
[1,] "104"    "4.25"
[2,] "106"    "4" 

4. 算法总结

我这里只是用R语言现实了Mahout的基于“用户的”,“欧氏距离”,“最近邻”的协同过滤算法。实现过程中发现,Mahout做各种算法时,都有自己的优化。

比如,算欧氏距离时,并不是标准的

similar = 1/(1+sqrt( (a-b)2 + (a-c)2 ))

而是改进的算法

similar = n/(1+sqrt( (a-b)2 + (a-c)2 )) 
  1. n为b,c的个数
  2. similar>1 => similar=1
  3. similar<-1 => similar=-1

从而更能优化结果。

5. 参考资料:

  1. Mahout In Action
  2. Mahout Source Code
  3. R help

转载请注明出处:
http://blog.fens.me/r-mahout-usercf/

打赏作者

[转] 深入探讨PageRank(二):PageRank原理剖析

深入探讨PageRank(二):PageRank原理剖析

 

关于PageRank的基础知识简介请参见博文:《深入探讨PageRank(一):PageRank算法原理入门》

 

http://blog.csdn.net/monkey_d_meng/article/details/6556295

 

一、PageRank算法的简单举例

Google PageRank算法的思想精华在于:将一个网页级别/重要性的排序问题转化成了一个公共参与、以群体民主投票的方式求解的问题,网页之间的链接即被认为是投票行为。同时,各个站点投票的权重不同,重要的网站投票具有较大的分量,而该网站是否重要的标准还需要依照其PageRank值。这看似是一个矛盾的过程:即我们需要用PageRank值来计算PageRank值~

听起来有点不可思议,既像是递归,又像是迭代,似乎陷入了一个漩涡,Google的创始人佩奇和布林证明了这个过程最终收敛值与初始值无关。遗憾的是我一直都没有找到这个证明,甚至我把佩奇他们当年那篇论文找出来看也没有发现~

对于PageRank的收敛性,我们是可以找到反例的,这说明PageRank至少在某些情况下是不可能收敛的,或者说是收敛不完备的。在本文的第三部分,我们将PageRank的问题转化为了马尔可夫链的概率转移问题,其收敛性的证明也即转化为了马氏链的平稳分布是否存在的证明。我们先来看一个简单的例子:

Google PageRank取值范围是0~10,为了叙述方便,我们使用0~1的区间作为度量,这并不会影响我们对PageRank原理的剖析,并且在初始化的时候,我们假设所有网站的PageRank的值是均匀分布的。这意味着,如果有N个网站,那么每个网站的PageRank初始值都是1/N。现在假设有4个网站A、B、C、D,则它们的初始PageRank都是0.25,它们的链接关系如下:

 

 

 

则初始值PR(A) = PR(B) = PR(C) = PR(D) = 0.25,又因为B、C、D都有指向A的链接,因此,它们每人都为A贡献了0.25的PageRank值,重新计算A的PageRank值为:PR(A) = PR(B) + PR(C) + PR(D) = 0.75,由于B、C和D并没有外部链接指向它们,因此PR(B)、PR(C)、PR(D)在这次计算中将被赋值为0。反复套用PageRank的计算公式,来看一下,这种情况下PageRank的收敛性,在第二次迭代之后,所有的PageRank值就都是0了:

PageRank

PR(A)

PR(B)

PR(C)

PR(D)

初始值

0.25

0.25

0.25

0.25

第一次迭代后

0.75

0

0

0

第二次迭代后

0

0

0

0

我们来分析一下这个例子PageRank收敛的情况,由于没有网站链接到D,那么第一次迭代之后PR(D)=0,这将导致PR(B)=0,继而导致PR(C)=0和PR(A)=0。

 

 

现在来看第个例子,假设网站B还有C链接,网站D上有其他三个网站的链接。对于B而言的话,它把自己的总价值分散投给了A和C,各占一半的PageRank,即0.125,C和D的情况同理。即一个网站投票给其它网站PageRank的值,需要除以它所链接到的网站总数。此时PageRank的计算公式为:

PR(A) = PR(B) / 2 + PR(C) / 1 + PR(D) / 3PR(B) = PR(D) / 3

PR(C) = PR(B) / 2 + PR(D) / 3

PR(D) = 0

 

 

PageRank

PR(A)

PR(B)

PR(C)

PR(D)

初始值

0.25

0.25

0.25

0.25

第一次迭代后

0.4583

0.0833

0.2083

0

第二次迭代后

0.25

0

0.0417

0

第三次迭代后

.0.417

0

0

0

第四次迭代后

0

0

0

0

PageRank值计算过程的一般步骤可以概括如下:

(1)为每个网站设置一个初始的PageRank值。

(2)第一次迭代:每个网站得到一个新的PageRank。

(3)第二次迭代:用这组新的PageRank再按上述公式形成另一组新的PageRank。

……

当然,我们最关心的问题是,如此迭代下去,这些PageRank的值最终会收敛吗?我们上述的两个例子都是收敛的,但是不是所有情况都是如此呢?而且,上述例子中,我们发现,一旦某个页面的外部链接数目为0的话,那必然将导致全部网页最终收敛值为0。

 

二、PageRank算法的“黑洞效应”

为了讨论收敛性的问题,我们暂时抛开具体的网站,把问题做一个抽象化的描述,我们可以把网页之间的关联关系理解为是若干张有向图,图与图之间是互不连通的,那我们只考虑每一部分的收敛性,并不会影响其他部分的收敛性。我们考虑把边权值当作网站所传递的PageRank值,则对于任意一个顶点而言,其出边的权值之和必为1。

 

一个很显然的结论是,如果连通图中有一个顶点的入度为0,则经过有限次迭代之后,该连通图内的所有顶点的PageRank均为0,形象的说,这个顶点就像一个黑洞一样,把整体的PageRank值慢慢地“吸收”了。由于它不对外贡献任何PR值,所以整体的PR总和是在不断地减少,直到最终收敛到0。我把它称之为:PageRank的“黑洞效应”。至于说Google是如何防止这种情况的发生,毕竟一个网站没有外链是完全有可能的,我也尚未找到确切的答案。不过网上道是有人给出了一种解决办法:即如果一个网站没有外链,那么就假定该连通图内其余所有的网点都是它的外链,这样我们就避免了整体PageRank值被吸收的现象。

当一个连通图内部每一个顶点入度均大于0时,不难看出,PR值在内部流通过程中,整体的PR值是守恒的。如果是存在一个顶点的入度为0呢?通过一次迭代,它的PR值就会变成0,而把它的那部分PR值贡献给了图中剩余的部分。所以,最终入度为0的顶点的PR值都将是0,而整体的PR仍然守恒。那么整体的PR值守恒就一定能够保证每个顶点的PR值最终会收敛吗?下面看一个简单的例子:

 

按照之前的迭代步骤,会得到一个迭代的结果表。这将是一个无限循环,且不会收敛的过程。

PageRank

PR(A)

PR(B)

PR(C)

PR(D)

初始值

0.25

0.25

0.25

0.25

第一次迭代后

0

0.375

0.25

0.375

第二次迭代后

0

0.375

0.375

0.25

第三次迭代后

0

0.25

0.375

0.375

第四次迭代后

0

0.375

0.25

0.375

第五次迭代后

0

其实,同样的问题我们还可以换一个角度来考虑,因为本质上有向图和矩阵是可以相互转化的,令A[i][j]表示从顶点i到达顶点j的概率,那么目力的矩阵表示就是:

0     0.5  0     0.50     0     1     0

0     0     0     1

0     1     0     0

而我们所给定的初始向量是:(0.25   0.25       0.25       0.25),做第一次迭代,就相当于用初始向量乘以上面的矩阵。第二次迭代就相当于第一次迭代的结果再乘以上面的矩阵……实际上,在随机过程理论中,上述矩阵被称为“转移概率矩阵”。这种离散状态按照离散时间的随机转移过程称为马氏链(马尔可夫链,Markov Chain)。设转移概率矩阵为P,若存在正整数N,使得P^N>0(每个元素大于0),这种链被称作正则链,它存在唯一的极限状态概率,并且与初始状态无关。

在这里,我们仅仅是非常简单地讨论了一下PageRank的原理,这与Google PageRank的实际算法实现相当甚远。域名数据、内容质量、用户数据、建站时间等都有可能被考虑进去,从而形成一个完善的算法。

当然,最让人惊叹的是,Google的PageRank能够应对互联网所产生的如此海量的网页信息和实时的变化,并能够在有限的时间内计算出所有网站的PageRank!这里面到底蕴涵着什么样的奥秘,我也会继续地追寻下去!

 

三、PageRank算法的马尔科夫过程分析

从第二节的陈述中我们知道,事实上,PageRank值在转移过程中变化规律是完全可以用马尔科夫的状态转移来进行表征的,两者本质属于同一个问题。则当PageRank值收敛时,即为马尔可科夫链达到平衡分布。推荐大家去读《随机过程》的教材,这里不在详细地讨论马氏链的内容,只给出相应的结论。

为了形象说明马氏链,这里举一个例子。假设一{A, B, C}为马氏链,其转移概率矩阵如下所示:

0.7         0.1         0.20.1         0.8         0.1

0.05       0.05       0.9

因为该马氏链是不可约的非周期的有限状态,平稳分布存在,则我们要求其平衡分布为:

X = 0.7X + 0.1Y + 0.05ZY = 0.1X + 0.8Y + 0.05Z

Z = 0.2X + 0.1Y + 0.9Z

X + Y + Z = 1

解得上述方程组的平稳分布为:X = 0.1765,Y = 0.2353,Z = 0.5882。

既然,说我们把PageRank收敛性问题转化为了求马尔可夫链的平稳分布的问题,那么我们就可以从马氏链的角度来分析问题。因此,对于PageRank的收敛性问题的证明也就迎刃而解了,只需要证明马氏链在什么情况下才会出现平稳分布即可。我们可以知道马氏链有三个推论:

推论1. 有限状态的不可约非周期马尔可夫链必存在平稳分布。

推论2. 若不可约马尔可夫链的所有状态是非常返或零常返的,则不存在平稳分布。

推论3. 若{Xi}是不可约的非周期马氏链的平稳分布,则lim(n→∞)Pj(n) = Xi。

上面的三个推论看不懂不要紧,找本《随机过程》的书就明白了,这里不再详细讨论了。既然问题得以转化,那么我们还计算一个实例,看看PageRank是如何工作的。假设这里有相互链接关系的7个HTML网页,并且HTML网页之间的链接关系闭合于这1~7个网页中,也即是说,除了这些网页之外,没有任何链接的出入。

 

那么我们可以很容易地将这个链接关系使用数学的方式表示出来。首先,分析链接的关系,列举出各个链接源的ID及其所链接的目标ID。

链接源I D 链接目标 ID1                   2,3 ,4,5, 7

2                   1

3                   1,2

4                   2,3,5

5                  1,3,4,6

6                   1,5

7                   5

使用邻接矩阵的形式表述网页之间的链接关系,A[i][j]=1表示从i到j有链接,否则表示无链接,A为7*7的矩阵。

A = [0, 1, 1, 1, 1, 0, 1;

1, 0, 0, 0, 0, 0, 0;

1, 1, 0, 0, 0, 0, 0;

0, 1, 1, 0, 1, 0, 0;

1, 0, 1, 1, 0, 1, 0;

1, 0, 0, 0, 1, 0, 0;

0, 0, 0, 0, 1, 0, 0;

]

我们现假设,每个网页初始的PageRank均为1,则会形成一个初始的PageRank转移矩阵。

A = [0,    1/5,        1/5,        1/5,        1/5,        0,    1/5;

1,    0,           0,           0,           0,           0,    0;

1/2, 1/2,        0,           0,           0,           0,    0;

0,    1/3,        1/3,        0,           1/3,        0,    0;

1/4, 0,           1/4,        1/4,        0,           1/4, 0;

1/2, 0,           0,           0,           1/2,        0,    0;

0,    0,           0,           0,           1,           0,    0;

]

这样的话,我们就可以按照求马氏链平稳分布的方式,求得PageRank收敛结果,方程组为:

X1 = X2 + X3 / 2 + X5 / 4 + X6 / 2X2 = X1 / 5 + X3 / 2 + X4 / 3

X3 = X1 / 5 + X4 / 3 + X5 / 4

X4 = X1 / 5 + X5 / 4

X5 = X1 / 5 + X4 / 3 + X6 / 2 + X7

X6 = X5 / 4

X7 = X1 / 5

X1 + X2 + X3 + X4 + X5 + X6 + x7 = 1

解这个方程,最终我们得到每个网页的PageRank收敛值分别为:

X1 = 0.303514,X2 = 0.38286,X3 = 0.32396,X4 = 0.24297,X5 = 0.41231,X6 = 0.10308,X7 = 0.13989。

将PageRank的评价按顺序排列,小数点3位四舍五入,可以得到下表:

名次 PageRank   文件ID   发出链接ID  被链接ID1     0.304     1       2,3,4,5,7   2,3,5,6

2     0.179     5       1,3,4,6     1,4,6,7

3     0.166     2       1           1,3,4

4     0.141     3       1,2         1,4,5

5     0.105     4       2,3,5       1,5

6     0.061     7       5           1

7     0.045     6       1,5          5

让我们详细地看一下。ID=1 的文件的 PageRank 是0.304,占据全体的三分之一,成为了第1位。特别需要说明的是,起到相当大效果的是从排在第3位的 ID=2页面中得到了所有的 PageRank(0.166)数。ID=2页面有从3个地方过来的反向链接,而只有面向 ID=1页面的一个链接,因此(面向ID=1页面的)链接就得到了所有的 PageRank 数。不过,就因为 ID=1页面是正向链接和反向链接最多的页面,也可以理解它是最受欢迎的页面吧。

 

 

 

依据上图的PageRank值,我们实际地试着计算一下PageRank的收支,只要将自各页的流入量单纯相加即可。譬如 ID=1 的流入量为:

ID=1的流入量=(ID=2发出的Rank)+(ID=3发出的Rank) + (ID=5发出的Rank) + (ID=6发出的Rank) = 0.166 + 0.141 / 2 + 0.179 / 4 + 0.045 / 2 = 0.30375

在误差范围内PageRank的收支相符合。其他页面ID的情况也一样。以上的 PageRank 推移图正表示了这个收支。沿着各自的链接发出的PageRank等于此页面原有的PageRank除以发出链接数的值,而且和各自的页面的PageRank收支相平衡。

不过,这样绝妙均衡的本身,对理解线形代数的人来说当然不会是让人惊讶的事情。因为这正是“特性值和固有矢量的性质”,总之这样被选的数值的组就是固有矢量。以上就是 PageRank 的基本原理。 Google 做的就是大规模地处理这样的非常特性值问题。

PS:LZ系保研,由于没有参加考研,像《线性代数》、《随机过程》好多年没摸过了,很多知识都有所遗忘,所以写的不深入。本文的一些内容是参考了别人的博客,自己又加入了些新元素,算是做一次探讨。当然,接下来LZ会开始复习一下相关的数学知识,后续会重写本文,以便于让本文显得更为Strong~

ubuntu装sqlplus比win要复杂的多!

首先,Ubuntu 12.04LTS,没有装Oracle的Server

$ uname -a
Linux conan 3.2.0-27-generic-pae
#43-Ubuntu SMP Fri Jul 6 15:06:05 UTC 2012 i686 i686 i386 GNU/Linux

 

下载Oracle Clinet rpm包
https://help.ubuntu.com/community/Oracle%20Instant%20Client

 

  • Download the Oracle Instantclient RPM files fromhttp://www.oracle.com/technetwork/database/features/instant-client/index-097480.html. Everyone needs either “Basic” or “Basic lite”, and most users will want “SQL*Plus” and the “SDK”.
  • Convert these .rpm files into .deb packages and install using “alien” (“sudo apt-get install alien” if you don’t have it):
    alien -i oracle-instantclient-basic*.rpm
    alien -i oracle-instantclient-sqlplus*.rpm
    alien -i oracle-instantclient-devel*.rpm

 

然后,设置 ldconfig

 

sudo vi /etc/ld.so.conf.d/oracle.conf
  • and add the oracle library path as the first line. For example,

 

/usr/lib/oracle/11.1.0.1/client/lib
  • or

 

/usr/lib/oracle/11.2/client/lib/
  • Then run ldconfig:
    sudo ldconfig

这时,执行sqlplus就不报缺少*.o的错误了。

找到client的安装目录,新建一个文件, tnsnames.ora,在这个文件配置相关的访问参数。

 

test=
(DESCRIPTION=
  (ADDRESS=(PROTOCOL=TCP)(HOST=192.168.1.1)(PORT+1521))
  (CONNECT_DATA=(SERVER=DEDICATED)(SERVICE_NAME=tea.tea))
)

然后,再设置环境变量TNS_ADMIN到clinet的安装目录

export TNS_ADMIN=/usr/lib/oracle/11.2/client/lib

 

都设置成功通过sqlplus启动
sqlplus username/password@test

 

[转] 如何“打败”CAP定理

CAP定理是数据系统设计的基本理论,目前几乎所有的数据系统的设计都遵循了这个定理。但CAP定理给目前的数据系统带来了许多复杂的、不可控的问题,使得数据系统的设计越来越复杂。Twitter首席工程师、Storm的作者Nathan Marz在本文中通过避开CAP定理带来的诸多复杂问题,展示了一个不同于以往的数据系统设计方案,给我们的数据系统设计带来了全新的思路。

 

原文 :http://www.programmer.com.cn/9260/

CAP定理指出,一个数据库不可能同时满足一致性(Consistency)、可用性(Availability)和分区容错性(Partition-Tolerance)。

一致性(Consistency)是指执行了一次成功的写操作之后,未来的读操作一定可以读到这个写入的值。可用性(Availability)是指系统总是可读可写的。Yammer的Coda Hale和Cloudera的Henry Robinson都阐述过,分区容错性是不能牺牲的,因此只能在一致性和可用性上做取舍,如何处理这种取舍正是目前NoSQL数据库的核心焦点。

选择一致性而不是可用性的系统将面临一些尴尬的问题,当系统不可用时怎么办?你可以对写操作进行缓冲处理,但如果存储缓冲数据的机器出现故障,客户端将丢失写入的值。同样地,缓冲写也可以被认为是一种非一致性的操作,因为客户端认为成功的写入实际上并没有写入到实际的数据库中。当然,系统可以在机器不可用时向客户端返回错误,但可以想象,一个经常告诉客户端“请重试”的产品是多么令人讨厌。

另一个方案是选择可用性放弃一致性。这种情况下最好的一致性保障是“最终一致性”(Eventually Consistency)。当使用最终一致性的系统时,客户端有时会读到与刚刚写入数据不同的数据。有时候,同一时间同一个key的多个请求有可能返回不同的结果。数据更新并不能及时在所有的复制节点上生效,所以不同的复制节点上可能读取到的是不同的值。当你检测到数据不一致性时,你需要进行修复(Repair)操作,这就需要使用矢量时钟(vector clock)记录数据的版本历史并合并不同的数据更新(这称为读取修复,read repair)。

我相信在应用层维护最终一致性对开发人员负担太重,开发人员极易弄错读取修复的代码,而一旦开发人员犯错,有问题的读取修复将对数据库系统造成不可逆的损坏。

所以牺牲可用性时问题会很多,牺牲一致性时构建和维护系统的复杂度又很高,但这里又只有两个选择,不管怎样做都会不完美。CAP定理是改不了的,那么还有什么其他可能的选择吗?

实际上,还有一个办法:你并不能避开CAP定理,但可以把复杂的问题独立出来,免得你丧失对整个系统的掌控能力。CAP定理带来的复杂性,其实是我们如何构建数据系统这一根本问题的体现。其中有两点特别重要:数据库中可变状态和更新状态的增量算法。复杂性正是这两点和CAP定理之间的相互作用导致的。

本文将通过一个数据库系统的设计,来说明如何解决CAP定理通常会造成的复杂性问题。但我要做的不仅仅如此,CAP定理是一个针对机器发生错误时系统容错性的一个定理,而这里有比机器容错性更加重要的容错性——人为操作容错性。在软件开发中一个确定的事实是,开发人员都并非完人,产品中难免有一些Bug,我们的系统必须对有Bug的程序写入的错误数据有足够的适应能力,我要展示的系统将是这样一个可以容忍人为错误的系统。

本文将挑战你对数据系统如何构建这一问题的假设,通过颠覆传统数据系统构建方法,我会让大家看到一个前所未见的优雅、扩展性强、健壮的数据系统。

什么是数据系统?

在开始介绍系统设计之前,让我们先来看看我们要解决的问题:数据系统的目的在于什么? 什么是数据? 在我们考虑CAP定理之前,我们必须给出一个可以适用于所有数据应用程序的定义来回答上述问题。

数据应用程序种类很多,包括存入和提取数据对象、连接、聚合、流处理、机器学习等。似乎并不存在一个对数据系统的明确定义,数据处理的多样性使得我们很难用一个定义来描述。

事实却并非如此,下面这个简单的定义:

Query = Function(All Data)

概括了数据库和数据系统的所有领域。每一个领域——有50年历史的RDBMS、索引、OLAP、OLTP、MapReduce、EFL、分布式文件系统、流处理器、NoSQL等——都可以被概括进这个方程。

所谓数据系统就是要回答数据集问题的系统,这些问题我们称之为“查询”。上面的方程表明,查询就是数据上的一个函数。

上述方程对于实际使用来说太过于笼统,几乎对复杂的数据系统设计不起什么作用。但如果所有的数据系统都遵循这个方程又会怎样呢?这个方程是探索我们数据系统的第一步,而它最终将引导我们找到“打败”CAP定理的方法。

这个方程里面有两个关键概念:数据、查询。这两个完全不同的概念经常被混为一谈,所以下面来看看这两个概念究竟是什么意思。

数据

我们先从“数据”开始。所谓数据就是一个不可分割的单位,它肯定存在,就跟数学里面的公理一样。

关于“数据”有两个关键的性质。首先,数据是跟时间相关的,一个真实的数据一定是在某个时间点存在于那儿。比如,假如Sally在她的社交网络个人资料中写她住在芝加哥,你拿到的这个数据肯定是她某个时间在芝加哥填写的。假如某天Sally把她资料里面居住地点更新为亚特兰大,那么她肯定在这个时候是住在亚特兰大的,但她住在亚特兰大的事实无法改变她曾经住在芝加哥这个事实——这两个数据都是真实的。

其次,数据无法改变。由于数据跟某个时间点相关,所以数据的真实性是无法改变的。没有人可以回到那个时间去改变数据的真实性,这说明了对数据操作只有两种:读取已存在的数据和添加更多的新数据。那么CRUD就变成了CR【译者注:CRUD是指Create Read Update Delete,即数据的创建、读取、更新和删除】。

我去掉了“更新”操作,因为更新对于不可改变的数据没有任何作用。例如,更新Sally的位置信息本质上就是在她住的地方数据中新加一条最近的位置信息而已。

我同样去掉了“删除”操作,因为绝大部分删除操作可以更好地表述为新加一条数据。比如Bob在Twitter上不再关注Mary了,这并不能改变他曾经关注过Mary这个事实。所以与其删除Bob关注Mary这个数据,还不如新加一条Bob在某个时间点不再关注Mary这个数据。

这里只有很少数的情况需要永久“删除”数据,例如规则要求你每隔一段时间清掉数据,这个情况在我将要展示的系统中有很好的解决方案,所以为了简洁,我们暂不考虑这些情况。

查询

查询是一个针对数据集的推导,就像是一个数学里面的定理。例如,你可以通过计算“Sally现在的位置在哪里”这个查询来得到Sally最新的位置数据。查询是整个数据集合上的函数,可以做一切事情:聚合、连接不同类型的数据等。因此,你可以查询系统中女性用户的数量,可以查询最近几小时热门的Twitter内容。

前面我已经定义查询是整个数据集上的函数,当然,不是所有的查询都需要整个数据集,它们只需要数据集的一个子集。但我的定义是涵盖了所有的查询类型,如果想要“打败”CAP定理,我们需要能够处理所有的查询。

打败CAP定理

计算查询最简单的办法就是按照查询语义在整个数据集上运行一个函数。如果这可以满足你对延迟的要求,那么就没有其他需要构建的了。

可想而知,我们不能指望在整个数据集上的查询能够很快完成,特别是那些服务大型网站、需要每秒处理几百万次请求的系统。但假如这种查询可以很快完成,让我们来看看像这样的系统和CAP定理的PK结果:你将会看到,这个系统不仅打败了CAP定理,而且还消灭了它。

CAP定理仍然适用,所以你需要在可用性和一致性上做出选择,这里的漂亮之处在于,一旦你权衡之后做出了选择,你就做完了所有的事情。通常的那些因为CAP定理带来的问题,都可以通过不可改变的数据和从原始数据中计算查询来规避。

如果你选择一致性而不是可用性,那么跟以前并没有多大的区别,因为你放弃了可用性,所以一些时候你将无法读取或者写入数据。当然这只是针对对强一致性有要求的系统。

如果你选择可用性而不是一致性,在这种情况下,系统可以达到最终一致性而且规避了所有最终一致性带来的复杂问题。由于系统总是可用的,所以你总可以写入新数据或者进行查询。在出错情况下,查询可能返回的不是最近写入的数据,但根据最终一致性,这个数据最终会一致,而查询函数最终会把这个数据计算进去。

这里的关键在于数据是不可变的。不可变数据意味着这里没有更新操作,所以不可能出现数据复制不同这种不一致的情况,也意味着不需要版本化的数据、矢量时钟或者读取修复。在一个查询场景中,一个数据只有存在或者不存在两种情况。这里只有数据和在数据之上的函数。这里没有需要你为确保最终一致性额外做的事情,最终一致性也不会因此使你的系统变得复杂。

之前的复杂度主要来自增量更新操作和CAP定理之间的矛盾,在最终一致性系统中可变的值需要通过读取修复来保证最终一致性。通过使用不可变数据,去掉增量更新,使用不可变数据,每次从原始数据计算查询,你可以规避那些复杂的问题。CAP定理就被打败了。

当然,现在讲的只不过是想法而已,而且每次从原始数据计算查询基本上不可能。但我们从中可以学到一些在实际解决方案中的关键点。

  • 数据系统因为不可变数据和不断增长的数据集变得简单了。
  • 基本的写入操作就是写入一条新的不可变数据。
  • 数据系统通过重新从原始数据计算查询规避了CAP定理带来的复杂度。
  • 数据系统利用增量算法使得查询的返回延迟降低到一个可以接受的程度。

让我们开始探索这个数据系统应该如何设计。请注意从这里开始我们所描述都是针对系统优化、数据库、索引、EFL、批量计算、流处理——这些技术都是对查询函数的优化,让查询返回时间降低到一个可以接受的程度。这很简单,但也是数据系统所面对的现实。数据库通常是数据管理的核心,但它们是更大蓝图中的一部分。

批量计算

“如何让任意一个函数可以在任意一个数据集上快速执行完成”这个问题太过于复杂,所以我们先放宽了一下这个问题依赖条件。首先假设,可以允许数据滞后几小时。放宽这个条件之后,我们可以得到一个简单、优雅、通用的数据系统构建解决方案。之后,我们会通过扩展这个解决方案使得它可以不用放宽条件来解决问题。

由于查询是所有数据的一个函数,让查询变快的最简单的方法就是预先计算好这些查询。只要这里有新的数据,你就重新计算这些查询。这是可能的,因为我们放宽了条件使得我们的数据可以滞后几个小时。图1展示了这个工作流程。

图1 预计算工作流程

图1 预计算工作流程

为了实现这个,你的系统需要:

  • 能很容易存储大的、不断增长的数据集;
  • 能在数据集上可扩展地计算查询函数。

这样的系统是存在的,即Hadoop。它是一个成熟的、经历了无数团队实战检验过的系统,同时拥有一个巨大的工具生态系统。它虽不完美,但是这里用来做批量处理的最好的一个工具。

许多人也许会告诉你,Hadoop只适用于那些“非结构化”的数据,这是完全错误的看法。Hadoop处理“结构化”的数据也很不错,通过使用像Thrift或者Protocol Buffers这样的工具,你可以使用丰富的数据结构存储你的数据。

Hadoop由分布式文件系统HDFS和批处理框架MapReduce两部分构成。HDFS可以通过文件存储大量数据,MapReduce可以在这样数据上进行可扩展计算。这个系统完全符合我们的要求。

我们将数据以文件形式存储到HDFS中去。文件可以包括一个数据记录序列。新增数据时,我们只需要在包括所有数据的文件夹中新增一个包含这条新记录的文件即可。像这样在HDFS存储数据满足了“能够很容易存储大的、不断增长的数据集”这个要求。

预计算数据集上的查询也很直观,MapReduce是一个足够复杂的框架,使得几乎所有的函数都可以按照多个MapReduce任务这种方式实现。像Cascalog、Cascading和Pig这样的工具使实现这些函数变得十分简单。

最后,为了可以快速访问这些预计算查询结果,你需要对查询结果进行索引,这里有许多数据库可以完成这个工作。ElephantDB和Voldemort read-only可以通过从Hadoop中导出key/value数据来加快查询速度。这些数据库支持批量写和随机读,同时不支持随机写。随机写使得数据库变得复杂,所以通过不支持随机写,这些数据库设计得特别简洁,也就几千行代码而已。简洁使得这些数据库鲁棒性变得非常好。

下面来看批量处理系统整体上是如何配合工作的。假设写一个网站分析程序来跟踪页面访问量,你需要能够查询到任意时间段的页面访问量,数据是以小时方式提供的。如图2所示。

图2 批处理工程流程示例(timestamp代表时间戳,count代表个数)

图2 批处理工程流程示例(timestamp代表时间戳,count代表个数)

实现这个很简单,每一个数据记录包括一个单一页面的访问量。这些数据通过文件形式存储到HDFS中,一个函数通过实现MapReduce计算任务,来计算一个URL下页面每小时的访问量。这个函数产生的是key/value对,其中[URL, hour]是key,value是页面的访问量。这些key/value对被导出到ElephantDB中去,使得应用程序可以快速得到任意[URL, hour]对对应的值。如果应用程序想要知道某个时间范围内某个页面的访问量,它可以查询ElephantDB中那段时间内的数据,然后把这些数据相加就可以得到这个访问量数据了。

在数据滞后几小时这个缺陷下,批量处理可以计算任意数据集上的任意函数。系统中的“任意性”是指这个系统可以处理任何问题。更重要的是,它很简单,容易理解和完全可扩展,你需要考虑的只是数据和查询函数,Hadoop会帮你处理并行的事情。

批处理系统、CAP定理和容忍人为错误

截至目前,我们的系统都很不错,这个批处理系统是不是可以达到容忍人为错误的目标呢?

让我们从CAP定理开始。这个批处理系统总是最终一致的:写入的数据总可以在几小时后被查询到。这个系统是一个很容易掌控的最终一致性系统,使得你可以只用关注你的数据和针对数据的查询函数。这里没有涉及读取修复、并发和其他一些需要考虑的复杂问题。

接下来看看这个系统对人为错误的容忍性。在这个系统中人们可能会犯两个错误:部署了一个有Bug的查询函数或者写入了错误的数据。

如果部署了一个有Bug的查询函数,需要做的所有事情就是修正那个Bug,重新部署这个查询函数,然后在主数据集上重新计算它。这之所以能起作用是因为查询只是一个函数而已。

另外,错误的数据有明确的办法可以恢复:删除错误数据,然后重新计算查询。由于数据是不可变的,而且数据集只是往后添加新数据,写入错误的数据不会覆盖或者删除正确的数据,这与传统数据库更新一个数据就丢掉旧的数据形成了鲜明的对比。

注意到MVCC和HBase类似的行版本管理并不能达到上面人为错误容忍级别。MVCC和HBase行版本管理不能永久保存数据,一旦数据库合并了这些版本,旧的数据就会丢失。只有不可变数据系统能够保证你在写入错误数据时可以找到一个恢复数据的方法。

实时层

上面的批量处理系统几乎完全解决了在任意数据集上运行任意函数的实时性需求。任何超过几个小时的数据已经被计算进入了批处理视图中,所以剩下来要做的就是处理最近几个小时的数据。我们知道在最近几小时数据上进行查询比在整个数据集上查询要容易,这是关键点。

为了处理最近几个小时的数据,需要一个实时系统和批处理系统同时运行。这个实时系统在最近几个小时数据上预计算查询函数。要计算一个查询函数,需要查询批处理视图和实时视图,并把它们合并起来以得到最终的数据。

图3 计算一个查询

图3 计算一个查询

在实时层,可以使用Riak或者Cassandra这种读写数据库,而且实时层依赖那些数据库中对状态更新的增量算法。

让Hadoop模拟实时计算的工具是Storm。我写Storm的目的是让Hadoop可以健壮、可扩展地处理大量的实时数据。Storm在数据流上运行无限的计算,并且对这些数据处理提供了强有力的保障。

让我们回到刚才那个根据某个URL查询某个页面在某个时间段内页面访问量的例子,通过这个例子我将展示实时层是如何工作的。

批处理系统还是跟之前一样:一个基于Hadoop和ElephantDB的批处理工作流,在几个小时之前的数据上预计算查询函数。剩下就是让实时系统去处理最近几小时数据了。

我们将最近几小时的数据状态存入Cassandra中,用Storm去处理页面访问量数据流并并行更新到数据库中,针对每一个页面访问量,在[URL, hour]所代表的key下,有一个计数器,这个计数器在Cassandra中实现。这就是所有的事情,Storm让事情变得非常简单。

图4 批处理/实时架构示例

图4 批处理/实时架构示例

 

批处理层+实时层、CAP定理和人为错误容忍性

貌似又回到一开始提出的问题上去了,访问实时数据需要使用NoSQL数据库和增量算法。这就说明回到了版本化数据、矢量时钟和读取修复这些复杂问题中来。但这是有本质区别的。由于实时层只处理最近几小时的数据,所有实时层的计算都会被最终批处理层重新计算。所以如果犯了什么错误或者实时层出了问题,最终都会被批处理层更正过来,所有复杂的问题都是暂时的。

这并不意味着不需要关心实时层的读取修复和最终一致性,你仍然需要实时层尽可能的一致。但当犯了一个错误时,不会永久性地破坏数据。这便移除了许多你所需要面对的复杂问题。

在批处理层仅需要考虑数据和数据上的查询函数,批处理层因此很好掌控。在实时层,需要使用增量算法和复杂的NoSQL数据库。把所有的复杂问题独立到实时层中,对系统的鲁棒性、可靠性做出了重大贡献。

同样的,实时层并没有影响系统的人为错误容忍性,这个数据不可变和只追加的批处理系统,仍然是整个系统的核心,所以所有的都可以像上面说的一样被纠正过来。

我有一个类似的系统:Hadoop和ElephantDB组成批处理系统,Storm和Cassandra组成实时系统。由于缺乏监控,某天当我起床的时候发现Cassandra运行满负荷了,使得所有的数据请求都超时。这使得Storm计算失败,一些数据又重新回到了等待队列中,这个数据就一次次重复请求。

如果我没有批处理层,那么我就需要扩展和恢复Cassandra,这个很不容易。更糟的是,因为请求不断的重复,无法得到正确的数据。

幸运的是,所有的复杂问题都被隔离到实时层中去了,我清空了所有的后台请求队列,把它们打到了批处理层上,同时重启了Cassandra集群,过了几个小时之后所有数据都恢复正常了。没有错误数据,请求中也没有不准确的地方。

垃圾回收

上面描述的所有东西都是建立在一个不可变的、不断增长的数据集上的。如果数据集已经很大,使得不可能用水平扩展储存所有时间的所有数据,该如何处理呢?这是不是就推翻了我说的一切呢?是不是需要回到可变数据的系统上呢?

不。我们可以很容易地用“垃圾回收”对基本模型进行扩展来解决上面的问题。垃圾回收是一个在主数据集上的简单函数,返回的是一个过滤版本的主数据集。垃圾回收掉了旧数据,可以选择任意的垃圾回收策略。可以在易变的系统中只保留数据最新的一个值或者保留每个数据的历史。比如,如果要处理位置数据,可以保留每人每年的一个地点。可变性是一个不是很灵活的垃圾回收形式(它跟CAP定理交互得也很糟糕)。

垃圾回收可以被实现成批处理的一个任务,隔段时间运行一下。由于它是作为离线批处理任务执行的,所以不影响我们与CAP定理的交互。

总结

让可扩展的数据系统复杂的原因不是CAP系统,而是数据增量算法和数据的可变状态。最近由于分布式数据库的兴起导致了复杂度越来越不可控。前面讲过,我将挑战对传统数据系统构建方法的假设。我把CRUD变成了CR,把持久化层分成了批处理和实时两个层,并且得到对人为错误容忍的能力。我花费了多年来之不易的经验打破我对传统数据库的假设,并得到了这些结论。

批处理/实时架构有许多有趣的能力我并没有提到,下面我总结了一些。

算法的灵活性。随着数据量的增长,一些算法会越来越难计算。比如计算标识符的数量,当标识符集合越来越大时,将会越来越难计算。批处理/实时分离系统给了你在批处理系统上使用精确算法和在实时系统上使用近似算法的灵活性。批处理系统计算结果会最终覆盖实时系统的计算结果,所以最终近似值会被修正,而你的系统拥有了“最终精确性”。

数据结构迁移变得很容易。数据结构迁移的难题将一去不复返。由于批量计算是系统的核心,很容易在整个系统上运行一个函数,所以很容易更改你数据的结构或者视图。

简单的Ad-Hoc网络。由于批处理系统的任意性,使得你可以在数据上进行任意查询。由于所有的数据在一个点上都可以获取,所以Ad-Hoc网络变得简单而且方便。

自我检查。由于数据是不可变的,数据集就可以自我检查。数据集记录了它的数据历史,对于人为错误容忍性和数据分析很有用。

我并没有说我已经“解决”了数据量过大的问题,但我已经为解决大数据问题制订了一个框架。批处理/实时架构可以应用到任何一个数据系统中去,“授人以鱼,不如授人以渔”,我已经告诉你了如何去构建这样的系统。

为了提高系统整体能力来解决大数据的问题,我们还有许多工作需要做。

  • 扩展数据模型,支持批量写和随机读。不是每一个应用程序都支持key/value的数据库,这也是我们团队对扩展ElephantDB,使得可以支持搜索、文档数据库、区间查询感兴趣的原因。
  • 更好的批处理原语。Hadoop并不是批处理的最终形态,好多批处理计算Hadoop效率不高。Spark是一个有意思的扩展MapReduce的项目。
  • 提升后的读写NoSQL数据库。这里不同类型数据的数据库还有很大的提升空间,随着这些数据库的成熟,它们将收获很多。
  • 高层级的抽象。未来工作中最有意思的就是对批处理模块和实时处理模块的高层次抽象,在批处理和实时架构下你没有理由不拥有一个简单的、描述性的、鲁棒性好的语言。

许多人需要一个可扩展的关系型数据库,本文就是想让你知道完全不需要那个。大数据量和NoSQL运动使数据管理比RDBMS更加复杂。那仅仅是因为我对大数据的处理采用了跟RDBMS同样的方法:把数据和视图混为一谈,并且依赖增量算法。大数据量需要采用完全不同的方式构建数据系统。通过存储持续增长的不可变数据,并且系统核心采用预计算,大数据系统就可以变得比关系型数据库更易掌控,并且可扩展性很强。

(感谢Nathan Marz先生的授权,原文名为How to beat the CAP theorem。同时感谢方建对本文翻译做出的贡献。)