算法与数据结构 - 架构师面试题库

侧重工程实践中的算法应用，考察候选人在真实系统中运用算法解决问题的能力，而非LeetCode刷题能力。

---

一、哈希与数据结构应用（1-15题）

1. 🔵 布隆过滤器在实际系统中有哪些应用场景？它的误判率如何计算？如何选择合适的哈希函数个数和位数组大小？

答：常见场景包括：缓存穿透防护（拦截不存在的key请求）、爬虫URL去重、垃圾邮件过滤、推荐系统已读过滤。误判率公式为 p ≈ (1 - e^(-kn/m))^k，其中k为哈希函数个数，n为插入元素数，m为位数组大小。最优k = (m/n) * ln2。实际工程中，Guava的BloomFilter和Redis的BF.ADD都可直接使用。需要注意布隆过滤器不支持删除，如需删除可用Counting Bloom Filter或Cuckoo Filter。

2. 🔵 一致性哈希算法的原理是什么？在分布式缓存中如何解决数据倾斜问题？虚拟节点的数量如何确定？

答：一致性哈希将哈希空间组织成环形（0~2^32-1），节点和数据都映射到环上，数据顺时针找到第一个节点即为归属节点。数据倾斜通过虚拟节点解决，每个物理节点映射多个虚拟节点。虚拟节点数量一般150-200个可达到较好均衡，具体需根据节点数和数据分布测试。Dubbo默认160个虚拟节点。进阶方案包括带权重的一致性哈希（按机器配置分配不同数量的虚拟节点）和Jump Consistent Hash（Google提出，无需存储环，O(1)空间）。

3. 🔴 HyperLogLog的基本原理是什么？Redis中的HyperLogLog实现有什么优化？在什么场景下你会选择它而不是精确计数？

答：基于概率统计，利用哈希值二进制表示中前导零的最大长度来估算基数。直觉：抛硬币连续出现k次正面的概率为1/2^k，如果观察到了k次连续正面，可以估算大约进行了2^k次实验。Redis实现使用16384个桶（寄存器），每个桶6bit，总共12KB固定内存，标准误差0.81%。适用场景：UV统计、日活统计等允许小误差的大基数统计。不适合需要精确计数或需要判断某元素是否存在的场景。

4. 🔵 跳表（Skip List）的原理是什么？为什么Redis的有序集合选择跳表而不是红黑树？

答：跳表是多层链表结构，每层是下层的”快速通道”，通过随机化决定节点层数，期望时间复杂度O(logN)。Redis选择跳表的原因：1）实现简单，代码量约红黑树的1/3；2）范围查询天然高效，直接遍历底层链表；3）插入删除只需修改前后指针，无需旋转；4）通过调整概率参数p（Redis用0.25）可灵活平衡空间和时间。Redis的跳表实现最大32层，支持score相同时按member字典序排序。

5. 🔴 在一个日活过亿的系统中，如何实现”最近7天活跃用户数”的统计？请对比不同方案的时间复杂度、空间复杂度和精确度。

答：方案对比：

• Bitmap方案：每天一个Bitmap，userId作为offset，7天做OR运算后BITCOUNT。空间：每天约12MB（1亿bit），7天84MB。精确，但用户ID需要连续或映射。
• HyperLogLog方案：每天一个HLL，7天PFMERGE。空间：每天12KB，7天84KB。误差约0.81%，适合允许误差的场景。
• Roaring Bitmap方案：压缩位图，对稀疏数据空间效率更高。适合用户ID不连续的场景。
• 数据库方案：直接COUNT(DISTINCT)，数据量大时性能差，需要预聚合。
  推荐：日活过亿场景下，Bitmap方案最实用，精确且性能好。如果用户ID不连续，用Roaring Bitmap。

6. 🔵 B+树和LSM-Tree各自的优缺点是什么？为什么MySQL用B+树而HBase/RocksDB用LSM-Tree？

答：B+树：读优化结构，数据有序存储，范围查询高效，但随机写入需要原地更新，写放大严重（可能需要页分裂）。LSM-Tree：写优化结构，所有写入先进内存（MemTable），满后刷盘为SSTable，读取需要合并多层查找。B+树适合读多写少（OLTP数据库），LSM-Tree适合写多读少（日志、时序数据）。LSM-Tree的Compaction策略（Size-Tiered vs Leveled）直接影响读写放大和空间放大的权衡。RocksDB默认Leveled Compaction，读放大较小但写放大较大。

7. 🔴 如何设计一个高性能的分布式ID生成器？请对比Snowflake、Leaf、UUID等方案的优劣。

答：

• Snowflake：64bit = 1bit符号 + 41bit时间戳 + 10bit机器ID + 12bit序列号。优点：趋势递增、性能高（单机4096/ms）、不依赖外部存储。缺点：时钟回拨问题、机器ID分配需要管理。
• Leaf-Segment（美团）：数据库号段模式，批量获取ID段缓存在内存。双Buffer预加载解决切换时的性能抖动。优点：简单可靠。缺点：依赖DB、ID不够随机。
• Leaf-Snowflake：用ZooKeeper管理workerID，解决手动分配问题。
• UUID：128bit，全局唯一无需协调。缺点：无序导致B+树页分裂、存储空间大、不可读。
• Redis INCR：简单但依赖Redis可用性，需要考虑持久化。
  推荐：大多数场景Snowflake变种即可，关键是解决时钟回拨（等待、报警、使用扩展位记录回拨次数）。

8. 🔵 LRU缓存的实现原理是什么？Java中LinkedHashMap如何实现LRU？在高并发场景下LRU有什么问题？如何优化？

答：LRU用HashMap+双向链表实现，HashMap保证O(1)查找，双向链表维护访问顺序。LinkedHashMap设置accessOrder=true即可实现LRU，重写removeEldestEntry控制容量。高并发问题：全局锁竞争严重。优化方案：1）分段LRU（ConcurrentHashMap思路）；2）Caffeine的W-TinyLFU算法，使用频率sketch+分段锁，性能远超Guava Cache；3）近似LRU（Redis的做法，随机采样淘汰）。Caffeine的Window区+Probation区+Protected区三段式设计兼顾了新鲜度和频率。

9. 🔴 什么是Trie树（前缀树）？在实际工程中有哪些应用？如何优化Trie树的空间占用？

答：Trie树每个节点代表一个字符，从根到叶子的路径构成一个字符串。应用：1）搜索引擎自动补全；2）IP路由最长前缀匹配；3）敏感词过滤（DFA实现）；4）拼写检查。空间优化：1）压缩Trie（Patricia Tree），合并只有一个子节点的路径；2）Double-Array Trie，用两个数组表示，空间紧凑且查询O(n)；3）HAT-Trie，结合哈希表和Trie。AC自动机（Aho-Corasick）在Trie基础上加失败指针，实现多模式匹配，适合敏感词过滤场景。

10. 🔵 时间轮（Timing Wheel）算法的原理是什么？Netty和Kafka中的时间轮实现有什么区别？

答：时间轮是一个环形数组，每个槽位代表一个时间刻度，指针按固定间隔转动。任务根据延迟时间放入对应槽位的链表中。Netty的HashedWheelTimer：单层时间轮，512个槽位，精度100ms，用round字段处理超出一圈的任务。简单但精度有限，适合大量粗粒度定时任务（如连接超时检测）。Kafka的时间轮：多层级时间轮（类似时钟的秒/分/时），高层时间轮的一个槽位等于低层整个轮的时间跨度，任务到期时降级到更细粒度的轮。支持更大时间范围且不浪费空间。对比JDK的DelayQueue（O(logN)插入），时间轮插入O(1)，适合海量定时任务场景。

11. 🔵 什么是Raft一致性算法？它和Paxos相比有什么优势？请描述Leader选举和日志复制的过程。

答：Raft将一致性问题分解为Leader选举、日志复制、安全性三个子问题。Leader选举：节点初始为Follower，超时未收到心跳则变为Candidate，发起投票，获得多数票成为Leader。每个任期（Term）最多一个Leader。日志复制：Leader接收客户端请求，追加到本地日志，并行发送AppendEntries RPC给Follower，多数确认后提交并应用到状态机。相比Paxos的优势：1）更易理解和实现；2）强Leader模型简化了日志管理；3）有明确的成员变更协议。实际应用：etcd、Consul、TiKV都使用Raft。需要注意的问题：脑裂（网络分区时可能出现双Leader，通过Term机制解决）、日志压缩（Snapshot）。

12. 🔴 在一个电商系统中，如何实现商品搜索的相关性排序？请描述TF-IDF和BM25算法的原理及区别。

答：TF-IDF：词频(TF) × 逆文档频率(IDF)。TF = 词在文档中出现次数/文档总词数，IDF = log(总文档数/包含该词的文档数)。问题：TF线性增长不合理，长文档天然TF高。BM25改进：1）TF饱和函数 TF * (k1+1) / (TF + k1 * (1-b+b*dl/avgdl))，k1控制饱和速度（通常1.2-2.0），b控制文档长度归一化（通常0.75）；2）对长文档有更好的惩罚。Elasticsearch默认使用BM25。实际电商搜索还需结合：销量权重、店铺评分、个性化因子、类目相关性等业务因子，通常用Learning to Rank（LTR）模型综合排序。

13. 🔵 图算法在实际系统中有哪些应用？请举例说明最短路径、拓扑排序、社区发现等算法的工程应用。

答：

• 最短路径（Dijkstra/A）：地图导航、网络路由、社交网络中两人最短关系链。A加入启发函数比Dijkstra更高效。
• 拓扑排序：任务调度（DAG工作流引擎如Airflow）、编译依赖分析、微服务启动顺序。
• 社区发现（Louvain/Label Propagation）：社交网络圈子发现、反欺诈团伙识别、推荐系统用户分群。
• PageRank：搜索引擎网页排名、社交网络影响力评估。
• 连通分量：网络故障影响分析、知识图谱实体关联。
  工程实践中，大规模图计算通常使用Pregel模型（BSP计算模型），如Apache Giraph、Spark GraphX。

14. 🔴 如何设计一个实时排行榜系统？要求支持千万级用户、实时更新、支持查询任意用户排名和Top N。

答：核心方案：Redis Sorted Set。ZADD更新分数O(logN)，ZRANK查排名O(logN)，ZREVRANGE查TopN O(logN+M)。千万级优化：1）分桶策略，按分数段分多个ZSet，先定位桶再查桶内排名；2）如果分数离散度高，可用分数区间计数快速估算排名；3）定时快照+增量更新，避免全量排序。更大规模方案：1）分片，按用户ID哈希分片，每个分片维护局部排行，合并时归并排序；2）近似排名，用分桶计数估算，误差可控。注意：Redis单个ZSet建议不超过百万级，超过需要分片。实时性要求不高时可用Flink窗口聚合+定时刷新。

15. 🔵 什么是限流算法？请对比令牌桶、漏桶、滑动窗口的原理和适用场景。

答：

