Leoncom

在实际中碰到这样一类问题，有一个结构体，中间包括各种不同的类型，但有一种函数，需要对不同类型字段的值都进行统计、排序等操作，函数中90%的代码都相同，唯一的不同是获取目标结构体的不同字段的值，为了避免针对不同类型的字段，声明不同类型的变量，通过封装get_field_val(struct)为模板函数解决此问题。如下代码

#include <iostream>
#include <string>
#include <vector>

using namespace std;

struct info_t{
 int a;
 string b;
 int c;
};

class account{
public:
 template<class T>
 void account_field(int type)
 {
 vector<T> vec;
 for(int i = 0; i < 8; i++)
 {
 T val;
 val = get_val<T>(infos[i], type);
 vec.push_back(val);
 }
 //统计, 排序xxxx一堆工作
 //...
 return;
 }

 template<class T>
 T get_val(info_t info, int type)
 {
 if(type == 1)
 return info.a;
 else
 return info.c;
 }

private:
 info_t infos[8];
};

template<> string account::get_val<string>(info_t info, int type)
{
 return info.b;
}

int main(void)
{
    account a;
    a.account_field<int>(1);
    a.account_field<string>(2);
    return 0;
}

如上，使用模板get_val函数和type获取指定字段的值，并且针对string进行模板的特化。对于类成员模板函数的特化，必须放在类定义的外部，否则会报Explicit specialization in non-namespace scope的错误，具体的原因可以参见如下说明。如果没有该特化，也可以直接重载一个函数，但这样就不能在调用函数时显示特化了，特别是对于调用a.account_field<T>(type)的函数。

An explicit specialization shall be declared in the namespace of which the template is a member, or, for member templates, in the namespace of which the enclosing class or enclosing class template is a member.

An explicit specialization of a member function, member class or static data member of a class template shall be declared in the namespace of which the class template is a member.

当我们需要对某段读写文件并进行处理的程序进行性能测试时，文件会被系统cache住从而影响I/O的效率，必须清理cache中的对应文件的才能正确的进行性能测试。通常清理内存可以采用下面的这条命令，但这条命令只有root才能使用，另外一方面这个会清理所有的cache，也许会影响其他程序的性能。

echo 3>/proc/sys/vm/drop_caches

linux下有一个posix_fadvise函数可以用来对cache中的文件进行清理，有关posix_fadvise的详细说明查看man手册。

int posix_fadvise(int fd, off_t offset, off_t len, int advice);

”Programs  can  use  posix_fadvise  to  announce an intention to access file data in a specific pattern in the future, thus allowing the kernel to perform appropriate optimisations”

fd是文件的描述符，用于清理对应文件cache的advice值选取POSIX_FADV_DONTNEED，利用此函数编写下面程序进行文件的清理。

int clear_file_cache(const char *filename)
{
	struct stat st;
	if(stat(filename , &st) < 0) {
		fprintf(stderr , "stat localfile failed, path:%s\n",filename);
		return -1;
	}

	int fd = open(filename, O_RDONLY);
	if( fd < 0 ) {
		fprintf(stderr , "open localfile failed, path:%s\n",filename);
		return -1;
	}

	//clear cache by posix_fadvise

	if( posix_fadvise(fd,0,st.st_size,POSIX_FADV_DONTNEED) != 0) {
		printf("Cache FADV_DONTNEED failed, %s\n",strerror(errno));
	}
	else {
		printf("Cache FADV_DONTNEED done\n");
	}

	return 0;
}

此外，linux-ftools这个工具也可以帮助清理并查看文件的内存状态，主页上也有详细的使用说明。编译后我们利用fincore这个工具来查看文件在内存中的状态，有关fincore的实现可以在linux下man mincore，mincore是根据缓存buffer指针来其指向的缓冲区判断在cache中的状态，fincore就是在mincore的基础上直接操作文件，就是通过对文件mmap获得指针，再调用mincore来判断。

首先我们通过cp命令拷贝了一个相对有点容量的文件，然后利用fincore查看文件在内存中的cache情况，可以看到大概cache了99.55%。

接着执行上面那段代码的运行程序，之后再执行命令查看该文件的缓存状态

可以看到，该文件在内存中已经没有被cache了。实际的清理效果也可以通过一些占用I/O的读文件程序来测试，一般程序第二遍运行时候由于文件已经被cache，实际程序运行的速度会比较快，通过上面的posix_fadivse清理之后，又会恢复和第一遍差不多的时间。

以下的一段代码是不是很眼熟

     char *a = new char[1024];
     if(a == NULL) {
           //申请失败，处理
     }
     else {
          //正常处理....
     }

