PHP面试题汇总(三)

归并排序算法原理

算法思路

时间复杂度：O(nlogn)

把 n 个记录看成 n 个长度为 l 的有序子表
进行两两归并使记录关键字有序，得到 n/2 个长度为 2 的有序子表
重复第 2 步直到所有记录归并成一个长度为 n 的有序表为止。

实例

两个正序数组，如[3 4 7 9], [2 6 8] 如何合并成一个正序数组
假设：
序列A：3 4 7 9
序列B：2 6 8
序列C：空
合并思路是：先申请一个序列，将指针分别指向3和2，这时候进行比较，3大于2，所以把2放到序列C，序列B指针后移到6，这时候序列A的3小于6，把3放到序列C，A序列指针后移
4小于序列B的6，把4放到序列C，依次类推。。。直到最后只剩下序列A中的9，把9合并到序列C，完成归并排序

参考

归并排序算法

一致性HASH原理和应用

问题：单机redis20G如何承载500G的cache（考虑redis集群应用）

应用场景

如何对请求与缓存服务器之间进行精准映射,以及优雅的扩展，剔除缓存服务器，提升缓存服务的容错性和扩展性

算法概述

一致性哈希将整个哈希空间组织成一个虚拟的圆环，假如整个哈希函数的值空间为0 - 2^32 -1(一个32位的无符号整形)，如下图:整个空间按顺时针方向组织,0和232-1在零点中方向重合

一致性HASH闭环

第一步：在哈希闭环中确定各台服务器位置

将各台服务器的ip或主机名为关键字通过H函数得到一个哈希值，然后在哈希闭环中标注位置。如下图3台redis服务：

第二步：定位数据访问的服务器

将数据key使用相同的函数H计算出哈希值h，通根据h确定此数据在环上的位置，从此位置沿环顺时针“行走”，第一台遇到的服务器就是其应该定位到的服务器

例如我们缓存服务器中有A、B、C、D四个key对应的数据对象，经过哈希计算后，在环空间上的位置如下：

一致性hash函数值空间

参考

MySQL索引知识点

索引类型

1. 从数据结构角度

B+树索引(O(nlogn))
hash索引：检索效率最高，仅能使用”=”,”IN”和”<=>”查询，不能使用范围查询和排序
2. 从物理存储角度
聚簇索引
非聚簇索引

3. 从逻辑角度

主键索引
普通索引
复合索引
唯一索引

InnoDB B+Tree索引原理

1. B+Tree数据结构

所有非叶子结点至多拥有两个儿子, 非叶子结点的左指针指向小于其关键字，右指针指向大于其关键字
所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的指针自小而大顺序连接
非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；

2. InnoDB数据页结构

页是InnoDB存储引擎管理数据库的最小磁盘单位(16K)
叶子节点(页与页之间)是双向链表串起来的,头连上一页的尾，尾连下一页的头
每个数据页中有两个虚拟的行记录，用来限定记录的边界
页目录(Page Directory)通过顺序排放的 记录指针(也叫槽) 存放了记录的相对位置，通过这些槽找到具体的数据位置

3. 查询B+树索引的流程
首先通过B+树索引找到叶节点，再找到对应的数据页，然后将数据页加载到内存中，通过二分查找页目录中的指针，查找出一个链表,然后就可以遍历这个链表找到具体的数据。

聚簇索引和非聚簇索引实现原理和区别

区别

聚簇索引一般是为主键索引，一张表只能有一个聚簇索引，B+树的叶子节点存储了行数据和主键。
非聚簇索引可以有多个，叶节点除了包含关键字键值外还包含聚集索引的主键

非聚簇索引的查询流程
先查到主键值，然后InnoDB再根据查到的主键值通过主键索引找到对应的数据块。

参考

MySQL InnoDB索引底层原理详解

Redis和Memcached的区别

Redis支持除key-value之外更多的数据类型
内存使用效率对比：使用简单的key-value存储的话，Memcached的内存利用率更高，而如果Redis采用hash结构来做key-value存储，由于其组合式的压缩，其内存利用率会高于Memcached
性能对比:由于Redis只使用单核，而Memcached可以使用多核，所以平均每一个核上Redis在存储小数据时比Memcached性能更高。而在100k以上的数据中，Memcached性能要高于Redis。结论是，无论你使用哪一个，每秒处理请求的次数都不会成为瓶颈。（比如瓶颈可能会在网卡）
数据持久化和同步:memcache不支持，redis支持
网络IO模型方面：Memcached是多线程，分为监听线程、worker线程，引入锁，带来了性能损耗。Redis使用单线程的IO复用模型，将速度优势发挥到最大，也提供了较简单的计算功能
集群管理的不同:memcached只能通过分布式算法来实现Memcached的分布式存储，redis 高级版本redis Cluster在服务端做了支持，并且引入了Master节点和Slave节点，保证单点故障下的数据可用性