• 令牌桶：以固定速率往桶中放令牌，请求需要获取令牌才能通过。允许突发流量（桶中有积累的令牌）。Guava RateLimiter的SmoothBursty实现。适合大多数API限流场景。
• 漏桶：请求进入桶中排队，以固定速率流出。严格平滑流量，不允许突发。适合对下游保护要求严格的场景（如调用第三方API）。
• 固定窗口：时间窗口内计数，超过阈值拒绝。问题：窗口边界突发（两个窗口交界处可能通过2倍流量）。
• 滑动窗口：将窗口细分为多个小窗口，滑动统计。解决固定窗口边界问题。Sentinel默认使用滑动窗口。
• 滑动日志：记录每个请求的时间戳，精确但内存开销大。
  分布式限流：Redis + Lua脚本实现原子操作，或使用Sentinel/Nginx限流模块。

---

二、排序与查找的工程实践（16-30题）

16. 🔵 TimSort算法的原理是什么？为什么Java的Arrays.sort和Python的sorted都使用TimSort？

答：TimSort是归并排序和插入排序的混合算法。核心思想：1）将数组分成多个已排序的run（利用数据中已有的有序性）；2）小run用插入排序扩展到minrun长度（通常32-64）；3）用归并排序合并run，通过galloping mode优化大量连续元素在同一侧的情况。优势：1）对部分有序数据接近O(n)；2）稳定排序；3）最坏O(nlogn)。Java中Arrays.sort对对象数组用TimSort（稳定），对基本类型用Dual-Pivot QuickSort（更快但不稳定）。

17. 🔴 在一个每秒百万级日志写入的系统中，如何实现高效的日志检索？请描述倒排索引的构建和查询过程。

答：倒排索引构建：1）分词（中文用IK/jieba）；2）为每个词建立posting list（包含文档ID、词频、位置信息）；3）posting list按文档ID排序，便于交集/并集操作。查询过程：1）对查询分词；2）查找每个词的posting list；3）AND查询取交集（跳表加速），OR查询取并集；4）按相关性评分排序。工程实践：Elasticsearch基于Lucene，使用FST（有限状态转换器）存储词典，压缩posting list（Frame of Reference编码），doc values列式存储用于排序聚合。百万级写入优化：批量写入、调大refresh_interval、使用bulk API、合理设置分片数。

18. 🔵 外部排序的原理是什么？如何对一个100GB的文件进行排序？内存只有4GB。

答：外部排序步骤：1）将文件分成25个4GB的块，每块在内存中排序后写入临时文件；2）使用K路归并，用最小堆维护每个临时文件的当前最小元素，每次取堆顶写入结果文件。优化：1）使用败者树替代最小堆，比较次数更少；2）替换选择（Replacement Selection）生成更长的初始run；3）多阶段归并减少IO次数；4）利用SSD的随机读写优势。实际工程中，MapReduce的Shuffle阶段就是外部排序，Hadoop使用的是多阶段归并排序。

19. 🔴 如何实现一个支持模糊匹配的搜索引擎？请描述编辑距离算法和N-gram索引的原理。

答：编辑距离（Levenshtein Distance）：两个字符串之间通过插入、删除、替换操作变成相同所需的最少操作数。DP实现O(mn)。用于拼写纠错、相似字符串匹配。N-gram索引：将字符串拆分为连续N个字符的子串（通常N=2或3），建立N-gram到字符串的倒排索引。查询时将查询串也拆分为N-gram，通过交集找到候选集，再用编辑距离精确过滤。Elasticsearch的fuzzy查询底层用的是Levenshtein Automaton，将编辑距离转化为有限状态自动机，可以在FST上高效遍历。

20. 🔵 位运算在工程中有哪些巧妙应用？请举例说明。

答：

• 权限控制：用位掩码表示权限，userPerm & READ_PERM != 0 判断是否有读权限。Linux文件权限rwx就是位运算。
• 状态压缩：一个int表示32个布尔状态，节省空间。游戏中常用。
• 布隆过滤器：位数组+多个哈希函数。
• 快速取模：hash & (tableSize - 1) 替代 hash % tableSize（tableSize为2的幂）。HashMap就是这么做的。
• 交换变量：a ^= b; b ^= a; a ^= b; 无需临时变量。
• 判断2的幂：n & (n-1) == 0。
• 位图排序：对有限范围整数排序，空间O(max/8)，时间O(n)。
• Redis Bitmap：用于签到、在线状态等场景。

21. 🔴 什么是Merkle Tree？它在分布式系统中有哪些应用？如何用它实现数据一致性校验？

答：Merkle Tree是一种哈希树，叶子节点是数据块的哈希，非叶子节点是其子节点哈希的哈希。根哈希可以快速判断两棵树的数据是否一致。应用：1）Git版本控制，每个commit是一棵Merkle Tree；2）区块链，交易验证；3）Cassandra/DynamoDB的反熵修复（Anti-Entropy），节点间交换Merkle Tree根哈希，不一致时逐层下探定位差异数据块，只同步差异部分；4）HDFS数据校验。优势：只需O(logN)次哈希比较即可定位差异，大幅减少网络传输。

22. 🔵 什么是一致性哈希的虚拟节点？Ketama算法是如何实现的？在实际项目中你是如何使用一致性哈希的？

答：Ketama算法是Memcached客户端使用的一致性哈希实现。每个物理节点生成多个虚拟节点（默认100-200个），虚拟节点名 = “节点地址-序号” 的MD5哈希值。将MD5的128bit分成4个32bit，每个作为一个虚拟节点的位置，所以每次MD5产生4个虚拟节点。查找时对key做MD5，在TreeMap中找到第一个大于等于该哈希值的虚拟节点。实际项目中：Dubbo的ConsistentHashLoadBalance、Redis Cluster的16384个slot（不是严格的一致性哈希，而是哈希槽）、自研分布式缓存的路由层。

23. 🔴 如何设计一个高效的去重系统？日均数据量10亿条，要求精确去重。

答：方案选择取决于数据特征：

• 内存足够：如果key是64bit数字，10亿条约8GB，用HashSet或RoaringBitmap。
• 内存不足：1）分桶策略，按key哈希分成N个桶，每个桶独立去重，可并行处理；2）外部排序后相邻比较；3）多级布隆过滤器（第一级过滤大部分重复，疑似新数据再查精确存储）。
• 分布式方案：1）Redis Set/HyperLogLog（近似）；2）Flink的KeyedState去重，基于RocksDB状态后端支持超大状态；3）ClickHouse的ReplacingMergeTree。
• 持久化方案：基于LSM-Tree的存储（如RocksDB），写入快且支持点查。
  关键权衡：精确度 vs 内存 vs 延迟。精确去重通常需要持久化存储。

24. 🔵 什么是Reservoir Sampling（蓄水池抽样）？在大数据场景下如何实现等概率随机抽样？

答：蓄水池抽样解决的问题：从未知大小的数据流中等概率抽取k个样本。算法：前k个元素直接放入蓄水池；对第i个元素（i>k），以k/i的概率替换蓄水池中随机一个元素。数学证明每个元素最终被选中的概率都是k/n。应用：1）大文件随机抽样（不知道总行数）；2）流式数据采样；3）A/B测试用户分流。分布式版本：每个节点独立抽样，最后合并时按权重再抽样。MapReduce实现：Map阶段每个分片蓄水池抽样，Reduce阶段合并。

25. 🔵 什么是Count-Min Sketch？它和布隆过滤器有什么区别？在什么场景下使用？

答：Count-Min Sketch是一个概率数据结构，用于频率估计。结构：d个哈希函数 × w个计数器的二维数组。插入时d个哈希函数各自对应位置+1，查询时取d个位置的最小值。特点：只会高估不会低估。与布隆过滤器区别：布隆过滤器判断存在性（是/否），CMS估计频率（次数）。应用：1）网络流量中的Heavy Hitter检测；2）搜索热词统计；3）数据库查询优化器的频率估计。Redis的Top-K模块底层就用了CMS。空间复杂度O(d×w)，与数据量无关。

26. 🔴 请描述Paxos算法的基本流程。为什么说Paxos是分布式一致性算法的基础？Multi-Paxos做了什么优化？

答：Basic Paxos两阶段：

• Prepare阶段：Proposer选择提案号n，向多数Acceptor发送Prepare(n)。Acceptor如果n大于已响应的最大提案号，承诺不再接受小于n的提案，并返回已接受的最大提案。
• Accept阶段：Proposer收到多数响应后，如果有已接受的值则用该值，否则用自己的值，发送Accept(n, value)。Acceptor如果n不小于已承诺的最大提案号则接受。
  问题：活锁（两个Proposer交替Prepare）、每个值需要两轮RPC。Multi-Paxos优化：选出稳定Leader，后续提案跳过Prepare阶段，一轮RPC即可。Raft本质上是Multi-Paxos的简化实现。ZooKeeper的ZAB协议也是Multi-Paxos变种。

27. 🔵 什么是Gossip协议？它在分布式系统中如何实现最终一致性？有哪些实际应用？

答：Gossip协议模拟流言传播：每个节点周期性随机选择若干节点交换信息。三种模式：1）Anti-Entropy（反熵），交换全部数据，保证最终一致但带宽大；2）Rumor Mongering（谣言传播），只传播新信息，收敛快但可能遗漏；3）两者结合。收敛时间O(logN)。应用：1）Redis Cluster节点间状态同步；2）Cassandra的节点发现和故障检测；3）Consul的成员管理（基于SWIM协议，Gossip的改进版）；4）区块链P2P网络。优点：去中心化、容错性强、扩展性好。缺点：最终一致（非强一致）、消息冗余。

28. 🔴 如何实现一个分布式锁？请对比Redis RedLock、ZooKeeper、etcd三种方案的优劣和适用场景。

答：

• Redis单节点：SET key value NX EX，简单高效。问题：主从切换时锁可能丢失。
• RedLock：向N个独立Redis节点加锁，多数成功则获锁。Martin Kleppmann质疑：GC暂停或时钟跳跃可能导致锁失效。Antirez反驳：实际工程中可接受。争议的核心是分布式锁本身的局限性。
• ZooKeeper：创建临时顺序节点，监听前一个节点。优点：可靠性高（ZAB协议保证一致性）、自动释放（会话超时）。缺点：性能较低（每次加锁需要写入多数节点）。
• etcd：基于Raft协议，Lease机制实现TTL，Revision机制实现公平锁。性能和可靠性介于Redis和ZK之间。
  选型建议：对一致性要求高用ZK/etcd，对性能要求高用Redis，RedLock适合折中场景。无论哪种方案，都要考虑锁续期（看门狗机制）和业务幂等。

29. 🔵 什么是CRDTs（无冲突复制数据类型）？它如何实现无协调的最终一致性？

答：CRDTs是一类数据结构，多个副本可以独立并发更新，最终自动收敛到一致状态，无需协调。两类：1）State-based（CvRDT）：合并状态，要求merge操作满足交换律、结合律、幂等律；2）Operation-based（CmRDT）：传播操作，要求操作可交换。常见CRDT：G-Counter（只增计数器，每节点独立计数，合并取max）、PN-Counter（增减计数器）、G-Set（只增集合）、OR-Set（可增删集合）、LWW-Register（最后写入胜出）。应用：Redis的CRDT模块（多活部署）、Riak数据库、协同编辑（如Figma）。局限：只适合特定数据结构，复杂业务逻辑难以用CRDT表达。

