985研一学习日记 - 2024.11.5

一个人内耗，说明他活在过去；一个人焦虑，说明他活在未来。只有当一个人平静时，他才活在现在。

日常

1、起床6:00

2、健身1.5h

今天练了胸，然后跑了会步，又吃多了，明天少吃点！

3、LeetCode刷了1题

1. 不同路径个数
   1. 不可以使用 递归+回溯 ！！！ 会超出时间限制！！！要使用动态规划DP
   2. 对于二维数组遍历所有路径时，最好不要使用递归+回溯，会超出时间限制，可以使用动态规划！！
2. Bellman_ford队列优化算法(SPFA)
   1. 对于Bellman_ford算法，每次松弛将所有边均进行一次松弛操作，此时很多边的松弛是无效的，因为很多顶点未访问，此时的松弛不是从源点开始的最短路径，只有上一次被访问过的顶点所连的边的松弛是有效的，对所有的边进行一次松弛操作，此时会有很多无效操作，因为很多边的松弛不是从源点开始的，故应该从上一次松弛后更新后的顶点开始松弛
   2. 故使用队列来记录每次松弛后更新过的顶点，下次从该顶点开始进行松弛操作，只要 minDist[to] > minDist[from] + value 则要对该边进行松弛操作，此时就要把 to 顶点加入队列，且为了防止顶点重复加入队列，故可以使用 visited数组 标记顶点是否在队列中
   3. 使用邻接表存储有向图，因为不仅要存放所达到的顶点，还要存放边的权值，所以在每个顶点的链表中的每个节点要包含可达的顶点以及该边的权值
   4. 不做队列优化的Bellman_ford算法要做n-1次对全部边的优化操作，故时间复杂度为O(V×E)，而当使用队列优化时，每次松弛只对上一次更新过的顶点(队列中的顶点)所连的边进行松弛操作，故时间复杂度不稳定，取决于结构的复杂，在理论上SPFA时间复杂度更胜一筹，但实际上，也要看图的稠密程度，如果 图很大且非常稠密的情况下，虽然 SPFA的时间复杂度接近Bellman_ford，但实际时间消耗 可能是 SPFA耗时更多，因为要做出队入队操作
   5. 不可以计算带负权回路的单源最短路径，可以计算带负权值的单源最短路径，Bellman_ford算法可以计算带负权值的单源最短路径，但不可以解决带负权回路的单源最短路径，因为存在负权回路时，此时经过松弛会一直使得最短路径变小；且可以使用Bellman_ford算法判断是否存在负权回路，当不存在时n-1次松弛后minDist数组就不会改变，否则会继续改变
3. Bellman_ford算法之判断负权回路
   1. 负权回路是指图中存在环且环上权值之和为负数，则此时存在负权回路，当存在负权回路时，求最短路径会导致在环里循环使得路径越来越小
   2. 可以使用Bellman_ford算法来判断是否有负权回路，因为Bellman_ford是对所有的边进行n-1次松弛操作，每次松弛对所有的边更新最短路径，且n-1次后就可以计算出从源点出发经过n-1条边可以达到顶点的最短路径，如果不存在负权回路，则在第n次松弛操作后，minDist数组的值是不会发生变化的，如果存在负权回路，则第n次松弛操作后，minDist的值会发生变化，故可以进行第n次松弛操作来判断是否存在负权回路
   3. 对于SPFA算法来说，因为是根据进入队列的节点来进行松弛操作的，故如果不存在负权回路，则每个节点最多加入 n-1 次队列。那么如果节点加入队列的次数 超过了 n-1次 ，那么该图就一定有负权回路
