1.MySQL索引失效的主要场景

1.1违反最左前缀原则

对于复合索引(username, age)：

-- 能使用索引
SELECT * FROM users WHERE username = 'john';
SELECT * FROM users WHERE username = 'john' AND age = 25;

-- 不能使用索引（违反最左前缀）
SELECT * FROM users WHERE age = 25;

1.2 在索引列上使用函数或运算

-- 索引失效
SELECT * FROM users WHERE YEAR(create_time) = 2023;
SELECT * FROM users WHERE age + 1 = 26;

-- 可以改写为（使用索引）
SELECT * FROM users WHERE create_time BETWEEN '2023-01-01' AND '2023-12-31';

1.3 使用不等于(!=或<>)查询

-- 索引失效
SELECT * FROM users WHERE username != 'john';

1.4 使用IS NULL或IS NOT NULL

-- 可能使索引失效（取决于数据分布）
SELECT * FROM users WHERE email IS NULL;

1.5使用LIKE以通配符开头

-- 索引失效
SELECT * FROM users WHERE username LIKE '%ohn';

-- 可以使用索引
SELECT * FROM users WHERE username LIKE 'joh%';

1.6类型转换导致索引失效

-- 如果email是字符串类型，但传入数字
SELECT * FROM users WHERE email = 123; -- 索引失效

-- 应该使用
SELECT * FROM users WHERE email = '123';

1.7 OR条件使用不当

-- 如果age没有索引，整个查询索引失效
SELECT * FROM users WHERE username = 'john' OR age = 25;

1.8使用NOT IN或NOT EXISTS

-- 索引失效
SELECT * FROM users WHERE username NOT IN ('john', 'mary');

1.9数据量少时优化器可能不使用索引

当表中数据量很少时，MySQL可能选择全表扫描而非使用索引。

1.10索引列参与计算

-- 索引失效
SELECT * FROM users WHERE age * 2 = 50;

1.11使用全表扫描比使用索引更快时

MySQL优化器会根据统计信息决定是否使用索引，当预计要访问大量数据时，可能放弃使用索引。

1.12如何避免索引失效

1. 遵循最左前缀原则设计和使用复合索引
2. 避免在索引列上使用函数或计算
3. 合理设计查询语句，避免全表扫描
4. 使用EXPLAIN分析查询执行计划
5. 定期更新统计信息(ANALYZE TABLE)

2.MySQL聚簇索引与非聚簇索引的区别

2.1聚簇索引(Clustered Index)

1. 数据存储方式：

   • 索引的叶子节点直接存储完整的数据行
   • 表数据本身就是索引的一部分
   • 一个表只能有一个聚簇索引

2. 特点：

   • InnoDB的主键索引就是聚簇索引
   • 数据按索引键值的顺序物理存储
   • 查询通过主键访问非常高效(只需一次查找)

3. 优势：

   • 范围查询效率高(相邻数据物理上存储在一起)
   • 减少I/O操作(数据与索引在一起)

4. 示例：

   -- InnoDB表中，PRIMARY KEY就是聚簇索引
   CREATE TABLE users (
     id INT PRIMARY KEY,  -- 聚簇索引
     name VARCHAR(50)
   );
   

2.2非聚簇索引(Secondary Index/Non-clustered Index)

1. 数据存储方式：

   • 索引的叶子节点不包含完整数据行
   • 存储的是主键值(对于InnoDB)
   • 一个表可以有多个非聚簇索引

2. 特点：

   • 需要二次查找(回表)才能获取完整数据
   • 数据物理存储顺序与索引顺序无关
   • 普通索引、唯一索引都是非聚簇索引

3. 查询过程：

   • 先通过非聚簇索引找到主键值
   • 再通过主键值到聚簇索引中查找完整数据行

4. 示例：

   CREATE TABLE users (
     id INT PRIMARY KEY,  -- 聚簇索引
     name VARCHAR(50),
     INDEX idx_name (name)  -- 非聚簇索引
   );
   

2.3主要区别对比

2.4实际应用中的注意事项

1. InnoDB引擎如果没有显式定义主键：
   • 会选择一个唯一的非空索引作为聚簇索引
   • 如果没有这样的索引，会隐式创建一个自增的ROWID作为聚簇索引
2. 覆盖索引优化：
   • 如果查询的列都包含在非聚簇索引中，可以避免回表操作
   • 例如：SELECT id, name FROM users WHERE name = 'John' (如果idx_name包含name和id)
3. 主键选择的影响：
   • 使用自增ID作为主键有利于顺序插入
   • 使用UUID等随机值可能导致页分裂，影响性能

3.MySQL的四种事务隔离级别

3.1 读未提交(Read Uncommitted)

• 特点：事务可以读取其他事务未提交的数据

• 问题：会出现"脏读”(Dirty Read)

• 示例：

  -- 事务A
  UPDATE accounts SET balance = balance - 100 WHERE id = 1;
  -- 此时事务B可以看到这个未提交的修改
    
  -- 如果事务A回滚，事务B读取的就是无效数据(脏数据)
  

3.2 读已提交(Read Committed)

• 特点：事务只能读取其他事务已提交的数据

• 解决了：脏读问题

• 问题：会出现"不可重复读”(Non-repeatable Read)

• 示例：

  -- 事务A第一次查询
  SELECT balance FROM accounts WHERE id = 1; -- 返回1000
    
  -- 事务B更新并提交
  UPDATE accounts SET balance = 900 WHERE id = 1;
  COMMIT;
    
  -- 事务A第二次查询(同一事务内)
  SELECT balance FROM accounts WHERE id = 1; -- 返回900(结果不一致)
  

3.3 可重复读(Repeatable Read) - MySQL默认级别

• 特点：同一事务内多次读取同样数据结果一致

• 解决了：不可重复读问题

• 问题：会出现"幻读”(Phantom Read)

• 示例：

  -- 事务A第一次查询
  SELECT COUNT(*) FROM accounts WHERE balance > 800; -- 返回10
    
  -- 事务B插入新记录并提交
  INSERT INTO accounts(id, balance) VALUES(11, 1000);
  COMMIT;
    
  -- 事务A第二次查询
  SELECT COUNT(*) FROM accounts WHERE balance > 800; -- 仍返回10(防止不可重复读)
    
  -- 但如果是范围更新，会看到"幻行"
  UPDATE accounts SET status = 1 WHERE balance > 800;
  -- 会更新包括事务B新插入的行
  

3.4 串行化(Serializable)

• 特点：最高隔离级别，完全串行执行

• 解决了：幻读问题

• 问题：性能最低，并发性差

• 实现方式：所有SELECT语句自动转为SELECT ... FOR SHARE

• 示例：

  -- 事务A
  SELECT * FROM accounts WHERE balance > 800; -- 会对记录加共享锁
    
  -- 事务B尝试修改这些记录会被阻塞
  UPDATE accounts SET balance = 750 WHERE id = 1; -- 等待事务A提交
  

MySQL中的实现特点