30. ⚫ 请设计一个全局唯一的分布式事务ID追踪系统（类似Jaeger/Zipkin），要求低开销、高吞吐、支持采样策略。核心的TraceID生成和传播算法如何设计？

答：TraceID设计：128bit = 时间戳(42bit) + 机器标识(16bit) + 进程ID(16bit) + 随机数(38bit) + 标志位(16bit)。保证全局唯一且可排序。传播机制：通过HTTP Header（如X-Trace-Id）或RPC Context透传，跨线程通过ThreadLocal/TransmittableThreadLocal传递。采样策略：1）概率采样（1%请求）；2）速率限制采样（每秒最多N条）；3）自适应采样（根据QPS动态调整采样率）；4）尾部采样（先收集完整链路再决定是否保留，可以保留慢请求和错误请求）。存储：Span数据通过Kafka异步写入，用Elasticsearch/ClickHouse存储。关键优化：异步上报、批量发送、本地聚合、采样前置。

---

三、并发与分布式算法（31-50题）

31. 🔵 什么是CAS（Compare-And-Swap）？Java中的Atomic类是如何基于CAS实现无锁并发的？ABA问题如何解决？

答：CAS是CPU级别的原子指令，比较内存值与期望值，相等则更新为新值。Java的Unsafe类封装了CAS操作，AtomicInteger等类基于此实现。ABA问题：值从A变为B再变回A，CAS认为没变化。解决：AtomicStampedReference加版本号，每次修改版本号+1。实际中ABA问题在大多数场景不影响正确性（如计数器），只在链表等指针操作场景需要关注。JDK8的LongAdder用分段CAS（Cell数组）解决高竞争下的性能问题，比AtomicLong快数倍。

32. 🔴 请描述Java AQS（AbstractQueuedSynchronizer）的核心原理。ReentrantLock、CountDownLatch、Semaphore是如何基于AQS实现的？

答：AQS核心：一个volatile int state + CLH变种队列（双向链表）。获取锁失败的线程封装为Node加入队列尾部，自旋+park等待。

• ReentrantLock：state表示重入次数，0为未锁定。非公平锁先CAS抢锁，失败再排队；公平锁直接排队。
• CountDownLatch：state初始化为count，countDown()时CAS减1，await()时如果state!=0则阻塞，state=0时唤醒所有等待线程。
• Semaphore：state表示许可数，acquire()减少许可，release()增加许可。
• ReentrantReadWriteLock：state高16位读锁计数，低16位写锁计数。
  AQS的精妙之处在于模板方法模式，子类只需实现tryAcquire/tryRelease，队列管理由AQS统一处理。

33. 🔵 什么是无锁队列？Disruptor的核心设计思想是什么？为什么它比JDK的BlockingQueue快？

答：Disruptor核心设计：1）Ring Buffer（环形数组），预分配内存，避免GC；2）无锁设计，生产者用CAS竞争序号，消费者各自维护消费进度；3）缓存行填充（Padding），避免伪共享（False Sharing）；4）序号屏障（SequenceBarrier），协调生产者和消费者进度。比BlockingQueue快的原因：1）无锁 vs 锁（ArrayBlockingQueue用ReentrantLock）；2）预分配 vs 动态分配；3）缓存友好（数组连续内存）vs 链表（LinkedBlockingQueue节点分散）；4）批量处理（消费者可以一次处理多个事件）。实测吞吐量可达BlockingQueue的5-10倍。LMAX交易所用Disruptor实现单线程百万TPS。

34. 🔴 什么是伪共享（False Sharing）？它对性能有多大影响？Java中如何避免？

答：CPU缓存以缓存行（通常64字节）为单位加载。如果两个线程修改的变量恰好在同一缓存行，即使它们逻辑上无关，也会导致缓存行在两个CPU核心间反复失效和同步（MESI协议），这就是伪共享。性能影响：可能导致数倍甚至数十倍的性能下降。Java避免方式：1）JDK8的@Contended注解（需要-XX:-RestrictContended）；2）手动填充，在变量前后各加7个long（56字节+变量8字节=64字节）；3）Disruptor的Sequence类就用了填充。Thread类的threadLocalRandomSeed也用了@Contended。验证方法：用JMH测试有无填充的性能差异，或用perf工具观察cache miss。

35. 🔵 什么是向量时钟（Vector Clock）？它如何检测分布式系统中的因果关系和冲突？

答：向量时钟为每个节点维护一个计数器向量 [N1:c1, N2:c2, ...]。规则：1）本地事件，自己的计数器+1；2）发送消息时附带自己的向量时钟；3）接收消息时，对每个分量取max，再将自己的计数器+1。因果关系判断：如果V1的每个分量都≤V2对应分量，则V1 happened-before V2。如果V1和V2互不支配，则并发（冲突）。应用：DynamoDB/Riak用向量时钟检测写冲突，冲突时返回多个版本让客户端解决。问题：向量时钟大小随节点数线性增长，大规模系统需要裁剪（如Riak的时钟裁剪策略）。替代方案：Lamport时钟（标量，只能判断偏序）、混合逻辑时钟（HLC，结合物理时钟和逻辑时钟）。

36. 🔴 什么是Phi Accrual Failure Detector？它比传统心跳检测有什么优势？Akka和Cassandra是如何使用它的？

答：传统心跳检测用固定超时判断节点存活，阈值难以设定（太短误判，太长延迟）。Phi Accrual Failure Detector基于统计：记录心跳间隔的历史分布（假设正态分布），计算当前间隔的异常程度φ值。φ = -log10(1 - CDF(timeSinceLastHeartbeat))。φ越大，节点故障的概率越高。优势：1）自适应，根据网络状况动态调整；2）输出连续值而非二元判断，上层可以设置不同阈值做不同决策。Akka默认φ阈值=8（约99.99%置信度），Cassandra默认φ阈值=8。实现时用滑动窗口（如最近1000个心跳间隔）计算均值和方差。

37. 🔵 什么是乐观锁和悲观锁？在数据库和Java中分别如何实现？各自适用什么场景？

答：

• 悲观锁：假设冲突频繁，先加锁再操作。数据库：SELECT ... FOR UPDATE。Java：synchronized、ReentrantLock。适合写多读少、冲突频繁的场景。
• 乐观锁：假设冲突少，操作时不加锁，提交时检查是否冲突。数据库：版本号（UPDATE ... SET version=version+1 WHERE version=oldVersion）或CAS。Java：AtomicInteger、StampedLock的乐观读。适合读多写少的场景。
  注意：乐观锁在高冲突场景下会大量重试，性能反而不如悲观锁。StampedLock的乐观读模式：先tryOptimisticRead获取stamp，读取数据后validate(stamp)检查期间是否有写操作，如果有则降级为悲观读锁。

38. 🔴 请描述Java内存模型（JMM）中的happens-before规则。volatile的底层实现原理是什么？

答：happens-before规则定义了操作间的可见性保证：1）程序顺序规则；2）volatile变量规则（写happens-before后续读）；3）锁规则（unlock happens-before后续lock）；4）线程启动/终止规则；5）传递性。volatile底层：1）写volatile时插入StoreStore + StoreLoad屏障，保证写入对其他线程可见；2）读volatile时插入LoadLoad + LoadStore屏障，保证读到最新值。x86架构下，volatile写会生成lock前缀指令（锁缓存行或总线锁），将写缓冲区刷新到主存并使其他CPU缓存行失效。volatile保证可见性和有序性，但不保证原子性（如i++需要AtomicInteger）。

39. 🔵 什么是Fork/Join框架？它的工作窃取（Work Stealing）算法是如何实现的？

答：Fork/Join框架将大任务递归拆分为小任务（fork），小任务执行完后合并结果（join）。工作窃取：每个工作线程有自己的双端队列（Deque），自己的任务从队列头部取（LIFO，利用缓存局部性），空闲时从其他线程的队列尾部偷（FIFO，偷大任务减少偷取次数）。Java的ForkJoinPool是Executor的实现，parallelStream底层就用ForkJoinPool.commonPool()。注意事项：1）任务粒度不能太细（拆分开销大于计算开销）；2）避免在ForkJoinTask中阻塞（会导致线程饥饿）；3）JDK8的commonPool线程数默认为CPU核心数-1。

40. 🔴 什么是Epoch-based Reclamation？它如何解决无锁数据结构的内存回收问题？和RCU有什么关系？

答：无锁数据结构的难题：删除节点时可能有其他线程正在读取该节点，不能立即释放内存。Epoch-based Reclamation：维护全局epoch计数器和每线程的本地epoch。线程进入临界区时记录当前epoch，退出时清除。当所有线程都观察到新epoch后，旧epoch的待回收内存可以安全释放。三个epoch轮转使用。RCU（Read-Copy-Update）是Linux内核的类似机制：读者无锁无等待，写者复制数据修改后原子替换指针，等待所有读者完成（grace period）后释放旧数据。Java中Stamped Lock的乐观读有类似思想。Crossbeam（Rust）和ConcurrentLinkedQueue（Java，用GC替代手动回收）都涉及类似问题。

41. 🔵 什么是线程池的拒绝策略？Java提供了哪些内置策略？在生产环境中你会如何选择？

答：当线程池队列满且线程数达到最大值时触发拒绝策略。内置策略：1）AbortPolicy（默认）：抛RejectedExecutionException；2）CallerRunsPolicy：调用者线程执行，起到反压作用；3）DiscardPolicy：静默丢弃；4）DiscardOldestPolicy：丢弃队列头部任务。生产建议：1）核心业务用CallerRunsPolicy（降级但不丢失）或自定义策略（记录日志+持久化到DB/MQ后续重试）；2）非核心业务可用DiscardPolicy但必须有监控告警；3）永远不要用默认的AbortPolicy而不catch异常。线程池参数设置：CPU密集型 coreSize=CPU核心数+1，IO密集型 coreSize=CPU核心数*2或根据IO等待比例计算。

42. 🔴 请描述ZAB协议（ZooKeeper Atomic Broadcast）的核心流程。它和Raft有什么异同？

答：ZAB两个阶段：1）Leader选举（Recovery阶段）：选出拥有最大zxid的节点为Leader，确保已提交的事务不丢失；2）原子广播（Broadcast阶段）：Leader将写请求转化为Proposal，发送给Follower，收到多数ACK后发送Commit。zxid = epoch(32bit) + counter(32bit)，epoch每次选举+1。与Raft异同：相同点：都是Leader-based、多数派确认、日志复制。不同点：1）ZAB的Leader选举考虑数据完整性（最大zxid），Raft只考虑日志最新（最大term+最长日志）；2）ZAB有专门的Recovery阶段同步数据，Raft在正常日志复制中处理；3）ZAB的事务ID是全局有序的，Raft的日志索引是每个Leader独立的。

43. 🔵 什么是协程（Coroutine）？Java 21的虚拟线程（Virtual Thread）是如何实现的？它对现有并发编程模型有什么影响？

