linux中配置内核参数sysctl详解

phpmianshi5年前 (2016-04-20)运维154
概念sysctl用于运行时配置内核参数,这些参数位于/proc/sys目录下。sysctl配置与显示在/proc/sys目录中的内核参数。用户只需要编辑/etc/sysctl.conf文件,即可手工或...

linux中tcpdump的详细用法

phpmianshi5年前 (2016-04-19)运维189
linux中tcpdump的详细用法
在调试网络通信程序是tcpdump是必备工具。tcpdump很强大,可以看到网络通信的每个细节。如TCP,可以看到3次握手,PUSH/ACK数据推送,close4次挥手,全部细节。包括每一次网络收包的...

linux中如何查看系统io使用情况

phpmianshi5年前 (2016-04-18)运维217
linux中查看IO的方法主要有下面几种方法:1. top   %wa    的含义是等待输入输出的CPU时间百分比,这个数字越高说明越多的CPU资源...

linux中cpu占用过高排查方法

phpmianshi5年前 (2016-04-17)运维177
CPU使用率查看top通过top -d 0.1可以缩短采样时间。-d:指定每两次屏幕信息刷新之间的时间间隔。当然用户可以使用s交互命令来改变之。load average后面的三个数分别是1分钟、5分钟...

linux中nf_conntrack table full dropping packet问题处理

phpmianshi5年前 (2016-04-16)运维219
概述:在日常的服务器运维过程中,发现某段时间 /var/log/messages日志报错nf_conntrack:table full,drop packet简介:nf_connt...

linux中高并发场景下too many open files问题处理

phpmianshi5年前 (2016-04-15)运维161
概述:高并发场景下 too many open files 问题。可以通过设置系统打开文件数,直接影响单个进程容纳的客户端连接数。比如会影响到长链接应用如聊天中单个进程能够维持的用户连接数, 运行ul...

linux中Cannot assign requested address的问题处理

phpmianshi5年前 (2016-04-14)运维202
问题描述:最近系统报警有类型如下错误:Cannot assign requested address  主要是连接mysql时产生的错误。分析原因:客户端与服务端每建立一个连接,客户端一侧都...

linux中查看系统活动情况报告sar命令详解

phpmianshi5年前 (2016-04-13)运维274
有很多工具可以看网络流量,但我最喜欢sar。sar(System Activity Reporter系统活动情况报告)是目前 Linux 上最为全面的系统性能分析工具之一,可以从多...

linux中连接数过多(TIME_WAIT/CLOSE_WAIT)读这一篇就够了

phpmianshi5年前 (2016-04-12)运维222
根据TCP/IP介绍,socket大概包含10个连接状态。我们平常工作中遇到的,除了针对SYN的拒绝服务攻击,如果有异常,大概率是TIME_WAIT和CLOSE_WAIT的问题。TIME_WAIT一般...

linux中netstat和ss命令详解

phpmianshi5年前 (2016-04-11)运维212
由于nio的普及,ck10k的问题已经成为过去式。现在随便一台服务器,都可以支持数十万级别的连接了。那么10万的连接需要多少资源呢?由于一个连接都是文件句柄,所以需要文件描述符数量支持才行,每一个so...

linux中lsof命令详解

phpmianshi5年前 (2016-04-10)运维464
简介lsof(list open files)是一个列出当前系统打开文件的工具,在Unix中一切(包括网络套接口)都是文件。有趣的是,lsof也是有着最多开关的Linux/Unix命令之一。它有那...

linux中浅谈端口占用和开闭管理

phpmianshi5年前 (2016-04-09)运维354
背景平时开发或线上运维少不了跟端口打交道,今天我们简单聊聊平时跟端口相关的几个场景首先查看某台主机某个端口服务是否正常比如查看本机 redis服务是否正常telnet 127.0.0.1&n...

Linux中nio的实现原理

phpmianshi5年前 (2016-04-08)运维243


1、应用程序中调用read() 方法,这里会涉及到一次上下文切换(用户态->内核态),底层采用DMA(direct memory access)读取磁盘的文件,并把内容存储到内核地址空间的读取缓存区。

操作系统检测到进程向I/O设备发起请求后就暂停进程的运行,怎么暂停运行呢?

很简单:只需要记录下当前进程的运行状态并把CPU的PC寄存器指向其它进程的指令就可以了。
进程有暂停就会有继续执行,因此操作系统必须保存被暂停的进程以备后续继续执行,显然我们可以用队列来保存被暂停执行的进程。

注意:现代磁盘向内存copy数据时无需借助CPU的帮助,这就是所谓的DMA(Direct Memory Access)。

