背包问题是动态规划中的经典问题类型，也是面试和竞赛中的高频考点。本文将系统讲解如何识别背包问题、通用的解题套路，并以 LeetCode 474「一和零」为例深入剖析。

一、如何识别背包问题

当你遇到以下特征的题目时，很可能是背包问题：

1.1 核心特征

问题描述中包含以下要素：

• 物品集合：有一组可选的物品（数组、列表等）
• 容量限制：存在一个或多个限制条件（重量、体积、数量等）
• 价值/目标：需要优化某个目标（最大价值、最小代价、方案数等）
• 选择约束：每个物品有选择次数的限制（选一次、无限次、至多 k 次等）

1.2 常见问法

背包问题通常以以下形式出现：

• “在限制 X 的情况下，最多/最少能…”
• “选择若干物品，使得总和不超过…”
• “有多少种方法可以…”
• “能否恰好达到…”

1.3 背包问题的分类

根据物品的选择规则和目标函数，背包问题分为：

阅读全文 »

一份全面的微服务架构参考手册，系统梳理 29 个核心概念，涵盖基础架构、可靠性保障、配置治理、可观测性、安全认证、数据管理、部署运维和高级模式等八大领域。每个概念都配有原理图解、实战代码和工具对比，适合作为日常开发的技术速查和架构设计的参考指南。

目录

基础架构层

• 1. 服务拆分（Service Decomposition）
• 2. API 网关（API Gateway）
• 3. RPC 与服务间通信（RPC & Inter-Service Communication）

可靠性保障

• 4. 熔断（Circuit Breaker）
• 5. 服务降级（Service Degradation）
• 6. 重试与超时（Retry & Timeout）
• 7. 隔离（Isolation）
• 8. 限流（Rate Limiting）

配置与治理

• 9. 服务发现与注册（Service Discovery & Registration）
• 10. 配置中心（Configuration Center）
• 11. 负载均衡（Load Balancing）
• 12. 服务网格（Service Mesh）

可观测性

• 13. 链路追踪（Distributed Tracing）
• 14. 日志聚合（Log Aggregation）
• 15. 监控告警（Monitoring & Alerting）
• 16. 健康检查（Health Check）

安全与认证

• 17. 认证与授权（Authentication & Authorization）
• 18. API 安全（API Security）
• 19. 服务间认证（Service-to-Service Auth）

数据管理

• 20. 分布式事务（Distributed Transaction）
• 21. 分布式缓存（Distributed Cache）
• 22. 数据一致性（Data Consistency）
• 23. 数据库分片（Database Sharding）

部署与运维

• 24. 容器化（Containerization）
• 25. CI/CD
• 26. 灰度发布（Canary Deployment）

高级模式

• 27. 事件驱动架构（Event-Driven Architecture）
• 28. BFF 模式（Backend for Frontend）
• 29. 领域驱动设计（DDD in Microservices）

阅读全文 »

本文档是 IO 多路复用深度剖析 项目的理论部分

项目地址

GitHub: https://github.com/d60-Lab/io-multiplexing-deep-dive

# 克隆项目并运行测试
git clone git@github.com:d60-Lab/io-multiplexing-deep-dive.git
cd io-multiplexing-deep-dive
ulimit -n 10240
cargo build --release
cd scripts && ./benchmark.sh

本文档结合实际代码和测试数据，深入剖析五种 IO 多路复用技术的原理、性能和适用场景。

目录

1. 问题背景：C10K 问题
2. 技术演进路线
3. 五种模型深度对比
4. 性能瓶颈分析
5. 实际测试结果
6. 结论与建议

问题背景：C10K 问题

什么是 C10K 问题？

C10K 指的是服务器如何支持 10,000 个并发连接 (Concurrent 10 Thousand)。在 2000 年左右，这是一个巨大的技术挑战。

为什么会有这个问题？

1. 传统模型的资源限制

每连接一个线程模型：

• 每个线程栈空间：2-8 MB
• 10,000 个线程 = 20-80 GB 内存（仅栈空间！）
• 线程上下文切换开销：O(n)
• 系统调度开销巨大

2. 具体瓶颈

资源消耗示例：
- 1 个连接 = 1 个线程
- 1 个线程 = 2 MB 栈 + 内核数据结构
- 10,000 连接 = 20 GB + 大量上下文切换

3. 为什么不能简单增加线程？

• 内存墙：物理内存有限
• 调度墙：CPU 时间片轮转，上下文切换成本高
• 锁竞争：大量线程导致锁争用

技术演进路线

时间线 | 技术      | 复杂度 | 并发能力  | 备注
-------|----------|--------|----------|------------------
1980s  | Blocking | O(1)   | < 100    | 每连接一个线程
1990s  | select   | O(n)   | < 1024   | FD_SETSIZE 限制
1997   | poll     | O(n)   | > 1024   | 突破 fd 限制
1999   | epoll    | O(1)   | > 100K   | Linux 2.6+
2000   | kqueue   | O(1)   | > 100K   | FreeBSD/macOS
2019   | io_uring | O(1)   | > 1M     | Linux 5.1+
2020s  | async    | O(1)   | > 1M     | 协程 + 事件循环

