zlog

计算机基础和算法

/笔记#学习#笔记
0%
分享
复制链接

计算机网络#

TCP#

三次握手#

image.png
  1. SYN 报文
  2. SYN+ACK 报文
  3. ACK 报文

三次握手能 防止历史连接的建立，也能减少双方不必要的资源开销，能帮助双方同步初始化序列号，而序列号能保证数据包不重复、不丢弃和按序传输

四次挥手#

image.png
  1. 客户端没有需要发送的数据打算关闭连接时，会发送一个 FIN 置为 1 的报文，FIN 报文，之后客户端进入 FIN_WAIT_1 状态
  2. 服务端收到该报文后，回复 ACK 报文，然后进入 CLOSED_WAIT 状态
  3. 客户端收到 ACK 应答报文后，进入 FIN_WAIT_2 状态
  4. 服务端处理完数据没有数据要发送之后，也向客户端发送 FIN 报文打算关闭连接，然后服务端进入 LAST_ACK 状态
  5. 客户端收到服务端的 FIN 报文后，回一个 ACK 报文，并进入 TIME_WAIT 状态，防止还有未送达的数据
  6. 服务端收到 ACK 报文之后，就进入 CLOSE 状态，至此服务端完成连接的关闭
  7. 客户端在经过 2MSL （最大报文生存时间）一段时间后，自动进入 CLOSE 状态，至此客户端也完成连接的关闭

每个方向都需要一个 FIN 和一个 ACK，所以四次握手

场景#

浏览器输入网址回车，页面呈现，网络部分发生了什么？#

输入网址后，浏览器先通过 DNS 把域名解析成 IP，然后通过 TCP/QUIC 建立连接，HTTPS 场景下进行 TLS 握手，再发送 HTTP 请求，服务端返回 HTML/CSS/JS 等资源，浏览器接收响应后继续请求依赖资源并完成渲染

用户输入 https://www.example.com 后，浏览器首先会解析 URL，识别协议是 https，域名是 www.example.com，端口默认是 443 。然后浏览器会判断缓存、HSTS、是否需要走代理等

接着进入 DNS 解析。浏览器需要把域名解析成 IP 地址。它会先查浏览器缓存、操作系统缓存、hosts 文件、本地 DNS 服务器，如果还没有结果，再递归/迭代查询根域名服务器、顶级域名服务器、权威 DNS 服务器，最终拿到 IP。DNS 本质就是把可读域名转换成机器可路由的 IP 地址

拿到 IP 后，如果是 HTTP/1.1 或 HTTP/2，一般会基于 TCP 建立连接，也就是三次握手：客户端发 SYN，服务端返回 SYN+ACK，客户端再发 ACK。连接建立后，如果是 HTTPS，还要进行 TLS 握手，协商加密算法、验证证书、生成会话密钥。HTTP 是应用层协议，通常运行在 TCP 或 TLS 加密的 TCP 连接之上；浏览器会发送 HTTP 请求，服务端返回 HTTP 响应，浏览器再根据响应内容渲染页面

最后，浏览器收到 HTML 后，会继续解析其中的 CSS、JS、图片、字体等资源，再发起新的网络请求。现代页面不是一次请求完成的，而是一个主文档请求加上一批静态资源请求

关于”翻墙经验”，比如 Clash 支持哪些方式，像系统代理，还有没有其他代理方式，那这些方式在计算机系统上是怎么工作的？#

我理解代理方式大致分为应用层代理和网络层代理。系统代理、HTTP 代理、SOCKS 5 更偏应用层，需要应用主动遵守代理配置；TUN/VPN 更偏网络层，通过虚拟网卡和路由表接管流量；透明代理则可以在网关侧做转发。Clash 这类工具核心能力是本地监听代理端口，然后根据域名、IP、GeoIP、规则集等进行分流

Clash 这类工具本质上可以理解为一个 本地代理客户端。它在本地监听一个端口，比如 HTTP 代理端口或 SOCKS 5 代理端口。应用程序把请求发给本地代理，本地代理再根据规则判断这条流量是直连、走某个代理节点还是拒绝访问
常见方式有几类：

  1. 系统代理
    系统代理是操作系统提供的代理配置。比如系统告诉应用：“http/https 请求请转发到 127.0.0.1:7890”。浏览器、部分客户端会读取这个配置，然后把请求交给本地代理。缺点是：不是所有程序都遵守系统代理，比如有些游戏、命令行工具、底层网络请求可能不走，所以才需要更彻底的模式如 TUN
  2. 浏览器代理/应用内代理
    只对某个应用生效，如浏览器自己配置代理，或者某个 IDE、Git、npm 单独配置代理。这种粒度更细，但管理麻烦
  3. SOCKS 5 代理
    SOCKS 5 更底层，可以代理 TCP 连接，不局限于 HTTP。应用把目标地址告诉 SOCKS 5，由代理帮它建立连接
  4. TUN 模式 / 虚拟网卡
    TUN 模式会在系统里创建一个虚拟网卡，把 IP 层的数据包捕获到用户态程序，再由代理程序根据规则转发。它比系统代理更“彻底”，因为即使应用不支持 HTTP/SOCKS 代理，只要它的流量走系统路由，也可能被 TUN 捕获
  5. VPN
    VPN 通常也会创建虚拟网卡，并修改系统路由表，把全部或部分流量导入加密隧道。它和普通系统代理的区别是：VPN 更偏网络层，代理更偏应用层或传输层
  6. 透明代理 / 网关代理
    比如在路由器或网关上做流量转发，终端设备不用单独设置代理，网关通过路由或防火墙规则把流量转给代理服务