的确经常会在程序里这样用，特别是上学时候很多的教科书里想当然的申请失败，返回了NULL。由于使用C++的同学一般不太使用Exception机制，而会忽略异常。其实C++的库中对operator new的声明如下形式。

void* operator new (std::size_t size) throw (std::bad_alloc);
void* operator new (std::size_t size, const std::nothrow_t& nothrow_constant) throw();
void* operator new (std::size_t size, void* ptr) throw();

第一种是我们最常使用的，这种方式在申请失败时会抛出std::bad_alloc的异常，而非返回NULL，如下代码。

#include <iostream>
#include <unistd.h>
using namespace std;

int main(void)
{
    while(1) {
        char *a = new char[1024*1024*1024];
        if( a != NULL) {
            cout<<"new 1GB buffer size"<<endl;
        }
        else {
            cout<<"new failed!\n"<<endl;
            return -1;
        }
    }
    return 0;
}

其运行结果如下图，可以看出，程序抛出了std::bad_alloc的异常

第二种则添加了nothrow参数，使得new不抛出异常。
对上面的第8行做如下修改:

        char *a = new(nothrow) char[1024*1024*1024];

从运行结果就可以看出来，程序不抛出异常，而直接返回NULL指针了。

最后一种是placement new，即是在ptr指向的空间上new对象，本身并不申请空间，因此也不会异常。

默认情况下的new是会抛出std::bad_alloc异常的，可以使用set_new_handler来处理默认情况下的异常，代码如下：

#include <iostream>
#include <unistd.h>
using namespace std;

void no_memory () {
  cout << "Failed to allocate memory!"<<endl;
  //这里可以写点清理代码
  throw bad_alloc();  //默认处理函数，继续往上层抛出
  exit (1);
}

int main(void)
{
    set_new_handler(no_momery);
    while(1) {
        char *a = new char[1024*1024*1024];
        if( a != NULL) {
            cout<<"new 1GB buffer size"<<endl;
        }
        else {
            cout<<"new failed!\n"<<endl;
            return -1;
        }
    }
    return 0;
}

则程序执行到new抛出了异常时，会利用set_new_handler的函数进行处理，也可以不throw转而直接exit/return等，执行效果如下：

这段代码告诫自己平常学习应该多钻研，多问，不能想当然，特别是学校课堂上的东西都太过于理想。如果不清楚的应该多看官方一点的东西，有关operator new的东西可以查看这里，描述的很清楚。

强制类型转换

MySQL中提供了两个函数来实现强制类型转换，分别为convert和cast，这两个函数在将一个数值转换为其他类型时的作用几乎一样，写法上略有不同，但convert函数可以将一个值转为其他编码。参考MySQL手册说明：

编码转换：CONVERT(expr  USING transcoding_name)，如

类型转换：CONVERT(expr , type) 或者 CAST(expr AS type)，其中type为以下类型中的一种

• BINARY [(N)]  转为二进制字符串，后面N为限定长度，有关BINARY类型的参考点这里
• CHAR [(N)]
• DATE   日期
• DATETIME  日期时间
• DECIMAL [(M[,D])]   转为浮点数，M为数字的长度(包括整数部分和小数部分)，N为小数点后位数

转为DECIMAL类似C语言中的atoi函数，即从头扫描字符串直到第一个不为数字的字符截至，对截断的那一位进行四舍五入取整。

默认不限定M,N，转换是转为整数，按照小数点后第一位进行四舍五入。

限定M不限定N，则根据数字的位数输出整数，需要注意的是，当M的长度小于实际的数字位数时，会转化成设定为最大的，如下面这个转换，由于设置M为1，即显示不了21这个两位数，就会显示 1位数中最大的9。如果对于设定了小数点后位数N的限定，也会这样转换，同时必须先满足小数点后的N位小数。

位数不够显示全部，则

  满足了1位小数，再取1位整数

必须先满足2位小数，不取整数部分。

正常的转换如下，尽可能的将M设置大，而N根据自己的需要选择保留几位小数。

保留一位小数，第二位四舍五入

保留两位小数

保留三位小数，加0补齐位数

需要注意，尽管M可以设置的足够大而不影响数字的长度，但转换依然会先满足小数位数N的需要

满足9位小数，只剩1位整数只能取9。

• SIGNED 有符号整数
• TIME 日期的时间部分
• UNSIGNED 无符号整数

其中上面的’2’-3由MySQL自动做了一次强制类型转换，根据四则运算将’2’转为了数字2。

自动类型转换

