All posts by dotte

Machine Learning &Deep Learning Resource

基础:

什么是机器学习?
机器学习该怎么入门?
机器学习的八个步骤
神经网络:卷积神经网络
数据挖掘学习图谱
图解机器学习
深度学习概述:从感知机到深度网络
A gentle guide to machine learning
Conv Nets: A Modular Perspective
周剑铭 柳渝:机器与“学习”——寻找人工智能的幽灵
一天搞懂深度學習
机器学习自学指南
一文读懂 CNN、DNN、RNN 内部网络结构区别
何为机器学习特征选择的经典三刀?
A Guide to Deep Learning by  YN2

数学及算法基础:
机器学习(一) 简单的背景介绍、线性回归、梯度下降
机器学习中的数学(1)-回归(regression)、梯度下降(gradient descent)
线性判别分析(LDA), 主成分分析(PCA)
麻省理工公开课:线性代数
李航老师的《统计学习方法》

框架:

 最好的Python机器学习库
SciKit-Learn
Caffe
Torchnet(Facebook)
TensorFlow(Google)
deeplearning4j

应用:

Neural Network for Recognition of Handwritten Digits
MNIST  OCR
ImageNet
TensorFlow在图像识别中的应用
探索推荐引擎内部的秘密,第 1 部分: 推荐引擎初探
机器学习问题的十个实例

平台 :

大数据竞赛平台——Kaggle 入门

课程:

Machine Learning
Neural Networks for Machine Learning

资源汇总:
机器学习入门资源不完全汇总
DeepLearning.net
josephmisiti/awesome-machine-learning · GitHub 机器学习资源大全
《机器学习实践》源码和《机器学习-算法原理与编程实践》源码以及学习心得
Learn Machine Learning With These Six Great 
博客文章索引
参考文献和Deep Learning学习资源
李航《浅谈我对机器学习的理解》 机器学习与自然语言处理
机器学习(Machine Learning)&深度学习(Deep Learning)资料
DeepLearning tutorial(3)MLP多层感知机原理简介+代码详解
DeepLearning tutorial(4)CNN卷积神经网络原理简介+代码详解
python sample code of DL
Scipy Lecture Notes
scikit-learn: machine learning in Python
Keras中文文档
机器学习资源大全中文版
机器学习的最佳入门学习资源
机器学习(Machine Learning)&深度学习(Deep Learning)资料

职位技能及需求:

大数据职位所需的数据场技能

 

Shell脚本编程总结及速查手册

Shell是一种编程语言, 它像其它编程语言如: C, Java, Python等一样也有变量/函数/运算符/if语句/循环控制/… 但在开始之前, 我想先理清Shell语言与Shell之间的关系.

Shell与Shell语言

上面说了Shell是一种编程语言但你可能也听说过: sh/bash/csh/zsh/…它们也叫Shell, 实际上这里所说的Shell是一种应用程序, 它负责解释执行你编写的Shell脚本, Mac默认就自带了sh/bash/csh/zsh/tcsh/ksh, 你可以这样查看cat /etc/shells
不同的shell的用法基本相同, 但有些shell提供了一些新特性, 比如我现在在用的就是zsh, 更多zsh的内容可以去看这篇文章。

第一个Shell脚本

#! /bin/sh
echo "hello shell!"

依国际惯例这里以在终端里打印一句hello shell!开始, 第一行的#!是一个约定标记, 它告诉脚本这段脚本需要什么解释器来执行. 第二行的echo命令则负责向屏幕上输出一句话.

如何运行

运行shell程序有3种方法:

  1. chmod +x使文件具有可执行权限, 直接运行
  2. 直接调用解释器, 将脚本文件作为参数传入 (比如bash hi.sh)
  3. 使用source(也可用 . 代替)执行文件

通常情况下, 最方便的方式就是方式1, 通过方式1执行你需要在脚本第一行写好这段脚本由哪个解释器来解释, 而通过方式2来执行则没有这个限制, 写了也没用.
除此之外方式1与方式2执行命令就没有区别了, 但方式3执行的方式与前两种都不同:

使用source执行shell脚本时, 不会创建子进程, 而是在父进程中直接执行!

这里不作更多解释, 感兴趣的同学可以去参考Linux Shell编程从入门到精通这本书的第一章的相关部分.

变量

和其它语言一样Shell中也有变量, 而且更简单, 但有一些比较特殊的地方.

  1. Shell中的变量只有字符串这一种类型
  2. Shell中变量名与变量值没有长度限制
  3. Shell的变量也允许比较操作和整数操作, 只要变量中的字符串为数字

定义变量

variable_name=ghui

需要注意: = 两边不能加空格, 当赋值语句包含空格时请加引号(单引号/双引号均可)比如:

variable_name="ghui's blog"

Shell中的变量可以分为两种类型:

  1. 局部变量 (定义变量时在前面加local修饰符)
  2. 全局变量 (定义变量时不加任何修饰符)