1. InnoDB在RR级别下通过MVCC+间隙锁：

   • 实际上解决了大部分幻读问题
   • 纯读操作不会出现幻读
   • 写操作通过间隙锁防止幻读

2. 隔离级别设置：

   -- 查看当前隔离级别
   SELECT @@transaction_isolation;
      
   -- 设置隔离级别(会话级或全局)
   SET SESSION TRANSACTION ISOLATION LEVEL READ COMMITTED;
   SET GLOBAL TRANSACTION ISOLATION LEVEL REPEATABLE READ;
   

3. 各隔离级别与问题对照：

(* InnoDB的RR级别通过间隙锁基本解决了幻读问题)

4.InnoDB事务实现与MVCC机制详解

4.1 InnoDB事务基础实现

InnoDB通过以下核心组件实现事务：

1. 事务ID系统：
   • 每个事务启动时会被分配一个唯一的事务ID(trx_id)
   • 事务ID是自增的，用于判断事务的先后顺序
2. Undo日志：
   • 记录数据修改前的状态，用于回滚和MVCC
   • 组成版本链，支持多版本并发控制
3. Redo日志：
   • 记录物理页的修改，保证事务的持久性
   • Write-Ahead Logging(WAL)机制

4.2 MVCC(多版本并发控制)核心原理

4.2.1 MVCC核心数据结构

• 隐藏字段：

  • DB_TRX_ID(6字节)：记录创建/最后一次修改该行的事务ID
  • DB_ROLL_PTR(7字节)：回滚指针，指向Undo日志中的旧版本
  • DB_ROW_ID(6字节)：隐含的自增行ID(当无主键时)

• ReadView：

  struct ReadView {
    trx_id_t m_low_limit_id;  // 高水位：大于等于这个ID的事务都不可见
    trx_id_t m_up_limit_id;   // 低水位：小于这个ID的事务都可见
    trx_id_t m_creator_trx_id; // 创建该ReadView的事务ID
    ids_t m_ids;              // 活跃事务ID列表
    // ...
  };
  

4.2.2 MVCC工作流程

数据可见性判断规则：

1. 比较行的DB_TRX_ID与ReadView的m_up_limit_id
   • 如果DB_TRX_ID < m_up_limit_id，说明在快照前提交，可见
2. 检查DB_TRX_ID是否在活跃事务列表(m_ids)中
   • 如果在，表示创建该版本的事务还未提交，不可见
   • 如果不在，且DB_TRX_ID < m_low_limit_id，说明已提交，可见
3. 如果不可见，则通过DB_ROLL_PTR找到Undo日志中的旧版本，重复检查

不同隔离级别的ReadView生成时机：

• RC(读已提交)：每次SELECT都会生成新的ReadView
• RR(可重复读)：第一次SELECT时生成ReadView，后续复用

4.2.3 版本链示例

假设有数据行更新历史：

时间线：事务100 → 事务200 → 事务300 → 事务400(当前)
版本链：v1(100) ← v2(200) ← v3(300)

当事务400(trx_id=400)查询时：

1. 先访问v3(trx_id=300)
   • 300 < 400且不在活跃事务列表 → 可见
2. 如果300不可见，则通过roll_ptr找到v2，继续判断

4.3 MVCC与锁的协同工作

1. 当前读 vs 快照读：
   • 快照读：普通SELECT，使用MVCC
   • 当前读：SELECT FOR UPDATE/SHARE, UPDATE, DELETE等使用记录锁
2. 防止幻读的间隙锁：
   • 在RR级别下，InnoDB通过间隙锁(Gap Lock)防止幻读
   • 与MVCC配合实现完整的隔离性

4.4 MVCC的优势与限制

优势：

1. 读不加锁，读写不冲突
2. 通过版本链支持非阻塞的读操作
3. 实现不同隔离级别的语义

限制：

1. 需要维护多个数据版本，增加存储开销
2. 频繁的UPDATE操作会导致大量Undo日志
3. 长期运行的事务可能导致Undo无法清理

5.Redis持久化机制

5.1 RDB (Redis Database)

5.1.1 核心特点

• 全量快照：在指定时间间隔生成数据集的时间点快照
• 二进制格式：紧凑的单一文件，适合备份和灾难恢复
• 高性能：使用子进程进行持久化，主进程继续处理请求

5.1.2 触发方式

• 自动触发：通过配置文件设置保存规则

  save 900 1      # 900秒(15分钟)内至少有1个key变化
  save 300 10     # 300秒(5分钟)内至少有10个key变化
  save 60 10000   # 60秒内至少有10000个key变化
  

• 手动触发：

  • SAVE：阻塞主进程直到RDB完成
  • BGSAVE：后台异步执行

5.1.3 工作流程

1. 父进程fork子进程
2. 子进程将数据集写入临时RDB文件
3. 写入完成后替换旧RDB文件

5.1.4 优缺点

优点：

• 文件紧凑，恢复速度快
• 最大化Redis性能（异步方式）
• 适合大规模数据备份

缺点：

• 可能丢失最后一次快照后的数据
• 大数据集时fork过程可能阻塞服务

5.2 AOF (Append Only File)

5.2.1 核心特点

• 日志记录：记录每个写操作命令
• 可读性：文本格式，可通过redis-check-aof工具修复
• 更安全：最多丢失1秒数据（取决于同步频率）

5.2.2 配置选项

appendonly yes               # 启用AOF
appendfilename "appendonly.aof"  # 文件名

# 同步策略
appendfsync always    # 每个命令都同步，最安全但性能最低
appendfsync everysec  # 每秒同步一次（推荐）
appendfsync no        # 由操作系统决定

5.2.3 重写机制

• 目的：压缩AOF文件体积，去除冗余命令
• 触发方式：
  • 自动：auto-aof-rewrite-percentage 100（增长100%时触发）
  • 手动：BGREWRITEAOF
• 实现原理：
  1. 创建子进程
  2. 子进程将当前数据集转换为写命令序列
  3. 父进程将重写期间的新命令追加到新AOF文件
  4. 替换旧AOF文件

5.2.4 优缺点

优点：

• 数据安全性更高
• 可恢复性更好
• 日志文件易读易解析

缺点：

• 文件体积通常比RDB大
• 恢复速度较慢
• 写入性能略低于RDB

5.3 混合持久化（Redis 4.0+）

5.3.1 核心特点

• 结合RDB和AOF：AOF文件包含RDB头部和增量AOF日志

• 配置方式：

  aof-use-rdb-preamble yes
  

5.3.2 工作流程

1. 重写时先以RDB格式保存当前数据集
2. 后续将新命令以AOF格式追加
3. 文件前半部分是RDB二进制，后半部分是AOF文本

5.3.3 优势

• 快速加载RDB部分
• 更完整的AOF增量数据
• 兼具RDB的快速恢复和AOF的低丢失特性

5.4 选择策略

5.5 数据恢复流程