在进行一些四则运算以及逻辑运算时，MySQL也会根据计算的类型以及操作数的类型进行自动转换。

四则运算，转为数字操作

逻辑运算，转为0或1

位操作，转为数字的二进制位。

也可以一些自动进行数字以及字符串向date的转换，例如下面的操作

写码过程中碰到这样一个需求。一个table中一列是varchar类型，但是输入的类似是’1.23/张’ 这样的数据，即前面是一个类似单价的东西，后面只是加了一个说明，另外一列为int，需要计算两列的乘积。有了MySQL这样的自动类型转换，就不需要select后逐条的进行atoi的操作，并计算结果进行update了，特别是其中某些列中的数据不全，即varchar为NULL或者int为NULL，会自动不处理，相当的方便哈。如下。

最后一句，大爱MySQL哈！！！

搜索引擎利用IR的方法对于一个特定的query检索出该关键词上的出价广告后，就需要对SERP页面上的广告栏分配给出价的广告主，牵扯到搜索广告的排序问题。一般共识是左侧的广告位(即搜索结果页上面的广告位)被看到和点击到的可能性最大，后侧的则按照从高到底排序，越靠上的广告位越好。简单的说就是谁出钱多谁得到的位置越好，复杂的研究这里面牵扯到博弈论之类的问题，假设存在n个对该关键词出价的广告主，k个广告位，每个广告主衡量自己想得到的广告位的价值，并根据他人的出价(有可能是透明，有可能不透明)来决定自己的出价，从而达到自己的宣传效果，同时又想尽可能的减少广告的CPC，而广告竞价又是一个不断变化的过程，如何达到某种相对的均衡状态。

常用竞拍模式

• First-Price Sealed-bid：一次性竞价，所有人同时出价，出价最高者获得物品，并支付他的出价。
• Second-Price Sealed-bid：出价方式同上，不同的是实际的支付价格是第二高的竞价。Vickrey拍卖。
• Open Ascending-bid：最常见的竞价方法，轮流喊，谁喊的最高谁拿，支付他的出价。称为英式拍卖。
• Open Descending-bid：荷式拍卖，拍卖人从高到低不断的减少定价，第一个能接受价格的人获得物品。

搜索广告的拍卖

Generailized Frist-Price Auction(GFP)：第一代拍卖方式，由Overtune.com提出，按照广告主的出价高低对广告进行排名，也引入了CPC机制，使得Overtune.com获得了巨大的成功并成为Yahoo和MSN的SE提供服务。GFP的结果是出价十分不稳定，动态的环境中每个广告主都会不断的调整自己的出价，希望尽可能的降低CPC，获得更高的回报。例如由两个广告位，分别吸引到200个Click和100个Click，之前的出价分别为4$和2$，但可能会不断的调整，调整到2$和2.01$。此时有可能广告主希望获得第一个广告位，出价2.02$，就这样不断的递增，然后递增到一定阈值后，索性放弃，又降到最低的2$，再一次竞价，该过程甚至可以由robot来完成，如下图。

Generailized Second-Price Auction(GSP)：Google与2002年实现，即每个广告主获得第i个位置实际支付的CPC由第i-1高的支付价决定，可能会略高一点(0.01$)，随后Overtune和Yahoo也采用了GSP这种方式，对广告主出价博弈更加友好。GSP的方式一般分为两种

1. Bid Ranking：按照广告的出价排序，位于第i位的广告的实际CPC为第i+1位的出价，如下图5个广告主在las vagas travel关键词上出价，有4个广告位：              
2. Revenue Ranking：按照实际的收益排序，此类排名考虑了每个广告的质量评分，即每个广告的CTR(表示的是广告与query的相关度，广告本身质量等，与位置无关的CTR)， 这样可以避免用户看到一些无关的、比较粗糙的广告会对搜索引擎本身产生反感。位置i上的广告主实际支付价格为 bid(i+1)*ctr(i+1)/ctr(i)，如果自身广告的质量评分远高于低一位的广告，则可以获得更低的支付价格。