4. Bellman_ford之单源有限最短路(指定最多k条边后最短路径)
   1. k次松弛操作是指经过 k 条边后能到达的最短路径，要基于上一次松弛后的 minDist 数组才是经过 k 条边所到达的最短路径，否则将是大于 k 条边后到达的最短路径，如果不存在负权回路则无影响(多松弛几次结果不变)，但是如果存在负权回路则会导致结果不正确(多松弛几次的结果不同)
   2. Bellman_ford算法可以用来计算带负权值的单源最短路径，计算一个顶点到所有顶点的最短路径，K次松弛操作是指从源点经过最多K条边后所能达到节点的最短距离，故要求到所有顶点的最短距离，最多经过 k-1 条边，故进行 k-1 次松弛操作就可以实现
   3. 对于指定边长度的单源有限最短路径，只需要进行对应次数的松弛操作即可，对于不用队列优化的Bellman_ford，则只需要进行指定次数的松弛操作即可，对应SPFA则需要在队列中以层序遍历的形式进行K层松弛操作即可
   4. 因为每次松弛操作时可能会基于当前松弛操作更新后的minDist数组，但因为第 k 次松弛操作是经过最多 k 条边后能到达的最短路径，故应该基于上一次松弛后的 minDist 来更新，所以使用 minDist_copy 数组存放上一次更新后的 minDist 数组，而不是直接在当前的 minDist 进行松弛，否则就会导致不是经过 k 条边才到达
   5. 在使用SPFA时，使用队列存放上一次更新后的节点，则每一层表示多经过一条边，故使用层序遍历的方法来遍历队列中的节点(用pos标志某层末尾rear，然后遍历一层加入新的节点)，即每次直接遍历上一层遍历后更新的节点，此时就可以控制松弛k次（每遍历一层表示多经过一条边）
   6. SPFA算法时间复杂度不一定优于不进行队列优化的Bellman_ford算法(稠密图)，有时因为入队出队操作可能导致更慢，可以使用visited数组标识已经在队列中的节点，就可以避免重复遍历
   7. Dijkstra是计算单源最短路径，每次选择离源点最近且未遍历过的节点，故在有限边数条件下不一定可以到达指定的节点，即使存在路径，因为是选择最短路径，而可到达的路径不一定是最短，故不可以使用Dijkstra求有限最短路

4、复盘

不复盘等于白学！！！

---

学习和感想

Redis学习

1. Redis为什么快？高性能设计之epoll和IO多路复用

1. IO多路复用(进程) 解决的问题
   1. 在多路复用之前，采用同步阻塞网络IO模型，此时每来一个网络请求就要创建一个进程去处理(也要new一个新连接)，即一对一，会造成巨大的开销，且进程切换也会耗时
   2. 多路复用就是解决一对一下创建多进程问题，让一个进程可以同时处理多个TCP连接
   3. 可以采用循环遍历来监控多个IO，但是效率太低，故使用IO多路复用，当监控的IO有请求时才会进行处理
   4. IO多路复用是指对进程的复用
2. IO多路复用
   1. I/O：网络I/O
   2. 多路：多个客户端连接（多个TCP连接）
   3. 复用：用一个进程处理多条连接，可以实现单进程处理多个连接
   4. 实现一个进程可以处理多个不同的IO网络请求，且不使用轮询，而是使用中断方式(epoll函数，当某个请求准备好时才进行处理) ![[Pasted image 20241105080637.png]]
   5. IO多路复用就是用一个进程来处理多个IO连接的请求，实现：select(轮询效率低)、poll、epoll(中断效率高)
3. redis为什么快？IO多路复用
   1. redis的性能瓶颈不在CPU和内存，而是网络
   2. redis采用epoll()函数实现IO多路复用，实现一个进程处理多个IO连接，整体由epoll()函数接受多个IO请求，并依次放到队列中，然后由事件派发器将请求发送到主进程进行处理
   3. redis用一个主线程执行所有redis命令，用多个IO线程来处理IO请求，采用Reactor方式实现文件事件处理器，每一个网络连接都对应一个文件描述符FD，并注册到epoll中![[Pasted image 20241105082112.png]]
   4. redis的网络事件处理器，有多个IO连接，并使用IO多路复用程序监控多个连接并将请求放到队列中，然后由时间分派器从队列中依次将请求分派给处理器，因为队列的消费是单线程的，故Redis才叫单线程模型，且只有一个主线程执行Redis命令
   5. 此时使用多个IO线程同时处理多个IO请求，解决网络IO问题，然后使用单个工作主线程执行Redis命令，保证线程安全