与其它语言一样局部变量的可见范围是代码块或函数内, 全局变量在全局范围内可见.看个简单的例子:

#! /bin/sh
num=111 #全局变量
 
func1()
{
  local num=222 #局部变量
  echo $num
}
 
echo "before---$num"
func1
echo "after---$num"

输出:

before---111
222
after---111

使用变量

使用一个定义过的变量, 只要在变量名前面加$即可, 如:

name=ghui
echo $name
echo ${name} #{} 为了帮助解释器识别变量边界, 非必须

在使用变量时还有一个地方需要注意, 请看下面的例子:

#! /bin/sh
str='abc'
echo "1 print $str"
echo '2 print $str'

输出:

1 print abc
2 print $str

即:
被双引号括起来的变量会发生变量替换, 单引号不会

注释

Shell中注释使用#, 而且它不支持多行注释.

常用的字符串操作

字符串拼接

name="shell"
sayHi="hello, "$name" !"
sayHi2="hello, ${name} !"
echo $sayHi $sayHi2

注意: 上面说的单双引号引起的变量替换问题

获得字符串长度

string="abcd"
echo ${#string} #输出:4

截取字符串

str="hello shell"
echo ${str:2}  #输出: llo shell
echo ${string:1:3} #输出:ell

更多关于字符串的操作可以看这个

if/else流程控制

基本语法结构:

if condition
then 
	 do something
elif condition
then 
	do something
elif condition
then 
	do something
else
	do something
fi

其中, elif语句和else语句非必须的.看个例子:

#! /bin/sh
a=1
if [ $1=$a ]
then
	echo "you input 1"
elif [ $1=2 ]
then
	echo "you input 2"
else
	#do nothing
	echo " you input $1"
fi

很简单, 不过这里有两个地方需要注意, 如果某个条件下的执行体为空, 则你就不能写这个条件 即下面这样会报错:

if condition
then 
	#do nothing
elif condition
then 
	# do nothing
#or
else
	#do nothing

另外, [ ] 两边一定要加空格, 下面这样都会报错:

if [$a=$b]
#or 
if [ $a=$b]
#or 
if [$a=$b ]

只有这样if [ $a=$b ]才是对的.
注意: 实际上这里的[]test命令的一种形式, [是系统的一个内置命令,存在路径是/bin/[,它是调用test命令的标识, 右中括号是关闭条件判断的标识, 因此下面的两个测试语句是等效的:

if test "2>3"
then
	...
fi

if [ "2>3" ]
then 
	...
fi

[]之外, shell语言中还有几种其它括号, 比如: 单小括号/双小括号/双中括号/… , 不同的括号有不同的用法, 更多关于shell中, 括号的用法可以看看这个

switch流程控制

当条件较多时, 可以选择使用switch语句, shell中的switch语句的写法和其它语言还是有些不同的, 基本结构如下:

case expression in
	pattern1)
		do something... ;;
	pattern2)
		do something... ;;
	pattern2)
		do something... ;;
	...
esac

看个例子:

#! /bin/sh
input=$1
case $input in
        1 | 0)
        str="一or零";;
        2)
        str="二";;
        3)
        str="三";;
        *)
        str=$input;;
esac
echo "---$str"

这个例子会根据你执行此脚本时传入的参数不同在屏幕上输出不同的值, 其中第一个case 1 | 0代表逻辑或.
NOTE:

  1. ;;相当于其它语言中的break
  2. 每个pattern之后记得加)
  3. 最后记得加esac (即反的case)

for循环

基本结构:

for name [in list]
do
	...
done

其中,[]括起来的 in list, 为可选部分, 如果省略in list则默认为in "$@", 即你执行此命令时传入的参数列表.
看个例子:

for file in *.txt
do
	open $file
done

遍历当前目录下的所有txt文件, 并依次打开.

while循环

基本结构:

while condition
do
	do something...
done

看个例子:

#! /bin/sh
i=0
while ((i<5));
do
	((i++))
	echo "i=$i"
done

输出:

i=1
i=2
i=3
i=4
i=5

NOTE: 你可能需要去了解一下(())的用法

until循环

基本结构

until condition
do
	do something...
done

看个例子:

#! /bin/sh
i=5
until ((i==0))
do
	((i--))
	echo "i=$i"
done

输出:

i=4
i=3
i=2
i=1
i=0

跳出循环

shell中也支持break跳出循环, continue跳出本次循环.用法与C, Java中相同

函数

要定义一个函数, 可以使用下面两种形式:

function funcname()
{
	do something
}

或者

funcname ()
{
	do something
}

看个例子

#! /bin/sh
# ad.sh 计算sum
add()
{
	let "sum=$1+$2"
	return $sum
}
 
add $1 $2
echo "sum=$?"

输入

ad 1 2

输出

sum=3

其中, $?在shell中保存的是上一条命令的返回值

NOTE:

  1. 函数必须先定义后使用
  2. 如果在函数中使用exit会退出脚本, 如果想退回到原本函数调用的地方, 则可使用return