迄今为止，使用最广告的竞价是GSP，该模型简单有效，也容易向客户进行解释，同时采用广告评分机制，能激励广告商尽可能的优化自己的广告，良好的广告信息对搜索引擎是有益的，对用户是友好的。此外，Vickery-Clark-Groves(VCG)拍卖也会在各个广告拍卖模型中被提起，VCG模型是一次性的对k个物品，n个竞拍者进行拍卖的过程，每一个竞拍者的实际出价由该竞拍者参与后对系统中其他竞拍者带来的损失决定。假设有两个广告位点击率分别为200和100，三个竞价者出价分别为$10,$4,$2。按照VCG模型，获得第二个广告位的人应该支付的价格为$2*100=$200，即因为他的参与，使得出价$2的参与者失去了第二个广告位，系统损失为$200。而第一个广告位获得者的支付价格为$600=$400+$200，$200是由于他的参与使得第三个竞拍者未获得广告位，而$400=$4*100，即他的参与使得出价$4的竞价者失去了以$4的CPC点击100次的广告效应。VCG的计算过程和讲解过程都很复杂，还没找到确切的文档资料说某个搜索引擎完全采用了VCG，有一些猜测G可能换了VCG。

VCG最主要的特性是truth-telling的占优策略，即如何所有的竞价者都真实的评估自己所想要得到的广告位价值，并按照此标准出价。而对于GSP动态中的均衡，Edelman引入了一种Locally envy free equilibrium，是纳什均衡的一种特例，在这种均衡状态下，每一个广告主都无法通过和自己前一位的广告交换出价交换位置得到更高的payoff。(payoff = c(i) * [v(i) – p(i)], c(i)是第i个位置的点击率，v(i)是广告主对第i位的真实估算价值，p(i)是实际的CPC)。

实际上搜索广告的排序除了出价以及广告质量外，还可能受其他各种各样的因素的影响，包括用户的地域、广告主的余额，以及广告主设定的策略等。

参考资料

Internet Advertising and the Generalized Second Price Auction, Edelman

搜索引擎的检索结果页下方一般会提示多个相似的搜索关键词，这些词可以被看作查询关键词query的rewriting。在计算广告中，当某一个query没有对应的bid phase出价广告，或者该query对应的bid phase较少的时候，可以利用query rewriting获取相似query对应的广告进行显示，以期望获得更多的click。相似query的确定可以利用用户session中的搜索关键词上下文，但此方法需要确定query的边界，例如用户搜索过程中可能会突然跳到一个完全不相干的搜索，然后又跳回来。或者利用传统的文本相似度匹配，而由于query一般都很短，传统相似度匹配的语料也不足。

Simrank

Simrank算法是一种用于衡量结构上下文中个体相似度的方法，直观上的含义是利用已有个体的相似度来推算其他与有关联个体的相似度。形式化的定义如下：

有向图G={V,E}中，节点a的入边集合记为I(a)，而出边集合记为O(a)，则两个节点a,b(a != b时)相似度s(a,b)按照如下公式计算，其含义是个体a,b的相似度取决于所有与a,b相连节点的相似度，s(a,b)∈[0,1]；当a=b时，s(a,b)=1；如果a != b，且只有同一个入节点c，我们不希望从c计算得到的s(a,b)也为1，因此c做为衰减因子，取值是[0,1]，即s(a,b) = C。

对于二分图G’ = (V1,V2,E)，对于任意的(A,a)∈E，有A∈V1和a∈V2，则所有V1集合中的节点相似度按照出度O(A)计算。V2集合中的节点相似度则按照上述公式，利用入度I(a)计算。

在搜索广告中，把query和ad看作节点，当用户搜索某个查询关键词q时，点击了广告a，则建立q至a的一条边，这样构成一个由query和ad组成的二分图G=(V,E)，其中V=Vq∪Va，任何边e=(q,a,w)，q∈Vq并且a∈Va，可以利用simrank算法来求query之间的相似度。E(q)表示q的边，N(q)表示E(q)的个数：

按照上述算法，我们看以下的例子，假设C等于0.8，则利用上述公式计算出的sim(pc,camera)的相似度在前5次迭代中都大于sim(camera,digital camera)，但从直观上说，由于camera和digital camera的共同邻居较多，应该具备更高的相似度，而simrank的结果是反直观的。针对上述问题，Antonellis等人在VLDB 08上提出了Simrank在计算广告方面的改进——Simrank++。

阅读全文…

简介

计算广告学于2008年由Yahoo Research的A.Broder提出，详细的定义参看百度百科，广义的定义是通过科学计算来选择最优的广告投放，主要研究的是互联网上的广告投放，其中典型的是在搜索引擎上查询关键词结果页出现的“推广链接”。

计算广告(或者说互联网广告)相比于传统的媒体广告的优势在于以下几点：

1. 投放的介质范围更广。传统的媒体广告一般只有相对较少的场合，例如报纸、杂志、电视、影院、路边广告牌，而互联网上除了大流量网页的banner等，搜索引擎上的一个词语就是一个投放介质。
2. 广告价格差距。cctv1的广告价格表，稍微像样的时段，30秒的广告都在10万人民币以上，就不提春晚这种露个脸就要上千万的地了。
3. 个性化。互联网广告可以根据人查询的关键字、Location以及个人信息等进行较为精确的投放。
4. 衡量投资回报率(ROI)。传统广告很难去衡量这个东西。