答：协程是用户态轻量级线程，切换不需要内核参与。Java 21的虚拟线程（Project Loom）：虚拟线程挂载在平台线程（载体线程）上执行，遇到阻塞操作（IO、sleep、锁等待）时自动卸载（unmount），载体线程可以执行其他虚拟线程。实现：基于Continuation（续体），保存和恢复栈帧。影响：1）可以创建百万级虚拟线程，每个请求一个线程的模型重新可行；2）简化异步编程，不再需要CompletableFuture链式调用；3）ThreadLocal需要迁移到ScopedValue。注意：CPU密集型任务不适合虚拟线程；synchronized会pin住载体线程（应改用ReentrantLock）；虚拟线程不应被池化。

44. 🔴 什么是MVCC（多版本并发控制）？MySQL InnoDB的MVCC是如何实现的？ReadView的生成时机对事务隔离级别有什么影响？

答：MVCC通过保存数据的多个版本，让读写操作互不阻塞。InnoDB实现：每行记录有隐藏列 trx_id（最后修改的事务ID）和 roll_pointer（指向undo log中的旧版本）。ReadView包含：m_ids（活跃事务ID列表）、min_trx_id、max_trx_id、creator_trx_id。可见性判断：trx_id < min_trx_id 可见；trx_id >= max_trx_id 不可见；trx_id在m_ids中不可见，不在则可见。RC隔离级别：每次SELECT生成新ReadView，所以能看到其他已提交事务的修改。RR隔离级别：只在第一次SELECT时生成ReadView，后续复用，所以看到的是事务开始时的快照。

45. 🔵 什么是分布式快照（Chandy-Lamport算法）？它在流计算中有什么应用？

答：Chandy-Lamport算法用于在分布式系统中获取一致性全局快照，无需暂停系统。流程：1）发起者记录自己的状态，向所有出边发送marker消息；2）节点收到marker后，如果是第一次收到，记录自己的状态并向所有出边发送marker，同时开始记录该通道的消息；3）收到某通道的marker后，停止记录该通道消息，记录的消息即为该通道的状态。应用：Flink的Checkpoint机制就是Chandy-Lamport的变种（Asynchronous Barrier Snapshotting），barrier替代marker，在数据流中插入barrier，算子收到所有输入的barrier后做快照。这保证了Exactly-Once语义。

46. 🔴 请设计一个分布式限流系统，要求支持多维度限流（用户级、接口级、集群级），QPS级别的精度，毫秒级延迟。

答：架构设计：

• 本地限流层：每个实例用令牌桶/滑动窗口做本地限流，拦截大部分超限请求，避免所有请求都走远程。
• 分布式限流层：Redis + Lua脚本实现原子操作。多维度key设计：rate:{userId}:{api}:{window}。滑动窗口用Redis Sorted Set（score=时间戳，ZRANGEBYSCORE统计窗口内请求数）或固定窗口用INCR+EXPIRE。
• 配置中心：限流规则动态下发，支持热更新。
• 降级策略：Redis不可用时降级为本地限流（按实例数均分配额）。
  优化：1）本地缓存配额，批量向Redis申请令牌（如每次申请100个），减少Redis访问；2）异步上报+同步检查；3）多级缓存（本地→Redis→兜底）。Sentinel的集群限流就是类似思路。

47. 🔵 什么是负载均衡算法？请对比轮询、加权轮询、最少连接、一致性哈希的优劣。

答：

• 轮询（Round Robin）：简单均匀，不考虑服务器差异。适合服务器配置相同的场景。
• 加权轮询（Weighted Round Robin）：Nginx的平滑加权轮询算法，避免权重大的节点连续被选中。适合服务器配置不同的场景。
• 最少连接（Least Connections）：选择当前连接数最少的服务器。适合长连接场景（如WebSocket）。加权最少连接：连接数/权重最小的节点。
• 一致性哈希：相同请求路由到相同节点，适合有状态服务或缓存场景。
• P2C（Power of Two Choices）：随机选两个节点，取负载低的。gRPC默认使用。简单且效果接近最优。
• 自适应负载均衡：根据响应时间、错误率动态调整权重。Dubbo的ShortestResponse策略。

48. 🔴 什么是Borg/Omega/Kubernetes的调度算法？如何实现大规模集群的高效资源调度？

答：

• Borg：两级调度，先过滤（Feasibility Checking，排除不满足约束的机器），再打分（Scoring，选最优机器）。打分考虑：资源碎片最小化、任务分散（减少关联故障）、已有包缓存等。
• Omega：共享状态调度，多个调度器并发操作共享的集群状态，用乐观并发控制解决冲突。
• Kubernetes：Scheduler分为Predicate（过滤）和Priority（打分）两阶段。过滤：节点资源是否足够、端口冲突、亲和性/反亲和性等。打分：资源均衡（LeastRequestedPriority）、节点亲和性、Pod拓扑分散等。调度框架（Scheduling Framework）提供扩展点，支持自定义插件。大规模优化：1）调度缓存（Cache）避免频繁访问API Server；2）抢占调度（Preemption）；3）Gang Scheduling（一组Pod同时调度）。

49. ⚫ 请设计一个支持多租户的分布式任务调度系统，要求：支持Cron和一次性任务、任务优先级、失败重试、任务依赖（DAG）、水平扩展、租户隔离。

答：核心架构：

• 调度层：多个Scheduler实例，通过分布式锁（etcd Lease）选主，主节点负责触发任务，从节点热备。Cron任务用Quartz的CronExpression解析，时间轮驱动触发。
• 执行层：Worker集群，按租户分组（资源隔离），支持动态扩缩容。任务分发用优先级队列（Redis Sorted Set，score=优先级+提交时间）。
• DAG引擎：任务依赖用DAG表示，拓扑排序确定执行顺序，前置任务完成后触发后续任务。用状态机管理任务生命周期（WAITING→READY→RUNNING→SUCCESS/FAILED）。
• 可靠性：任务执行前写入持久化存储（MySQL），Worker心跳检测，超时任务自动重新分配。失败重试用指数退避。
• 租户隔离：配额管理（每租户最大并发数）、队列隔离、Worker分组。
  参考：XXL-JOB、DolphinScheduler、Airflow的设计。

50. ⚫ 在一个全球部署的系统中，如何实现跨数据中心的数据一致性？请对比同步复制、异步复制、半同步复制的方案，并讨论CAP定理的实际权衡。

答：

• 同步复制：所有数据中心确认后才返回成功。一致性最强，但延迟=最慢数据中心的RTT，跨洋延迟100-300ms不可接受。适合金融核心系统的同城双活。
• 异步复制：本地确认即返回，异步复制到其他数据中心。延迟最低，但可能丢数据。适合非核心数据。
• 半同步复制：本地+至少一个远程数据中心确认。MySQL的semi-sync replication。折中方案。
• Quorum方案：W+R>N保证读到最新数据。如5个数据中心，W=3,R=3。CockroachDB/Spanner的做法。
  CAP实际权衡：网络分区是必然的，所以实际是CP和AP的选择。但分区是暂时的，大部分时间可以同时保证C和A。实践中更有意义的是PACELC模型：分区时选CP或AP，无分区时选低延迟(L)或一致性(C)。Google Spanner用TrueTime（原子钟+GPS）实现了外部一致性，代价是写延迟较高。

---

四、搜索与推荐算法（51-65题）

51. 🔵 什么是倒排索引的压缩算法？请描述Frame of Reference、Roaring Bitmap等压缩方案。

答：倒排索引的posting list需要压缩以减少存储和IO。

• Frame of Reference（FOR）：将有序整数列表分块（如128个一组），每块存储最小值+差值，差值用更少的bit表示。Lucene使用的PackedInts。
• PForDelta：FOR的改进，大部分差值用固定bit数，少数异常值单独存储。
• Variable Byte（VByte）：每个字节的最高位标记是否还有后续字节，适合差值较小的场景。
• Roaring Bitmap：将32bit整数空间分成65536个桶（高16bit），每个桶根据基数选择：<4096用有序数组，≥4096用位图，连续区间用RLE。兼顾稀疏和稠密数据。
  Elasticsearch/Lucene综合使用这些技术，posting list用FOR+VByte，filter cache用Roaring Bitmap。

52. 🔴 如何设计一个实时搜索建议（Search Suggestion）系统？要求毫秒级响应、支持拼音、支持纠错。

答：架构设计：

• 离线层：从搜索日志中挖掘热门query，构建Trie树/DAT（Double-Array Trie）。拼音支持：为每个query生成拼音变体，加入Trie。纠错：构建编辑距离1-2的候选词典。
• 在线层：用户输入前缀 → Trie前缀匹配 → 按热度/个性化排序 → 返回Top10。拼音匹配：同时在汉字Trie和拼音Trie中查找，合并结果。纠错：输入无匹配时，用编辑距离或N-gram找相似query。
• 性能优化：1）Trie树常驻内存（压缩后通常几百MB）；2）结果缓存（LRU，命中率很高因为热门前缀集中）；3）客户端防抖（300ms）减少请求量。
• 个性化：结合用户历史搜索、地域、时间等因子重排序。
  参考：Elasticsearch的Completion Suggester（基于FST）、自研方案用DAT+Redis。

53. 🔵 什么是协同过滤推荐算法？User-based和Item-based各自的优缺点是什么？

答：协同过滤基于”相似用户喜欢相似物品”的假设。

• User-based CF：找到与目标用户相似的用户群，推荐他们喜欢但目标用户未接触的物品。相似度：余弦相似度、Pearson相关系数。优点：能发现新颖推荐。缺点：用户数远大于物品数时计算量大，用户兴趣变化快导致不稳定。
• Item-based CF：计算物品间相似度，推荐与用户已喜欢物品相似的物品。优点：物品相似度相对稳定，可离线计算；可解释性好（”因为你买了X，推荐Y”）。缺点：倾向推荐相似物品，多样性不足。
• 实际应用：Amazon用Item-based CF，Netflix用矩阵分解（SVD/ALS）。大规模场景用ALS（交替最小二乘法）分布式计算，Spark MLlib有实现。冷启动问题需要结合内容推荐。

54. 🔴 什么是ANN（近似最近邻）搜索？请对比HNSW、IVF、PQ等算法的原理和适用场景。

答：精确KNN在高维空间计算量巨大，ANN用近似换速度。

• HNSW（Hierarchical Navigable Small World）：多层图结构，上层稀疏用于快速定位，下层稠密用于精确搜索。查询从顶层开始贪心搜索，逐层下降。优点：查询快、召回率高。缺点：内存占用大、构建慢。
• IVF（Inverted File Index）：先用K-Means聚类，查询时只搜索最近的nprobe个聚类中心对应的倒排列表。优点：内存效率高。缺点：聚类质量影响效果。
• PQ（Product Quantization）：将高维向量分成多个子空间，每个子空间独立量化。大幅压缩存储（128维float→16字节）。通常与IVF结合（IVFPQ）。
• ScaNN（Google）：各向异性量化，在PQ基础上优化内积计算。
  选型：内存充足用HNSW（Milvus/Qdrant默认），内存受限用IVFPQ（Faiss），超大规模用磁盘索引（DiskANN）。

55. 🔵 什么是Learning to Rank？请描述Pointwise、Pairwise、Listwise三种方法的区别。