4. Unix网络编程中的五种IO模型
   1. 同步和异步：服务提供者提供结果的方式
      1. 同步：顺序执行，发送请求后一直等待结果后才可以执行后续操作
      2. 异步：异步执行，不会一直等待，而是先执行别的，结果出来后再继续执行，一般通过回调通知
      3. 同步和异步区别在于服务提供者提供调用结果的消息通知方式上，同步是一直等待结果返回，异步是回调通知，不会一直等待
   2. 阻塞与非阻塞：服务调用者调用请求后的行为
      1. 阻塞：调用者一直等待而别的事情什么也不做，当前线程/进程会被挂起
      2. 非阻塞：调用者发出请求后，先去忙别的事情，不会阻塞当前线程/进程
      3. 阻塞和非阻塞谈论服务调用者(请求者)，重点在于等待消息时的行为
      4. 而同步与非同步谈论服务提供者，重点在于返回调用结果的方式（当面，回调）
   3. 组合方式![[Pasted image 20241105085115.png]]
   4. 阻塞IO、非阻塞IO、IO多路复用 ![[Pasted image 20241105082757.png]]
5. BIO、NIO、IO多路复用
   1. BIO：阻塞式IO（会一直阻塞等待数据）
      1. 单线程时一个服务端进程只可以同时处理一个Socket连接，无法同时处理多个socket请求，当有多个socket连接时，只会处理一个，其余全部阻塞，并将请求加入队列，当前的连接关闭后才会处理别的连接，且会直接全部执行某个连接的请求（可能造成瞬间压力过大） ![[Pasted image 20241105092758.png]]
      2. 多线程模型：服务端为每个socket连接均建立一个线程进行处理，此时read()只会阻塞对应的线程，此时可以同时处理多个socket连接，但要创建多个线程，如果某个线程等待数据则会阻塞，利用率不高，且创建线程要进入内核态，来回切换线程也会造成极大开销 ![[Pasted image 20241105095008.png]]![[Pasted image 20241105095737.png]]
      3. 阻塞式BIO，每次发起都会阻塞，会一直等待数据传输完成![[Pasted image 20241105100232.png]]
      4. 由用户进程调用recvfrom()函数从一个socket上获得数据，数据先从socket到OS内核，然后从内核到用户内存，用户进程在这两个阶段均阻塞，效率最低
      5. recvfrom()：接收一个数据并保存地址，阻塞式IO模型![[Pasted image 20241105090429.png]]
      6. BIO每发起一个请求就会阻塞，一直等待，而NIO是不阻塞，直接返回，不存在时返回error，用轮询替代阻塞
      7. Tomcat7之前就是使用BIO多线程来解决多连接，会为每个连接创建一个线程，造成极大开销
   2. NIO：非阻塞式IO（轮询代替阻塞）
      1. 阻塞式BIO，当数据未准备好时会一直阻塞等待；而非阻塞式NIO，当数据未准备好时会返回error，此时需要轮询去询问数据是否准备好，用轮询代替阻塞，且轮询期间占用CPU；NIO一切都是非阻塞（数据没有准备好时则直接返回error，有数据时阻塞读取） ![[Pasted image 20241105102534.png]]
      2. NIO下没有阻塞，用轮询代替阻塞，可以将多个连接加入数组中，遍历数组，如果read()没有返回error说明有数据则进行读取，否则继续遍历，此时就可以实现一个线程处理多个socket连接，但效率很低，要一直占用CPU进行轮询![[Pasted image 20241105103826.png]]
      3. 对于BIO阻塞式IO，此时每个线程只处理一个socket连接，会一直阻塞等待请求数据准备完成，故可以使用非阻塞NIO，当数据未准备好时，返回error，需要轮询去询问数据是否准备好，即用轮询代替阻塞，轮询期间占用CPU ![[Pasted image 20241105101540.png]]
      4. 使用异步非阻塞，当服务端发出接收数据的请求后，异步非阻塞，当数据准备好后再继续执行，此时可以转去处理别的连接的请求，可以同时处理多个连接
      5. NIO不需要为每个连接创建一个线程，一个单线程就可以处理多个socket连接，将多个socket连接存放到数组中，循环遍历每个连接是否有数据，用轮询代替阻塞，但会一直占用CPU，且每次都会遍历所有的连接，使用read()方法也会进行用户态到核心态的切换![[Pasted image 20241105104753.png]]![[Pasted image 20241105105003.png]]
      6. 将多个socket连接的遍历一次性传给内核去完成，内核是非阻塞的
   3. IO多路复用
      1. 解决的问题
         1. NIO非阻塞式时，此时可以一个线程同时处理多个socket连接，但需要轮询遍历所有的数组来判断是否有数据，且调用read()要进行用户态与核心态的转换，故引入了IO多路复用，其不需要遍历所有的socket，而是哪个请求处理哪个，且在内核态进行
         2. IO多路复用就是一个线程同时处理多个socket连接，且是触发式，谁发送请求就处理谁，不是轮询遍历
      2. 是什么
         1. 文件描述符FD来表示每个socket连接
            1. FD是一个索引，每当进程打开一个文件时，内核就会返回该文件的文件描述符FD，通过该FD去访问打开文件表中的文件
         2. IO多路复用：一个线程同时处理多个socket连接，且刚开始线程阻塞等待某个socket发出请求，而不是去轮询是否有数据，当某个有数据时，再使用工作线程对该请求进行处理，不是轮询是否有数据，而是等待连接发出处理请求，将对每个FD的遍历操作封装到内核态函数中，此时一次系统调用就可以完成之前多次的系统调用 ![[Pasted image 20241105125636.png]]
         3. IO多路复用技术(事件驱动IO)通过一种机制，使得一个进程可以同时监控多个描述符(socket连接)，一旦某个描述符IO就绪，就通知程序进行相应的操作，是由描述符通知程序进行操作，而不是程序去轮询描述符
         4. IO多路复用就是select\poll\epoll，等待多个描述符进入就绪状态
         5. 将客户端socket的FD注册进入epoll()，由epoll来监控哪个socket准备就绪（不需要轮询是否完成），并将事件返回到用户态，此时再由工作线程执行对应的操作，当无准备就绪时，epoll会阻塞，不会占用CPU，且epoll函数在内核中，不需要状态切换
      3. 能干嘛
         1. redis服务采用Reactor的方式实现文件事件处理器（每一个socket连接就是一个文件描述符），由IO多路复用程序(select、poll、epoll)来监控多个socket连接，当有准备就绪时就将事件发送到事件分派器，由事件分派器将事件分派到事件处理器中进行处理，因为Redis事件分派器的消费是单线程的，即只有一个事件处理器，故Redis才叫单线程模型 ![[Pasted image 20241105132454.png]]
         2. IO多路复用就是使用select\poll\epoll来实现，由epoll来监控多个socket连接的FD，当准备就绪时通知epoll将其放入队列中，然后由事件分派器将队列中的时间分派给处理器进行执行，从而实现一个线程可以同时处理多个socket连接，且epoll函数不是轮询且在在内核中运行![[Pasted image 20241105131406.png]]
         3. 只需要一个阻塞对象来监控多个socket连接的描述符，当没有准备就绪时就阻塞，当存在准备就绪时就从阻塞状态返回进行业务处理
         4. Reactor设计模式(Dispatcher)就是设置一个阻塞对象来监控所有的描述符，当有准备就续时就加入事件分派器中，由事件分派器将事件分派给事件处理器进行处理![[Pasted image 20241105132229.png]]
      4. IO多路复用程序：select、poll、epoll
         1. select
            1. 优点：select函数做到了一个线程同时处理多个socket连接FD，且相对于NIO，select减少了系统调用的开销，只需要一次select函数调用就可以在内核态中遍历所有的socket连接是否就绪，而不用每次都进入内核态遍历，但仍要调用系统调用进入内核态对就绪的FD进行读取![[Pasted image 20241105135305.png]]
            2. 缺点：使用1024位bitmap存放FD（故最多只可以遍历1024个socket连接的FD）、返回的FD置位数组rset不可以重复使用、仍要将FD数组拷贝到内核态进行遍历、不可以直接返回FD，而是返回置位后的FD数组rset，仍要O(N)遍历才可以知道哪个就绪![[Pasted image 20241105134942.png]]
            3. 就是将NIO中遍历socket数组是否有数据的操作封装到select函数中去内核态执行，此时只需要一次内核态切换就可以遍历所有的数组，返回对就绪的FD进行置位，返回FD数组，此时用户态就可以遍历FD数组得到就绪的socket连接，而不用每次判断都进入内核态
            4. 调用后会阻塞直到有描述符就绪，会将就绪的数组拷贝到内核空间，也就是当调用select时会在内核中判断哪个socketFD有数据，并对其FD在数组对应位置进行置位，然后返回，在用户态下直接遍历FD数组就可以得到就绪的FD，然后进行读取，而不用每次去内核态遍历是否就绪 ![[Pasted image 20241105133127.png]]![[Pasted image 20241105134454.png]]
         2. poll：对select优化，解决了bitmap大小限制和rset不可重用
            1. select是将NIO中轮询查找socket数组是否有数据的操作封装到内核中进行实现，减少了系统调用的次数
            2. poll函数对select函数进行了优化，解决了bitmap大小限制和rset不可重用（遍历后重置为0，使得可以重用） ![[Pasted image 20241105140322.png]]
            3. 但仍要将socket连接的FD数组拷贝到内核态才可以遍历，且无法直接返回就绪的FD，仍要在用户态进行O(N)遍历rset数组看哪个就绪
         3. epoll：最优方法
            1. epoll_create(size)：创建指定建议大小的数组来存放socket连接的FD
            2. epoll_ctl()：对指定数组下的某个FD进行相应的添加、删除、修改监控操作，每个socket连接的FD只在第一次拷贝进入内核态，其余时间遍历时不需要重复拷贝
            3. epoll_wait()：从指定的数组中监听设置的每个FD，当有请求时就将对应的事件放到event中，不需要全部进行遍历，然后直接返回总的事件个数K，此时就可以直接遍历event数组前k个就绪事件进行处理即可，不需要遍历整个FD数组，不需要遍历FD数组看是否置位，而是直接遍历event事件进行处理 ![[Pasted image 20241105192058.png]]
            4. epoll函数只将准备就绪的FD描述符的事件放到数组中，此时服务端就不需要遍历整个FD数组，而是直接遍历前k个事件执行处理即可，且epoll通过回调来监控每个FD
            5. 将FD拷贝操作epoll_ctl()和监控操作epoll_wait()分开进行，只有第一次执行epoll_ctl()时才会将FD拷贝到核心态，然后调用epoll_Wait()对FD进行监控，故只需要拷贝一次，且epoll_wait()使用回调的方法监控FD，不是遍历
         4. 对比![[Pasted image 20241105192655.png]]
6. 小总结
   1. Redis对三个IO多路复用函数均进行了保存，以实现对不同OS的兼容，且Redis在Linux系统上(epoll())效率最高
   2. IO多路复用就是一个线程同时处理多个socket连接，且之所以快，是因为其将原来的多次轮询系统调用(NIO)变为一次系统调用+内核态中遍历，然后返回到用户态，可以减少系统调用的时间，其epoll还将拷贝和遍历分开，当新添加一个连接时使用epoll_ctl()将新连接的FD加入FD数组中，只在第一次加入时拷贝，后面就不需要拷贝了，然后调用epoll_wait()对所有FD数组以回调的方式进行遍历，且直接返回event事件，此时用户态直接遍历event事件数组即可，不需要O(N)遍历整个FD数组看是否置位 ![[Pasted image 20241105193138.png]]
7. redis只有装在linux系统上（因为linux系统使用的是epoll()来实现IO多路复用）才可以发挥最大性能