[日常] 面试知识点总结(持续更新)
数据结构和算法: 物理结构和逻辑结构 1.逻辑结构(集合结构,线性结构,树形结构,图形结构) 2.物理结构一般是讲内存,顺序存储结构,链式存储结构 浅谈算法中,高斯算法从1加到100,循环的话是100次,高斯的方法只需要一次 1.推导大O阶:O(1) O(n) O(n^2) O(logn) 1.常数1取代时间所有加法常数 2.只保留最高项 3.去除项相乘的常数,去掉系数 2.O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)时间复杂度从小到大 3.一般是指的最坏运行时间 TCP: OSI七层/五层协议:物理层,数据链路层,网络层,传输层,应用层(会话层/表示层) 数据链路层:做到封装成帧,透明传输,差错检验 数据链路层的差错检测:路由器能做到的是传输接收后如果有错误就丢掉,用的CRC循环冗余检验,不提供可靠传输 网络层:负责在不同网络之间尽力转发数据包,不负责丢失重传,也不负责顺序 查看路由表:route -n ARP协议可以将网络层地址到任意物理地址转换,从IP地址到MAC地址转换 传输层 TCP(传输控制协议) 需要将要传输的文件分段传输,建立会话,可靠传输,流量控制 1.面向连接,只能有两个端点,点到点;提供全双工(同时收和发)既要发了信息,也得收信息确认对方有没有收到 客户端 ===> SYN MSS=1460(最大数据包是1460字节) [seq=0 序列号是0] ===> 服务器 客户端 <=== SYN,ACK [seq=0,ack=1 序列号是0,确认号是1] MSS=1424(服务器最大数据包是1424字节) WS=7(window) win=3737600(服务器最多缓存3737600字节)<=== 服务器 客户端 ===> ACK [seq=1,ack=1 序列号是1,确认号是1] win=66816(客户端最多缓存是66816字节) ===> 服务器 2.面向字节流,比如 发送文件,文件二进制=>TCP发送缓存=>TCP接收缓存=>应用程序,这也是发送和接收窗口技术 3.TCP协议使用滑动窗口技术实现可靠传输 1.停止等待协议效率不高,连续发送确认是窗口技术 2.以字节为单位的滑动窗口技术,连续发送,接收窗口收到后确认,往右滑动发送窗口,接收窗口也要往右滑动 3.如果中间有顺序的包丢了,接收窗口发送确认号的时候,会发丢之前的ack号,选择重发的包序号,选择确认 4.超时重传,tcp每发送一个报文段,就设置一次计时器,重传时间到但还没收到确认,就重传这一报文段,这个时间是加权平均的往返时间 4.TCP流量控制是解决的通信两端处理数据能力不一致的问题,TCP协议如何实现流量控制 1.接收方数据处理不完了,就调整了接收窗口的大小 2.通过窗口大小来控制流量 TCP的传输连接管理: 1.连接建立=>数据传输=>连接释放 2.主动发起连接的是客户端,被动接受连接的是服务器 3. 客户端 ==> SYN是1同步 ,ACK确认标志是0,seq序号是x ==> 服务器 客户端 <== SYN是1同步 ,ACK确认标志是1,seq序号是y,ack确认号是x+1 <==服务器 客户端 ==> ACK确认标志是1,seq序号是x+1,ack确认号是y+1 ==>服务器 4.为什么需要第三次握手再次确认,因为服务器需要确认客户端收到我的回复 5.状态转移 1.客户端发送完变成 SYN-SENT , 服务端接收到后变成SYN-RECEIVED,客户端接收到确认变成 ESTABLISHED,服务端收到确认变成 ESTABLISHED 2.当客户端访问不存在的IP时,可以看到客户端变成SYN-SENT状态,接收不到服务端的确认回复 3.SYN攻击,可以伪造来源ip,因此可以看到服务端变成SYN-RECEIVED状态,接收不到客户端的确认回复 6.四次挥手 客户端(主动关闭) ==> FIN标志是1,seq序号是u ==>服务器 客户端 <== ACK确认标志是1,seq序号是v,ack确认号是u+1 <== 服务器 客户端 <== FIN标志是1,ACK确认标志是1,seq序号是w,ack确认号是u+1 <== 服务器 客户端 ==> ACK确认标志是1,seq序号是u+1,ack确认号是w+1 ==>服务器 7.状态转移 主动关闭的一方是time_wait的状态 被动关闭的一方是close_wait的状态 UDP(用户报文协议) 一个数据包就能完成数据通信,不需要建立会话,不分段,不用流量控制,不可靠传输 HTTP: HTTP状态码: 100-199 信息性状态码 100 continue 请继续 101 switching protocols 切换协议，返回upgraded头 200-299 成功状态码 200 ok 201 created 创建资源 202 accepted 请求已经接收到，不保证完成 203 non-authoritative information 非权威信息，不是来自于源端服务器 204 no content 没有内容 205 reset content 重置内容，主要是对浏览器html元素 206 partial content 执行了部分内容 300-399 重定向状态码 300 multiple choices 多项选择,会返回一个选项列表 301 moved permanently 资源被移除，location中包含url 302 Found 与301类似，客户端应该使用location中的url临时定位 303 see other 允许post请求的响应重定向 304 not modified 资源没有修改，返回的时候不能有主体内容，还是本地的内容 305 use proxy 使用代理来请求资源 307 temporary redirect 临时重定向，与301类似 因为http1.0和http1.1的差别因此有交叉 4xx系列和客户端有关: 400 bad request 错误请求 401 unauthorized 没权限 402 payment required 未使用 403 forbidden 禁止 404 not found 405 methord not allowed 请求url不支持的方法，应该返回allow首部告诉允许啥 406 not acceptable 客户端指定参数说明可以接受什么类型的文本 407 proxy authentication required 要求代理服务器认证权限 408 request timeout 请求超时 409 conflict 请求冲突 410 gone 类似404 411 length required 需要请求中包含content-length 412 precondition failed 先决条件失败 413 request entity too large 客户端发的内容太大 414 request uri too long 请求的url太长 415 unsuport media type 不支持的媒体类型 416 requested range not satisfiable 请求的范围不满足，无效 417 expectation failed 服务器无法满足请求 nginx自定义的状态码: 495, https certificate error 496, https no certificate 497, http to https 498, canceled 499, client has closed connection是客户端等到超时主动关掉的 500-599 服务器错误状态码 500 internal server error 内部错误 501 not implemented 没有实现，超出了服务器的范围 502 bad gateway 代理或者网关下一链路收到未响应 503 service unavailable 服务不可用 504 gateway timeout 类似408,超时来自代理 505 http version not supported http协议版本不支持 主流的WEB服务:REST,SOAP,RPC 1.REST是基于HTTP协议的一个补充，他的每一次请求都是一个HTTP请求，然后根据不同的method来处理不同的逻辑 2.SOAP是W3C在跨网络信息传递和远程计算机函数调用方面的一个标准。但是SOAP非常复杂 3.GO天生提供方便的RPC机制 4.有连接的流式Socket（SOCK_STREAM）TCP 和无连接数据报式Socket（SOCK_DGRAM）UDP 5.IPv4的地址位数为32位，也就是最多有2的32次方的网络设备可以联到Internet上,IPv6采用128位地址长度，几乎可以不受限制地提供地址 MySQL: mysql分层: 1.client ==>连接层 ==>服务层==>引擎层==>存储层 server 3.连接层: 提供与客户端连接的服务 4.服务层: 1.提供各种用户使用的接口(增删改查),sql解析 2.提供SQL优化器(MySQL Query Optimizer),重写查询,决定表的读取顺序,选择合适的索引 mysql的hint关键字有很多比如:SQL_NO_CACHE FORCE_INDEX SQL_BUFFER_RESULT 5.引擎层:innoDB和MyISAM 1.innoDB:事务优先(适合高并发修改操作;行锁) 2.MyISAM:读性能优先 3.show engines;查询支持哪些引擎 4.查看当前默认的引擎 show variables like '%storage_engine%';default_storage_engine sql的解析过程比如: from ... on ... where ... group by ... having ... select ... order by ... limit innoDB引擎的四大特性:插入缓冲,二次写,自适应哈希索引,预读 事务的四种隔离级别:读未提交(read uncommitted),读已提交(read committed),可重复读(repeatable read),串行(serializable) MYSQL的锁机制: 1.无论何时只要有多个查询在同一时刻修改数据,都会产生并发控制的问题 2.讨论mysql在两个层面,服务器层和存储引擎层,如何并发控制读写 3.举了个mbox邮箱文件的例子,说如果有多个进程同时对mbox文件写东西,那么在文件的末尾会,交叉混乱的添加,比如进程1写了几行,进程2也写了几行,互相交叉,数据就是错误的了.设计良好的mbox需要加锁,比如进程1锁住了文件,进程2必须等待进程1结束,锁释放才能去写.但是这样的话就不支持并发了,同一时刻只有一个进程可以写数据 4.读取时可能也会有问题,比如一个进程正在读数据,另一个进程同时想去删数据,此时就是不安全的;共享锁叫读锁,排他锁叫写锁 5.读锁是共享的,它不会阻塞其他读锁;写锁是排他的,它会阻塞其他读锁和写锁;读读不互斥,读写互斥,写写互斥 6.mysql每时每刻都在发生锁定,当某用户在修改数据时,会阻塞其他用户读取该数据 7.mysql中有两种锁粒度,锁住整张表和锁住表中一行 表锁:当某用户修改数据时,会获取写锁,此时会锁住整张表,其他用户都不能读和写,myisam 行锁:当某用户修改某几行数据,会获取写锁,此时只是锁住那几行,那几行其他用户不能读和写;其他行没有影响,但是管理锁会消耗资源,innodb 8.使用命令来锁表 unlock tables 解锁所有行 lock tables 表名 read或者write MVCC 多版本并发控制实现的事务: 1.没有一个统一的实现标准,实现了非阻塞的读操作,写操作也只锁定必要的行 2.通过保存数据在某个时间点的快照实现的 3.典型的有乐观并发控制和悲观并发控制 4.innodb的mvcc是每次事务都有递增的版本号,通过在每行记录的后面添加两列隐藏字段,两列分别是是创建版本号和删除版本号,存储操作它事务的版本号 5.在事务中增删改查就是对两列版本号字段进行操作 insert 为新插入的每一行保存当前事务版本号到 行创建版本号字段 update 插入一行新的保存当前事务创建版本号,修改原行数据的删除版本号为本次事务的版本号 delete 修改行的删除版本号字段为本次事务的版本号 select 查询 创建版本号字段 小于等于当前事务版本的数据 确保该记录是本次之前就存在的或本次事务新插的 查询 删除版本号字段 不存在或者大于当前版本的数据 确保该记录在本次事务之前没删除 6.这样的设计就不需要加锁了,读和操作性能好,但是需要额外的存储空间 7.mvcc只在REPEATABLE READ和READ COMMITED两个隔离下工作;READ UNCOMMITED总是读取最新数据;SERIALIZABLE对读取的行都加锁 mysql 死锁: 1.两个或多个事务在同一个资源上相互占用,并请求锁定对方占用的资源,导致恶性循环 2.解决这种问题,检测到死锁的循环依赖,立即返回一个错误 3.时间达到了锁等待超时限定,放弃锁请求 4.将持有最少行级写锁的事务回滚 5.如果是真正的数据冲突,这种是很难避免的,必须要提交或回滚其中一个事务 ERROR 1205 (HY000): Lock wait timeout exceeded; try restarting transaction mysql中的索引类型(index/key): 普通索引:默认的 主键索引:自增字段一定是,唯一性约束;主键不一定自增 唯一索引:提供唯一性约束,可以有多个唯一索引 全文索引:不支持中文全文检索,一般用第三方,coreseek/xunsearch 外键索引:只有InnoDB支持,效率不高不推荐,只使用外键思想保证数据一致性和完整性 mysql索引: 1.索引如果没有特别指明类型,一般是说b树索引,b树索引使用b树数据结构存储数据,实际上很多存储引擎使用的是b+树,每一个叶子节点都包含指向下一个叶子节点的指针,从而方便叶子节点的范围遍历 2.底层的存储引擎也可能使用不同的存储结构,NDB集群存储引擎使用了T树,InnoDB使用的是B+树 3.MyISAM使用前缀压缩技术使得索引更小,InnoDB按照原数据格式进行存储,MyISAM通过数据的物理位置引用被索引的行,InnoDB根据主键引用被索引的行 4.b树意味着所有的值是按照顺序存储的,并且每一个叶子页到根的距离相同 5.b树索引能够加快访问数据的速度,存储引擎不需要再进行全表扫描来获取需要的数据,取而代之的是从索引的根节点开始进行搜索,根节点的槽中存放了指向子节点的指针,存储引擎根据这些指针向下层查找.通过比较节点页的值和要查找的值可以找到合适的指针进入下层子节点.树的深度和表的大小直接相关 6.叶子节点比较特别,他们的指针指向的是被索引的数据,而不是其他的节点页 7.b树对索引列是顺序存储的,所以很适合查找范围数据. 8.索引对多个值进行排序的依据是,定义索引时列的顺序,比如联合索引key(a,b,c),这三个列的顺序 9.上面的联合索引对以下查询语句有效 全值匹配 where a=x and b=x and c=x 最左前缀 where a=x 匹配列前缀 where a like x% 匹配范围值 where a>x and a、in等。eq_ref或者ref_or_null。且查询需要访问表的整行数据，即不能直接通过二级索引的元组数据获得查询结果(索引覆盖)。 (6)index：遍历所有索引。 (7)all：遍历全表 possible_keys：显示可能应用在这张表中的索引 key： 实际使用的索引 key_len：使用的索引的长度。在不损失精确性的情况下，长度越短越好 mysql索引的长度计算: 1.所有的索引字段，如果没有设置not null，则需要加一个字节。 2.定长字段,int占4个字节、date占3个字节、char(n)占n个字符。 3.变长字段,varchar(n)，则有n个字符+两个字节。 4.不同的字符集，一个字符占用的字节数不同。latin1编码的，一个字符占用1个字节，gbk编码的，一个字符占用2个字节，utf8编码的，一个字符占用3个字节。utf8mb4是一个字符占4个字节 5.使用explain语句查询到的key_len字段,可以适用于上面的计算规则,可以看到查询是否使用到了联合索引 6.mysql优化器会对条件中的 and的前后顺序根据多列索引顺序自动纠正过来 rows:通过索引查询到的数据量 extra: (1) Using filesort：文件内排序，说明mysql使用了外部排序。 (2) Using temporary：使用了保存中间结构。（order by 、group by）,使用了隐式临时表 (3) Using index：效率不错，表示使用了索引。 Redis: 五种数据类型必记: 字符串（string）， 散列（hash）， 列表（list）， 集合（set）， 有序集合（sorted set） redis的设计与实现: 1.假如有一个用户关系模块,要实现一个共同关注功能,计算出两个用户关注了哪些相同的用户,本质上是计算两个用户关注集合的交集,如果使用关系数据库,需要 对两个数据表执行join操作,对合并的结果执行去重distinct操作,非常复杂 2.Redis直接内置了集合数据类型,支持对集合执行交集/并集/差集等集合计算操作,交集操作可以直接用于共同关注功能,使用之后速度更快代码量更少,可读性大大提高 3.越来越多的疑问:五种数据类型是由什么数据结构实现的?字符串数据类型既可以存储字符串,又可以存储整数浮点数,二进制位,在内部是怎么存储这些值的? 有些命令只能对特定数据类型执行,是如何进行类型检查的?怎样存储各种不同类型的键值对?过期键是怎样实现自动删除的?发布与订阅/脚本/事务等特性是如何实现的?使用什么模型处理客户端的命令请求?一条命令从发送到返回需要经历的步骤? 4.第一版发布的时候还不是很完善,作者一边注释源码一边写,只介绍了内部机制和单机特性,新版添加了关于二进制位操作/排序/复制/Sentinel和集群等主题的新章节 5.数据结构与对象,单机数据库的实现,多机数据库的实现,独立功能的实现 6.数据库里面的每个键值对都是由对象组成的:数据库键总是字符串对象;键的值可以是字符串对象/列表对象(list object)/哈希对象(hash object)/集合对象(set object)/有序集合对象(sorted set object),这五种中的其中一种 7.第一部分和第二部分单机功能比较重要:第一部分,简单动态字符串,链表,字典,跳跃表,整数集合,压缩列表,对象 8.Redis自己构建了一个SDS的类型用来保存所有的字符串对象,包括键值对的键,值中存储字符串对象的底层也是SDS redis的设计与实现-list的底层实现 链表 1.链表提供了高效的节点重排能力,顺序性的节点访问方式,通过增删节点调整链表的长度,C语言不内置,Redis构建了自己的链表实现 2.列表键的底层实现之一就是链表,当元素比较多,元素都是比较长的字符串,就会使用链表作为底层实现 3.发布与订阅,慢查询,监视器等功能也用到了链表,redis本身使用链表保存多个客户端的状态信息 4.每个链表节点使用adlist.h/listNode结构表示,通过prev和next指针组成双端链表;使用adlist.h/list结构操作更方便,提供了表头指针head,表尾指针tail,长度计数len,特定类型的函数等 5.链表表头前置和表尾后置都是指向null,所以是无环链表,设置不同类型特定函数,可以用于保存不同类型的值 PHP-FPM: cgi:一种协议,CGI/1.1 标准 fastcgi:一种升级版协议,常驻型 php-cgi:解释PHP脚本的程序,实现了fastcgi协议,进程管理较差 php-fpm:是fastcgi进程的管理器,升级版php-cgi,升级了进程调度 php-fpm控制子进程的个数: pm = dynamic #对于专用服务器，pm可以设置为static。 #如何控制子进程，选项有static和dynamic。如果选择static，则由pm.max_children指定固定的子进程数。如果选择dynamic，则由下开参数决定： pm.max_children #，子进程最大数 pm.start_servers #，启动时的进程 pm.min_spare_servers #，保证空闲进程数最小值，如果空闲进程小于此值，则创建新的子进程 pm.max_spare_servers #，保证空闲进程数最大值，如果空闲进程大于此值，此进行清理 php-fpm开启慢查询日志: /etc/php/7.0/fpm/pool.d/www.conf slowlog = /var/log/php-fpm-$pool.log.slow request_slowlog_timeout = 5 配置php-fpm的php的错误日志: /usr/local/php7.1.10/etc/php-fpm.d/www.conf php_admin_value[error_log] = /var/log/php-fpm/fpm-php.www.log php_admin_flag[log_errors] = on php-fpm的默认错误日志,在这里配置/etc/php/7.0/fpm/php-fpm.conf error_log,只是fpm启动信息的日志,没有php的错误日志 配置临时文件目录: env[TMP] = /data1/phptmp env[TMPDIR] = /data1/phptmp env[TEMP] = /data1/phptmp PHP: session id的生成原理: hash_func = md5 / sha1 #可由php.ini配置 PHPSESSIONID = hash_func(客户端IP + 当前时间（秒）+ 当前时间（微妙）+ PHP自带的随机数生产器) 获取UUID: apt-get install uuid uuid-dev pecl install uuid配置cli和fpm的ini文件,引入扩展 php有这个扩展uuid: uuid_create()生成唯一id:时间戳、毫秒数、机器码、自增计数 接口安全性: 接口的安全性主要围绕Token、Timestamp和Sign三个机制展开设计，保证接口的数据不会被篡改和重复调用，下面具体来看： (1)Token授权机制：(Token是客户端访问服务端的凭证)--用户使用用户名密码登录后服务器给客户端返回一个Token（通常是UUID），并将Token-UserId以键值对的形式存放在缓存服务器中。服务端接收到请求后进行Token验证，如果Token不存在，说明请求无效。 (2)时间戳超时机制：(签名机制保证了数据不会被篡改)用户每次请求都带上当前时间的时间戳timestamp，服务端接收到timestamp后跟当前时间进行比对，如果时间差大于一定时间（比如5分钟），则认为该请求失效。时间戳超时机制是防御DOS攻击的有效手段。 (3)签名机制：将 Token 和 时间戳 加上其他请求参数再用MD5或SHA-1算法（可根据情况加点盐）加密，加密后的数据就是本次请求的签名sign，服务端接收到请求后以同样的算法得到签名，并跟当前的签名进行比对，如果不一样，说明参数被更改过，直接返回错误标识。
更多精彩