目标：

Find the “best match” between a given user in a given context and a suitable adverstiment.

互联网广告常用的付费方式有如下类型

• CPM(Cost Per Thousand Impressions)，按照展示次数付费，主要用于一些图形广告和首页banner。
• CPC(Cost Per Click)，按点击付费，搜索引擎的关键词广告常用付费方式。
• CPT/CPA(Cost Per Transcation/Action)，针对达到成功的营销效果的事务进行付费，例如购物类网站、酒店机票订购，用户消费后像广告投放商进行付费。
• 此外还有淘宝等国内网站的一种CPT(Cost Per Time)，即时间计费，可以包月包日。

计算广告学主要研究的是文本类广告(Textual Ads)，文本类广告的投放主要分为两种，由搜索关键词驱动的广告投放和由页面内容决定的广告投放，即Google大名鼎鼎的Adwords和Adsense。当然随着社交网络和SNS的发展，还会出现基于人际关系以及人的特性、行为的”Ad Profile”，例如之前某Boss去米国，一下飞机登录他的Facebook，发现右侧的广告是有关于“英语学习”和”美国回中国机票”。

文本广告组成

一个完整的搜索竞价广告示例，包括出价词语(Bid Phrase)、出价(Bid)，标题(Title)，描述(Creative)，显示的Url(Display URL)，而Landing URL是点击该广告的登录页面URL，Landing Page也经常用于关键词广告匹配过程。

检索方法概述

广告也可以看作成是一种信息，因此广告的匹配过程可以根据用户输入的查询关键词以及其他一些信息，例如之前搜索的内容、用户的Location等，采用一些传统的IR方法，将广告的出价词语、标题、描述以及Landing Page当做广告文档的语料，用来和用户输入的query进行文档相似度匹配。

A.Broder在SIGIR 2007提出了一种利用web search的结果来对query进行分类、从而进行广告选择的方法。用户在搜索引擎中输入的查询关键词一般都很短，有时候很难通过关键词了解到用户到底需要寻找什么，而通常如果看到了搜索结果的网页，就会了解用户到底要找什么，例如用户搜索一个v880，通过搜索结果页可以了解用户需要找一款Android的手机，此时就可以投放相应的手机广告了，即利用搜索结果为广告的选择提供额外的信息。

该方法需要研究的内容就是如何利用搜索结果页，是利用前几项片段还是利用整个结果页，是利用搜索结果页上的快照信息还是利用原网页信息，以及多个搜索结果并不统一，是采用整合还是投票选择机制。

计算广告学其中有很多问题需要算法来进行解决，包括广告分析、Query分析与重写、广告排序(纯粹谁出价高谁排前面就算了)之类的可以学习，本笔记的学习资料来源在这里。

声明：本文都是从AWS以及其他网上获取的知识整理笔记，不敢臆测Amazon内部的机制= =

Amazon位于N.Virginia的云计算数据中心于太平洋时间4月21日凌晨1点左右宕机，Service Health dashboard上写的是系统的连通性、延迟以及错误率等较高。其宕机影响了包括Quora、Foursquare、Reddit等众多的Web2.0明星应用，报道详情猛击这里，此外这篇评论也很有阅读价值(可能要翻墙，话说现在什么乱七八糟的网站都开始被墙了)。

报道中提到了Amazon没有解释为什么自己没有绕开出问题的AZ将服务转移，特意去关注了下AWS提供的服务在Failure Tolerance方面提供的一些特性。

Regions & Availablity Zones

Amazon EC2由Regions和Availablity Zones组成，按照其文档上的说明，Region由Availability Zones组成并分布在不同的地域甚至国家，AZs是Regions内部的可用区域，不同的AZ之间以工程设计的方式隔开以保证一个AZ的失效不会影响到其他AZ，同一个Region内部的不同AZ之间提供了inexpensive和low latency的通信。将自己的instance运行在多个独立的AZs中能避免自己的应用程序单点失效。Amazon目前有5个Region，分别位于N.Virginia、N.California、Ireland、Singapore以及Tokyo。

EC2的SLA协议中提到每个Region的可用性达到99.95%，EC2通过备份instance的快速启用以及预测启用提供高可靠的运行环境，These “availability zones” are supposed to ensure redundancy, but failed in this case。

Amazon Simple Storage(S3)

