0%

Redis 引出的问题

学习蒋德钧老师的《Redis核心技术与实战》,这系列文章会根据老师的内容进行精简提炼整理并添加自我的思考等等,与原文有重叠的部分,如侵权请于主页联系本人必删除

为了保证数据的可靠性,Redis 需要在磁盘上读写 AOF 和 RDB,但在高并发场景里,这就会直接带来两个新问题:

  • 一个是写 AOF 和 RDB 会造成 Redis 性能抖动。(AOF,将Redis的操作日志以追加的方式写入文件。 RDB,将Redis在内存中的数据库记录定时dump到磁盘上的RDB持久化。)
  • 另一个是 Redis 集群数据同步和实例恢复时,读 RDB 比较慢,限制了同步和恢复速度。

使用 Redis不同公司的“玩法”却不太一样,比如说,有做缓存 的,有做数据库 的,也有用做分布式锁的。不过,他们遇见的“坑”,总体来说集中在四个方面:

  • CPU 使用上的“坑”,例如数据结构的复杂度、跨 CPU 核的访问;

  • 内存使用上的“坑”,例如主从同步和 AOF 的内存竞争;

  • 存储持久化上的“坑”,例如在 SSD 上做快照的性能抖动;

  • 网络通信上的“坑”,例如多实例时的异常网络丢包。

Redis 知识全景图

Redis知识全景图

两大维度,三大主线

“两大维度”就是指系统维度和应用维度,“三大主线”也就是指高性能、高可靠和高可扩展(可以简称为“三高”)。

Redis 的问题画像图

Redis的问题画像图

PAAS、IAAS和SAAS之间的区别

云计算的发展这几年大家也看到了,非常火热。各种新概念层出不穷,如果你不是专业人士,这些新概念让你一脸茫然是很正常的。

所以最近比较多的小伙伴向我咨询一个问题,那就是PAAS、IAAS和SAAS之间的区别?正好今天小编比较闲,就在这为大家解释一下。当然首先请允许小编从专业的角度来解释一下PAAS、IAAS和SAAS之间的概念区别。

用户通过Internet 可以从完善的计算机基础设施获得服务。这类服务可以称为基础设施即服务,这就是通常所说的IAAS。而相应的另外两种服务就是平台即服务和软件即服务。平台及服务提供了用户可以访问的完整或部分的应用程序开发,我们通常称之为PAAS。软件及服务则提供了完整的可直接使用的应用程序,我们通常称之为SAAS。如果把他们看作层次结构,那么第一层自然叫做IAAS,第二层就是PAAS,第三层也就是SAAS。好了专业的就说到这里,想必很多小伙伴还是一知半解。那么下面开始说人话。

假设、如果、假如你是个吃货,而且还非常喜欢披萨这种食品,那么这个问题就很好解释了。一个吃货是怎样吃到披萨的呢?大致有下面的几种方法:

1. 完全自己做

不好意思,如果自己做这实在是个麻烦事,你得准备很多东西,比如餐桌、披萨面团。。。。。等等,如下图所示:

2. 买好速食披萨回家自己做着吃

你只需要从披萨店里买回成品,回家烘焙就好了,在自己的餐桌上吃。和自己在家做不同,你需要一个披萨供应商。如下图所示:

3. 打电话叫外卖将披萨送到家中

打个电话,披萨就送到家门口。如下图所示:

4.在披萨店吃披萨

你什么都不需要准备,连餐桌也是披萨店的。如下图所示:

总结一下

是不是如下图所示几种途径都可以吃到披萨:

现在我们从披萨中回到云计算的概念来。假设你是一家超级牛逼的技术公司,根本不需要别人提供服务,你拥有基础设施、应用等等其它一切,你把它们分为三层:基础设施(infrastructure)、平台(platform)和软件(software),如下图:

这其实就是云计算的三个分层,基础设施在最下端,平台在中间,软件在顶端,分别是Infrastructure-as-a-Service(IAAS),Platform-as-a-Service(PAAS),Software-as-a-Service(SAAS),别的一些“软”的层可以在这些层上面添加。

而你的公司什么都有,现在所处的状态叫本地部署(On-Premises),就像在自己家做披萨一样。如果你想在办公室或者公司的网站上运行一些企业应用,你需要去买服务器,或者别的高昂的硬件来控制本地应用,让你的业务运行起来,这就叫本地部署。

假如你突然有一天想明白了,只是为了吃上披萨,为什么非要自己做呢?于是,准备考虑一家云服务供应商,这个云服务供应商能提供哪些服务呢?其所能提供的云服务也就是云计算的三个分层:PAAS、IAAS和SAAS,就像披萨店提供三种服务:买成品回家做、外卖和到披萨店吃。如下图:

IAAS: Infrastructure-as-a-Service(基础设施即服务),有了IAAS,你可以将硬件外包到别的地方去。IAAS公司会提供场外服务器,存储和网络硬件,你可以租用。节省了维护成本和办公场地,公司可以在任何时候利用这些硬件来运行其应用。一些大的IAAS公司包括Amazon, Microsoft, VMWare, Rackspace和Red Hat.不过这些公司又都有自己的专长,比如Amazon和微软给你提供的不只是IAAS,他们还会将其计算能力出租给你来host你的网站。