答：LTR用机器学习模型对搜索结果排序。

• Pointwise：将排序转化为回归/分类问题，预测每个文档的相关性分数。简单但忽略了文档间的相对关系。代表：线性回归、GBDT。
• Pairwise：将排序转化为文档对的偏序关系预测，目标是正确排列每对文档的顺序。代表：RankSVM、LambdaMART（XGBoost实现）。LambdaMART是工业界最常用的LTR算法。
• Listwise：直接优化整个列表的排序指标（如NDCG）。代表：ListNet、LambdaRank。理论上最优但训练复杂。
  实际应用：特征工程是关键，包括查询-文档匹配特征（BM25、TF-IDF）、文档质量特征（PageRank、点击率）、用户特征（历史偏好）。电商搜索通常用LambdaMART + 深度模型（如DIN）的两阶段排序。

56. 🔴 如何设计一个大规模推荐系统的架构？请描述召回、粗排、精排、重排各阶段的作用和常用算法。

答：四阶段漏斗架构：

• 召回（Retrieval）：从百万级候选集中筛选出千级候选。多路召回：协同过滤、向量召回（双塔模型+ANN）、热门召回、标签召回。要求高吞吐低延迟。
• 粗排（Pre-ranking）：从千级筛选到百级。用轻量模型（如双塔模型、DSSM）快速打分。特征较少，侧重效率。
• 精排（Ranking）：从百级筛选到十级。用复杂模型（DIN/DIEN/DCN）精确打分。特征丰富，包括用户画像、物品属性、交叉特征、序列特征。
• 重排（Re-ranking）：最终调整。考虑多样性（MMR算法）、去重、业务规则（广告插入、新品提权）、上下文（已曝光过滤）。
  工程关键：特征工程平台（实时特征+离线特征）、模型在线推理（TensorFlow Serving/Triton）、A/B测试平台。

57. 🔵 什么是SimHash？它如何实现海量文本的近似去重？和MinHash有什么区别？

答：SimHash：将文档转化为64bit指纹，相似文档的指纹汉明距离小。步骤：1）分词并计算每个词的哈希值；2）按权重（TF-IDF）加权，哈希值的每一位，1则+weight，0则-weight；3）累加后每位取符号（正为1，负为0）。去重：汉明距离≤3认为相似。海量数据中查找：将64bit分成4段，建立倒排索引，至少一段相同的才计算完整汉明距离（鸽巢原理）。MinHash：用于集合相似度（Jaccard系数）估计，多个哈希函数取最小值。SimHash适合文本相似度，MinHash适合集合相似度。Google用SimHash做网页去重。

58. 🔴 什么是局部敏感哈希（LSH）？它如何实现高维空间的近似最近邻搜索？

答：LSH的核心思想：设计特殊的哈希函数族，使得相似的数据点以高概率映射到同一个桶，不相似的数据点以低概率映射到同一个桶。不同距离度量对应不同的LSH族：余弦相似度用随机超平面LSH（SimHash），欧氏距离用p-stable分布LSH，Jaccard相似度用MinHash。多表策略：用多组哈希函数建立多个哈希表，查询时取并集提高召回率。参数调优：哈希函数个数k（增大k降低误报但降低召回）、哈希表个数L（增大L提高召回但增加空间）。E2LSH是经典实现。实际中HNSW在大多数场景优于LSH，但LSH有理论保证且支持动态更新。

59. 🔵 什么是A*搜索算法？它和Dijkstra有什么区别？在游戏和地图导航中如何应用？

答：A在Dijkstra基础上加入启发函数h(n)，评估函数f(n) = g(n) + h(n)，g(n)是起点到n的实际代价，h(n)是n到终点的估计代价。h(n)需要满足可容许性（不高估实际代价）才能保证最优解。常用启发函数：曼哈顿距离（网格地图）、欧氏距离（连续空间）。与Dijkstra区别：Dijkstra是A的特例（h(n)=0），A通过启发函数减少搜索空间。游戏应用：NPC寻路、RTS游戏单位移动。地图导航：分层A（高速公路优先）、ALT算法（预计算landmark距离作为启发函数）、Contraction Hierarchies（预处理快捷边）。Google Maps用的是CH算法的变种。

60. 🔴 如何设计一个实时异常检测系统？请描述基于统计、基于机器学习的异常检测算法。

答：

• 统计方法：3-sigma规则（超出均值±3倍标准差为异常）、箱线图（IQR）、EWMA（指数加权移动平均）。简单但假设数据正态分布。
• 时序分解：STL分解（趋势+季节性+残差），对残差做异常检测。适合有周期性的指标（如日活、QPS）。
• 机器学习：Isolation Forest（随机森林变种，异常点更容易被隔离）、LOF（局部离群因子，基于密度）、One-Class SVM。
• 深度学习：LSTM自编码器（重建误差大的为异常）、Transformer-based（如时序基础模型）。
• 工程实践：多指标联合检测、动态阈值（基于历史同期）、告警收敛（避免告警风暴）。开源方案：LinkedIn的Luminol、Yahoo的EGADS、阿里的Metis。

61. 🔵 什么是MapReduce编程模型？它的Shuffle过程是如何实现的？有哪些性能优化手段？

答：MapReduce：Map阶段将输入数据转化为<key, value>对，Shuffle阶段按key分区排序传输，Reduce阶段对相同key的values聚合。Shuffle过程：Map端：输出写入环形缓冲区（默认100MB），达到80%触发spill（溢写），溢写前按partition+key排序，可选Combiner本地聚合，多次溢写的文件最终merge。Reduce端：拉取对应partition的数据，归并排序后交给Reduce函数。性能优化：1）Combiner减少网络传输；2）压缩Map输出（Snappy/LZ4）；3）调大缓冲区减少溢写次数；4）合理设置Reduce数量；5）数据倾斜处理（加盐打散、两阶段聚合）。

62. 🔴 什么是数据倾斜？在Spark/Flink中如何处理数据倾斜问题？

答：数据倾斜：少数key的数据量远大于其他key，导致个别task处理时间远超其他task。处理方案：

• 预聚合：Map端Combine，减少Shuffle数据量。
• 加盐打散：给倾斜key加随机前缀，分散到多个task，再二次聚合去掉前缀。
• 广播小表：大表join小表时，将小表广播到所有节点，避免Shuffle。Spark的BroadcastHashJoin。
• 倾斜key单独处理：识别倾斜key，单独用广播join处理，其他key正常join，最后union。
• 调整并行度：增加partition数，但不能根本解决。
• Spark AQE：自适应查询执行，运行时自动检测倾斜并拆分大partition。
• Flink：LocalKeyBy本地预聚合、MiniBatch攒批处理。

63. 🔵 什么是Bitmap索引？它在OLAP场景中有什么优势？Roaring Bitmap做了什么优化？

答：Bitmap索引：为每个列的每个取值创建一个位图，第i位为1表示第i行的值等于该取值。优势：1）多条件AND/OR查询只需位运算，极快；2）适合低基数列（如性别、状态）。劣势：高基数列位图太多，空间爆炸。Roaring Bitmap优化：将32bit空间分成65536个容器（高16bit），每个容器根据基数自适应选择存储格式：<4096个元素用有序short数组（紧凑），≥4096用位图（高效），连续区间用RLE（压缩）。实际应用：ClickHouse的跳数索引、Druid的位图索引、Elasticsearch的filter cache。

64. 🔴 请设计一个实时风控系统的规则引擎，要求支持复杂规则（如”5分钟内同一用户在3个不同城市登录”），毫秒级响应。

答：架构设计：

• 数据采集层：用户行为事件通过Kafka实时接入。
• 特征计算层：Flink实时计算滑动窗口特征（如5分钟内登录城市数）。用KeyedState按用户分组，窗口聚合计算。特征存入Redis供规则引擎查询。
• 规则引擎层：Drools/Aviator/自研表达式引擎。规则DSL：IF user.login_city_count_5min >= 3 THEN risk_level = HIGH。规则热更新：规则存储在配置中心，变更时动态加载。
• 决策层：综合多条规则的结果，输出最终风险等级和处置动作（放行/验证/拦截）。
  性能优化：1）Rete算法优化规则匹配（避免重复计算）；2）特征预计算+缓存；3）规则分级（简单规则前置快速过滤）；4）异步决策（非关键路径异步处理）。

65. ⚫ 请设计一个支持万亿级边的图数据库查询引擎，要求支持多跳查询（如”朋友的朋友”），秒级响应。核心的图存储和查询算法如何设计？

答：存储设计：

• 邻接表存储：每个顶点的出边按目标顶点ID排序存储，支持二分查找。边数据按顶点ID范围分片。
• 分层存储：热数据（高度数顶点）在内存，温数据在SSD，冷数据在HDD。
• CSR格式：压缩稀疏行（Compressed Sparse Row），两个数组：offset数组（每个顶点的边起始位置）+ edge数组（目标顶点ID）。内存紧凑，遍历高效。
  查询优化：
• 多跳查询：BFS逐层扩展，用Bitmap记录已访问顶点避免重复。
• 剪枝：度数过大的超级节点（如明星用户）特殊处理（采样或跳过）。
• 并行化：BSP模型，每层扩展并行处理。
• 索引：对常见查询模式预计算（如2跳邻居索引）。
  参考：Neo4j（单机）、JanusGraph（分布式，基于HBase/Cassandra）、ByteGraph（字节跳动，万亿边）。

---

五、动态规划与贪心的工程应用（66-80题）

66. 🔵 动态规划在实际工程中有哪些应用？请举例说明背包问题、最长公共子序列等在业务中的映射。

答：

• 背包问题：资源分配（广告预算分配到不同渠道使ROI最大化）、服务器装箱（将容器分配到物理机使资源利用率最高）、推荐系统多样性（在有限展示位中选择收益最大的物品组合）。
• 最长公共子序列（LCS）：diff工具（Git diff）、DNA序列比对、文本相似度计算。
• 编辑距离：拼写纠错、模糊搜索、数据清洗（相似记录合并）。
• 最短路径：网络路由、物流配送路径优化。
• 区间调度：会议室分配、任务调度、资源预约系统。
  关键：识别业务问题中的DP结构（最优子结构+重叠子问题），而不是死记模板。

67. 🔴 什么是贪心算法在系统设计中的应用？请举例说明Huffman编码、任务调度等场景。

答：

• Huffman编码：数据压缩（gzip/zlib的基础）。频率高的字符用短编码，频率低的用长编码。构建：用最小堆每次取两个最小频率节点合并。应用：HTTP/2的HPACK头部压缩。
• 任务调度：最短作业优先（SJF）最小化平均等待时间；带截止时间的任务调度（按截止时间排序贪心选择）。
• 负载均衡：最少连接算法就是贪心策略。
• 缓存淘汰：LRU/LFU都是贪心策略（局部最优选择）。
• 网络路由：Dijkstra算法本质是贪心（每次选最短的未访问节点）。
• 资源分配：Kubernetes调度器的BestFit策略（选择剩余资源最少但足够的节点）。
  贪心的关键：证明局部最优能导致全局最优（贪心选择性质+最优子结构）。