参考

redis和memcached的区别

进程、线程、协程(轻量级线程)和go中的Goroutine

进程、线程和协程之间概念的区别

需要区分进程、线程(内核级线程)、协程(用户态的轻量级的线程)三个概念

对于进程、线程，都是有内核进行调度，有CPU时间片的概念，进行抢占式调度（有多种调度算法）
对于协程(用户态的轻量级的线程)，这是对内核透明的，也就是系统并不知道有协程的存在，是完全由用户自己的程序进行调度的。
因为是由用户程序自己控制，那么就很难像抢占式调度那样做到强制的CPU控制权切换到其他进程/线程。
通常只能进行协作式调度，需要协程自己主动把控制权转让出去之后，其他协程才能被执行到。
ps：所以说协程是不需要进行内核态的切换的。

goroutine 和协程区别

本质上，goroutine 就是协程。不同的是，Golang 在 runtime、系统调用等多方面对 goroutine 调度进行了封装和处理，
当遇到长时间执行或者进行系统调用时，会主动把当前 goroutine 的CPU转让出去，让其他 goroutine 能被调度并执行，
也就是 Golang 从语言层面支持了协程 。
Golang 的一大特色就是从语言层面原生支持协程，在函数或者方法前面加 go关键字就可创建一个协程。

线程和协程的区别?

一旦创建完线程，你就无法决定他什么时候获得时间片，什么时候让出时间片了，你把它交给了内核。
而协程编写者可以有： 一是可控的切换时机 ， 二是很小的切换代价
从操作系统有没有调度权上看，协程就是因为不需要进行内核态的切换，所以会使用它，会有这么个东西。
这个定义相对准确： 协程－用户态的轻量级的线程

进程、线程、协程的联系与区别

进程是系统进行资源分配和调度的独立单位，也就是说不同进程拥有自己独立的堆和栈，既不共享堆也不共享栈
线程是进程的一个实体，是CPU调度和分配的基本单位，它是比进程更小的能独立运行的基本单位，它拥有独立的栈和共享的堆。
协程又称”微线程”，它和线程一样拥有独立的栈和共享的堆。是由程序员调度的执行单元，
它自带CPU上下文，当一个协程发现自己执行不下去了(比如异步等待网络的数据回来，但是当前还没有数据到),
这个时候就可以由这个协程通知调度器，这个时候执行到调度器的代码，调度器根据事先设计好的调度算法找到当前最需要CPU的协程

区别和优缺点

一个程序至少拥有一个进程，一个进程至少拥有一个线程（主线程）
进程在执行过程中拥有独立的内存单元，而多个线程共享内存，从而极大地提高了程序的运行效率
协程、线程不能够独立执行，必须依存在进程中，应当使用互斥锁机制来加以控制
进程之间可以通过MQ来传递数据，而线程、协程之间的全局变量是共享的
进程和线程都是由操作系统调度的，而协程的调度是用户(程序员)控制的
在IO操作密集型的程序使用协程可以很好的避免CPU的浪费，将CPU的资源主动让出给其他协程使用。
操作系统为了程序运行的高效性每个线程都有自己缓存Cache等等数据，操作系统还会帮你做这些数据的恢复操作。
所以线程的切换非常耗性能。但是协程的切换只是单纯的操作CPU的上下文，所以一秒钟切换个上百万次系统都抗的住

内存分配中的堆与栈

程序中用来存放数据的内存分为四块:

全局区(静态区)（static）:全局变量和静态变量会存放在这里,程序结束时系统会释放这块资源.
文字常量区：我们定义的常量字符串就放在这块地方,也叫常量池，程序结束时系统会释放这块资源.
栈区（stack）：存放函数的参数和局部变量的值 .在进入作用域时分配内存空间，离开时就会释放这部分内存
堆区（heap）： 一般由程序员分配释放，若程序员不释放，程序结束时可能由系统回收。
由于这个原因，在C和C++中就有能产生大量程序员分配但忘记释放的堆区内存，造成可使用内存越来越少，这个被称之为内存泄露.
我们使用new进行实例化后分配的内存就在这部分区域

并行和并发区别

并行是指程序的运行状态，要有两个线程正在执行才能算是Parallelism；要在多核或者多处理器情况下才能做到。
并发指程序的逻辑结构 ，Concurrency则只要有两个以上线程还在执行过程中即可，不一定是多核处理器

参考：

进程、线程、协程的联系与区别
 进程、线程、轻量级进程、协程和go中的Goroutine 那些事儿
 Golang协程详解
 内存分配中的堆与栈

TCP/IP协议

考察：三次握手、四次挥手、为什么需要三次握手？为什么需要2MSL？

参考

TCP/IP知识点

HTTP协议

请求信息：