1. 重启时检查AOF文件是否存在
2. 如果存在则加载AOF（混合持久化时先加载RDB部分）
3. 如果AOF不存在则加载RDB文件
4. 加载完成后开始服务

6.Redis数据类型

6.1 基本数据类型

6.1.1 String（字符串）

• 特点：最基本的数据类型，二进制安全，最大512MB

• 常用命令：

  SET key value [EX seconds] [PX milliseconds] [NX|XX]
  GET key
  INCR key       # 原子递增
  DECR key       # 原子递减
  MSET k1 v1 k2 v2
  MGET k1 k2
  

• 应用场景：

  • 缓存HTML片段、JSON数据
  • 计数器（文章阅读量）
  • 分布式锁（SETNX）

6.1.2 Hash（哈希）

• 特点：键值对集合，适合存储对象

• 常用命令：

  HSET user:1000 name "John" age 30
  HGET user:1000 name
  HGETALL user:1000
  HINCRBY user:1000 age 1
  

• 应用场景：

  • 存储用户信息、商品信息等对象数据
  • 比String更节省空间（针对字段单独存储）

6.1.3 List（列表）

• 特点：有序、可重复的字符串集合，双向链表实现

• 常用命令：

  LPUSH list item1  # 左插入
  RPUSH list item2  # 右插入
  LPOP list         # 左弹出
  LRANGE list 0 -1  # 获取范围元素
  

• 应用场景：

  • 消息队列（LPUSH+BRPOP）
  • 最新消息排行（LPUSH+LTRIM）
  • 记录用户操作历史

6.1.4 Set（集合）

• 特点：无序、不重复的字符串集合，自动去重

• 常用命令：

  SADD tags redis database
  SMEMBERS tags
  SINTER set1 set2  # 交集
  SUNION set1 set2  # 并集
  

• 应用场景：

  • 标签系统
  • 共同好友（交集）
  • 唯一IP统计

6.1.5 ZSet（有序集合）

• 特点：不重复元素集合，每个元素关联一个分数(score)用于排序

• 常用命令：

  ZADD leaderboard 100 "player1" 200 "player2"
  ZRANGE leaderboard 0 -1 WITHSCORES
  ZREVRANK leaderboard "player1"  # 获取排名
  

• 应用场景：

  • 排行榜系统
  • 带权重的消息队列
  • 范围查询（如时间范围的事件）

6.2 高级数据类型（Redis模块提供）

6.2.1 Bitmaps（位图）

• 本质：String类型的位操作

• 常用命令：

  SETBIT online 1001 1  # 用户1001上线
  GETBIT online 1001    # 检查是否在线
  BITCOUNT online       # 统计在线用户数
  

• 应用场景：

  • 用户在线状态
  • 每日活跃用户统计

6.2.2 HyperLogLog

• 特点：用于基数统计（不重复元素数量），误差率0.81%

• 常用命令：

  PFADD ip_20230501 "192.168.1.1" "192.168.1.2"
  PFCOUNT ip_20230501  # 估算基数
  

• 应用场景：

  • 大规模UV统计
  • 搜索词去重计数

6.2.3 GEO（地理空间）

• 本质：基于ZSet实现的地理位置存储

• 常用命令：

  GEOADD cities 116.405285 39.904989 "Beijing"
  GEODIST cities "Beijing" "Shanghai" km
  GEORADIUS cities 116 39 100 km  # 附近100km的城市
  

• 应用场景：

  • 附近的人/地点
  • 地理位置计算

6.2.4 Stream（流，Redis 5.0+）

• 特点：消息队列，支持消费组

• 常用命令：

  XADD mystream * sensor-id 1234 temp 19.8
  XREAD COUNT 2 STREAMS mystream 0
  XGROUP CREATE mystream mygroup $
  

• 应用场景：

  • 消息队列系统
  • 事件溯源

6.3 数据类型选择建议

6.4 内部编码优化

Redis会根据数据特征自动选择最优的内部编码（可通过OBJECT ENCODING key查看）：

• String：int/embstr/raw
• Hash：ziplist/hashtable
• List：quicklist（3.2+）
• Set：intset/hashtable
• ZSet：ziplist/skiplist

7.Redis List底层和时间复杂度

7.1 底层实现演变

Redis List 的底层实现经历了几个重要版本的优化：

7.1.1 Redis 3.2 之前

• 小列表：使用 ziplist（压缩列表）
  • 连续内存空间存储
  • 适合元素较少且元素较小时（默认配置：元素数<512且元素大小<64字节）
• 大列表：使用 双向链表（linkedlist）
  • 每个节点独立分配内存
  • 包含指向前后节点的指针（prev/next）

7.1.2 Redis 3.2 及之后版本

• 统一采用 quicklist 结构
  • 本质上是 ziplist 组成的双向链表
  • 平衡了内存效率和操作性能

7.2、QuickList 详细结构

struct quicklist {
    quicklistNode *head;    // 头节点指针
    quicklistNode *tail;    // 尾节点指针
    unsigned long count;    // 元素总数
    unsigned long len;      // quicklistNode节点数
    int fill : 16;          // ziplist大小限制（由list-max-ziplist-size配置）
    unsigned int compress : 16; // 压缩深度（由list-compress-depth配置）
};

struct quicklistNode {
    quicklistNode *prev;    // 前驱指针
    quicklistNode *next;    // 后继指针
    unsigned char *zl;      // 指向ziplist的指针
    unsigned int sz;        // ziplist字节大小
    unsigned int count : 16;// ziplist元素计数
    unsigned int encoding : 2; // 编码方式（RAW=1, LZF=2）
    unsigned int container : 2; // 容器类型（NONE=1, ZIPLIST=2）
    unsigned int recompress : 1; // 是否需要重新压缩
};

7.3 操作时间复杂度分析

7.4 查找操作（LINDEX）的详细过程

1. 确定节点位置：
   • 根据index判断是从头还是从尾开始查找
   • 计算目标元素在哪个quicklistNode中
2. 在ziplist中查找：
   • ziplist是连续内存空间
   • 需要遍历才能找到指定位置的元素
   • 最坏情况下需要遍历所有ziplist
3. 性能优化：
   • Redis会记录上次访问的位置（优化连续访问）
   • 对于靠近头尾的访问（index=0或-1）有特殊优化

7.5 设计优势

1. 内存效率：

   • ziplist减少了小元素的内存碎片
   • 压缩列表可以节省指针占用的空间（每个元素节省16字节）

2. 性能平衡：

   • 头部/尾部操作保持O(1)复杂度
   • 通过控制ziplist大小限制最坏情况下的性能

3. 可配置性：

   list-max-ziplist-size -2   # 单个ziplist大小限制（-2表示8KB）
   list-compress-depth 1      # 两端不压缩的节点数
   

7.6 与其它数据结构对比

8.操作系统通信方式

8.1 进程间通信(IPC)方式

8.1.1 管道(Pipe)

• 特点：

  • 单向通信，半双工
  • 只能用于父子进程或兄弟进程间
  • 基于字节流传输