按照官方的说明，S3提供了高达99.999999999%的可用性，设计上可以容忍分布两个设备上数据同时丢失或者不可访问。同时利用数据版本策略对数据提供进一步的保护，用户可以保留、恢复不同的数据版本，读取中通过指定版本号可以读取较旧的数据进行恢复。此外，S3还提供了一种Reduced Redundancy Storage(RRS)的策略，RRS也会存储数据的多个副本，但副本个数会少于标准的S3服务，RRS主要用于一些敏感性不高、可再生的数据，提供的可用性为99.99%，话说这差距对一般个人使用估计也没啥吧，相对就便宜一点，支持单个设备上的数据丢失的情况。Amazon S3号称提供了一个高可靠、可扩展的安全策略用于数据的备份和隐私的归档，利用Amazon Import/Export进行大数据的导入导出，以使得从灾难中快速恢复。看了半天也就是S3说自己会对数据冗余复制在多个Facilites中，按照理解这个Facilities应该是不同的AZ。

Elastic Storage Block(EBS)

Amazon EBS是一个用于持久保存运行在instance上数据的存储块，可以创建类似未格式化的文件卷Volumn，并attach到位于同一Availability Zone的instance上，EBS本身的冗余复制到各个EBS Server都是位于同一个AZ内部的，因此并不能明显的提高可靠性。但EBS Volumn提供快照功能，可以创建数据的snapshot并存放在S3中，而S3的冗余备份会跨越多个AZ。

Elastic Load Balancing

按照AWS文档的描述，可以部署多个EC2 instance，将instances放置到Elastic Load Balancer后面，由Balancer自动的根据instance以及AZ的traffic info将请求转发到健康的instance来提高应用程序的Failure Tolerance。Elastic Load Balancer背后的多个EC2 instance既可以部署在同一个AZ中也可以跨越AZ部署，跨越AZ的instance会提供更好的可靠性。

Auto Scaling

Auto Scaling可以使得应用程序根据发展的需要动态的增加以及减少instance，因此也可以使用Auto Scaling来提高应用程序的可靠性，例如在Auto Scaling中设置条件，保证系统中健康的instance个数不会低于两个或者应用程序中任何一个EC2 instance的latency在一段时间内不能超过5秒。一旦这些条件被触发，系统就会自动的增加instance的个数从而提高服务的可用性。

从上面的一些Failure Tolerance的策略中可以看出，AWS一般提供跨Availability Zone的可靠性，数据会在AZ之间冗余，如果一个AZ中的服务不可用，会转移到另外一个AZ上继续提供服务，而N.Virginia的Region包含4个Availability Zone，这也是国外媒体质疑的地方，莫非Dashboard上写的connectivity影响到了整个Region。

AWS的EC2以及提供的EBS、Load balancing、Auto Scaling等特性确实很棒，特别适合start-up的公司，不需要投入大量资金和人力到硬件部署和升级上，报道硅谷最近的公司员工入职都是直接一台机器，上AWS编程，RoR应用很多，开发效率各种高，不过光看这次宕机影响的网站也就知道硅谷目前对于AWS的依赖程度了。不知道国内啥时候能开始接触和适应这种模式，阿里云到现在也没见到个影子啊。

之前看过一篇报道，当我们都在关注Google的技术、Apple的创造力、Facebook的影响速度时，是不是忽略了Amazon，甚至沃尔玛这样的公司对IT的影响力。

—————————————————————————————————————————–

Amazon在修复了事故之后给出了详细的报道，详情http://aws.amazon.com/message/65648/，看E文的就不用往下看了。

EBS由两个组件构成，EBS Clusters用来存储用户的数据，每一个Cluster运行在一个单独的AZ中，由多个Nodes 组成，每个Node有一个对应的备份node，当主节点感知备份node失效后，会向Cluster重新请求一个可用的Server做备份节点，进行re-mirroing过程，过程中数据访问被block；EBS Control panel则将用户请求发送到合适的EBS Cluster中，Control panel services分布在各个Region的各个AZ中。

同时EBS Cluster中的nodes通过两条网络链接。primary network具备较高的带宽，提供节点间的正常通信服务。而secondary network带宽较低，主要用于备份通信以及数据复制过程中额外的带宽，未被设计用于正常的网络服务。

N.Virginia的宕机是由于在升级过程中，网络切换错误导致产生的，本来应将primary network切换至另外一个router的primary network，结果切换到了一个secondary network上。由于secondary network低带宽无法承载系统的服务，造成了对应AZ的大量node无法连接到自己的back-up，认为back-up失效后请求cluster重新寻求备份，从而产生了re-mirroing strom。