68. 🔵 什么是滑动窗口算法？在网络协议和流式计算中有哪些应用？

答：滑动窗口维护一个动态区间，随着数据流动调整窗口边界。应用：

• TCP流量控制：接收窗口（rwnd）控制发送速率，窗口大小动态调整。拥塞窗口（cwnd）配合慢启动、拥塞避免算法。
• 限流：滑动窗口计数器，将时间窗口分成多个小格子，统计窗口内总请求数。
• 流式计算：Flink的时间窗口（Tumbling/Sliding/Session Window），对数据流分窗口聚合。
• 数据库：MySQL的binlog滑动窗口清理、InnoDB的自适应哈希索引统计。
• 监控：滑动窗口计算QPS、P99延迟等指标。
• 字符串处理：最长无重复子串、最小覆盖子串等经典问题。

69. 🔴 什么是线性规划？它在广告竞价、资源调度中有哪些应用？

答：线性规划：在线性约束条件下最大化/最小化线性目标函数。单纯形法或内点法求解。应用：

• 广告竞价：在预算约束下最大化点击量/转化量。约束：每个广告主的预算上限、每个广告位的展示次数。目标：最大化平台收入或用户体验。
• 资源调度：在CPU/内存/带宽约束下最大化任务完成数。Kubernetes的资源配额管理。
• 物流配送：车辆路径问题（VRP），在车辆容量和时间窗口约束下最小化总行驶距离。
• 推荐系统：在多样性、新鲜度等约束下最大化点击率。
  工程实现：Google OR-Tools、Apache Commons Math、Python的scipy.optimize.linprog。大规模问题用近似算法或启发式方法。

70. 🔵 什么是一致性哈希在数据库分片中的应用？如何处理分片扩容时的数据迁移？

答：分片策略：1）范围分片（按ID范围），优点是范围查询高效，缺点是热点问题；2）哈希分片（hash(key) % N），优点是均匀分布，缺点是扩容需要大量数据迁移；3）一致性哈希分片，扩容只需迁移相邻节点的部分数据。数据迁移方案：1）双写方案：新老分片同时写入，后台迁移历史数据，迁移完成后切换读；2）影子表方案：在新分片创建影子表，增量同步+全量迁移；3）中间件方案：ShardingSphere的弹性伸缩，基于binlog增量同步。关键：迁移过程中保证数据一致性和服务可用性，通常需要停写窗口或双写+校验。

71. 🔴 什么是最小生成树算法？在网络设计和聚类分析中有哪些应用？

答：最小生成树（MST）：连接所有节点的最小权重边集合。Kruskal算法：按边权排序，贪心选择不形成环的最小边（用并查集判环），O(ElogE)。Prim算法：从一个节点开始，每次选择连接已选和未选节点的最小边（用最小堆），O(ElogV)。应用：

• 网络设计：最小成本连接所有节点（如光纤铺设、道路规划）。
• 聚类分析：基于MST的聚类，删除MST中权重最大的k-1条边得到k个聚类。
• 图像分割：将像素作为节点，相似度作为边权，MST分割。
• 近似算法：TSP（旅行商问题）的2-近似算法基于MST。

72. 🔵 什么是并查集（Union-Find）？它在实际工程中有哪些应用？路径压缩和按秩合并如何优化？

答：并查集维护不相交集合，支持合并（Union）和查找（Find）操作。路径压缩：Find时将路径上所有节点直接指向根，均摊O(α(n))≈O(1)。按秩合并：将矮树合并到高树下，保持树的平衡。应用：

• 社交网络：判断两人是否在同一社交圈。
• 连通性检测：网络中两节点是否连通。
• Kruskal算法：判断加入边是否形成环。
• 图像处理：连通区域标记。
• 分布式系统：等价类合并（如数据去重中的记录合并）。
• 编译器：类型推断中的类型等价判断。

73. 🔴 什么是模拟退火算法？它在组合优化问题中有哪些应用？和遗传算法有什么区别？

答：模拟退火模拟金属退火过程：高温时接受较差解（跳出局部最优），温度逐渐降低，接受较差解的概率减小。接受概率：exp(-ΔE/T)。参数：初始温度、降温速率、终止温度。应用：TSP路径优化、VLSI芯片布局、神经网络超参数搜索。遗传算法：模拟自然选择，维护种群，通过选择、交叉、变异进化。区别：SA是单解搜索，GA是种群搜索；SA实现简单参数少，GA更适合多目标优化。工程中更常用的是贝叶斯优化（超参数搜索）和进化策略（强化学习中的ES算法）。

74. 🔵 什么是拓扑排序？在微服务依赖管理和构建系统中如何应用？

答：拓扑排序：对DAG（有向无环图）的顶点排序，使得每条边的起点在终点之前。两种实现：1）Kahn算法（BFS）：维护入度为0的队列，每次取出一个节点，删除其出边，新的入度为0的节点入队；2）DFS后序遍历的逆序。应用：

• 构建系统：Maven/Gradle的依赖解析，确定编译顺序。
• 微服务启动：按依赖关系确定服务启动顺序。
• 任务调度：Airflow/DolphinScheduler的DAG任务执行顺序。
• 数据库迁移：Flyway/Liquibase的迁移脚本执行顺序。
• 课程选修：先修课程约束下的选课顺序。
  环检测：如果拓扑排序无法包含所有节点，说明存在环（循环依赖）。

75. 🔴 什么是最大流算法？在网络流量调度和任务分配中有哪些应用？

答：最大流问题：在有容量限制的网络中，从源点到汇点的最大流量。Ford-Fulkerson方法：不断寻找增广路径，沿路径增加流量。Edmonds-Karp（BFS找最短增广路）O(VE²)。Dinic算法（分层图+阻塞流）O(V²E)。应用：

• 网络流量调度：CDN节点间的流量分配，最大化带宽利用率。
• 任务分配：二部图最大匹配（匈牙利算法是最大流的特例），如将任务分配给工人。
• 图像分割：最小割=最大流（Max-Flow Min-Cut定理），将图像分为前景和背景。
• 棒球淘汰问题：判断某队是否已被淘汰。
• 项目选择：有依赖关系的项目中选择收益最大的子集。

76. 🔵 什么是字符串匹配算法？请对比KMP、Boyer-Moore、Rabin-Karp的原理和适用场景。

答：

• KMP：预处理模式串构建next数组（部分匹配表），失配时利用已匹配信息跳过不必要的比较。O(n+m)。适合单模式精确匹配。
• Boyer-Moore：从模式串尾部开始比较，利用坏字符规则和好后缀规则跳过大量字符。最好O(n/m)，实际中通常比KMP快。grep命令的默认算法。
• Rabin-Karp：滚动哈希，将模式串和文本子串的哈希值比较，哈希相同再精确比较。O(n+m)期望。适合多模式匹配（同时搜索多个模式串）。
• AC自动机：Trie+失败指针，多模式匹配O(n+m+z)，z为匹配次数。适合敏感词过滤、病毒特征码扫描。
• 后缀数组/后缀树：预处理文本，支持O(mlogn)的任意子串查找。适合文本索引。

77. 🔴 什么是空间索引？R-Tree、Geohash、S2在地理位置服务中如何应用？

答：

• R-Tree：用最小外接矩形（MBR）层次化组织空间对象。查询时从根节点开始，只搜索与查询区域相交的子树。PostGIS使用R-Tree索引。适合矩形范围查询和最近邻查询。
• Geohash：将二维坐标编码为一维字符串，相近的点有相同前缀。优点：可以用B-Tree索引、前缀匹配实现范围查询。缺点：边界效应（相邻格子的Geohash可能完全不同）。Redis的GEO命令底层用Geohash+Sorted Set。
• S2（Google）：将地球表面映射到正方体的6个面，再用Hilbert曲线编码。比Geohash更均匀，无边界效应。Google Maps、Uber使用S2。
• H3（Uber）：六边形网格系统，比正方形网格更均匀（每个格子到中心距离相等）。适合出行场景的区域划分。

78. 🔵 什么是双指针技术？在工程中有哪些应用场景？

答：双指针是一种遍历优化技巧，用两个指针协同移动减少时间复杂度。应用：

• 归并操作：归并排序的merge阶段，两个有序数组合并。
• 快慢指针：链表环检测（Floyd判圈算法）、找链表中点。
• 滑动窗口：本质是双指针的变种，左右指针维护窗口。
• 数据库：Sort-Merge Join，两个有序结果集用双指针合并。
• Git diff：Myers差分算法用双指针在编辑图上搜索最短路径。
• 流式数据合并：多路归并（K个有序流合并为一个有序流）。
• 对撞指针：有序数组两数之和，从两端向中间逼近。

79. 🔴 什么是随机化算法？在分布式系统和负载均衡中有哪些应用？

答：随机化算法引入随机性来简化算法或提高期望性能。应用：

• 跳表：随机决定节点层数，期望O(logN)。
• 快速排序：随机选择pivot，避免最坏情况O(n²)。
• 负载均衡：P2C（随机选两个取较优），简单且效果好。
• 布隆过滤器：多个独立哈希函数。
• 一致性哈希：虚拟节点的哈希映射。
• 蓄水池抽样：流式数据等概率采样。
• 随机化共识：Ben-Or随机化共识算法，绕过FLP不可能定理。
• HyperLogLog：基于哈希值的概率统计。
• SimHash：随机超平面投影。
  随机化的优势：简化实现、避免最坏情况、去中心化（无需协调）。

80. ⚫ 请设计一个支持实时OLAP查询的列式存储引擎，要求支持百亿级数据、秒级聚合查询。核心的存储格式和查询优化算法如何设计？

答：存储设计：

• 列式存储：每列独立存储，相同类型数据压缩率高。编码：字典编码（低基数列）、RLE（连续重复值）、Delta编码（递增数值）、位图编码（枚举值）。
• 分区+分桶：按时间分区（天/小时），分区内按高频查询列哈希分桶。
• 稀疏索引：每个数据块记录min/max值，查询时跳过不相关的块（Zone Map）。
• 物化视图：预计算常见聚合查询的结果。
  查询优化：
• 向量化执行：批量处理（如1024行一批），利用CPU SIMD指令。ClickHouse的核心优化。
• 延迟物化：先用过滤条件在位图上操作，最后才读取需要的列。
• 预聚合：Druid的Roll-up，写入时按维度预聚合。
• 近似查询：HyperLogLog（COUNT DISTINCT）、t-digest（分位数）。
  参考：ClickHouse、Apache Doris、StarRocks的设计。

---

六、加密与安全算法（81-90题）

81. 🔵 对称加密和非对称加密的区别是什么？HTTPS的TLS握手过程中如何结合使用两者？

答：对称加密（AES）：加解密用同一密钥，速度快，适合大量数据。非对称加密（RSA/ECC）：公钥加密私钥解密，速度慢，适合密钥交换和签名。TLS 1.3握手：1）Client Hello（支持的密码套件、随机数、密钥共享参数）；2）Server Hello（选择密码套件、随机数、密钥共享参数、证书、签名）；3）双方用ECDHE算法协商出对称密钥（Pre-Master Secret）；4）后续通信用对称加密（AES-GCM）。TLS 1.3相比1.2：1）握手从2-RTT减少到1-RTT（0-RTT可选但有重放风险）；2）移除了不安全的算法（RSA密钥交换、CBC模式）；3）强制前向保密（PFS）。