• 类型：

  • 匿名管道：int pipe(int fd[2])
  • 命名管道(FIFO)：mkfifo命令创建

• 示例：

  int fd[2];
  pipe(fd);  // fd[0]读端，fd[1]写端
  

8.1.2 消息队列(Message Queue)

• 特点：

  • 消息链表结构，存储在内核
  • 按消息类型读取，克服了管道只能承载无格式字节流的缺点
  • POSIX和System V两种标准

• 相关函数：

  msgget()  // 创建/获取队列
  msgsnd()  // 发送消息
  msgrcv()  // 接收消息
  

8.1.3 共享内存(Shared Memory)

• 特点：
  • 最高效的IPC方式，进程直接访问同一块内存
  • 需要同步机制配合（如信号量）
• 实现步骤：
  1. 创建共享内存段 shmget()
  2. 附加到进程地址空间 shmat()
  3. 分离 shmdt()
  4. 控制 shmctl()

8.1.4 信号量(Semaphore)

• 作用：

  • 用于进程间同步，不用于数据传输
  • 解决资源共享的互斥访问

• 操作：

  semget()  // 创建/获取信号量集
  semop()   // P/V操作
  

8.1.5 信号(Signal)

• 特点：
  • 异步通知机制，用于通知进程发生了某事件
  • 如 SIGKILL, SIGTERM 等
• 处理方式：
  • 忽略信号
  • 捕获并处理
  • 执行默认动作

8.1.6 套接字(Socket)

• 特点：
  • 可用于不同主机间的进程通信
  • 全双工通信
• 类型：
  • 流式套接字(SOCK_STREAM)
  • 数据报套接字(SOCK_DGRAM)

8.1.7 内存映射(Memory Mapping)

• 原理：

  • 将文件映射到进程地址空间
  • 多个进程可映射同一文件实现共享

• 函数：

  mmap()  // 创建映射
  munmap() // 解除映射
  

8.2 线程间通信方式

8.2.1 共享变量

• 通过全局变量或堆内存共享数据
• 需要配合同步机制（互斥锁等）

8.2.2 互斥锁(Mutex)

pthread_mutex_lock(&mutex);
// 临界区代码
pthread_mutex_unlock(&mutex);

8.2.3 条件变量(Condition Variable)

pthread_cond_wait(&cond, &mutex); // 等待条件
pthread_cond_signal(&cond);       // 通知等待线程

8.2.4 读写锁(Read-Write Lock)

pthread_rwlock_rdlock(&lock);  // 读锁
pthread_rwlock_wrlock(&lock);  // 写锁

8.2.5 线程信号量(Semaphore)

• 类似进程信号量，但更轻量级

sem_init(&sem, 0, 1);  // 初始化
sem_wait(&sem);        // P操作
sem_post(&sem);        // V操作

8.3 通信方式对比

8.4 选择建议

1. 高性能场景：共享内存+信号量
2. 结构化数据：消息队列
3. 简单通信：管道
4. 跨主机通信：套接字
5. 线程同步：互斥锁/条件变量

9.死锁产生的条件

9.1 四个必要条件（Coffman条件）

9.1.1 互斥条件（Mutual Exclusion）

• 定义：资源一次只能由一个进程/线程占有，其他请求者必须等待
• 示例：打印机、共享变量等排他性资源
• 特点：某些资源本质就是互斥的，无法同时共享

9.1.2 占有并等待（Hold and Wait）

• 定义：进程已经持有至少一个资源，同时又在等待获取其他被占用的资源
• 示例：
  • 进程A持有资源1，请求资源2
  • 进程B持有资源2，请求资源1

9.1.3 非抢占条件（No Preemption）

• 定义：已分配给进程的资源不能被其他进程强行夺取，必须由进程自行释放
• 特点：
  • 资源只能自愿释放
  • 操作系统不能强行回收已分配资源

9.1.4 循环等待条件（Circular Wait）

• 定义：存在一个进程等待的循环链，每个进程都在等待下一个进程所占用的资源

• 示例：

  进程A → 持有资源1，等待资源2
  进程B → 持有资源2，等待资源1
  

• 表现形式：等待图中存在环

10.select、poll、epoll的区别

10.1 基本概念对比

10.2 底层实现原理

10.2.1 select

int select(int nfds, fd_set *readfds, fd_set *writefds,
           fd_set *exceptfds, struct timeval *timeout);

// 工作流程：
// 1. 用户态拷贝fd_set到内核
// 2. 内核线性扫描所有fd
// 3. 标记可读写状态
// 4. 拷贝修改后的fd_set回用户态

问题：

• 每次调用需要重置fd_set
• 每次都需要全量拷贝
• 遍历复杂度O(n)

10.2.2 poll

int poll(struct pollfd *fds, nfds_t nfds, int timeout);

struct pollfd {
    int fd;         // 文件描述符
    short events;   // 监听的事件
    short revents;  // 返回的事件
};

改进：

• 使用pollfd数组，突破1024限制
• 分离了监听事件和返回事件
• 但仍然需要轮询所有fd

10.2.3 epoll

int epoll_create(int size);
int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);
int epoll_wait(int epfd, struct epoll_event *events,
               int maxevents, int timeout);

// 核心改进：
// 1. 使用红黑树管理fd(O(logN)查找)
// 2. 就绪列表保存活跃fd
// 3. 回调机制通知内核事件

10.3 性能对比

连接数 vs 性能

• 少量连接：三者性能相当
• 万级连接：epoll优势明显
• 十万级连接：select/poll基本不可用

关键差异点

10.4 边缘触发(ET) vs 水平触发(LT)

epoll特有模式：

struct epoll_event {
    uint32_t events;  // EPOLLIN | EPOLLET 表示边缘触发
    epoll_data_t data;
};

ET模式注意事项：

1. 必须使用非阻塞IO
2. 必须一次性读完所有数据(直到read返回EAGAIN)
3. 容易遗漏事件，需要更严谨的代码逻辑

10.5 编程接口对比

典型select代码

fd_set read_fds;
while(1) {
    FD_ZERO(&read_fds);
    FD_SET(sockfd, &read_fds);
    select(sockfd+1, &read_fds, NULL, NULL, NULL);
    if(FD_ISSET(sockfd, &read_fds)) {
        // 处理数据
    }
}

典型epoll代码

int epfd = epoll_create(1);
struct epoll_event ev, events[MAX_EVENTS];
ev.events = EPOLLIN;
ev.data.fd = sockfd;
epoll_ctl(epfd, EPOLL_CTL_ADD, sockfd, &ev);

while(1) {
    int nfds = epoll_wait(epfd, events, MAX_EVENTS, -1);
    for(int i = 0; i < nfds; i++) {
        if(events[i].data.fd == sockfd) {
            // 处理数据
        }
    }
}

10.6 选型建议

1. 跨平台需求：使用poll(比select更现代)
2. Linux高并发：必须使用epoll
3. 低延迟场景：epoll+ET模式
4. 简单应用：select/poll足够