向脚本传递参数

先shell脚本传递参数, 非常简单, 只需要在你执行命令的后面跟上即可, 看个例子:

#! /bin/sh
# test.sh
echo "$# parameters";
echo "$@";
echo "$0"
echo "$1"

输入:

test.sh 11 22

输出:

2 parameters
11 22
test.sh
11

后记

之所以要写这篇博客, 有以下几个原因:

  1. 想总结一下shell编程中的关键知识点, 方便日后查看.
  2. 想通过shell优化一下我的hexo写作及博客管理流程, 目前相关脚本已完成, 待我下一篇博客分享给大家, 如果你也是在用Hexo写博客, 相信对你会很有用, 尽请期待! 已经发布
  3. 可以看的出这里总结的都是最关键的知识点, 还有很多这里并没有说. 是因为我觉得刚开始学习一个东西没必要太计较一些细节/琐碎的东西, 掌握好大致知识框架, 然后在大家编写具体的脚本时, 遇到具体问题, 再去google寻找即可.

参考

  1. Shell脚本编程30分钟入门
  2. Linux Shell编程从入门到精通

from:http://ghui.me/post/2016/06/shell-handbook/

 

Web系统大规模并发——电商秒杀与抢购

电商的秒杀和抢购,对我们来说,都不是一个陌生的东西。然而,从技术的角度来说,这对于Web系统是一个巨大的考验。当一个Web系统,在一秒钟内收到数以万计甚至更多请求时,系统的优化和稳定至关重要。这次我们会关注秒杀和抢购的技术实现和优化,同时,从技术层面揭开,为什么我们总是不容易抢到火车票的原因?

一、大规模并发带来的挑战

在过去的工作中,我曾经面对过5w每秒的高并发秒杀功能,在这个过程中,整个Web系统遇到了很多的问题和挑战。如果Web系统不做针对性的优化,会轻而易举地陷入到异常状态。我们现在一起来讨论下,优化的思路和方法哈。

1. 请求接口的合理设计

一个秒杀或者抢购页面,通常分为2个部分,一个是静态的HTML等内容,另一个就是参与秒杀的Web后台请求接口。

通常静态HTML等内容,是通过CDN的部署,一般压力不大,核心瓶颈实际上在后台请求接口上。这个后端接口,必须能够支持高并发请求,同时,非常重要的一点,必须尽可能“快”,在最短的时间里返回用户的请求结果。为了实现尽可能快这一点,接口的后端存储使用内存级别的操作会更好一点。仍然直接面向MySQL之类的存储是不合适的,如果有这种复杂业务的需求,都建议采用异步写入。

当然,也有一些秒杀和抢购采用“滞后反馈”,就是说秒杀当下不知道结果,一段时间后才可以从页面中看到用户是否秒杀成功。但是,这种属于“偷懒”行为,同时给用户的体验也不好,容易被用户认为是“暗箱操作”。

2. 高并发的挑战:一定要“快”

我们通常衡量一个Web系统的吞吐率的指标是QPS(Query Per Second,每秒处理请求数),解决每秒数万次的高并发场景,这个指标非常关键。举个例子,我们假设处理一个业务请求平均响应时间为100ms,同时,系统内有20台Apache的Web服务器,配置MaxClients为500个(表示Apache的最大连接数目)。

那么,我们的Web系统的理论峰值QPS为(理想化的计算方式):

20*500/0.1 = 100000 (10万QPS)

咦?我们的系统似乎很强大,1秒钟可以处理完10万的请求,5w/s的秒杀似乎是“纸老虎”哈。实际情况,当然没有这么理想。在高并发的实际场景下,机器都处于高负载的状态,在这个时候平均响应时间会被大大增加。

就Web服务器而言,Apache打开了越多的连接进程,CPU需要处理的上下文切换也越多,额外增加了CPU的消耗,然后就直接导致平均响应时间增加。因此上述的MaxClient数目,要根据CPU、内存等硬件因素综合考虑,绝对不是越多越好。可以通过Apache自带的abench来测试一下,取一个合适的值。然后,我们选择内存操作级别的存储的Redis,在高并发的状态下,存储的响应时间至关重要。网络带宽虽然也是一个因素,不过,这种请求数据包一般比较小,一般很少成为请求的瓶颈。负载均衡成为系统瓶颈的情况比较少,在这里不做讨论哈。

那么问题来了,假设我们的系统,在5w/s的高并发状态下,平均响应时间从100ms变为250ms(实际情况,甚至更多):

20*500/0.25 = 40000 (4万QPS)

于是,我们的系统剩下了4w的QPS,面对5w每秒的请求,中间相差了1w。

然后,这才是真正的恶梦开始。举个例子,高速路口,1秒钟来5部车,每秒通过5部车,高速路口运作正常。突然,这个路口1秒钟只能通过4部车,车流量仍然依旧,结果必定出现大塞车。(5条车道忽然变成4条车道的感觉)