阅读全文 »

阅读全文 »

作者：bjmayor
时间：2025年11月
目标：用简化的本地实现来验证百亿级短URL系统的核心技术点

引言

李智慧老师在《高并发架构实战课》中设计了一个名为Fuxi的短URL系统，目标是处理144亿条短URL、4万QPS并发、12TB存储。这是一个典型的高并发+海量数据场景。

但作为学习者，我们遇到几个问题：

1. 无法复现环境：家用电脑没有几百G内存、几十T硬盘
2. 概念难以理解：HDFS、HBase、Redis集群配置复杂
3. 缺少直观验证：为什么要预生成？缓存策略真的有效吗？

本文的目标：用简化的本地实现，通过代码和测试数据，验证李智慧设计中的核心技术点。

一、为什么不用Hash？不用自增？

问题分析

生成短URL有三种常见方案：

代码验证

我实现了三种算法并进行对比测试：

// 方法1：Hash截断
func GenerateWithHash(input string) string {
    hash := simpleHash(input)
    result := make([]byte, 6)
    for i := 0; i < 6; i++ {
        result[i] = charset[hash%64]
        hash = hash / 64
    }
    return string(result)
}

// 方法2：自增序列
func GenerateWithSequence(seq int64) string {
    result := make([]byte, 6)
    for i := 0; i < 6; i++ {
        result[5-i] = charset[seq%64]
        seq = seq / 64
    }
    return string(result)
}

// 方法3：随机生成（带布隆过滤器）
func (g *Generator) Generate(count int) ([]string, error) {
    urls := make([]string, 0, count)
    for generated < count {
        code := g.generateRandom()
        if !g.bloomFilter.Contains(code) {
            g.bloomFilter.Add(code)
            urls = append(urls, code)
            generated++
        }
    }
    return urls, nil
}

阅读全文 »

权限系统设计：从 RBAC 到图权限，再到列表查询的性能难题

一、权限系统的本质

权限系统的核心是三元组：实体、资源、操作

以 Linux 文件系统为例：

• 实体（Who）: 用户（User）
• 资源（What）: 文件（File）
• 操作（How）: rwx（读、写、执行）

# 示例：用户 alice 对文件 /data/report.txt 有读写权限
alice (实体) -> /data/report.txt (资源) -> rw- (操作)

二、权限模型的演进

2.1 ACL（访问控制列表）- 最原始的方式

直接定义 “谁对什么有什么权限”：

alice   -> /data/report.txt  -> read, write
bob     -> /data/report.txt  -> read
charlie -> /data/secret.txt  -> read, write

问题：

• 用户多了管理困难（每个用户都要单独配置）
• 权限变更成本高（要改 100 个用户的权限就要改 100 次）

2.2 用户组（Group）- 对实体的包装

引入"组"的概念，批量管理用户：

组: managers = [alice, bob, charlie]
组: developers = [david, eve, frank]

managers    -> /data/reports/*  -> read, write
developers  -> /data/code/*     -> read, write, execute

改进：

• 新增用户只需加入组
• 调整组的权限即可影响所有成员

仍然不够：权限类型（read, write, execute）仍然散落各处，难以复用

2.3 RBAC（基于角色的访问控制）- 对操作的包装

引入"角色"的概念，封装一组操作：

角色定义:
  - 角色: admin        -> 操作: [read, write, delete, grant]
  - 角色: editor       -> 操作: [read, write]
  - 角色: viewer       -> 操作: [read]

用户分配:
  - alice   -> 角色: admin    (on /data/reports/*)
  - bob     -> 角色: editor   (on /data/reports/*)
  - charlie -> 角色: viewer   (on /data/reports/*)

优点：

• 权限管理清晰：用户 -> 角色 -> 资源
• 易于扩展：新增角色即可，无需修改用户配置
• Go 语言推荐库：Casbin (支持 RBAC/ABAC/RESTful 等多种模型)

2.4 RBAC 的局限性

RBAC 适合：

• ✅ 静态的组织结构（角色相对固定）
• ✅ 权限与角色强相关（如：管理员、编辑、访客）
• ✅ 资源类型有限（如：文档、订单、用户）

RBAC 不适合：

• ❌ 动态的权限继承（领导自动继承下属权限）
• ❌ 复杂的关系链（A 的上级的上级也有权限）
• ❌ 资源之间有依赖（文件夹权限影响子文件）

三、权限继承的难题：Google Zanzibar

3.1 真实场景：组织层级权限

场景:
  - Alice 是 Bob 的领导
  - Bob 对资源 C 有权限
  - 期望: Alice 自动继承 Bob 的权限（领导能看下属的所有资源）

传统 RBAC 解决不了这个问题，因为：

• Bob 的权限可能很多，手动给 Alice 分配不现实
• Bob 的下属可能变化（离职、调岗），需要实时更新
• 权限是间接的、传递的

阅读全文 »