11.http1.0和2.0的区别

11.1 基础架构对比

11.2 关键差异详解

11.2.1 多路复用 (Multiplexing)

• HTTP/1.0问题：

  • 每个请求需要单独TCP连接（开启Keep-Alive后略改善）
  • 线头阻塞(Head-of-Line Blocking)：顺序处理请求

• HTTP/2.0解决方案：

  graph TD
    A[流1] -->|帧1| B[TCP连接]
    C[流2] -->|帧2| B
    D[流3] -->|帧3| B
  

  • 单个TCP连接上并行交错传输多个请求/响应
  • 通过二进制分帧实现（数据拆分为帧，带流ID标识）

11.2.2 二进制分帧层

• HTTP/1.0：

  GET /index.html HTTP/1.0
  Host: example.com
  

  纯文本格式，按行解析

• HTTP/2.0：

  +-----------------------------------------------+
  | Length (24) | Type (8) | Flags (8) | R (1) | Stream ID (31) |
  |                   Frame Payload (24)          |
  +-----------------------------------------------+
  

  二进制格式帧结构，更高效解析

11.2.3 头部压缩 (HPACK)

• HTTP/1.0问题：
  • 每次请求重复发送相同头部（Cookie/User-Agent等）
  • 头部未压缩，占用大量带宽
• HTTP/2.0解决方案：
  • 使用HPACK算法压缩
  • 维护静态表(61个常用头字段)和动态表
  • 差分编码减少重复传输

11.2.4 服务器推送 (Server Push)

sequenceDiagram
    Client->>Server: 请求/index.html
    Server->>Client: 返回/index.html + 推送style.css
    Server->>Client: 推送script.js

• 服务端可主动推送资源，减少往返延迟
• 客户端可通过RST_STREAM拒绝推送

11.2.5请求优先级

• 可设置流的依赖关系和权重

  Stream 1: 依赖根流，权重=16
  Stream 2: 依赖流1，权重=8
  

• 确保关键资源优先传输

11.3 性能对比示例

加载包含20个资源的页面：

11.4 兼容性与部署

1. 协议协商机制：
   • TLS使用ALPN扩展
   • 明文HTTP通过Upgrade头部协商
2. 必须使用HTTPS吗？
   • 标准不强制，但所有主流浏览器只支持HTTP/2 over TLS
3. 降级处理：
   • 当客户端不支持时，服务器自动回退到HTTP/1.x

11.5 实际应用建议

1. 迁移到HTTP/2.0：
   • 无需修改应用代码（二进制分帧对应用层透明）
   • 但可优化资源加载策略（减少文件合并）
2. 优化方向：
   • 减少域名分片（HTTP/2下多个域名反而降低性能）
   • 停止使用雪碧图/合并脚本（充分利用多路复用）
   • 合理使用服务器推送（避免过度推送）

12.对称加密常用的算法

12.1 主流对称加密算法

12.1.1 AES (Advanced Encryption Standard)

• 密钥长度：128/192/256位
• 分组大小：128位
• 轮数：10/12/14（取决于密钥长度）
• 特点：
  • 目前最安全的对称加密标准
  • 取代了旧的DES标准
  • 被美国政府选为联邦信息处理标准(FIPS)
• 工作模式：
  • ECB（不推荐）
  • CBC（最常用）
  • GCM（带认证的加密）

12.1.2 DES (Data Encryption Standard)

• 密钥长度：56位（已不安全）
• 分组大小：64位
• 轮数：16
• 现状：
  • 已被证明可暴力破解
  • 仅用于遗留系统
  • 3DES是其改进版（三个DES组合）

12.1.3 3DES (Triple DES)

• 密钥长度：168位（实际安全强度约112位）
• 加密过程：加密→解密→加密（EDE模式）
• 特点：
  • 比DES更安全
  • 性能比AES差
  • 正在被逐步淘汰

12.1.4 ChaCha20

• 密钥长度：256位
• 特点：
  • 由Google设计
  • 移动设备上性能优于AES
  • 与Poly1305认证结合使用
  • TLS 1.3标准支持

12.1.5 RC4 (已弃用)

• 类型：流密码
• 密钥长度：40-2048位
• 安全问题：
  • 已被证明存在严重漏洞
  • 2015年被RFC禁止在TLS中使用

12.2 算法对比表

12.3 工作模式选择

1. CBC (Cipher Block Chaining)

• 需要初始化向量(IV)
• 并行度低
• 易受填充预言攻击

2. GCM (Galois/Counter Mode)

• 认证加密(AEAD)
• 支持并行计算
• TLS 1.2+推荐模式

3. ECB (Electronic Codebook)

• 简单但不安全
• 相同明文生成相同密文
• 仅适用于随机数据加密

12.4 代码示例

AES-CBC加密示例（Python）

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from Crypto.Random import get_random_bytes

key = get_random_bytes(16)  # AES-128
iv = get_random_bytes(16)

# 加密
cipher = AES.new(key, AES.MODE_CBC, iv)
plaintext = b"Hello World!"
ciphertext = cipher.encrypt(pad(plaintext, AES.block_size))

# 解密
cipher = AES.new(key, AES.MODE_CBC, iv)
decrypted = unpad(cipher.decrypt(ciphertext), AES.block_size)

ChaCha20-Poly1305示例（Go）

package main

import (
	"crypto/rand"
	"golang.org/x/crypto/chacha20poly1305"
)

func main() {
	key := make([]byte, chacha20poly1305.KeySize)
	rand.Read(key)
	
	aead, _ := chacha20poly1305.New(key)
	nonce := make([]byte, aead.NonceSize())
	
	plaintext := []byte("Hello World!")
	ciphertext := aead.Seal(nil, nonce, plaintext, nil)
	
	decrypted, _ := aead.Open(nil, nonce, ciphertext, nil)
}

12.5 选型建议

1. 通用场景：AES-256-GCM
2. 移动/Web：ChaCha20-Poly1305
3. 遗留系统：3DES（尽快迁移）
4. 避免使用：DES、RC4、ECB模式

13.HTTPS的加密方式，以及如何通信

13.1 HTTPS使用的加密技术

13.1.1 混合加密体系

HTTPS采用对称加密和非对称加密相结合的方式：

13.1.2 核心加密组件

• SSL/TLS协议：安全传输层协议（现主要使用TLS 1.2/1.3）
• 数字证书：由CA签发，验证服务器身份
• 密钥交换：ECDHE或RSA密钥交换

13.2 HTTPS完整通信流程

13.2.1 TCP三次握手

客户端 → 服务器：SYN
客户端 ← 服务器：SYN-ACK 
客户端 → 服务器：ACK

13.2.2 TLS握手（以TLS 1.2为例）

步骤1：Client Hello

客户端 → 服务器：
- 支持的TLS版本
- 客户端随机数(random_C)
- 支持的加密套件列表
- SNI（服务器名称指示）

步骤2：Server Hello