系统代理时，访问 qq.com 会走代理吗？外网显示地区不在中国怎么解决？#

访问 qq.com 是否走代理，取决于规则。系统代理只是告诉应用可以把流量转发给本地代理，但最终代理客户端还会根据规则判断。比如规则模式下，qq.com 命中国内域名或 GeoIP CN 规则，就会直连；如果是 global 模式，就会走代理；如果应用不遵守系统代理，则可能完全不走代理（就可能需要 TUN 模式）

关于“在外网显示地区不在中国怎么解决”，思路是做智能分流：国内服务走国内出口，国外服务走海外出口。判断依据可以是域名规则、IP 地址库、GeoIP、ASN、DNS 解析结果、SNI、业务标签等。这样访问国内站点时使用中国大陆出口或直连，访问海外服务时再走海外出口

SSE#

SSE 是什么？它和 WebSocket 有什么区别？#

SSE 是一种服务端向客户端单向推送数据的技术，基于 HTTP 协议，与 WebSocket 的主要区别是：

SSE WebSocket
通信方向 单向（服务端­­­➔客户端） 双向
协议 HTTP 独立的 ws 协议
连接 普通 HTTP 连接 需要协议升级握手
数据格式 纯文本 文本或二进制
断线重连 浏览器自动重连 需要自己实现
兼容性 几乎所有浏览器 部分老浏览器不支持

SseEmitter 超时时间设置，连接断开怎么处理#

一般设置 5 分钟，有的工作流执行时间较长
做 LLM 流式输出时，生成一篇长文章可能要两三分钟，但也不能设太长，5-10 分钟基本能覆盖大部分正常请求也不会让异常连接占用太久资源
而连接断开有几种情况，并且每种情况都需要处理

  • 正常完成，数据发完了服务端主动调用 complete () 关闭连接，并触发 onCompletion 回调
  • 超时，超过了设置的时间还没完成，会出发 onTimeout 回调，这时候就应该主动关闭连接清理资源
  • 客户端主动断开，比较常见的情况如用户刷新页面、关闭浏览器页签或者网络波动，这时候再往 sseEmitter 里发送数据会抛 IOException，并且会触发 onError

算法#

HashSet 的 contains() 平均复杂度是 O(1) 关键词：无序，要求 O(n)`，判断是否存在，不关心原数组排序，连续数字

快慢指针
关键词：原地，不使用额外数组，保持相对顺序，删除/移动/过滤某类元素

左右双指针/对撞指针
每次根据某种规则，安全排除掉一边的情况，把原本 <sup>O(n^2)</sup> 的枚举优化成 O(n)
关键词：回文判断，两端往中间收缩，要求 n 但暴力 n^2，有序数组找目标和，

常用排序算法#

简单排序：冒泡、选择、插入，O (n2)
高级比较排序：快排、归并、堆排，O ($n\log n$)

快排平均最快，但最坏 O (n2)，不稳定
归并稳定，时间稳定O ($n\log n$)，但需要 O (n) 空间
堆排原地，最坏O ($n\log n$)，但不稳定

排序算法 平均时间 最坏时间 空间复杂度 是否稳定 是否原地
冒泡排序（相邻两两比较，把大的“冒泡”到后面） O (n2) O (n2) O (1) 稳定 原地
选择排序（每一轮从未排序区间中选择最小值，放到前面） O (n2) O (n2) O (1) 不稳定 原地
插入排序（把数组分成已排序区和未排序区，每次从未排序区拿一个元素插入到前面合适的位置） O (n2) O (n2) O (1) 稳定 原地
快速排序（设置一个基准值，把小于它的放左边，大于它的放右边，递归排序左右两边） O ($n\log n$) O (n2) O ($\log n$) 不稳定 原地
归并排序（把数组不断拆成两半，分别排好序，再合并两个有序数组） O ($n\log n$) O ($n\log n$) O (n) 稳定 非原地
堆排序（先建立大根堆，然后每次把堆顶最大值放到数组末尾，再调整堆） O ($n\log n$) O ($n\log n$) O (1) 不稳定 原地

Linux#

Linux 里的 mv 指令为什么有的快有的慢，有的 10 tb 的文件秒执行，而有的要卡很久？#

mv 的快慢和挂载点有关，如果源目录和目标目录在同一个挂载点、同一个文件系统内，mv 通常只是修改目录项，不搬真实数据，所以很快；如果源目录和目标目录属于不同挂载点，比如一个在 /data，一个在 /mnt/backup，背后可能是不同磁盘、不同分区或者网络存储，那么 mv 就会变成复制再删除，就会很慢

mv 是否秒完成，核心看是不是同一个文件系统；而不同硬盘、不同分区、不同挂载点往往意味着不同文件系统，所以容易导致 mv 从“改元数据”（修改目录项）变成“复制数据”