同理,某一个秒内,20*500个可用连接进程都在满负荷工作中,却仍然有1万个新来请求,没有连接进程可用,系统陷入到异常状态也是预期之内。

其实在正常的非高并发的业务场景中,也有类似的情况出现,某个业务请求接口出现问题,响应时间极慢,将整个Web请求响应时间拉得很长,逐渐将Web服务器的可用连接数占满,其他正常的业务请求,无连接进程可用。

更可怕的问题是,是用户的行为特点,系统越是不可用,用户的点击越频繁,恶性循环最终导致“雪崩”(其中一台Web机器挂了,导致流量分散到其他正常工作的机器上,再导致正常的机器也挂,然后恶性循环),将整个Web系统拖垮。

3. 重启与过载保护

如果系统发生“雪崩”,贸然重启服务,是无法解决问题的。最常见的现象是,启动起来后,立刻挂掉。这个时候,最好在入口层将流量拒绝,然后再将重启。如果是redis/memcache这种服务也挂了,重启的时候需要注意“预热”,并且很可能需要比较长的时间。

秒杀和抢购的场景,流量往往是超乎我们系统的准备和想象的。这个时候,过载保护是必要的。如果检测到系统满负载状态,拒绝请求也是一种保护措施。在前端设置过滤是最简单的方式,但是,这种做法是被用户“千夫所指”的行为。更合适一点的是,将过载保护设置在CGI入口层,快速将客户的直接请求返回。

二、进攻与防守

秒杀和抢购收到了“海量”的请求,实际上里面的水分是很大的。不少用户,为了“抢“到商品,会使用“刷票工具”等类型的辅助工具,帮助他们发送尽可能多的请求到服务器。还有一部分高级用户,制作强大的自动请求脚本。这种做法的理由也很简单,就是在参与秒杀和抢购的请求中,自己的请求数目占比越多,成功的概率越高。

这些都是属于“违规的手段”,不过,有“进攻”就有“防守”,这是一场没有硝烟的战斗哈。

1. 同一个账号,一次性发出多个请求

部分用户通过浏览器的插件或者其他工具,在秒杀开始的时间里,以自己的账号,一次发送上百甚至更多的请求。实际上,这样的用户破坏了秒杀和抢购的公平性。

这种请求在某些没有做数据安全处理的系统里,也可能造成另外一种破坏,导致某些判断条件被绕过。例如一个简单的领取逻辑,先判断用户是否有参与记录,如果没有则领取成功,最后写入到参与记录中。这是个非常简单的逻辑,但是,在高并发的场景下,存在深深的漏洞。多个并发请求通过负载均衡服务器,分配到内网的多台Web服务器,它们首先向存储发送查询请求,然后,在某个请求成功写入参与记录的时间差内,其他的请求获查询到的结果都是“没有参与记录”。这里,就存在逻辑判断被绕过的风险。

 

应对方案:

在程序入口处,一个账号只允许接受1个请求,其他请求过滤。不仅解决了同一个账号,发送N个请求的问题,还保证了后续的逻辑流程的安全。实现方案,可以通过Redis这种内存缓存服务,写入一个标志位(只允许1个请求写成功,结合watch的乐观锁的特性),成功写入的则可以继续参加。

或者,自己实现一个服务,将同一个账号的请求放入一个队列中,处理完一个,再处理下一个。

2. 多个账号,一次性发送多个请求

很多公司的账号注册功能,在发展早期几乎是没有限制的,很容易就可以注册很多个账号。因此,也导致了出现了一些特殊的工作室,通过编写自动注册脚本,积累了一大批“僵尸账号”,数量庞大,几万甚至几十万的账号不等,专门做各种刷的行为(这就是微博中的“僵尸粉“的来源)。举个例子,例如微博中有转发抽奖的活动,如果我们使用几万个“僵尸号”去混进去转发,这样就可以大大提升我们中奖的概率。

这种账号,使用在秒杀和抢购里,也是同一个道理。例如,iPhone官网的抢购,火车票黄牛党。

应对方案:

这种场景,可以通过检测指定机器IP请求频率就可以解决,如果发现某个IP请求频率很高,可以给它弹出一个验证码或者直接禁止它的请求:

 

  1. 弹出验证码,最核心的追求,就是分辨出真实用户。因此,大家可能经常发现,网站弹出的验证码,有些是“鬼神乱舞”的样子,有时让我们根本无法看清。他们这样做的原因,其实也是为了让验证码的图片不被轻易识别,因为强大的“自动脚本”可以通过图片识别里面的字符,然后让脚本自动填写验证码。实际上,有一些非常创新的验证码,效果会比较好,例如给你一个简单问题让你回答,或者让你完成某些简单操作(例如百度贴吧的验证码)。
  2. 直接禁止IP,实际上是有些粗暴的,因为有些真实用户的网络场景恰好是同一出口IP的,可能会有“误伤“。但是这一个做法简单高效,根据实际场景使用可以获得很好的效果。

 

3. 多个账号,不同IP发送不同请求