客户端 ← 服务器：
- 选择的TLS版本
- 服务器随机数(random_S)
- 选择的加密套件
- 服务器证书（包含公钥）
- （可选）证书请求

步骤3：验证证书

• 客户端验证证书：
  1. 证书链验证
  2. 有效期检查
  3. CRL/OCSP吊销检查
  4. 域名匹配验证

步骤4：密钥交换

客户端 → 服务器：
- 预主密钥(pre_master_secret)（用服务器公钥加密）
- （ECDHE）客户端密钥交换参数

步骤5：生成会话密钥

双方通过以下参数生成相同的会话密钥：

master_secret = PRF(pre_master_secret, "master secret", random_C + random_S)

步骤6：握手完成

客户端 ←→ 服务器：
- 切换加密通信
- 验证握手消息完整性

13.2.3 加密数据传输

使用协商好的对称密钥加密HTTP数据：

加密数据 = AES(HTTP数据, 会话密钥)

13.3 TLS 1.3的改进（2018年发布）

1. 简化握手：握手时间减少到1-RTT（甚至0-RTT）
2. 移除不安全算法：去除RSA密钥传输、SHA-1、CBC模式等
3. 前向安全：默认使用ECDHE密钥交换
4. 加密SNI：解决隐私泄露问题

13.4 密钥交换过程详解（ECDHE为例）

sequenceDiagram
    Client->>Server: ClientHello (支持ECDHE)
    Server->>Client: ServerHello + ECDHE参数 + 证书
    Client->>Server: ECDHE客户端参数
    Note over Client,Server: 双方独立计算得出相同的会话密钥

1. 服务器生成椭圆曲线参数：(curve, G, pub_S = d_S * G)
2. 客户端生成：pub_C = d_C * G
3. 双方计算共享密钥：shared_key = d_C * pub_S = d_S * pub_C

13.5 数字证书验证流程

1. 获取证书链：从服务器证书到根CA证书
2. 验证签名：用上级CA公钥验证下级证书签名
3. 检查有效期：证书是否在有效期内
4. 检查吊销状态：通过CRL或OCSP协议
5. 域名匹配：确保证书中的域名与访问域名一致

13.6 HTTPS数据包结构示例

| IP头部 | TCP头部 | TLS记录层 | 加密的HTTP数据 |
                    ↓
TLS记录层包含：
| 内容类型 | 版本 | 长度 | 加密数据 |

13.7 常见加密套件解析

示例：TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256

• 密钥交换：ECDHE
• 身份验证：RSA
• 对称加密：AES-128-GCM
• 散列算法：SHA-256

13.8 部署建议

1. 证书选择：

   • 使用RSA 2048位或ECC 256位
   • 选择受信任的CA机构

2. 协议配置：

   • 禁用TLS 1.0/1.1
   • 优先使用TLS 1.3

3. 加密套件顺序：

   ssl_ciphers 'TLS_AES_128_GCM_SHA256:TLS_AES_256_GCM_SHA384:ECDHE-ECDSA-AES128-GCM-SHA256';
   

14.四次挥手的过程、为啥要等待2MSL

14.1 四次挥手完整过程

sequenceDiagram
    participant Client as 主动关闭方(客户端)
    participant Server as 被动关闭方(服务器)
    
    Client->>Server: FIN=1, seq=u (FIN_WAIT_1)
    Server->>Client: ACK=1, ack=u+1 (CLOSE_WAIT)
    Server->>Client: FIN=1, seq=v, ack=u+1 (LAST_ACK)
    Client->>Server: ACK=1, ack=v+1 (TIME_WAIT)

详细步骤说明：

1. 第一次挥手(FIN_WAIT_1)：
   • 主动关闭方发送FIN报文，序列号为u
   • 进入FIN_WAIT_1状态
2. 第二次挥手(CLOSE_WAIT)：
   • 被动关闭方收到FIN，回复ACK确认(ack=u+1)
   • 进入CLOSE_WAIT状态
   • 主动关闭方收到ACK后进入FIN_WAIT_2状态
3. 第三次挥手(LAST_ACK)：
   • 被动关闭方处理完剩余数据后，发送FIN报文，序列号为v
   • 进入LAST_ACK状态
4. 第四次挥手(TIME_WAIT)：
   • 主动关闭方收到FIN后，发送ACK确认(ack=v+1)
   • 进入TIME_WAIT状态，等待2MSL后关闭
   • 被动关闭方收到ACK后立即关闭连接

14.2 TIME_WAIT状态存在的必要性

1. 确保最后一个ACK到达对端（可靠性）

• 如果最后一个ACK丢失，被动关闭方会重传FIN

• 主动关闭方在TIME_WAIT期间能响应这个重传的FIN

• 如果没有TIME_WAIT：

  graph LR
    A[ACK丢失] --> B[被动方重传FIN]
    B --> C[主动方已关闭无法响应]
    C --> D[被动方无法正常关闭]
  

2. 让网络中残留的旧报文失效（避免混淆）

• MSL(Maximum Segment Lifetime)：报文最大生存时间（通常30秒-2分钟）
• 等待2MSL确保两个方向上的旧报文都从网络中消失
• 防止旧连接的延迟报文被新连接误接收

14.3 2MSL等待时间的计算

• MSL定义：RFC 793建议为2分钟，实际实现常为30秒/60秒

• 2MSL时长：

  • Linux：60秒（MSL=30秒）
  • Windows：240秒（MSL=120秒）

• 计算公式：

  TIME_WAIT持续时间 = 2 × MSL
  

14.4 TIME_WAIT的影响与优化

高并发场景问题

• 大量连接处于TIME_WAIT状态
• 占用端口资源，可能导致新连接无法建立

优化方案

1. 内核参数调整：

   # 减少TIME_WAIT时间（Linux）
   echo 30 > /proc/sys/net/ipv4/tcp_fin_timeout
      
   # 启用TIME_WAIT重用
   echo 1 > /proc/sys/net/ipv4/tcp_tw_reuse
   

2. 连接池管理：

   • 避免频繁创建短连接
   • 使用长连接减少握手/挥手次数

3. SO_LINGER选项：

   struct linger so_linger;
   so_linger.l_onoff = 1;  // 启用
   so_linger.l_linger = 0; // 直接发送RST跳过TIME_WAIT
   setsockopt(sockfd, SOL_SOCKET, SO_LINGER, &so_linger, sizeof(so_linger));
   

14.5 异常情况处理

1. 主动关闭方崩溃

• 未发送最后一个ACK：被动关闭方等待重传超时后关闭

2. 被动关闭方崩溃

• 主动关闭方在FIN_WAIT_2状态有超时机制（tcp_fin_timeout）

3. 同时关闭

sequenceDiagram
    participant A as 主机A
    participant B as 主机B
    A->>B: FIN
    B->>A: FIN
    A->>B: ACK
    B->>A: ACK

双方都经历FIN_WAIT和CLOSING状态

14.6 与三次握手的对比

15.多线程的实现

15.1 基础实现方式