PAAS: Platform-as-a-Service(平台即服务),第二层就是所谓的PAAS,某些时候也叫做中间件。你公司所有的开发都可以在这一层进行,节省了时间和资源。

PAAS公司在网上提供各种开发和分发应用的解决方案,比如虚拟服务器和操作系统。这节省了你在硬件上的费用,也让分散的工作室之间的合作变得更加容易。网页应用管理,应用设计,应用虚拟主机,存储,安全以及应用开发协作工具等。

一些大的PAAS提供者有Google App Engine,Microsoft Azure,Force.com,Heroku,Engine Yard。最近兴起的公司有AppFog,Mendix和Standing Cloud.

SAAS: Software-as-a-Service(软件即服务),第三层也就是所谓SAAS。这一层是和你的生活每天接触的一层,大多是通过网页浏览器来接入。任何一个远程服务器上的应用都可以通过网络来运行,就是SAAS了。你消费的服务完全是从网页如Netflix,MOG,Google Apps,Box.net,Dropbox或者苹果的iCloud那里进入这些分类。尽管这些网页服务是用作商务和娱乐或者两者都有,但这也算是云技术的一部分。一些用作商务的SaaS应用包括Citrix的Go To Meeting,Cisco的WebEx,Salesforce的CRM,ADP,Workday和SuccessFactors。

参考文档

IaaS,PaaS,SaaS 的区别 - 阮一峰的网络日志

冒泡排序

一、冒泡排序

原理:对一组数据,比较相邻数据的大小,将值小数据在前面,值大的数据放在后面。 (以下都是升序排列,即从小到大排列)

举例说明: $arr = array(6, 3, 8, 2, 9, 1);

$arr 有6个数据,按照两两比较大小如下,注意 比较轮数 和 每轮比较次数

第一轮排序:

第一次比较 6和3比较 结果:3 6 8 2 9 1

第二次比较 6和3比较 结果:3 6 8 2 9 1

第三次比较 8和2比较 结果:3 6 2 8 9 1

第四次比较 8和9比较 结果:3 6 2 8 9 1

第五次比较 9和1比较 结果:3 6 2 8 1 9

第一轮比较总结:

1.排序第1轮、比较5次,没有获得从小到大的排序

2.因为每次比较都是大数往后靠,所以比较完成后,可以确定大数排在最后(9 已经冒泡冒出来了,下轮比较可以不用比较了 )

第二轮排序:

第一次比较 3和6比较 结果:3 6 2 8 1 9

第二次比较 6和2比较 结果:3 2 6 8 1 9

第三次比较 6和8比较 结果:3 2 6 8 1 9

第四次比较 8和1比较 结果:3 2 6 1 8 9

第一轮比较总结:

1.排序第2轮、比较4次,没有获得从小到大的排序

2.冒泡出了 8,下轮不用比较8 了

第三轮排序:

第一次比较 3和2比较 结果:2 3 6 1 8 9

第二次比较 3和6比较 结果:2 3 6 1 8 9

第三次比较 6和1比较 结果:2 3 1 6 8 9

第三轮比较总结:

1.排序第3轮、比较3次,没有获得从小到大的排序

2.冒泡出了 6,下轮不用比较6 了 

第四轮排序:

第一次比较 2和3比较 结果:2 3 1 6 8 9

第二次比较 3和1比较 结果:2 1 3 6 8 9

第四轮比较总结:

1.排序第4轮、比较2次,没有获得从小到大的排序

2.冒泡出了 3,下轮不用比较3 了

第五轮排序:

第一次比较 2和1比较 结果:1 2 3 6 8 9

第五轮比较总结:

1.排序第5轮、比较1次,没有获得从小到大的排序

2.冒泡出了 2,由于还剩一个1,不用再比较了,至此通过5轮排序,完成整个排序。

结论

通过以上五轮排序,若干次比较,我们有理由推断出一个结论:

对于一个长度为N的数组,我们需要排序 N-1 轮,每 i 轮 要比较 N-i 次。对此我们可以用双重循环语句,外层循环控制循环轮次,内层循环控制每轮的比较次数。

Golang实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func sort_bubble(arr []int) {

len := len(arr)
for i:=1;i<len;i++{
for j:=0;j<len-i;j++{
if arr[j] > arr[j+1]{
arr[j],arr[j+1] = arr[j+1],arr[j]

}
fmt.Println(arr)
}
}
fmt.Println()
fmt.Println(arr)
}

func main() {
arr := [...]int{6,3,8,2,9,1}
slice := arr[:]
fmt.Println(slice)
fmt.Println()
sort_bubble2(slice)
}

PHP实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function bubble($arr)
{
$count = count($arr);

for ($i = 1; $i <$count;$i++){
for ($j =0; $j<$count-$i;$j++){
if($arr[$j] > $arr[$j+1]){
$tmp = 0;
$tmp = $arr[$j];
$arr[$j] = $arr[$j+1];
$arr[$j+1] = $tmp;

}
}
}
print_r($arr);
}