82. 🔴 什么是JWT？它的安全风险有哪些？在微服务架构中如何安全地使用JWT？

答：JWT = Header.Payload.Signature，Base64编码（非加密）。安全风险：1）Token泄露无法撤销（无状态的代价）；2）Payload明文可读（不要放敏感信息）；3）算法混淆攻击（将RS256改为HS256，用公钥作为HMAC密钥）；4）过期时间设置不当。安全实践：1）短过期时间（15分钟）+ Refresh Token（长期，存储在HttpOnly Cookie）；2）Token黑名单（Redis存储已撤销的Token，用jti标识）；3）使用RS256而非HS256（非对称签名，私钥不需要分发）；4）Payload加密（JWE）保护敏感信息；5）绑定客户端指纹（IP+User-Agent哈希）防止Token被盗用。微服务中：API Gateway统一验证JWT，内部服务间可用mTLS。

83. 🔵 什么是OAuth 2.0？请描述授权码模式的完整流程。Access Token和Refresh Token的设计考量是什么？

答：OAuth 2.0授权码模式流程：1）客户端引导用户到授权服务器（带client_id、redirect_uri、scope、state）；2）用户登录并授权；3）授权服务器重定向到redirect_uri，附带authorization_code；4）客户端用code+client_secret向授权服务器换取access_token和refresh_token；5）客户端用access_token访问资源服务器。设计考量：Access Token短期（15分钟-1小时），减少泄露风险；Refresh Token长期（7-30天），存储在安全位置（服务端或HttpOnly Cookie），用于无感刷新Access Token。Refresh Token Rotation：每次使用Refresh Token时颁发新的，旧的失效，检测到重用说明被盗。PKCE扩展：防止授权码拦截攻击，适合移动端/SPA。

84. 🔴 什么是零知识证明？它在身份认证和区块链中有哪些应用？

答：零知识证明：证明者向验证者证明某个陈述为真，但不泄露任何额外信息。三个性质：完备性（真陈述能被证明）、可靠性（假陈述不能被证明）、零知识性（验证者学不到额外信息）。经典例子：阿里巴巴洞穴问题。应用：1）身份认证：证明知道密码但不传输密码（如Schnorr协议）；2）区块链隐私：Zcash的zk-SNARKs，证明交易有效但隐藏金额和地址；3）zkRollup：以太坊L2扩容，用零知识证明压缩交易验证；4）隐私计算：证明数据满足某条件但不暴露数据本身。工程实现：zk-SNARKs（简洁非交互式，需要可信设置）、zk-STARKs（无需可信设置，证明更大）、Bulletproofs。

85. 🔵 什么是密码学哈希函数？MD5、SHA-256、bcrypt各自适用什么场景？为什么密码存储不能用MD5？

答：密码学哈希函数性质：单向性、抗碰撞性、雪崩效应。

• MD5：128bit，已被破解（碰撞攻击），不安全。仅适合文件完整性校验（非安全场景）。
• SHA-256：256bit，目前安全。适合数字签名、证书、区块链。但不适合密码存储（计算太快，易被暴力破解）。
• bcrypt：专为密码存储设计，内置盐值和可调工作因子（cost factor），计算慢（故意的）。cost=10时约100ms/次，暴力破解不可行。
• scrypt/Argon2：比bcrypt更安全，额外消耗内存，抵抗GPU/ASIC暴力破解。Argon2是Password Hashing Competition的冠军。
  密码存储最佳实践：Argon2id > bcrypt > PBKDF2。永远不要用MD5/SHA存储密码。

86. 🔴 什么是mTLS（双向TLS）？在微服务零信任架构中如何实现服务间的身份认证？

答：mTLS：不仅服务端向客户端证明身份（标准TLS），客户端也向服务端证明身份。流程：TLS握手时服务端发送CertificateRequest，客户端返回自己的证书和签名。微服务实现：

• 证书管理：每个服务有自己的证书（SPIFFE标准定义服务身份）。证书自动签发和轮转（cert-manager + Vault）。
• Service Mesh方案：Istio/Linkerd的Sidecar自动处理mTLS，应用无感知。Istio用Citadel签发证书，Envoy代理处理TLS。
• 零信任原则：不信任网络位置，每次请求都验证身份。即使在内网，服务间通信也加密认证。
• 证书轮转：短期证书（24小时），自动续期，减少泄露风险。

87. 🔵 什么是CSRF和XSS攻击？在Java Web应用中如何防御？

答：

• CSRF（跨站请求伪造）：攻击者诱导用户点击恶意链接，利用用户已登录的Cookie发起请求。防御：1）CSRF Token（表单中嵌入随机token，服务端验证）；2）SameSite Cookie属性（Strict/Lax）；3）检查Referer/Origin头；4）关键操作要求二次验证。Spring Security默认开启CSRF防护。
• XSS（跨站脚本）：攻击者注入恶意脚本到页面。三种类型：存储型、反射型、DOM型。防御：1）输出编码（HTML实体编码）；2）CSP（Content Security Policy）头限制脚本来源；3）HttpOnly Cookie防止JS读取；4）输入验证和过滤。Java中用OWASP Java Encoder或Thymeleaf（自动转义）。

88. 🔴 什么是SQL注入？除了参数化查询，还有哪些防御手段？ORM框架是否能完全防止SQL注入？

答：SQL注入：通过构造恶意输入改变SQL语义。防御：1）参数化查询/预编译语句（PreparedStatement），最有效；2）输入验证（白名单校验）；3）最小权限原则（应用账号不给DROP/ALTER权限）；4）WAF（Web应用防火墙）；5）存储过程（减少直接SQL拼接）。ORM不能完全防止：1）MyBatis的${}是字符串拼接，有注入风险（#{}才是参数化）；2）JPA的原生SQL查询如果拼接参数也有风险；3）动态排序字段（ORDER BY不能参数化）需要白名单校验。二阶注入：恶意数据先存入数据库，后续查询时触发。防御：所有SQL都用参数化，不只是用户直接输入。

89. 🔵 什么是分布式系统中的安全通信？如何实现端到端加密？密钥管理有哪些最佳实践？

答：安全通信层次：1）传输层加密（TLS/mTLS）；2）应用层加密（敏感字段加密存储）；3）端到端加密（E2EE，只有通信双方能解密，服务端无法解密）。E2EE实现：Signal协议（Double Ratchet算法），每条消息用不同密钥，前向保密+后向保密。密钥管理最佳实践：1）密钥不硬编码，使用密钥管理服务（HashiCorp Vault、AWS KMS）；2）密钥轮转（定期更换，支持多版本密钥解密历史数据）；3）信封加密（用主密钥加密数据密钥，数据密钥加密数据）；4）密钥分离（不同环境、不同用途使用不同密钥）；5）审计日志（记录密钥的使用情况）。

90. ⚫ 请设计一个安全的API网关认证授权系统，要求支持多租户、多种认证方式（API Key、OAuth2、JWT、mTLS）、细粒度权限控制（RBAC+ABAC）、限流和审计。

答：架构设计：

• 认证层：责任链模式，依次尝试不同认证方式。API Key查Redis验证；OAuth2验证Access Token（本地JWT验证或远程Introspection）；mTLS从证书提取服务身份。认证结果统一为SecurityContext（包含主体身份、租户ID、角色列表）。
• 授权层：RBAC（角色→权限映射）+ ABAC（基于属性的策略，如”只能访问本租户数据”、”工作时间才能调用”）。策略引擎：OPA（Open Policy Agent），策略用Rego语言编写，支持热更新。
• 限流层：多维度限流（租户级、用户级、API级），令牌桶算法，Redis实现分布式限流。
• 审计层：所有请求记录到审计日志（Kafka→Elasticsearch），包含：谁、什么时间、访问什么资源、结果如何。
• 租户隔离：租户配置独立存储，支持不同认证方式和权限策略。

---

七、系统设计中的算法综合（91-105题）

91. 🔵 什么是一致性协议在工程中的选型原则？什么场景用Raft，什么场景用Gossip，什么场景用2PC？

答：选型原则基于CAP权衡和性能需求：

• Raft/Paxos：强一致性场景。配置管理（etcd）、分布式锁（ZooKeeper）、元数据管理。节点数通常3-7个，写入需要多数确认。
• Gossip：最终一致性场景。集群成员管理（Consul）、状态广播（Redis Cluster）。节点数可以很多（数百上千），去中心化。
• 2PC/3PC：分布式事务。数据库跨分片事务、微服务Saga。2PC有阻塞问题（协调者故障），3PC增加PreCommit阶段减少阻塞但不能完全解决。
• Quorum NWR：可调一致性。W+R>N强一致，W=1弱一致高可用。Cassandra/DynamoDB。
  实际中常组合使用：元数据用Raft强一致，数据用Gossip最终一致。

92. 🔴 如何设计一个高可用的配置中心？要求支持实时推送、灰度发布、版本回滚、多环境隔离。

答：核心架构：

• 存储层：MySQL存储配置数据（namespace→key→value→version），Git存储配置变更历史（审计+回滚）。
• 推送机制：长轮询（Apollo方案，客户端30秒长轮询，配置变更时立即返回）或WebSocket（实时性更好但连接管理复杂）。兜底：客户端定时全量拉取。
• 灰度发布：配置关联发布规则（IP列表、机器分组、百分比），灰度客户端优先获取新配置，观察无异常后全量发布。
• 版本管理：每次发布生成新版本号，支持一键回滚到任意历史版本。
• 多环境：namespace隔离（dev/staging/prod），支持配置继承（公共配置+环境特有配置）。
• 高可用：配置服务集群化，客户端本地缓存（文件持久化），配置中心不可用时使用本地缓存。
  参考：Apollo、Nacos、Spring Cloud Config的设计。

93. 🔵 什么是服务降级和熔断？Hystrix和Sentinel的熔断算法有什么区别？

答：降级：系统压力大时主动关闭非核心功能，保证核心功能可用。熔断：检测到下游服务异常时自动切断调用，避免级联故障。状态机：Closed→Open→Half-Open。

• Hystrix：基于滑动窗口统计（10秒内10个桶），错误率超过阈值（默认50%）且请求量超过阈值（默认20）时熔断。已停止维护。
• Sentinel：三种熔断策略：1）慢调用比例（RT超过阈值的请求比例）；2）异常比例；3）异常数。滑动窗口统计，支持更细粒度的控制。还支持热点参数限流、系统自适应保护（根据CPU/Load动态调整）。
  实践建议：熔断阈值不要太敏感（避免误熔断），Half-Open阶段用少量请求探测，配合降级方案（返回缓存数据/默认值/友好提示）。

94. 🔴 什么是背压（Backpressure）机制？在响应式编程和消息队列中如何实现？

答：背压：下游处理速度跟不上上游生产速度时，向上游反馈压力，让上游减速。实现方式：