re-mirroing storm耗尽对应的Cluster的可用空间，使得通过EBS Control panel的API进行volumn create的操作无法进行，而API的延迟设置相对较高，进而耗尽了EBS Control panel的thread pool，使得其他的API请求也无法进行，影响了其他AZ的服务。

前几天去吃葫芦头的路上，大飞哥给详细的讲解了他在比较文本相似度实验时对Google的simhash方法高效的惊叹，回来特意去找了原文去拜读。

Simhash

传统IR领域内文本相似度比较所采用的经典方法是文本相似度的向量夹角余弦，其主要思想是根据一个文章中出现词的词频构成一个向量，然后计算两篇文章对应向量的向量夹角。但由于有可能一个文章的特征向量词特别多导致整个向量维度很高，使得计算的代价太大，对于Google这种处理万亿级别的网页的搜索引擎而言是不可接受的，simhash算法的主要思想是降维，将高维的特征向量映射成一个f-bit的指纹(fingerprint)，通过比较两篇文章的f-bit指纹的Hamming Distance来确定文章是否重复或者高度近似。

simhash算法很精巧，但却十分容易理解和实现，具体的simhash过程如下：

1. 首先基于传统的IR方法，将文章转换为一组加权的特征值构成的向量。

2.初始化一个f维的向量V，其中每一个元素初始值为0。

3.对于文章的特征向量集中的每一个特征，做如下计算：

利用传统的hash算法映射到一个f-bit的签名。对于这个f- bit的签名，如果签名的第i位上为1，则对向量V中第i维加上这个特征的权值，否则对向量的第i维减去该特征的权值。

4.对整个特征向量集合迭代上述运算后，根据V中每一维向量的符号来确定生成的f-bit指纹的值，如果V的第i维为正数，则生成f-bit指纹的第i维为1，否则为0。

simhash和普通hash最大的不同在于传统的hash函数虽然也可以用于映射来比较文本的重复，但是对于可能差距只有一个字节的文档也会映射成两个完全不同的哈希结果，而simhash对相似的文本的哈希映射结果也相似。Google的论文中取了f=64，即将整个网页的加权特征集合映射到一个64-bit的fingerprint上。

比起simhash，整片文章中Google所采用的查找与给定f-bit的fingerprint的海明距离(Hamming Distance)小于k的算法相对还稍微难理解点。

fingerprint的Hamming Distance

问题：一个80亿的64-bit指纹组成的集合Q，对于一个给定64-bit的指纹F，如何在a few millionseconds中找到Q中和f至多只有k(k=3)位差别的指纹。

思想：1. 对于一个具有2^d个记录的集合，只需要考虑d-bit hash。2. 选取一个d’使得|d’-d|十分小，因此如果两fingerprint在d’-bits上都相同，那么在d-bits也很可能相同。然后在这些d-bit match的结果中寻找整个f-bit的Hamming Distance小于k的fingerprint。 简单的说，就是利用fingerprint少量特征位数比较从而首先缩小范围，然后再去确定是否差异小于k个bit。

算法：

1. 首先对于集合Q构建多个表T1，T2…Tt，每一个表都是采用对应的置换函数π(i)将64-bit的fingerprint中的某p(i)位序列置换换到整个序列的最前面。即每个表存储都是整个Q的fingerprint的复制置换。

2.对于给定的F，在每个Ti中进行匹配，寻找所有前pi位与F经过π(i)置换后的前pi位相同的fingerprint。

3.对于所有在上一步中匹配到的置换后的fingerprint，计算其是否与π(i)(F)至多有k-bit不同。

算法的重点在于对于集合Q的分表以及每个表所对应的置换函数，假设对于64-bit的fingerprint，k=3，存储16个table，划分参考下图:

将64-bit按照16位划分为4个区间，每个区间剩余的48-bit再按照每个12-bit划分为4个区间，因此总共16个table并行查找，即使三个不同的k-bit落在A、B、C、D中三个不同的区块，此划分方法也不会导致遗漏。

以上方法是对于online的query，即一个给定的F在集合中查找相似的fingerprint。如果爬虫每天爬取了100w个网页，快速的查找这些新抓取的网页是否在原集合中有Near-duplication，对于这种batch-query的情况，Map-Reduce就发挥它的威力了。

不同的是，在batch-query的处理中，是对待查集合B(1M个fingerprint)进行复制置换构建Table而非8B的目标集合，而在每一个chunkserver上对Fi(F为整个8B的fingerprint)在整个Table(B)中进行探测，每一个chunkserver上的的该Map过程输出该Fi中与整个B的near-duplicates，Reduces过程则将所有的结果收集、去重、然后输出为一个sorted file。