GET /s?wd=tinyint%20mysql%20%E8%8C%83%E5%9B%B4&rsv_spt=1&rsv_iqid=0xdc5b82ba0000f8f1&issp=1&f=8&rsv_bp=0&rsv_idx=2&ie=utf-8&tn=92821989_s_hao_pg&rsv_enter=1&rsv_sug3=1 HTTP/1.1
Host: www.baidu.com
Connection: keep-alive
Upgrade-Insecure-Requests: 1
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_13_3) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/64.0.3282.167 Safari/537.36
Accept: text/html,application/xhtml+xml,application/xml;q=0.9,image/webp,image/apng,*/*;q=0.8
Accept-Encoding: gzip, deflate, br
Accept-Language: zh-CN,zh;q=0.9,de;q=0.8,en;q=0.7
Cookie: BAIDUID=112214E2FB5B1B92AE076721859B590F:FG=1; BIDUPSID=112214E2FB5B1B92AE076721859B590F; 

wd=tinyint%20mysql%20%E8%8C%83%E5%9B%B4&rsv_spt=1&rsv_iqid=0xdc5b82ba0000f8f1&issp=1&f=8&rsv_bp=0&rsv_idx=2&ie=utf-8&tn=92821989_s_hao_pg&rsv_enter=1&rsv_sug3=1

响应信息：

HTTP/1.1 301 Moved Permanently
Server: nginx
Date: Mon, 26 Feb 2018 09:36:40 GMT
Content-Encoding:gzip
Content-Type: text/html
set-cookie:sf_remember=1e055cc0983b652de8e2d2fd02ff068d; expires=Tue, 06-Mar-2018 02:25:12 GMT; Max-Age=604800; path=/
Location: http://www.sina.com.cn/
Expires: Mon, 26 Feb 2018 10:36:40 GMT
Cache-Control: max-age=3600
Age: 14
Content-Length: 122
X-Cache: HIT from cnc.xidan.sinacache.24.nb.sinaedge.com


＜html＞
＜head＞
＜title＞http＜/title＞
＜/head＞
＜body＞
＜!-- body goes here --＞
＜/body＞
＜/html＞

http code与缓存层

200状态：当浏览器本地没有缓存或下一层失效时或用户点击CTRL+F5，直接去服务器下载最新数据
304状态：这一层由last-modify/etag控制。当下一层失效或用户点击F5时，浏览器会发送请求给服务器，如果服务端没有变化，则返回304给浏览器
ps:etag是对url进行标记，检测标记是否存在，但是由于分布式系统中各个机器生成的标记不同，所以一般会关闭掉
200(from cache)：这一层由expires/cache-control控制。
1. expires(http1.0版有效)是绝对时间。
2. cache-control(http1.1版本有效)，相对时间，两者都存在时，cache-control覆盖expires只要没有失效，浏览器只访问自己的缓存
总结：expires和cache-control都是本地的缓存过期时间，缓存期不会请求服务端，last-modify会发生服务端的请求，检测服务端是否有更改。

关于 Cache-Control: max-age=秒和 Expires

区别：
Expires = 绝对时间，HTTP 1.0 版本，缓存的截止时间，允许客户端在这个时间之前不去检查（发请求）
max-age = 秒，HTTP 1.1版本，资源在本地缓存多少秒。
如果max-age和Expires同时存在，则被Cache-Control的max-age覆盖。
优缺点
Expires 的缺点：返回的到期时间是服务器端的时间，这样存在一个问题，如果客户端的时间与服务器的时间相差很大，那么误差就很大，所以在HTTP 1.1版开始，使用Cache-Control: max-age=秒替代。

Last-Modified：会发生服务器的请求

在浏览器第一次请求某一个URL时，服务器端的返回状态会是200，内容是你请求的资源，同时有一个Last-Modified的属性标记(HttpReponse Header)此文件在服务期端最后被修改的时间，格式类似这样：
Last-Modified:Tue, 24 Feb 2009 08:01:04 GMT

客户端第二次请求此URL时，根据HTTP协议的规定，浏览器会向服务器传送If-Modified-Since报头(HttpRequest Header)，询问该时间之后文件是否有被修改过：

If-Modified-Since:Tue, 24 Feb 2009 08:01:04 GMT

如果服务器端的资源没有变化，则自动返回HTTP304（NotChanged.）状态码，内容为空，这样就节省了传输数据量。当服务器端代码发生改变或者重启服务器时，则重新发出资源，返回和第一次请求时类似。从而保证不向客户端重复发出资源，也保证当服务器有变化时，客户端能够得到最新的资源。

注：如果If-Modified-Since的时间比服务器当前时间(当前的请求时间request_time)还晚，会认为是个非法请求

HTTP状态码

200 OK
301 永久重定向
302 临时重定向
304 页面未修改

400 客户端请求参数有误
401 未授权
403 拒绝访问
404 网页不存在

500 服务器内部未知错误
502 错误的网关
503 服务临时不可用
504 网关超时

参考

http协议详解