实际上:操作系统中除了有阻塞队列之外也有就绪队列,所谓就绪队列是指队列里的进程准备就绪可以被CPU执行了。
你可能会问为什么不直接执行非要有个就绪队列呢?

答案很简单:那就是僧多粥少,在即使只有1个核的机器上也可以创建出成千上万个进程,CPU不可能同时执行这么多的进程,因此必然存在这样的进程,即使其一切准备就绪也不能被分配到计算资源,这样的进程就被放到了就绪队列。

当进程A被暂停执行后CPU是不可以闲下来的,因为就绪队列中还有嗷嗷待哺的进程B,这时操作系统开始在就绪队列中找下一个可以执行的进程,也就是这里的进程B。
此时操作系统将进程B从就绪队列中取出,找出进程B被暂停时执行到的机器指令的位置,然后将CPU的PC寄存器指向该位置,这样进程B就开始运行啦。

此后磁盘终于将全部数据都copy到了进程A的内存中,这时磁盘通知操作系统任务完成啦,你可能会问怎么通知呢?这就是中断
操作系统接收到磁盘中断后发现数据copy完毕,进程A重新获得继续运行的资格,这时操作系统小心翼翼的把进程A从阻塞队列放到了就绪队列当中。

注意:从前面关于就绪状态的讨论中我们知道,操作系统是不会直接运行进程A的,进程A必须被放到就绪队列中等待,这样对大家都公平。

此后进程B继续执行,进程A继续等待,进程B执行了一会儿后操作系统认为进程B执行的时间够长了,因此把进程B放到就绪队列,把进程A取出并继续执行。

注意:操作系统把进程B放到的是就绪队列,因此进程B被暂停运行仅仅是因为时间片到了而不是因为发起I/O请求被阻塞。

进程A继续执行,此时buff中已经装满了想要的数据,进程A就这样愉快的运行下去了,就好像从来没有被暂停过一样


2、由于应用程序无法读取内核地址空间的数据,如果应用程序要操作这些数据,必须把这些内容从读取缓冲区拷贝到用户缓冲区。这个时候,read() 调用返回,且引发一次上下文切换(内核态->用户态),现在数据已经被拷贝到了用户地址空间缓冲区,这时,如果有需要,应用程序可以操作修改这些内容。

3、我们最终目的是把这个文件内容通过Socket传到另一个服务中,调用Socket的send()方法,这里又涉及到一次上下文切换(用户态->内核态),同时,文件内容被进行第三次拷贝,被再次拷贝到内核地址空间缓冲区,但是这次的缓冲区与目标套接字相关联,与读取缓冲区没有半点关系。

4、send()调用返回,引发第四次的上下文切换,同时进行第四次的数据拷贝,通过DMA把数据从目标套接字相关的缓存区传到协议引擎进行发送。

"在整个过程中,过程1和4是由DMA负责,并不会消耗CPU,只有过程2和3的拷贝需要CPU参与


如果在应用程序中,不需要操作内容,过程2和3就是多余的,如果可以直接把内核态读取缓存冲区数据直接拷贝到套接字相关的缓存区,是不是可以达到优化的目的?

我们上一篇文章 《linux中netstat和ss命令详解》中提到了nio 原文:https://phpmianshi.com/?id=105有一些小伙伴私信想了解什么是nio,我们这篇详细介绍下什么...

内存分配堆与栈的区别

phpmianshi5年前 (2016-04-07)运维386
堆(Heap)与栈(Stack)是开发人员必须面对的两个概念,在理解这两个概念时,需要放到具体的场景下,因为不同场景下,堆与栈代表不同的含义。一般情况下,有两层含义:(1)程序内存布局场景下,堆与栈表...

linux中磁盘被占用找不到占用文件

phpmianshi5年前 (2016-04-06)运维226
1、用df 检查发现磁盘占用过高[root@VM_0_15_centos ~]# df -h2、用du检查发现各目录占用的空间都很少,有约10G的空间找不到了[root@...

PHP对象使用数组形式访问成员变量

phpmianshi5年前 (2016-04-06)php256
PHP中有很多接口类,不过平时都不会怎么用到.一般访问php类的变量都是使用类->变量名进行访问.除了这样还可以实现接口类用数组方式进行访问类["变量名"]需要实现的是Arr...

Linux中ss命令Recv-Q和Send-Q详解

phpmianshi5年前 (2016-04-05)运维267
ss用来显示处于活动状态的套接字信息。ss命令可以用来获取socket统计信息,它可以显示和netstat类似的内容。但ss的优势在于它能够显示更多更详细的有关TCP和连接状态的信息,而且比netst...

高并发场景下backlog详解

phpmianshi5年前 (2016-04-04)运维216
本文详解高并发场景下backlog的配置和作用环境介绍: PHP 7.3.5 +nginx/1.16.0 +Linux VM_0_15_centos 3.10.0-514.26.2.el7.x86_6...