Haffman编码压缩

上述的查询过程，特别是针对online-version的算法，可以看出需要对8B的fingerprint进行多表复制和构建，其占据的容量是非常大的，不过由于构建的每一个置换Table都是sorted的，因此可以利用每一个fingerprint与其前一个的开始不同的bit-position h(h∈[0,f-1]) 来进行数据压缩，即如果前一个编码是11011011，而自身是11011001，则后一个可以编码为(6)1，即h=6，其中6表示从第6位(从0开始编号)开始和上一个fingerprint不相同(上一个为1，这个必然为0)，然后再保存不相同位置右侧的编码，依次生成整个table。

Google首先计算整个排序的fingerprint表中h的分布情况，即不同的h出现次数，依据此对[0,f-1]上出现的h建立Haffman code，再根据上述规则生成table（例如上面的6就表示成对应的Haffman code）。其中table分为多个block，每一个block中的第一个fingerprint保存原数据，后面的依次按照编码生成。

将每一个block中所对应的最后一个fingerprint保存在内存中，因此在比对的时候就可以直接根据内存中的fingerprint来确定是哪一个block需要被decompress进行比较。

8B个64-bit的fingerprint原占据空间大约为64GB，利用上述Haffman code压缩后几乎会减少一般，而内存中又只对每一个block保存了一个fingerprint。

每次看Google的论文都会让人眼前一亮，而且与很多(特别是国内)的论文是对未来进行设想不同，Google的东西都是已经运行了2，3年了再到WWW，OSDI这种顶级会议上灌个水。再次各种羡慕能去这个Dream Company工作的人，你们懂得。

参考:

Detecting Near-Duplicates for Web Crawling(Paper)

Detecting Near-Duplicates for Web Crawling(PPT)

当前NoSQL的分布式存储系统的资料(包括Paper以及各大Blog上的内容)，大部分都是关于分布式Key-Value存储下的读写操作、数据一致性、节点失效与修复等问题上，很少有系统的提及有关Load Balance的处理。不过既NoSQL指导型原则是CAP原理，而系统在实现时无论偏重AP还是CP，P都是必选的，因此对于分布式的各个节点的负载均衡也应该是要面对的问题，不过很遗憾，在BigTable, Dynamo以及Cassandra的Paper中对于Load Balance基本都没有提及，都只是很简单的进行了说明。特地花了几天去找了一些资料，总结记录于此。

1. Dynamo

Dynamo的论文上对于Load Balance的提及基本就是一个关键词”uniform hashing”，”A uniform key distribution can help us achieve uniform load distribution assuming the access distribution of keys is not highly skew“。即通过均匀的hash函数，保证将所有的key以及node都可以均匀的分布到同一哈希地址空间上，从而实现负载的均衡，此类常用的函数包括MD5 hash函数和SHA-1 hash函数。

除了利用哈希函数使得整个存储的item被均匀的分配到整个地址空间上，此外Dynamo的Virtual Node机制也对负载均衡进行一定的帮助，根据机器的性能指标不同划分不同的VNode即可。

此外，当新的VNode启动以及离开时，需要将某个VNode的数据迁移至邻居节点，而此种迁移有时会带来比较大的计算量(Merkle Tree等)，因此Dynamo又采用了一个将整个地址空间划分成段的策略(如下图所示)，然后每个VNode只能在一个段边界位置进行添加，即每一个VNode管理段长的整数倍的地址空间，此种方式对于节点的启动以及恢复，数据的归档等都有好处。

由于Dynamo虽然是NoSQL数据库的雏形以及类white paper，但由于工业界基于此模型构建实际针对业务数据库并是特别认可，因此资料也较少。

2.  Cassandra

Cassandra首先包含了两种Partitioner，这两种Partitioner对负载均衡的影响完全不同。

RandomPartitioner: RandomPartitioner采用均匀的hash函数，将负载均匀的划分到Key space空间上。RandomPartitioner gives you pretty good load balancing with no further work required。不过由于hash函数会将连续的Key映射到不同的环上地址，缺点就是无法进行range query.
OrderPreservingPartitioner:OrderPreservingPartitioner会使得连续的key映射到环上的地址空间后也是连续的，因此支持range query. OrderPreservingPartitioner let u perform range queries on the keys, but requires choosing node tokens carefully and active load balancing.

也就是说RandomPartitioner几乎是不需要进行Load Balancing的，但对于后者，就需要在Load Balancing上下一点功夫。

阅读全文…