$arr = array(6, 3, 8, 2, 9, 1);
bubble($arr);

直接插入排序

思路分析:在要排序的一组数中,假设前面的数已经是排好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数也是排好顺序的。如此反复循环,直到全部排好顺序。

第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从后向前扫描,把第三个数按大小插入到有序表中;依次进行下去,进行了(n-1)趟扫描以后就完成了整个排序过程。

直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较,所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较,直到找到比待比较数值小的并将待比较数值置入其后一位置,结束该次循环。

插入排序的基本方法是:每步将一个待排序的记录按其关键字的大小插到前面已经排序的序列中的适当位置,直到全部记录插入完毕为止。

PHP实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//直接插入排序
function InsertSort(array &$arr){
$count = count($arr);
//数组中第一个元素作为一个已经存在的有序表
for($i = 1;$i < $count;$i ++){
$temp = $arr[$i]; //设置哨兵/临时值
//$arr[$i];//需要插入的元素; $arr[$j];//需要比较的元素
for($j = $i - 1;$j >= 0 && $arr[$j] > $temp;$j --){
//发现插入的元素要小,交换位置
//将后边的元素与前面的元素互换
$arr[$j + 1] = $arr[$j];
//将前面的数设置为 当前需要交换的数
$arr[$j] = $temp;
}
}
}

GOLANG实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//直接插入排序
func sort_insert(arr []int){
for i:=1;i<len(arr);i++{
tmp := arr[i]
for j:=i-1;j>=0 && arr[j] > tmp; j--{
arr[j],arr[j+1] = tmp,arr[j];
}
}
}

func main() {
arr := [...]int{6,3,8,2,9,1}
slice := arr[:]
fmt.Println(slice)
fmt.Println()
sort_insert(slice)
fmt.Println(slice)
}

选择排序

原理: 在一列数字中,选出最小数与第一个位置的数交换。然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止。(以下都是升序排列,即从小到大排列)

举例说明: $arr = array(6, 3, 8, 2, 9, 1);

第一轮:

第一次比较, 第一个数 6 与(3, 8, 2, 9, 1)中 3 比较,6大,当前最小数为3,位置为 1

第二次比较, 最小数字 3 与(3, 8, 2, 9, 1)中 8 比较,3小,当前最小数为3,位置为 1

第三次比较, 最小数字 3 与(3, 8, 2, 9, 1)中 2 比较,3大,当前最小数为2,位置为 3

第四次比较, 最小数字 2 与(3, 8, 2, 9, 1)中 9 比较,2小,当前最小数为2,位置为 3

第五次比较, 最小数字 2 与(3, 8, 2, 9, 1)中 1 比较,2大,当前最小数为1,位置为 5

第一轮比较完成后,确定最小数为1,小于第一个数6,交换位置上的数,交换后结果为 1 3 8 2 9 6

总结:第一轮比较,可以确定第一个位置的最小值。

第二轮:

第一次比较, 3与(8, 2, 9, 6)中 8 比较,3小,当前最小数为3,位置为 1

第二次比较, 3与(8, 2, 9, 6)中 2 比较,3大,当前最小数为2,位置为 3

第三次比较, 2与(8, 2, 9, 6)中 9 比较,2小,当前最小数为2,位置为 3

第四次比较, 2与(8, 2, 9, 6)中 6 比较,2小,当前最小数为2,位置为 3

第二轮比较完成后,确定最小数为2,小于第二个数3,交换位置上的数,交换后结果为 1 2 8 3 9 6

总结:第二轮比较,可以确定第二个位置的最小值。至此确定了前两个位置上的数。

第三轮:

第一次比较, 8与( 3, 9, 6)中 3 比较,8大,当前最小数为3,位置为3

第二次比较, 3与( 3, 9, 6)中 9 比较,3小,当前最小数为3,位置为3

第三次比较, 6与( 3, 9, 6)中 6 比较,3小,当前最小数为3,位置为3

第三轮比较完成后,确定最小数为3,小于第三个数8,交换位置上的数,交换后结果为 1 2 3 8 9 6

总结:第三轮比较,可以确定第三个位置的最小值。至此确定了前三个位置上的数。

第四轮

第一次比较, 8与( 9, 6)中 9 比较,8小,当前最小数为8,位置为 3

第二次比较, 8与( 9, 6)中 6 比较,8大,当前最小数为6,位置为 5

第四轮比较完成后,确定最小数为6,小于第四个数8交换位置上的数,交换后结果为 1 2 3 6 9 8

总结:第四轮比较,可以确定第四个个位置的最小值。至此确定了前四个位置上的数。

第五轮:

第一次比较, 9与 8 比较,9大,当前最小数为8,位置为5

第五轮比较完成后,确定最小数为8,小于第五个数9,交换位置上的数,交换后结果为 1 2 3 6 8 9

总结:第五轮比较,可以确定第五个个位置的最小值。至此确定了前5个位置上的数。

##总结

###综合以上五轮比较,每一轮比较都可以确定一个位置,对于N个数,比较N-1轮可以确定N个位置上的数,因为确定了N-1个位置,最后一个位置也就确定了。每i轮需要排序的次数为 N-i