• 响应式编程：Reactor/RxJava的Subscription.request(n)，下游告诉上游自己能处理n个元素。Reactor的策略：buffer（缓冲）、drop（丢弃）、latest（只保留最新）、error（报错）。
• 消息队列：Kafka消费者按自己的速度pull消息（天然背压）；RocketMQ的push模式底层也是pull。队列积压时：1）增加消费者；2）消费者批量处理；3）临时扩容队列。
• TCP：滑动窗口就是背压机制，接收方通过窗口大小告知发送方。
• Flink：基于Credit的背压，下游算子通过Credit告知上游可接收的buffer数量。
• gRPC：Flow Control，基于HTTP/2的窗口更新帧。

95. 🔵 什么是数据分片策略？Range分片、Hash分片、一致性哈希分片各自的优缺点？

答：

• Range分片：按key范围划分（如用户ID 1-100万分片1，100万-200万分片2）。优点：范围查询高效、分片规则直观。缺点：热点问题（新注册用户集中在最后一个分片）、需要手动调整分片边界。HBase的Region就是Range分片。
• Hash分片：hash(key) % N。优点：数据均匀分布。缺点：范围查询需要扫描所有分片、扩容需要大量数据迁移（rehash）。Redis Cluster用CRC16(key) % 16384。
• 一致性哈希：扩容只迁移相邻节点数据。优点：扩缩容影响小。缺点：实现复杂、可能不均匀（需要虚拟节点）。
• 复合分片：先按时间Range分区，再按用户Hash分桶。兼顾范围查询和均匀分布。

96. 🔴 请设计一个支持多级缓存的系统架构，要求：本地缓存→分布式缓存→数据库，保证缓存一致性。

答：架构设计：

• L1本地缓存：Caffeine，容量小（万级）、过期时间短（秒级）。优点：无网络开销，纳秒级访问。
• L2分布式缓存：Redis Cluster，容量大（亿级）、过期时间长（分钟-小时级）。
• L3数据库：MySQL，持久化存储。
  一致性方案：
• 写操作：先更新DB，再删除Redis缓存（Cache Aside Pattern），再通过消息广播通知所有实例删除本地缓存。
• 延迟双删：更新DB后删缓存，延迟500ms再删一次（防止并发读写导致脏数据）。
• Canal监听binlog：DB变更通过Canal解析binlog，异步更新/删除缓存，最终一致。
• 本地缓存同步：Redis Pub/Sub或RocketMQ广播，通知所有实例失效本地缓存。
• 兜底：缓存设置合理的TTL，即使一致性方案失败，TTL到期后也会自动修复。

97. 🔵 什么是读写分离？如何解决主从延迟导致的数据不一致问题？

答：读写分离：写操作走主库，读操作走从库，提高读性能。主从延迟问题（通常毫秒级，极端情况秒级）解决方案：

• 强制走主库：关键读操作（如刚下单后查订单）强制读主库。通过注解或路由规则控制。
• 延迟感知路由：监控从库延迟，延迟超过阈值时自动路由到主库。
• 会话一致性：记录用户最近写操作的时间戳，读请求时检查从库是否已同步到该时间戳。
• 半同步复制：至少一个从库确认收到binlog后才返回成功，减少延迟。
• GTID方案：MySQL的GTID（全局事务ID），读请求指定GTID，等待从库同步到该GTID后再读。
  中间件支持：ShardingSphere、MyCat都支持读写分离和延迟感知。

98. 🔴 什么是事件溯源（Event Sourcing）？它和CQRS如何配合使用？在什么场景下适合使用？

答：事件溯源：不存储当前状态，而是存储所有状态变更事件。当前状态通过重放事件得到。优点：1）完整审计日志；2）可以回溯到任意时间点的状态；3）事件不可变，天然适合分布式。缺点：1）查询当前状态需要重放（用快照优化）；2）事件schema演进复杂；3）最终一致性。CQRS（命令查询职责分离）：写操作产生事件存入Event Store，读操作从物化视图（Read Model）查询。事件通过消息队列异步更新Read Model。适合场景：金融系统（交易流水）、审计系统、协同编辑、购物车。不适合：简单CRUD、强一致性要求高的场景。框架：Axon Framework（Java）、EventStoreDB。

99. ⚫ 请设计一个支持百万TPS的订单系统，要求：高可用、数据不丢失、支持分库分表、支持分布式事务。

答：核心架构：

• 接入层：Nginx负载均衡 + API Gateway限流熔断。
• 服务层：订单服务无状态，水平扩展。异步化：下单请求写入MQ，异步处理（削峰填谷）。
• 数据层：分库分表（按用户ID哈希，64库×64表=4096张表）。ShardingSphere路由。主从复制+半同步。
• 分布式事务：Saga模式（下单→扣库存→扣余额，失败则补偿回滚）。可靠消息最终一致性（RocketMQ事务消息）。
• 高可用：多机房部署，数据库同城双活（主主复制+冲突检测）。Redis缓存热点数据。
• 数据不丢失：MQ持久化+同步刷盘，数据库WAL+双写。
• 百万TPS关键：1）异步化（MQ削峰）；2）缓存（库存预扣减在Redis）；3）批量处理（攒批写入DB）；4）分库分表（并行写入）。
  参考：阿里双11订单系统、美团外卖订单架构。

100. ⚫ 请设计一个全链路压测系统，要求：不影响线上数据、支持流量录制回放、支持影子库/影子表、实时监控压测指标。

答：核心架构：

• 流量标记：压测请求在Header中打标（如X-Test: shadow），全链路透传（HTTP Header→RPC Context→MQ Header→ThreadLocal）。
• 流量录制：线上流量通过TCPCopy/GoReplay录制，存储到文件/Kafka。回放时按比例放大。
• 影子库/表：中间件层拦截SQL，压测流量路由到影子库（独立数据库实例）或影子表（同库加_shadow后缀）。Redis加前缀shadow:。MQ用影子Topic。
• 数据隔离：所有存储层根据流量标记路由，确保压测数据不污染线上数据。
• 监控：Prometheus+Grafana实时展示QPS、RT、错误率、资源利用率。压测流量和正常流量分开统计。
• 安全机制：压测开关（一键停止）、熔断保护（线上指标异常自动停止压测）、压测数据自动清理。
  参考：阿里的全链路压测方案、Dialtesting。

101. 🔵 什么是服务网格（Service Mesh）中的流量管理算法？Envoy的负载均衡和重试策略是如何实现的？

答：Envoy负载均衡算法：1）Round Robin（加权轮询）；2）Least Request（最少请求，随机选两个取请求数少的，即P2C）；3）Ring Hash（一致性哈希，用于会话保持）；4）Maglev（Google的一致性哈希变种，查表O(1)）；5）Random。重试策略：可配置重试条件（5xx、connect-failure、reset等）、重试次数、重试间隔（指数退避+抖动）、重试预算（限制重试请求占总请求的比例，防止重试风暴）。流量管理：1）金丝雀发布（按权重分流）；2）故障注入（延迟注入、错误注入，用于混沌工程）；3）熔断（连接数/请求数/重试次数超限时熔断）；4）限流（本地令牌桶或全局限流服务）。

102. 🔴 什么是混沌工程？Netflix的Chaos Monkey原理是什么？如何设计一个混沌工程平台？

答：混沌工程：在生产环境中主动注入故障，验证系统的容错能力。Chaos Monkey：随机终止生产环境中的虚拟机实例，验证服务在实例故障时能否自动恢复。Netflix的Simian Army还包括：Latency Monkey（注入延迟）、Chaos Gorilla（模拟整个可用区故障）。混沌工程平台设计：

• 故障注入：网络（延迟、丢包、分区）、进程（kill、CPU满载、内存满载）、存储（磁盘满、IO延迟）、应用（异常注入、线程池满）。
• 爆炸半径控制：从小范围开始（单实例→单机房→跨机房），自动停止条件（核心指标异常时立即停止）。
• 实验管理：定义稳态假设→注入故障→观察指标→分析结果。
• 工具：ChaosBlade（阿里）、Litmus（K8s）、Chaos Mesh（PingCAP）。

103. 🔵 什么是灰度发布？蓝绿部署、金丝雀发布、A/B测试有什么区别？如何实现基于用户特征的精准灰度？

答：

• 蓝绿部署：两套完整环境（蓝/绿），新版本部署到绿环境，验证通过后流量切换。优点：回滚快（切回蓝环境）。缺点：资源成本翻倍。
• 金丝雀发布：新版本先部署少量实例（如5%），逐步增加比例。按流量比例分流。
• A/B测试：按用户特征分流（如用户ID尾号），不同用户看到不同版本，用于功能效果对比。
  精准灰度实现：1）流量染色：在网关层根据用户特征（ID、地域、设备、标签）打标；2）路由规则：Istio VirtualService按Header路由到不同版本；3）特征服务：维护灰度白名单和规则，支持动态调整；4）指标对比：灰度版本和基线版本的核心指标实时对比，异常自动回滚。

104. 🔴 什么是数据血缘（Data Lineage）？如何在大数据平台中实现自动化的数据血缘追踪？

答：数据血缘：追踪数据从产生到消费的完整链路，包括数据来源、转换过程、下游依赖。实现方案：

• SQL解析：解析Hive/Spark SQL的AST，提取表级和字段级的输入输出关系。Apache Atlas的Hook机制。
• 执行计划分析：从Spark/Flink的执行计划中提取数据流向。
• 埋点采集：在ETL框架中埋点，记录每个任务的输入输出。
• 存储：图数据库（Neo4j/JanusGraph）存储血缘关系，支持多跳查询。
• 可视化：DAG图展示数据流向，支持正向追踪（影响分析：改了这张表会影响哪些下游）和反向追踪（溯源：这个报表的数据从哪来）。
  应用：数据质量问题排查、合规审计（GDPR数据删除）、变更影响评估。开源方案：Apache Atlas、DataHub（LinkedIn）、OpenLineage。

105. ⚫ 请设计一个支持多数据中心的分布式数据库，要求：跨地域强一致性、自动故障转移、在线DDL、分布式事务。请描述核心的数据复制和事务提交算法。

答：核心设计（参考Spanner/CockroachDB）：

• 数据复制：Raft协议，每个数据分片（Range/Region）一个Raft Group，3-5副本分布在不同数据中心。Leader处理读写，Follower同步日志。
• 跨地域一致性：TrueTime/HLC（混合逻辑时钟）提供全局有序的时间戳。写入时获取时间戳，等待不确定性窗口（Spanner的commit-wait）后才返回，保证外部一致性。
• 分布式事务：2PC + MVCC。事务协调者选择commit时间戳，所有参与者在该时间戳上提交。读操作根据时间戳读取对应版本（快照隔离）。
• 自动故障转移：Raft Leader故障后自动选举新Leader（秒级）。跨数据中心故障：优先在同区域选举，减少延迟。
• 在线DDL：Schema变更作为分布式事务执行，所有节点在同一逻辑时间点切换Schema版本。F1的异步Schema变更协议，通过中间状态（delete-only→write-only→public）避免数据不一致。
• 存储引擎：LSM-Tree（RocksDB），支持高写入吞吐。Range分片，自动分裂和合并。