所谓道高一尺,魔高一丈。有进攻,就会有防守,永不休止。这些“工作室”,发现你对单机IP请求频率有控制之后,他们也针对这种场景,想出了他们的“新进攻方案”,就是不断改变IP。

有同学会好奇,这些随机IP服务怎么来的。有一些是某些机构自己占据一批独立IP,然后做成一个随机代理IP的服务,有偿提供给这些“工作室”使用。还有一些更为黑暗一点的,就是通过木马黑掉普通用户的电脑,这个木马也不破坏用户电脑的正常运作,只做一件事情,就是转发IP包,普通用户的电脑被变成了IP代理出口。通过这种做法,黑客就拿到了大量的独立IP,然后搭建为随机IP服务,就是为了挣钱。

应对方案:

说实话,这种场景下的请求,和真实用户的行为,已经基本相同了,想做分辨很困难。再做进一步的限制很容易“误伤“真实用户,这个时候,通常只能通过设置业务门槛高来限制这种请求了,或者通过账号行为的”数据挖掘“来提前清理掉它们。

僵尸账号也还是有一些共同特征的,例如账号很可能属于同一个号码段甚至是连号的,活跃度不高,等级低,资料不全等等。根据这些特点,适当设置参与门槛,例如限制参与秒杀的账号等级。通过这些业务手段,也是可以过滤掉一些僵尸号。

4. 火车票的抢购

看到这里,同学们是否明白你为什么抢不到火车票?如果你只是老老实实地去抢票,真的很难。通过多账号的方式,火车票的黄牛将很多车票的名额占据,部分强大的黄牛,在处理验证码方面,更是“技高一筹“。

高级的黄牛刷票时,在识别验证码的时候使用真实的人,中间搭建一个展示验证码图片的中转软件服务,真人浏览图片并填写下真实验证码,返回给中转软件。对于这种方式,验证码的保护限制作用被废除了,目前也没有很好的解决方案。

因为火车票是根据身份证实名制的,这里还有一个火车票的转让操作方式。大致的操作方式,是先用买家的身份证开启一个抢票工具,持续发送请求,黄牛账号选择退票,然后黄牛买家成功通过自己的身份证购票成功。当一列车厢没有票了的时候,是没有很多人盯着看的,况且黄牛们的抢票工具也很强大,即使让我们看见有退票,我们也不一定能抢得过他们哈。

最终,黄牛顺利将火车票转移到买家的身份证下。

解决方案:

并没有很好的解决方案,唯一可以动心思的也许是对账号数据进行“数据挖掘”,这些黄牛账号也是有一些共同特征的,例如经常抢票和退票,节假日异常活跃等等。将它们分析出来,再做进一步处理和甄别。

三、高并发下的数据安全

我们知道在多线程写入同一个文件的时候,会存现“线程安全”的问题(多个线程同时运行同一段代码,如果每次运行结果和单线程运行的结果是一样的,结果和预期相同,就是线程安全的)。如果是MySQL数据库,可以使用它自带的锁机制很好的解决问题,但是,在大规模并发的场景中,是不推荐使用MySQL的。秒杀和抢购的场景中,还有另外一个问题,就是“超发”,如果在这方面控制不慎,会产生发送过多的情况。我们也曾经听说过,某些电商搞抢购活动,买家成功拍下后,商家却不承认订单有效,拒绝发货。这里的问题,也许并不一定是商家奸诈,而是系统技术层面存在超发风险导致的。

1. 超发的原因

假设某个抢购场景中,我们一共只有100个商品,在最后一刻,我们已经消耗了99个商品,仅剩最后一个。这个时候,系统发来多个并发请求,这批请求读取到的商品余量都是99个,然后都通过了这一个余量判断,最终导致超发。(同文章前面说的场景)

在上面的这个图中,就导致了并发用户B也“抢购成功”,多让一个人获得了商品。这种场景,在高并发的情况下非常容易出现。

2. 悲观锁思路

解决线程安全的思路很多,可以从“悲观锁”的方向开始讨论。

悲观锁,也就是在修改数据的时候,采用锁定状态,排斥外部请求的修改。遇到加锁的状态,就必须等待。

虽然上述的方案的确解决了线程安全的问题,但是,别忘记,我们的场景是“高并发”。也就是说,会很多这样的修改请求,每个请求都需要等待“锁”,某些线程可能永远都没有机会抢到这个“锁”,这种请求就会死在那里。同时,这种请求会很多,瞬间增大系统的平均响应时间,结果是可用连接数被耗尽,系统陷入异常。

3. FIFO队列思路

那好,那么我们稍微修改一下上面的场景,我们直接将请求放入队列中的,采用FIFO(First Input First Output,先进先出),这样的话,我们就不会导致某些请求永远获取不到锁。看到这里,是不是有点强行将多线程变成单线程的感觉哈。