TCP协议中的三次握手和四次挥手

phpmianshi5年前 (2016-04-03)运维206






TCP(Transmission Control Protocol) 传输控制协议

三次握手

TCP是主机对主机层的传输控制协议,提供可靠的连接服务,采用三次握手确认建立一个连接:

位码即tcp标志位,有6种标示:

SYN(synchronous建立联机) 同步报文段

ACK(acknowledgement 确认)

PSH(push传送)

FIN(finish结束) 结束报文段

RST(reset重置) 复位报文段

URG(urgent紧急) 紧急指针

Sequence number(顺序号码)

Acknowledge number(确认号码)

客户端TCP状态迁移:

CLOSED->SYN_SENT->ESTABLISHED->FIN_WAIT_1->FIN_WAIT_2->TIME_WAIT->CLOSED

服务器TCP状态迁移:

CLOSED->LISTEN->SYN收到->ESTABLISHED->CLOSE_WAIT->LAST_ACK->CLOSED


各个状态的意义如下: 

LISTEN - 侦听来自远方TCP端口的连接请求; 

SYN-SENT -在发送连接请求后等待匹配的连接请求; 

SYN-RECEIVED - 在收到和发送一个连接请求后等待对连接请求的确认; 

ESTABLISHED- 代表一个打开的连接,数据可以传送给用户; 

FIN-WAIT-1 - 等待远程TCP的连接中断请求,或先前的连接中断请求的确认;

FIN-WAIT-2 - 从远程TCP等待连接中断请求; 

CLOSE-WAIT - 等待从本地用户发来的连接中断请求; 

CLOSING -等待远程TCP对连接中断的确认; 

LAST-ACK - 等待原来发向远程TCP的连接中断请求的确认; 

TIME-WAIT -等待足够的时间以确保远程TCP接收到连接中断请求的确认; 

CLOSED - 没有任何连接状态;


TCP/IP协议中,TCP协议提供可靠的连接服务,采用三次握手建立一个连接,如图1所示。

(1)第一次握手:建立连接时,客户端A发送SYN包(SYN=j)到服务器B,并进入SYN_SEND状态,等待服务器B确认。

(2)第二次握手:服务器B收到SYN包,必须确认客户A的SYN(ACK=j+1),同时自己也发送一个SYN包(SYN=k),即SYN+ACK包,此时服务器B进入SYN_RECV状态。

(3)第三次握手:客户端A收到服务器B的SYN+ACK包,向服务器B发送确认包ACK(ACK=k+1),此包发送完毕,客户端A和服务器B进入ESTABLISHED状态,完成三次握手。

完成三次握手,客户端与服务器开始传送数据。

确认号:其数值等于发送方的发送序号 +1(即接收方期望接收的下一个序列号)。

图1 TCP三次握手建立连接  


理解:窗口和滑动窗口TCP的流量控制TCP使用窗口机制进行流量控制什么是窗口?连接建立时,各端分配一块缓冲区用来存储接收的数据,并将缓冲区的尺寸发送给另一端接收方发送的确认信息中包含了自己剩余的缓冲区...

KD-Tree原理详解

phpmianshi5年前 (2015-11-11)算法20

这样就会出现很多长条的分割,对于KDTree来说是很不利的。


为了避免这种情况,需要修改一下算法,纬度的选择的依据为数据范围最大的那一维作为分割纬度,之后也是选中这个纬度的中间节点作为轴点,然后进行分割,分割出来的结果是:



这样的结果对于最邻近搜索是非常友好的。

但是这样做还是有一些不好,就是在树上很可能有一些空的节点,当要限制树的高度的时候,这种方法就不合适了。

构建示例

二维样例:{(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)}

构建步骤:

1、初始化分割轴:

发现x轴的方差较大,所以,最开始的分割轴为x轴。

2、确定当前节点:

对{2,5,9,4,8,7}找中位数,发现{5,7}都可以,这里我们选择7,也就是(7,2);

3、划分双支数据:

在x轴维度上,比较和7的大小,进行划分:

左支:{(2,3),(5,4),(4,7)}

右支:{(9,6),(8,1)}

4、更新分割轴:

一共就两个维度,所以,下一个维度是y轴。

5、确定子节点:

左节点:在左支中找到y轴的中位数(5,4),左支数据更新为{(2,3)},右支数据更新为{(4,7)}

右节点:在右支中找到y轴的中位数(9,6),左支数据更新为{(8,1)},右支数据为null。

6、更新分割轴:

下一个维度为x轴。

7、确定(5,4)的子节点:

左节点:由于只有一个数据,所以,左节点为(2,3)