15.1.1 继承Thread类

class MyThread extends Thread {
    @Override
    public void run() {
        System.out.println("线程运行中: " + Thread.currentThread().getName());
    }
}

// 使用
MyThread thread = new MyThread();
thread.start();  // 启动线程

15.1.2 实现Runnable接口（推荐）

class MyRunnable implements Runnable {
    @Override
    public void run() {
        System.out.println("Runnable线程: " + Thread.currentThread().getName());
    }
}

// 使用
Thread thread = new Thread(new MyRunnable());
thread.start();

15.1.3 实现Callable接口（带返回值）

class MyCallable implements Callable<String> {
    @Override
    public String call() throws Exception {
        return "Callable结果: " + Thread.currentThread().getName();
    }
}

// 使用
FutureTask<String> futureTask = new FutureTask<>(new MyCallable());
Thread thread = new Thread(futureTask);
thread.start();
String result = futureTask.get();  // 获取返回值

15.2 线程池实现（Executor框架）

15.2.1 常用线程池类型

// 1. 固定大小线程池
ExecutorService fixedPool = Executors.newFixedThreadPool(5);

// 2. 可缓存线程池
ExecutorService cachedPool = Executors.newCachedThreadPool();

// 3. 单线程池
ExecutorService singleThreadPool = Executors.newSingleThreadExecutor();

// 4. 定时任务线程池
ScheduledExecutorService scheduledPool = Executors.newScheduledThreadPool(3);

15.2.2 使用示例

ExecutorService pool = Executors.newFixedThreadPool(3);

// 提交Runnable任务
pool.execute(() -> {
    System.out.println("Lambda Runnable: " + Thread.currentThread().getName());
});

// 提交Callable任务
Future<String> future = pool.submit(() -> {
    return "Lambda Callable: " + Thread.currentThread().getName();
});

// 关闭线程池
pool.shutdown();

15.3 Java并发工具类

15.3.1 同步控制

// 1. synchronized关键字
public synchronized void syncMethod() { /*...*/ }

// 2. ReentrantLock
Lock lock = new ReentrantLock();
lock.lock();
try {
    // 临界区代码
} finally {
    lock.unlock();
}

// 3. Semaphore
Semaphore semaphore = new Semaphore(5); // 允许5个线程同时访问
semaphore.acquire();
try {
    // 受限资源访问
} finally {
    semaphore.release();
}

15.3.2 线程协作

// 1. CountDownLatch
CountDownLatch latch = new CountDownLatch(3);
// 主线程等待
latch.await();
// 工作线程完成时
latch.countDown();

// 2. CyclicBarrier
CyclicBarrier barrier = new CyclicBarrier(3, () -> {
    System.out.println("所有线程到达屏障");
});
// 工作线程中
barrier.await();

// 3. Phaser (更灵活的屏障)
Phaser phaser = new Phaser(3); // 注册3个线程
phaser.arriveAndAwaitAdvance();

15.4 线程安全集合

15.4.1 并发集合类

// 1. ConcurrentHashMap
Map<String, String> concurrentMap = new ConcurrentHashMap<>();

// 2. CopyOnWriteArrayList
List<String> copyOnWriteList = new CopyOnWriteArrayList<>();

// 3. BlockingQueue
BlockingQueue<String> blockingQueue = new LinkedBlockingQueue<>(10);
blockingQueue.put("item");  // 阻塞插入
String item = blockingQueue.take();  // 阻塞获取

15.4.2 使用示例

ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();
map.compute("key", (k, v) -> v == null ? 1 : v + 1);

15.5 Java内存模型(JMM)与volatile

15.5.1 volatile关键字

private volatile boolean running = true;

public void stop() {
    running = false;  // 对其他线程立即可见
}

15.5.2 原子类

AtomicInteger counter = new AtomicInteger(0);
counter.incrementAndGet();  // 原子操作

15.6 最佳实践

1. 优先选择线程池而非直接创建线程

2. 实现Runnable/Callable优于继承Thread

3. 使用并发集合替代同步集合(如Vector/Hashtable)

4. 合理使用锁：

   • 减小同步代码块范围
   • 避免嵌套锁

5. 处理异常：

   ExecutorService pool = Executors.newFixedThreadPool(1);
   pool.submit(() -> {
       try {
           // 任务代码
       } catch (Exception e) {
           // 处理异常
       }
   });
   

15.7 Java 8+新特性

1. CompletableFuture

CompletableFuture.supplyAsync(() -> "Hello")
    .thenApply(s -> s + " World")
    .thenAccept(System.out::println);

2. 并行流

List<String> list = Arrays.asList("a", "b", "c");
list.parallelStream().forEach(System.out::println);

16.垃圾回收算法

16.1 基础垃圾回收算法

16.1.1 标记-清除算法(Mark-Sweep)

工作原理：

1. 标记阶段：从GC Roots出发，标记所有可达对象
2. 清除阶段：回收未被标记的对象占用的内存

特点：

• 会产生内存碎片
• 执行效率不稳定（堆越大，耗时越长）
• 适用于老年代（如CMS回收器的老年代回收）

16.1.2 复制算法(Copying)

工作原理：

1. 将内存分为大小相同的两块
2. 只使用其中一块，当这块用完时
3. 将存活对象复制到另一块
4. 清理已使用的内存空间

特点：

• 没有内存碎片
• 浪费一半内存空间
• 适用于新生代（如Serial、ParNew等新生代回收器）
• 实际JVM实现中，新生代按8:1:1比例分为Eden和两个Survivor区

16.1.3 标记-整理算法(Mark-Compact)

工作原理：

1. 标记阶段：与标记-清除相同
2. 整理阶段：将所有存活对象向一端移动
3. 清理边界以外的内存

特点：

• 避免内存碎片
• 移动对象需要时间
• 适用于老年代（如Serial Old、Parallel Old）

16.1.4 分代收集理论

内存划分：

• 新生代(Young Generation)：新创建的对象
  • Eden区
  • Survivor区（From/To）
• 老年代(Old Generation)：长期存活的对象
• 永久代/元空间(PermGen/Metaspace)：类元数据等

回收策略组合：

• 新生代：通常使用复制算法
• 老年代：通常使用标记-清除或标记-整理算法

16.2 现代垃圾收集器

16.2.1 Serial收集器

• 单线程收集器
• 新生代使用复制算法，老年代使用标记-整理算法
• Client模式下的默认收集器
• -XX:+UseSerialGC显式指定

16.2.2 ParNew收集器

• Serial收集器的多线程版本
• 新生代并行收集，老年代串行
• CMS的默认新生代搭档
• -XX:+UseParNewGC指定

16.2.3 Parallel Scavenge收集器

• 关注吞吐量(用户代码时间/(用户代码时间+GC时间))
• 新生代使用复制算法，老年代使用标记-整理
• -XX:+UseParallelGC或-XX:+UseParallelOldGC

16.2.4 CMS(Concurrent Mark Sweep)收集器