然后,我们现在解决了锁的问题,全部请求采用“先进先出”的队列方式来处理。那么新的问题来了,高并发的场景下,因为请求很多,很可能一瞬间将队列内存“撑爆”,然后系统又陷入到了异常状态。或者设计一个极大的内存队列,也是一种方案,但是,系统处理完一个队列内请求的速度根本无法和疯狂涌入队列中的数目相比。也就是说,队列内的请求会越积累越多,最终Web系统平均响应时候还是会大幅下降,系统还是陷入异常。

4. 乐观锁思路

这个时候,我们就可以讨论一下“乐观锁”的思路了。乐观锁,是相对于“悲观锁”采用更为宽松的加锁机制,大都是采用带版本号(Version)更新。实现就是,这个数据所有请求都有资格去修改,但会获得一个该数据的版本号,只有版本号符合的才能更新成功,其他的返回抢购失败。这样的话,我们就不需要考虑队列的问题,不过,它会增大CPU的计算开销。但是,综合来说,这是一个比较好的解决方案。

有很多软件和服务都“乐观锁”功能的支持,例如Redis中的watch就是其中之一。通过这个实现,我们保证了数据的安全。

四、小结

互联网正在高速发展,使用互联网服务的用户越多,高并发的场景也变得越来越多。电商秒杀和抢购,是两个比较典型的互联网高并发场景。虽然我们解决问题的具体技术方案可能千差万别,但是遇到的挑战却是相似的,因此解决问题的思路也异曲同工。

from:http://www.csdn.net/article/2014-11-28/2822858

海量数据处理:经典实例分析

有关海量数据处理的问题,主要有以下3类:top K问题、重复问题、排序问题

top K 问题

在大规模数据处理中,经常会遇到的一类问题:在海量数据中找出出现频率最高的前K个数,或者从海量数据中找出最大的前K个数,这类问题通常被称为top K问题。例如,在搜索引擎中,统计搜索最热门的10个查询词;在歌曲库中统计下载率最高的前10首歌等。

针对top k 类问题,通常比较好的方案是分治+Trie树+小顶堆,即现将数据集按照hash方法分解成多个小数据集,然后使用Trie树或者Hash统计每个小数据集中的query词频,之后用小顶堆求出每个数据集中出现频率最高的前K个数,最后在所有top K中求出最终的top K。

例子:有1亿个浮点数,找出其中最大的10000个?

解决方案

将数据全部排序

最容易想到的方法是将数据全部排序,然后在排序后的集合中进行查找,最快的排序算法的时间复杂度一般为O(nlogn),如快速排序。而在32位机器上,每个float类型占4个字节,1亿个浮点数就要占用400MB的存储空间,对于一些可用内存小于400MB的计算机而言,很显然是不能一次将全部数据读入内存进行排序的。其实即使内存能够满足要求,该方法也并不高效,因为题目要求是寻找出最大的10000个数即可,而排序却是将所有的元素都排序了。

局部淘汰法

该方法与排序方法类似,用一个容器保存前10000个数,然后将剩余的所有数字一一与容器内的最小数字相比,如果所有后续的元素都比容器内的1000个数还小,那么容器内的这10000个数就是最大的10000个数。如果某一后续元素比容器内的最小数字大,则删掉容器内最小元素,并将该元素插入容器,最后遍历完这1亿个数,得到的结果容器中保存的数即为最终结果了。此时的时间复杂度为O(n+m^2),其中m为容器的大小,即10000.

分治法

将1亿个数据分成100份,每份100万个数据,找出每份数据中最大的10000个,最后在剩下的100*10000个数据里面找出最大的10000个。如果100万数据选择足够理想,那么可以过滤掉1亿数据里面99%的数据。100万个数据里面查找最大的10000个数据的方法如下:
用快速排序的方法,将数据分为2堆,如果大的那堆个数N大于10000个,继续对大堆快速排序一次分成2堆,如果大堆个数N小于10000,就在校的那堆里面快速排序一次,找第10000-n大的数字;递归以上过程,就可以找到第1w大的数。参考上面的找出的第1w大数字,就可以类似的方法找出前10000大数字了。此种方法每次需要的内存空间为10^6*4=4MB,一共需要101此这样的比较

Hash法

如果这1亿个数里面有很多重复的数,先通过Hash法,把着1亿个数字去重复,这样如果重复率很高的话,会减少很大的内存用量,从而缩小运算空间,然后通过分治法或最小堆法查找最大的10000个数。

最小堆

首先读入前10000个数来创建大小为10000的小顶堆,建堆的时间复杂度为O(mlogm)(m为数组的大小即为10000),然后遍历后续的数字,并与堆顶(最小)数字进行比较。如果比最小的数小,则继续读取后续数字;如果比堆顶数字大,则替换对顶元素并重新调整堆为小顶堆。整个过程直至1亿个数全都遍历完为止。然后按照中序遍历的方式输出当前堆中的所有10000个数字。该算法的时间复杂度为O(nmlogm),空间复杂度是10000(常数)。