PHP实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function selection_sort($arr)
{
for ($i=0;$i<count($arr)-1;$i++){ // N个数,需要进行N-1轮次, 每轮次需要进行 (N-第几轮次) 次比较

$minIndex = $i;

for ($j=$i+1;$j<count($arr);$j++){ //j代表未排列好的第二个值开始到结尾
if($arr[$j] <$arr[$minIndex] ){
$minIndex = $j;
}
}
if($i != $minIndex){
$temp = $arr[$i];
$arr[$i] = $arr[$minIndex];
$arr[$minIndex] = $temp;
unset($temp);
}

}
return $arr;

}

echo "<pre>";
$arr = array(6, 3, 8, 2, 9, 1);
$result = selection_sort($arr);
print_r($result);

GOLANG实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func sort_selection(arr []int) []int{

for i:=0;i<len(arr);i++{
minIndex := i
for j:=i+1;j<len(arr) ;j++ {
if arr[minIndex] > arr[j]{
minIndex = j
}
}
if(i != minIndex){
arr[i],arr[minIndex] = arr[minIndex],arr[i]
}
}
return arr
}

func main() {
arr := [...]int{6,3,8,2,9,1}
slice := arr[:]
fmt.Println(slice)
fmt.Println()
fmt.Println(sort_selection(slice))
}

快速排序

基本思想:

快速排序(Quicksort)是对冒泡排序的一种改进。他的基本思想是:通过一趟排序将待排记录分割成独立的两部分,其中一部分的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行快速排序,整个排序过程可以递归进行,以达到整个序列有序的目的。

基本算法步骤:

举个栗子:
假如现在待排序记录是:

1
6   2   7   3   8   9

第一步、创建变量 $low 指向记录中的第一个记录,$high 指向最后一个记录,$pivot 作为枢轴赋值为待排序记录的第一个元素(不一定是第一个),这里:

1
2
3
$low = 0;
$high = 5;
$pivot = 6;

第二步、我们要把所有比 $pivot 小的数移动到 $pivot 的左面,所以我们可以开始寻找比6小的数,从 $high 开始,从右往左找,不断递减变量 $high 的值,我们找到第一个下标 3 的数据比 6 小,于是把数据 3 移到下标 0 的位置($low 指向的位置),把下标 0 的数据 6 移到下标 3,完成第一次比较:

1
2
3
4
//这时候,$high 减小为 3
$low = 0;
$high = 3;
$pivot = 6;

第三步、我们开始第二次比较,这次要变成找比 $pivot 大的了,而且要从前往后找了。递加变量 $low,发现下标 2 的数据是第一个比 $pivot 大的,于是用下标 2 ($low 指向的位置)的数据 7 和 指向的下标 3 ($high 指向的位置)的数据的 6 做交换,数据状态变成下表:

1
2
3
4
5
6
3   2   6   7   8   9

//这时候,$high 减小为 3
$low = 2;
$high = 3;
$pivot = 6;

完成第二步和第三步我们称为完成一个循环。

第四步(也就是开启下一个循环)、模仿第二步的过程执行。
第五步、模仿第三步的过程执行。

执行完第二个循环之后,数据状态如下:

1
2
3
4
5
6
3   2   6   7   8   9

//这时候,$high 减小为 3
$low = 2;
$high = 2;
$pivot = 6;

到了这一步,我们发现 $low 和 $high“碰头”了:他们都指向了下标 2。于是,第一遍比较结束。得到结果如下,凡是 $pivot(=6) 左边的数都比它小,凡是 $pivot 右边的数都比它大。

然后,对 、$pivot 两边的数据 {3,2} 和 {7,8,9},再分组分别进行上述的过程,直到不能再分组为止。

注意:第一遍快速排序不会直接得到最终结果,只会把比k大和比k小的数分到k的两边。为了得到最后结果,需要再次对下标2两边的数组分别执行此步骤,然后再分解数组,直到数组不能再分解为止(只有一个数据),才能得到正确结果。

Partition()函数才是整段代码的核心,因为该函数的功能是:
选取当中的一个关键字,比如选择第一个关键字。然后想尽办法将它放到某个位置,
使得它左边的值都比它小,右边的值都比它大,我们将这样的关键字成为枢轴(pivot)。

算法实现:

PHP实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//交换函数
function swap(array &$arr,$a,$b){
$tmp = $arr[$a];
$arr[$a] = $arr[$b];
$arr[$b] = $tmp;
}

//选取数组当中的一个关键字,使得它处于数组某个位置时,左边的值比它小,右边的值比它大,该关键字叫做枢轴
//使枢轴记录到位,并返回其所在位置
function Partition(&$arr,$low,$hight){
$pivot_value = $arr[$low]; //选取子数组第一个元素作为枢轴
while ($low < $hight) //从数组的两端交替向中间扫描(当 $low 和 $high 碰头时结束循环)
{
while ($low < $hight && $arr[$hight] > $pivot_value) //如果改为$arr[$hight] >= $pivot_value,则最坏情况不但会堕落为O(n*n).而且除了每次比较的消耗外,还会产生n次交互的额外开销
{
$hight--;
}
swap($arr,$low,$hight); //终于遇到一个比$pivot小的数,将其放到数组低端
while ($low < $hight && $pivot_value > $arr[$low]) //如果改为$pivot_value >= $arr[$low],则最坏情况不但会堕落为O(n*n).而且除了每次比较的消耗外,还会产生n次交互的额外开销
{
$low++;
}
swap($arr,$low,$hight); //终于遇到一个比$pivot大的数,将其放到数组高端
}

return $low; //返回high也行,毕竟最后low和high都是停留在pivot下标处
}