四阶段过程：

1. 初始标记(STW)
2. 并发标记
3. 重新标记(STW)
4. 并发清除

特点：

• 低停顿时间为目标
• 使用标记-清除算法，会产生碎片
• -XX:+UseConcMarkSweepGC启用

16.2.5 G1(Garbage First)收集器

Region分区模型：

• 将堆划分为多个大小相等的Region(1MB~32MB)
• 新生代和老年代不再是物理隔离

回收过程：

1. 初始标记(STW)
2. 并发标记
3. 最终标记(STW)
4. 筛选回收(Evacuation)

特点：

• 可预测的停顿时间模型
• 整体基于标记-整理，局部基于复制算法
• JDK9+默认收集器
• -XX:+UseG1GC启用

16.2.6 ZGC和Shenandoah

新一代低延迟收集器：

• 目标：停顿时间不超过10ms
• 关键技术：
  • 染色指针(Colored Pointers)
  • 读屏障(Read Barriers)
• 适用于超大堆内存(8TB+)
• -XX:+UseZGC或-XX:+UseShenandoahGC

16.3 关键概念与调优参数

1. 重要概念

• Stop-The-World(STW)：GC时暂停所有应用线程
• 安全点(Safepoint)：GC时线程暂停的位置
• 卡表(Card Table)：记录老年代对新生代引用的数据结构
• 记忆集(Remembered Set)：记录跨代引用的数据结构

2. 常用JVM参数

# 堆内存设置
-Xms4g -Xmx4g  # 初始和最大堆大小
-XX:NewRatio=2 # 老年代/新生代比例
-XX:SurvivorRatio=8 # Eden/Survivor比例

# GC日志
-XX:+PrintGCDetails -Xloggc:gc.log

# 收集器选择
-XX:+UseSerialGC
-XX:+UseParallelGC
-XX:+UseConcMarkSweepGC
-XX:+UseG1GC

# 调优参数
-XX:MaxGCPauseMillis=200 # 目标最大停顿时间(G1)
-XX:G1HeapRegionSize=8m # G1 Region大小
-XX:InitiatingHeapOccupancyPercent=45 # G1触发并发标记的堆占用率

16.4 GC触发条件

1. Minor GC/Young GC

• 触发条件：Eden区满
• 特点：频率高，速度快

2. Major GC/Full GC

• 触发条件：
  • 老年代空间不足
  • 方法区空间不足
  • System.gc()调用(不一定立即执行)
  • CMS GC失败后的担保失败
• 特点：停顿时间长，应尽量避免

16.5 选择策略

17.标记清除流程

17.1 算法核心步骤

17.1.1 标记阶段（Mark Phase）

graph TD
    A[GC Roots] -->|引用| B[对象A]
    A -->|引用| C[对象B]
    B -->|引用| D[对象C]
    C -->|引用| E[对象D]

具体过程：

1. 暂停应用程序线程（Stop-The-World）
2. 从GC Roots出发，遍历对象引用图
   • GC Roots包括：
     • 虚拟机栈中引用的对象
     • 方法区中静态属性引用的对象
     • 方法区中常量引用的对象
     • 本地方法栈中JNI引用的对象
3. 对每个可达对象打上标记（通常在对象头中记录）

17.1.2 清除阶段（Sweep Phase）

graph LR
    A[已标记对象] --> B[保留]
    C[未标记对象] --> D[回收内存]

具体过程：

1. 线性遍历堆内存中的所有对象
2. 对于未被标记的对象，将其所在内存块记录到空闲列表（Free List）中
3. 清除所有对象的标记位（为下次GC做准备）
4. 恢复应用程序线程

17.2 内存布局示例

回收前堆状态：

[对象A][对象B][对象C][对象D][对象E]
  ↑       ↑       ×       ↑       ×
 (标记)  (标记) (未标记) (标记) (未标记)

回收后堆状态：

[对象A][对象B][空闲][对象D][空闲]

17.3 算法特点分析

优点：

1. 实现简单：逻辑直观，易于实现
2. 不移动对象：适合存活对象多的场景（如老年代）

缺点：

1. 内存碎片：会产生不连续的内存空间
   • 可能导致后续大对象无法分配（即使总空闲足够）
2. 效率问题：
   • 标记阶段需要遍历所有存活对象（与存活对象数量正相关）
   • 清除阶段需要遍历整个堆（与堆大小正相关）
3. STW停顿：两个阶段都需要暂停应用线程

17.4 实际应用中的改进

1. 标记优化技术

• 三色标记法：
  • 白色：未访问
  • 灰色：已访问但子引用未处理完
  • 黑色：已访问且子引用已处理
• 增量更新（CMS使用）：
  • 记录并发标记期间新增的引用
• 原始快照（G1/Shenandoah使用）：
  • 以标记开始时为快照进行扫描

2. 清除优化技术

• 空闲列表管理：
  • 按内存块大小维护多个空闲列表
  • 分配时选择最合适大小的块
• 碎片整理：
  • 后续的标记-整理算法解决此问题

17.5 与其它算法的关系

1. 标记-整理算法：在标记-清除基础上增加整理阶段
2. 分代收集：老年代常使用标记-清除或其变种
3. CMS回收器：老年代并发标记-清除的代表实现

17.6 典型应用场景

1. CMS回收器的老年代回收（除并发失败后的Full GC）
2. 大对象分配的专用内存区域
3. 早期JVM的主要回收算法

18.手撕：二维数组的二分查找

18.1 行列均有序的二维数组（LeetCode 240题）

方法一：从右上角开始的搜索

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        
        int rows = matrix.length;
        int cols = matrix[0].length;
        int row = 0;
        int col = cols - 1; // 从右上角开始
        
        while (row < rows && col >= 0) {
            if (matrix[row][col] == target) {
                return true;
            } else if (matrix[row][col] < target) {
                row++; // 排除当前行
            } else {
                col--; // 排除当前列
            }
        }
        return false;
    }
}

时间复杂度：O(m + n)，其中m是行数，n是列数

方法二：二分查找优化

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        
        int rows = matrix.length;
        int cols = matrix[0].length;
        
        int left = 0;
        int right = rows * cols - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int midValue = matrix[mid / cols][mid % cols];
            
            if (midValue == target) {
                return true;
            } else if (midValue < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
}

时间复杂度：O(log(mn))，标准的二分查找复杂度

18.2 严格有序的二维数组（LeetCode 74题）

方法：将二维数组视为一维数组进行二分查找

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        
        int m = matrix.length;
        int n = matrix[0].length;
        
        int left = 0;
        int right = m * n - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int midElement = matrix[mid / n][mid % n];
            
            if (midElement == target) {
                return true;
            } else if (midElement < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
}

关键点：

1. 将二维坐标转换为一维索引：index = row * n + col
2. 将一维索引转换为二维坐标：row = index / n, col = index % n

边界条件处理

1. 空数组检查
2. 单行或单列的特殊情况
3. 目标值小于最小值或大于最大值的情况