实际上,最优的解决方案应该是最腹黑实际设计需求的方案,在实际应用中,可能有足够大的内存,那么直接将数据扔到内存中一次性处理即可,也可能机器有多个核,这样可以采用多线程处理整个数据集。

不同应用场景的解决方案

单机+单核+足够大内存

如果需要查找10亿个查询词(每个占8B)中出现频率最高的10个,考虑到每个查询词占8B,则10亿个查询词所需的内存大约是10^9*8B = 8GB 内存。如果有这么大的内存,直接在内存中对查询词进行排序,顺序遍历找出10个出现频率最大的即可。这种方法简单快速,更加实用。当然,也可以先用HashMap求出每个词出现的频率,然后求出频率最大的10个词。

单机+多核+足够大内存

这时可以直接在内存中使用Hash方法将数据划分成n个partition,每个partition交给一个线程处理,线程的处理逻辑是同(1)类似,最后一个线程将结果归并。
该方法存在一个瓶颈会明显影响效率,即数据倾斜。每个线程的处理速度可能不同,快的线程需要等待慢的线程,最终的处理速度取决于慢的线程。而针对此问题,解决方法是,将数据划分成c*n个partition(c>1),每个线程处理完当前partition后主动取下一个partition继续处理,直到所有数据处理完毕,最后由一个线程进行归并

单机+单核+受限内存

这种情况下,需要将原数据文件切割成一个一个小文件,如采用hash(x)%M,将源文件中的数据切割成M小文件,如果小文件仍大于内存大小,继续采用Hash的方法对数据文件进行切割,直到每个小文件小于内存大小,这样每个文件可放到内存中处理。采用(1)的方法依次处理每个小文件。

多机+受限内存

这种情况下,为了合理利用多台机器的资源,可将数据分发到多台机器上,每台机器采用(3)节中的策略解决本地的数据。可采用hash+socket方法进行数据分发。

小结

从实际应用考虑,上述的不同场景的解决方案并不可行,因为在大规模数据处理环境下,作业效率并不是首要考虑的问题,算法的扩展性和容错性才是首要考虑的。算法应该具有良好的扩展性,以便数据量进一步加大(随着业务的发展,数据量加大是必然的)时,在不修改算法框架的前提下,可达到近似的线性比;算法应该具有容错性,即当前某个文件处理失败后,能自动将其交给另外一个线程继续处理,而不是从头开始处理。

TOP K问题很适合采用MapReduce框架解决,用户只需编写一个Map函数和两个Reduce函数,然后提交到Hadoop(采用Mapchain和Reducechain)上即可解决该问题。具体而言,就是首先根据数据值或者把数据hash(MD5)后的值按照范围划分到不同的机器上,最好可以让数据划分后依次读入内存,这样不同的机器赋值处理不同的数值范围,实际上就是Map。得到结果后,各个机器只需拿出各自出现次数最多的前N个数据,然后汇总,选出所有的数据中出现次数最多的前N个数据,这实际上就是Reduce的过程。对于Map函数,采用Hash算法,将Hash值相同的数据交给同一个Reduce task;对于第一个Reduce函数,采用HashMap统计出每个词出现的频率,对于第二个Reduce函数,统计所有Reduce task,输出数据中的top K 即可。

直接将数据均分到不同的机器上进行处理时无法得到正确的结果的。因为一个数据可能被均分到不同的机器上,而另一个则可能完全聚集到一个机器上,同时还可能存在具有相同数目的数据。

Top K问题还有很多应用场景,尤其是在程序媛面试笔试中有很多实例,它们都可以采用上述方法解决。以下是一些历年来经常被各大互联网公司提及的该类问题。
(1)有1亿个记录,这些查询串的重复度比较高,如果除去重复后,不超过3百万个。一个查询串的重复度过高,说明查询它的用户越多,也就是越热门。请统计最热门的10个查询串,要求使用的内存不能超过1GB
(2)有10个文件,每个文件1GB,每个文件的每一行存放的都是用户的query,每个文件的query都可能重复。按照query的频度排序。
(3)有一个1GB大小的文件,里面的每一行是一个词,词的大小不超过16个字节,内存限制大小是1MB。返回频数最高的100个词
(4)提取某日访问网站次数最多的那个IP
(5)10亿个整数找出重复次数最多的100个整数
(6)搜索的输入信息是一个字符串,统计300万条输入信息中最热门的前10条,每次输入的一个字符串为不超过255B,内存使用只有1GB
(7)有1000万个身份证号以及它们对应的数据,身份证号可能重复,找出出现次数最多的身份证号。

重复问题

海量数据中查找出重复出现的元素或者去除重复出现的元素
针对此类问题,一般可以通过位图法实现。

例如,已知某个文件内包含一些电话号码,每个号码为8位数字,统计不同号码的个数。

本题最好的解决方法是通过使用位图法来实现。8位整数可以表示的最大十进制数值为99999999.如果每个数字对应于位图中一个bit位,那么存储8位整数大约需要99MB。因为1B=8bit,所以99Mbit折合成内存为 99/8 = 12.375MB的内存表示所有的8位数电话号码的内容。