function Qsort(array &$arr, $low, $hight){
//当 $low >= $hight 时表示不能再进行分组,已经能够得出正确结果了
if($low >= $hight){
return ;
}
$pivot_index = Partition($arr,$low,$hight); //将$arr[$low...$high]一分为二,算出枢轴值
Qsort($arr,$low,$pivot_index-1); //对低子表($pivot左边的记录)进行递归排序
Qsort($arr,$pivot_index+1,$hight); //对高子表($pivot右边的记录)进行递归排序

}
//主函数
function QuickSort(array &$arr){
$low = 0;
$hight = count($arr) -1;
Qsort($arr,$low,$hight); //主函数中,由于第一遍快速排序是对整个数组排序的,因此开始是 $low=0,$high=count($arr)-1。
}

//调用
echo "<pre>";
$arr = [6,2,7,3,8,9];
QuickSort($arr);
print_r($arr);

GOLANG实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//选取数组当中的一个关键字,使得它处于数组某个位置时,左边的值比它小,右边的值比它大,该关键字叫做枢轴
//使枢轴记录到位,并返回其所在位置
func Partition(arr []int,low int , hight int) int{
piovt_value := arr[low]
for low<hight {
for low < hight && arr[hight] > piovt_value{
hight--
}
arr[low],arr[hight] = arr[hight],arr[low]
for low < hight && arr[low] < piovt_value{
low++
}
arr[low],arr[hight] = arr[hight],arr[low]
}

return low
}

func Qsort(arr []int , low int ,hight int) {
if low >= hight {
return
}
piovt_index := Partition(arr,low,hight) //将$arr[$low...$high]一分为二,算出枢轴值
Qsort(arr,low,piovt_index-1) //对低子表($pivot左边的记录)进行递归排序
Qsort(arr,piovt_index+1,hight) //对高子表($pivot右边的记录)进行递归排序
}
func QuickSort(arr []int){
low :=0
hight := len(arr)-1
Qsort(arr,low,hight);
}

func main() {
arr := [...]int{6,3,8,2,9,1}
slice := arr[:]
fmt.Println(slice)
fmt.Println()
QuickSort(slice)
fmt.Println(slice)

}

PHP快速排序,代码简单但性能较低的一种实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