右节点:由于只有一个数据,所以,右节点为(4,7)

8、确定(9,6)的子节点:

左节点:由于只有一个数据,所以,左节点为(8,1)

右节点:右节点为空。

最终,就可以构建整个的kd-tree了。

邻近搜索

给定一个KDTree和一个节点,求KDTree中离这个节点最近的节点.(这个节点就是最临近点)

这里距离的求法用的是欧式距离。



基本的思路很简单:首先通过二叉树搜索(比较待查询节点和分裂节点的分裂维的值,小于等于就进入左子树分支,等于就进入右子树分支直到叶子结点),顺着“搜索路径”很快能找到最近邻的近似点,也就是与待查询点处于同一个子空间的叶子结点;然后再回溯搜索路径,并判断搜索路径上的结点的其他子结点空间中是否可能有距离查询点更近的数据点,如果有可能,则需要跳到其他子结点空间中去搜索(将其他子结点加入到搜索路径)。重复这个过程直到搜索路径为空。

这里还有几个细节需要注意一下,如下图,假设标记为星星的点是 test point, 绿色的点是找到的近似点,在回溯过程中,需要用到一个队列,存储需要回溯的点,在判断其他子节点空间中是否有可能有距离查询点更近的数据点时,做法是以查询点为圆心,以当前的最近距离为半径画圆,这个圆称为候选超球(candidate hypersphere),如果圆与回溯点的轴相交,则需要将轴另一边的节点都放到回溯队列里面来。


判断轴是否与候选超球相交的方法可以参考下图:



下面再用一个例子来具体说一下查询的过程。

假设我们的k-d tree就是上面通过样本集{(2,3), (5,4), (9,6), (4,7), (8,1), (7,2)}创建的。
我们来查找点(2.1,3.1),在(7,2)点测试到达(5,4),在(5,4)点测试到达(2,3),然后search_path中的结点为<(7,2), (5,4), (2,3)>,从search_path中取出(2,3)作为当前最佳结点nearest, dist为0.141;
然后回溯至(5,4),以(2.1,3.1)为圆心,以dist=0.141为半径画一个圆,并不和超平面y=4相交,如下图,所以不必跳到结点(5,4)的右子空间去搜索,因为右子空间中不可能有更近样本点了。
于是在回溯至(7,2),同理,以(2.1,3.1)为圆心,以dist=0.141为半径画一个圆并不和超平面x=7相交,所以也不用跳到结点(7,2)的右子空间去搜索。
至此,search_path为空,结束整个搜索,返回nearest(2,3)作为(2.1,3.1)的最近邻点,最近距离为0.141。



再举一个稍微复杂的例子,我们来查找点(2,4.5),在(7,2)处测试到达(5,4),在(5,4)处测试到达(4,7),然后search_path中的结点为<(7,2), (5,4), (4,7)>,从search_path中取出(4,7)作为当前最佳结点nearest, dist为3.202;
然后回溯至(5,4),以(2,4.5)为圆心,以dist=3.202为半径画一个圆与超平面y=4相交,如下图,所以需要跳到(5,4)的左子空间去搜索。所以要将(2,3)加入到search_path中,现在search_path中的结点为<(7,2), (2, 3)>;另外,(5,4)与(2,4.5)的距离为3.04 < dist = 3.202,所以将(5,4)赋给nearest,并且dist=3.04。
回溯至(2,3),(2,3)是叶子节点,直接平判断(2,3)是否离(2,4.5)更近,计算得到距离为1.5,所以nearest更新为(2,3),dist更新为(1.5)
回溯至(7,2),同理,以(2,4.5)为圆心,以dist=1.5为半径画一个圆并不和超平面x=7相交, 所以不用跳到结点(7,2)的右子空间去搜索。

至此,search_path为空,结束整个搜索,返回nearest(2,3)作为(2,4.5)的最近邻点,最近距离为1.5。



所以在搜索中可能会出现不同的情况,比如下面的两张图就是比较极端的两个例子。



代码清单

以下是k-d树的c++代码实现,包括建树过程和搜索过程。算法main函数输入k-d树训练实例点,算法会完成建树操作,随后可以输入待查询的目标点,程序将会搜索K-d树找出与输入目标点最近邻的训练实例点。本程序只实现了1近邻搜索,如果要实现k近邻搜索,只需对程序稍作修改。比如可以对每个结点添加一个标记,如果已经输出该结点为最近邻结点,那么就继续查找次近邻的结点,直到输出k个结点后算法结束。

简介kd树(k-dimensional树的简称),是一种分割k维数据空间的数据结构。主要应用于多维空间关键数据的搜索(如:范围搜索和最近邻搜索)。一个KDTree的例子上图的树就是一棵KDTree,形...