#include<iostream>
#include<stdlib.h>
#include<time.h>

using namespace std;

#define BITWORD 32
#define ARRNUM 100
int mmin = 10000000;
int mmax = 99999999;

int N = (mmax-mmin+1);
#define BITS_PER_WORD 32
#define WORD_OFFSET(b) ( (b)/BITS_PER_WORD )
#define BIT_OFFSET(b) ((b)%BITS_PER_WORD )

void SetBit( int *words, int n )
{
    n -= mmin;
    words[WORD_OFFSET(n)] |= ( 1<< BIT_OFFSET(n));
}

void ClearBit( int *words, int n )
{
    words[WORD_OFFSET(n)] &= ~( 1<< BIT_OFFSET(n));
}
int GetBit( int *words, int n )
{
    int bit = words[WORD_OFFSET(n)] & ( 1<< BIT_OFFSET(n));
    return bit != 0 ;
}


int main()
{
    int arr[ ARRNUM ];
    int *words = new int[ 1+N/BITS_PER_WORD ];
    if( words == NULL )
    {
        cout << " new error \n " << endl;
        exit(0);
    }

    int count = 0;
    for(int i=0; i<N; i++ )
        ClearBit( words,i);
    srand( (unsigned)time(NULL));
    cout << " the size of the array : " << ARRNUM << endl;

    for(int j=0; j<ARRNUM; j++ )
    {
        arr[j] = rand() % N;
        arr[j] += mmin;
        cout << arr[j] << "\t";
    }

    for(int j=0; j<ARRNUM; j++ )
        SetBit( words, arr[j]);

    cout << "after sort, a : " << endl;
    for( int i=0; i<N; i++ )
        if( GetBit( words,i) )
        {
            cout << i+mmin << "\t";
            count++;
        }
    cout << " sum is : " << count << endl;
    delete[] words;
    words = NULL;

    return 0;
}

上例中,采用时间作为种子,产生了100个随机数,对这100个数进行位图法排序,进而找出其中重复的数据。与此问题相似的面试笔试题还有:
(1)10亿个正整数,只有1个数重复出现过,要求在O(n)的时间里找出这个数
(2)给定a、b两个文件,各存放50亿个url,每个url各占用64B,要求在O(n)的时间里找出a、b文件共同的url
(3)给40亿个不重复的unsigned int的整数,没拍过序的,然后再给一个数,如何快速判断这个数是否在那40亿个数中?

排序问题

海量数据处理中一类常见的问题就是排序问题,即对海量数据中的数据进行排序。例如,一个文件中有9亿条不重复的9位整数,对这个文件中的数字进行排序。

针对这个问题,最容易想到的方法是将所有数据导入到内存中,然后使用常规的排序方法,如插入排序、快速排序、归并排序等各种排序方法对数据进行排序,最后将排序好的数据存入文件。但这些方法却不能在此适用,由于数据量巨大,在32位机器中,一个整数占用4个字节,而9亿条数据共占用9*10^8*4B,大约需要占用3.6GB内存,对于32位机器而言,很难将这么多数据一次载入到内存,所以,需要考虑其他方法。

数据库排序法

将文本文件导入到数据库中,让数据库进行索引排序操作后提取数据到文件。该种方法虽然操作简单、方便,但是运算速度较慢,而且对数据库设备要求比较高。

分治法

通过hash将9亿条数据分为20段,每段大约5000万条,大约占用5*10^6*4B=200MB空间,在文件中依次搜索0~5000万,50000001~1亿。。。将排序的结果存入文件。该方法要装满9位整数,一共需要20此,所以一共要进行20次排序,需要对文件进行20次读操作。该方法虽然缩小了每次使用的内存空间大小,但是编码复杂,速度也慢。

位图法

考虑到最大的9位整数为 999999999,由于9亿条数据是不重复的,可以把这些数据组成一个队列或数组,让它有0~999999999(一共10亿个数)个元素数组下标表示数值,结点中用0表示没有这个数,1表示存在这个数,判断0或1只用一个bit存储就够了,而声明一个可以包含9位整数的bit数组,一共需要10亿/8,大约120MB内存,把内存中的数据全部初始化为0,读取文件中的数据,并将数据放入内存。比如读到一个数据为341245909,那就先在内存中找到341245909这个bit,并将bit值置为1,遍历整个bit数组,将bit为1的数组下标存入文件,最终得到排序后的内容。

此类排序问题的求解方法一般都是采用上述方法。海量数据处理中与此类似的问题还有以下几种:
(1)一年的全国高考考生人数为500万,分数使用标准分,最低100分,最高900分,不存在成绩为小数的情况,把这500万考生的分数排序
(2)一个包含n个正整数的文件,每个正整数小于n,n等于1000万,并且文件内的正整数没有重复和关联数据u,输出整数的升序排列。

from:http://blog.csdn.net/omenglishuixiang1234/article/details/51724734