function quick_sort($arr) {
//先判断是否需要继续进行
$length = count($arr);
if($length <= 1) {
return $arr;
}
//如果没有返回,说明数组内的元素个数 多余1个,需要排序
//选择一个标尺
//选择第一个元素
$base_num = $arr[0];
//遍历 除了标尺外的所有元素,按照大小关系放入两个数组内
//初始化两个数组
$left_array = array();//小于标尺的
$right_array = array();//大于标尺的
for($i=1; $i<$length; $i++) {
if($base_num > $arr[$i]) {
//放入左边数组
$left_array[] = $arr[$i];
} else {
//放入右边
$right_array[] = $arr[$i];
}
}
//再分别对 左边 和 右边的数组进行相同的排序处理方式
//递归调用这个函数,并记录结果
$left_array = quick_sort($left_array);
$right_array = quick_sort($right_array);
//合并左边 标尺 右边
return array_merge($left_array, array($base_num), $right_array);

参考文档

PHP实现排序算法—-快速排序(Quick Sort)、快排 - CSDN博客

快速排序的php实现 - 根号五 - 博客园

大话数据结构

Mac find 去除 “Permission denied” 信息

Mac 下查找文件,最简单的方法应该是

1
mdfind filename

等同于

1
mdfind -name filename

不过,mdfind 貌似无法查找隐藏文件,比如,你要查找.zshrc,那么,用mdfind .zshrc 将一无所获。

此时,我们还是需要用回 find 命令。但如果我们用

1
find / -name .zshrc

我们将发行满屏的permission denied,如

1
2
3
4
5
... ...
find: /private/var/spool/postfix/hold: Permission denied
find: /private/var/spool/postfix/incoming: Permission denied
find: /private/var/spool/postfix/maildrop: Permission denied
... ...

这不是我们想看到的结果,如何阻止这些 permission denied 信息呢。

主要有以下三种方法:

  • 用管理员权限执行 find
1
sudo find / -name "keyword" -print
  • 丢弃所有错误输出
1
find / -name "keyword" -print 2>/dev/null
  • 过滤 permission denied 信息
1
find / -name "keyword" -print 2>&1 | fgrep -v "Permission denied"

iptables常用模块介绍

connlimit

connlimit模块允许你限制每个客户端ip的并发连接数,即每个ip同时连接到一个服务器个数。

connlimit模块主要可以限制内网用户的网络使用,对服务器而言则可以限制每个ip发起的连接数。

1
2
--connlimit-above n 限制为多少个
--connlimit-mask n 这组主机的掩码,默认是connlimit-mask 32 ,即每ip.

#限制除了172.16.130.40此ip外,其他ip通过TCP访问444端口并发数为30

1
2
3
iptables -I INPUT -p tcp --dport 444 -m connlimit --connlimit-above 30 -j REJECT

iptables -I INPUT -s 172.16.130.40 -p tcp --dport 444 -j ACCEPT

#允许每个客户机同时两个telnet连接

1
2
3
iptables -A INPUT -p tcp --syn --dport 23 -m connlimit --connlimit-above 2 -j REJECT

iptables -A INPUT -p tcp --syn --dport 23 -m connlimit ! --connlimit-above 2 -j ACCEPT

#只允许每组C类ip同时16个http连接

1
iptables -p tcp --syn --dport 80 -m connlimit --connlimit-above 16 --connlimit-mask 24 -j REJECT

#只允许每个ip同时5个80端口转发,超过的丢弃:

1
iptables -I FORWARD -p tcp --syn --dport 80 -m connlimit --connlimit-above 5 -j DROP

#只允许每组C类ip同时10个80端口转发:

1
iptables -I FORWARD -p tcp --syn --dport 80 -m connlimit --connlimit-above 10 --connlimit-mask 24 -j DROP

#为了防止DOS太多连接进来,那么可以允许最多15个初始连接,超过的丢弃.

1
2
3
iptables -A INPUT -s 192.186.1.0/24 -p tcp --syn -m connlimit --connlimit-above 15 -j DROP

iptables -A INPUT -s 192.186.1.0/24 -p tcp -m state --state ESTABLISHED,RELATED -j ACCEP

本文地址: http://www.cszhi.com/20120510/iptables-modules-connlimit.html

NGINX防止CC攻击

1.geo指令定义了一个白名单

2.使用map指令映射搜索引擎客户端的ip为空串,如果不是搜索引擎就显示本身真实的ip,这样搜索引擎ip就不能存到limit_req_zone内存session中,所以不会限制搜索引擎的ip访问

3.ngx_http_limit_req_module模块

1
2
3
4
5
6
7
8
limit_req_zone $binary_remote_addr zone=perip:10m rate=1r/s;
limit_req_zone $server_name zone=perserver:10m rate=10r/s;

server {
...
limit_req zone=perip burst=5 nodelay;
limit_req zone=perserver burst=10;
}

nginx.conf文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
http{
#定义白名单 limited
geo $limited{
default 1;
172.16.130.40/32 0;
}
#自定义$limit
map $limited $limit {
1 $binary_remote_addr;
0 "";
}
map $limited $limit_server_name {
1 $server_name;
0 "";
}
limit_req_zone $limit zone=perip:10m rate=1r/s;
limit_req_zone $limit_server_name zone=perserver:10m rate=1r/s;
include ssl.conf;
}

ssl.conf文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
server {
server_name 127.0.0.1;
listen 444;
listen [::]:444;
ssl on;
ssl_certificate /Data/apps/nginx/conf/33iq.crt;
ssl_certificate_key /Data/apps/nginx/conf/33iq_nopass.key;
ssl_protocols TLSv1 TLSv1.1 TLSv1.2;
ssl_ciphers ECDHE-RSA-AES256-SHA384:AES256-SHA256:!RC4:HIGH:!MD5:!aNULL:!eNULL:!NULL:!DH:!EDH:!AESGCM;
ssl_prefer_server_ciphers on;
ssl_session_cache shared:SSL:10m;
ssl_session_timeout 10m;
client_max_body_size 512M;
root /Data/apps/wwwroot/firewall/apps/admin;
index index.html index.htm index.php;
location / {
limit_req zone=perip burst=5 nodelay;
limit_req zone=perserver burst=10;
index index.htm index.html index.php;
if (!-e $request_filename){
rewrite ^(.*)$ /index.php last;
}
}
location ~ \.php(.*)$ {
fastcgi_pass 127.0.0.1:9000;
fastcgi_index index.php;
fastcgi_param SCRIPT_FILENAME $document_root$fastcgi_script_name;
fastcgi_param PATH_INFO $fastcgi_path_info;
include fastcgi_params;
}
}

https://blog.csdn.net/u012566181/article/details/49968283

http://nginx.org/en/docs/http/ngx_http_limit_req_module.html

http://nginx.org/en/docs/http/ngx_http_limit_conn_module.html

PHP的垃圾回收机制

前言

平时听到大神提到的GC ,就是垃圾回收器,全称Garbage Collection.
在介绍这个新的GC之前,读者必须先了解PHP中变量的内部存储相关知识,请先阅读变量的内部存储:引用和计数

变量的结构与类型

PHP在内核中是通过zval这个结构体来存储变量的,所以写扩展的时候当然也是一样。
在Zend/zend.h文件中找到了其定义:

1
2
3
4
5
6
struct _zval_struct {
zvalue_value value; /* 变量的值 */
zend_uint refcount__gc;
zend_uchar type; /* 变量当前的数据类型 */
zend_uchar is_ref__gc;
};

快速理解:为方便起见可以直接把zval结构体理解成一个由

1
2
3
4
5
value
type
refcount__gc
is_ref__gc

组成的对象就好了,*__gc是管理内存相关的时候会用到的,这里可以先不管。

什么算垃圾

首先我们需要定义一下“垃圾”的概念,新的GC负责清理的垃圾是指变量的容器zval还存在,但是又没有任何变量名指向此zval。因此GC判断是否为垃圾的一个重要标准是有没有变量名指向变量容器zval。

假设我们有一段PHP代码,使用了一个临时变量$tmp存储了一个字符串,在处理完字符串之后,就不需要这个$tmp变量了,$tmp变量对于我们来说可以算是一个“垃圾”了,但是对于GC来说,$tmp其实并不是一个垃圾,$tmp变量对我们没有意义,但是这个变量实际还存在,$tmp符号依然指向它所对应的zval,GC会认为PHP代码中可能还会使用到此变量,所以不会将其定义为垃圾。

那么如果我们在PHP代码中使用完$tmp后,调用unset删除这个变量,那么$tmp是不是就成为一个垃圾了呢。很可惜,GC仍然不认为$tmp是一个垃圾,因为$tmp在unset之后,refcount减少1变成了0(这里假设没有别的变量和$tmp指向相同的zval),这个时候GC会直接将$tmp对应的zval的内存空间释放,$tmp和其对应的zval就根本不存在了。此时的$tmp也不是新的GC所要对付的那种“垃圾”。那么新的GC究竟要对付什么样的垃圾呢,下面我们将生产一个这样的垃圾。

顽固垃圾的产生过程

如果读者已经阅读了变量内部存储相关的内容,想必对refcount和isref这些变量内部的信息有了一定的了解。这里我们将结合手册中的一个例子来介绍垃圾的产生过程:

1
2
3
4
5
<?php

$a = "new string";

?>

在这么简单的一个代码中,$a变量内部存储信息为a: (refcount=1, is_ref=0)=’new string’
当把$a赋值给另外一个变量的时候,$a对应的zval的refcount会加1

1
2
3
4
5
6
7
<?php

$a = "new string";

$b = $a;

?>

此时$a和$b变量对应的内部存储信息为

a,b: (refcount=2, is_ref=0)=’new string’

当我们用unset删除$b变量的时候,$b对应的zval的refcount会减少1

1
2
3
4
5
6
7
8
9
10

<?php

$a = "new string"; //a: (refcount=1, is_ref=0)='new string'

$b = $a; //a,b: (refcount=2, is_ref=0)='new string'

unset($b); //a: (refcount=1, is_ref=0)='new string'

?>

对于普通的变量来说,这一切似乎很正常,但是在复合类型变量(数组和对象)中,会发生比较有意思的事情:

1
2
3
4
5
<?php

$a = array('meaning' => 'life', 'number' => 42);

?>

a的内部存储信息为:

1
2
3
4
a: (refcount=1, is_ref=0)=array (
'meaning' => (refcount=1, is_ref=0)='life',
'number' => (refcount=1, is_ref=0)=42
)

数组变量本身($a)在引擎内部实际上是一个哈希表,这张表中有两个zval项 meaning和number,
所以实际上那一行代码中一共生成了3个zval,这3个zval都遵循变量的引用和计数原则,用图来表示:

下面在$a中添加一个元素,并将现有的一个元素的值赋给新的元素:

1
2
3
4
5
6
7
<?php

$a = array('meaning' => 'life', 'number' => 42);

$a['life'] = $a['meaning'];

?>

那么$a的内部存储为:

1
2
3
4
5
a: (refcount=1, is_ref=0)=array (
'meaning' => (refcount=2, is_ref=0)='life',
'number' => (refcount=1, is_ref=0)=42,
'life' => (refcount=2, is_ref=0)='life'
)

其中的meaning元素和life元素之指向同一个zval的:

现在,如果我们试一下,将数组的引用赋值给数组中的一个元素,有意思的事情就发生了:

1
2
3
4
5
6
7
<?php

$a = array('one');

$a[] = &$a;

?>

这样$a数组就有两个元素,一个索引为0,值为字符one,另外一个索引为1,为$a自身的引用,内部存储如下:

1
2
3
4
a: (refcount=2, is_ref=1)=array (
0 => (refcount=1, is_ref=0)='one',
1 => (refcount=2, is_ref=1)=…
)

“…”表示1指向a自身,是一个环形引用:

这个时候我们对$a进行unset,那么$a会从符号表中删除,同时$a指向的zval的refcount减少1

1
2
3
4
5
6
7
8
9
<?php

$a = array('one');

$a[] = &$a;

unset($a);

?>

那么问题也就产生了,$a已经不在符号表中了,用户无法再访问此变量,但是$a之前指向的zval的refcount变为1而不是0,因此不能被回收,这样产生了内存泄露:

这样,这么一个zval就成为了一个真是意义的垃圾了,新的GC要做的工作就是清理这种垃圾。

为解决这种垃圾,PHP5.3以后的GC

在PHP5.3版本中,使用了专门GC机制清理垃圾,在之前的版本中是没有专门的GC,那么垃圾产生的时候,没有办法清理,内存就白白浪费掉了。在PHP5.3源代码中多了以下文件:{PHPSRC}/Zend/zend_gc.h {PHPSRC}/Zend/zend_gc.c, 这里就是新的GC的实现。

GC算法

在较新的PHP手册中有简单的介绍新的GC使用的垃圾清理算法,这个算法名为 Concurrent Cycle Collection in Reference Counted Systems , 这里不详细介绍此算法,根据手册中的内容来先简单的介绍一下思路:

判断处理过程

  • 1:如果一个zval的refcount增加,那么此zval还在使用,不属于垃圾

  • 2:如果一个zval的refcount减少到0, 那么zval可以被释放掉,不属于垃圾

  • 3:如果一个zval的refcount减少之后大于0,那么此zval还不能被释放,此zval可能成为一个垃圾

只有在准则3下,GC才会把zval收集起来,然后通过新的算法来判断此zval是否为垃圾。那么如何判断这么一个变量是否为真正的垃圾呢?

简单的说,就是对此zval中的每个元素进行一次refcount减1操作,操作完成之后,如果zval的refcount=0,那么这个zval就是一个垃圾。首先引用手册中的一张图:

A:为了避免每次变量的refcount减少的时候都调用GC的算法进行垃圾判断,此算法会先把所有前面准则3情况下的zval节点放入一个节点(root)缓冲区(root buffer),并且将这些zval节点标记成紫色,同时算法必须确保每一个zval节点在缓冲区中之出现一次。当缓冲区被节点塞满的时候,GC才开始开始对缓冲区中的zval节点进行垃圾判断。

B:当缓冲区满了之后,算法以深度优先对每一个节点所包含的zval进行减1操作,为了确保不会对同一个zval的refcount重复执行减1操作,一旦zval的refcount减1之后会将zval标记成灰色。需要强调的是,这个步骤中,起初节点zval本身不做减1操作,但是如果节点zval中包含的zval又指向了节点zval(环形引用),那么这个时候需要对节点zval进行减1操作。

C:算法再次以深度优先判断每一个节点包含的zval的值,如果zval的refcount等于0,那么将其标记成白色(代表垃圾),如果zval的refcount大于0,那么将对此zval以及其包含的zval进行refcount加1操作,这个是对非垃圾的还原操作,同时将这些zval的颜色变成黑色(zval的默认颜色属性)

D:遍历zval节点,将C中标记成白色的节点zval释放掉。

来个白话文版的:
例如:

1
2
3
4
5
<?php
$a = ['one']; --- zval_a(将$a对应的zval,命名为zval_a)
$a[] = &$a; --- step1
unset($a); --- step2

为进行unset之前(step1),进行算法计算,对这个数组中的所有元素(索引0和索引1)的zval的refcount进行减1操作,由于索引1对应的就是zval_a,所以这个时候zval_a的refcount应该变成了1,这样说明zval_a不是一个垃圾不进行回收。

当执行unset的时候(step2),进行算法计算,由于环形引用,上文得出会有垃圾的结构体,zval_a的refcount是1(zval_a中的索引1指向zval_a),用算法对数组中的所有元素(索引0和索引1)的zval的refcount进行减1操作,这样zval_a的refcount就会变成0,于是就认为zval_a是一个需要回收的垃圾。

算法总的套路:对于一个包含环形引用的数组,对数组中包含的每个元素的zval进行减1操作,之后如果发现数组自身的zval的refcount变成了0,那么可以判断这个数组是一个垃圾。

算法优化配置

可能会发现,每次都进行这样的操作好像会影响性能,是的,php做事情套路都是走批量的原则。

申请内存也是申请一大块,仅使用当前的一小部分剩下的等下回再用,避免多次申请。

这个gc算法也是这样,会有一个缓冲区的概念,等缓冲区满了才会一次性去给清掉。

  • 开关配置
1
2

php.ini中设置 zend.enable_gc 项来开启或则关闭GC。
  • 缓冲区配置
    缓冲区默认可以放10,000个节点,当缓冲区满了才会清理。可以通过修改Zend/zend_gc.c中的GC_ROOT_BUFFER_MAX_ENTRIES 来改变这个数值,需要重新编译链接PHP

  • 关键函数

gc_enable() : 开启GC

gc_disable() : 关闭GC

gc_collect_cycles() : 在节点缓冲区未满的情况下强制执行垃圾分析算法

涉及到垃圾回收的知识点

  • unset函数

unset只是断开一个变量到一块内存区域的连接,同时将该内存区域的引用计数-1;内存是否回收主要还是看refcount是否到0了,以及gc算法判断。

  • = null 操作

a=null是直接将a 指向的数据结构置空,同时将其引用计数归0。

  • 脚本执行结束

脚本执行结束,该脚本中使用的所有内存都会被释放,不论是否有引用环。

参考文档

参考文档
参考文档
参考文档