Hash

字母异位词

排序每一个单词，就知道是不是异位词。

两数之和

从数组中，找到nums[i] + nums[j] == target，并返回{ i, j }。
思路是双重循环，遍历每一个元素，求和是否为target。
然而，双重循环需要$O(N^2)$的复杂度。因此，可以使用一张表，使用containsKey方法识别是否存在当前i的target - nums[i]，即可减少一重循环。

关键思想

用Map高效率查找，减少一重循环。

最长连续序列

从乱序数组中，找到最长连续（数组中不一定连续）的序列。要求$O(N)$。
首先用数组的值存入哈希表，然后遍历数组，判断map.constains(curNum++)。
然而，即使这样还是效率不够高。

优化

1. 中间值不进入循环，序列开始值才进入，使用!contains(curNum - 1)判断是否为序列开始值
2. 去重，不要哈希表，不需要键值对，使用哈希Set，只存储值。

关键思想

去重；不处理中间值

GMP

协程

协程是用户态的概念。多个协程实际上映射为1个线程。

协程是用户态概念，因此创建、销毁、调度都在用户态完成，不需要切换内核态。
由于协程从属于同一个内核级线程，因此实际上无法并行；而一个协程的阻塞最终也会导致整个线程下的所有协程阻塞。

Goroutine

Go解耦了协程和线程的绑定关系，从而使线程变为一个中间层，协程可以灵活地映射到不同的线程上，相当于“虚拟线程”。

好处如下：

• 可以利用多个线程，实现并行
• 通过调度器，实现灵活的映射
• 栈空间动态扩展（线程大小固定，会产生内存浪费）

GMP

Goroutine Machine Processor
GMP就是协程调度器。
GMP有一个全局队列存储Goroutine；不过实际上Processor都会优先在自己的本地队列调度Goroutine（没有则向全局队列获取），并映射Goroutine到Machine上执行。
如果全局队列没有Goroutine，那么会尝试获取就绪态（正在IO）的协程。
如果仍然失败，那么会从其他Processor中窃取一半的Goroutine，实现负载均衡。

全局队列是互斥的，获取Goroutine要防止获取多次。

type schedt struct {
    ...
    lock     mutex
    runq     gQueue
    runqsize int32
}

Hello World

func main() {
    h := server.Default()

    h.GET("/hello", func(c context.Context, ctx *app.RequestContext) {
        ctx.Data(consts.StatusOK, consts.MIMETextPlain, []byte("Hello World!"))
    })

    h.Spin()
}

$ go run main.go

IDL

Thrift

# echo.thrift
namespace go api

struct Request {
    1: string message
}

struct Response {
    1: string message
}

service Echo {
    Response echo(1: Request req)
}

CloudweGo代码生成

go install github.com/cloudwego/thriftgo@latest

mkdir -p demo/demo_thrift
cd demo/demo_thrift
cwgo server --type RPC \
--module demo/demo_thrift \
--service demo_thrift \
--idl ../../echo.thrift

Protobuf

syntax = "proto3"

package pbapi;

option go_package = "/pbapi";

message Request {
    string msg = 1;
}

message Response {
    string msg = 1;
}

service EchoService {
    rpc Echo (Request) returns (Response) {}
}

CloudweGo代码生成

mkdir -p demo/demo_proto
cd demo/demo_proto

cwgo server -I ../../idl
--type RPC \
--module demo/demo_proto \
--service demo_proto \
--idl ../../echo.thrift

MakeFile自动cwgo代码生成

.PHONY: gen-demo-proto
gen-demo-proto:
    @cd demo/demo_proto && cwgo server -I ../../idl --type RPC --module demo/demo_proto --service demo_proto --idl ../../echo.thrift

Consul服务注册、发现

服务注册用于为服务集群提供统一接口，自动处理集群loadbalance和宕机

// r, err := consul.NewConsulRegister("localhost:8500")
r, err := consul.NewConsulRegister(conf.Getconf().Registry.RegistryAddress[0])
if err != nil {
    log.Fatal(err)
}
opts = append(opts, server.WithRegistry(r))

version: '3'
services:
  consul:
    ports:
      - 8500:8500

Gorm操作数据库

package model

import "gorm.io/gorm"

type User struct {
    gorm.Model
    Email string `gorm:"uniqueIndex;type:varchar(128) not null"`
    Password string `gorm:"type:varchar(64) not null"`

}

新增页面

• 路由

// main.go
func main() {
    ...
    h.GET("/your-page", func(c context.Context, ctx *app.RequestContext) {
        ctx.HTML(consts.StatusOK, "your-page.tmpl", utils.H("Title: Your Title"))
    })
}

• 模板

// your-page.tmpl
{{ define "your-page" }}
<div>
    ...
</div>
{{ end }}

• Hertz生成IDL接口代码

syntax = "proto3"

package pbapi;

option go_package = "/pbapi";

message Request {
    string msg = 1;
}

message Response {
    string msg = 1;
}

service EchoService {
    rpc Echo (Request) returns (Response) {}
}

MCP

RAG的局限性

对于AI来说，RAG仅仅是外部知识库，AI只起到一个总结效果。而总结的效果取决于向量相似度匹配，可能遗漏关键信息。

direction: right
结构化数据 -> 文本块
非结构化数据 -> 文本块

文本块 -> 向量数据库 -> 检索文本块 -> 生成最终响应

• 生成内容不完整：RAG处理的是文本的切片，因此无法看到整篇文档信息。
• RAG无法判断需要多少切片才能解决问题。
• 多轮检索能力弱。

MCP基础

Function Calling

Coze的Agent就是基于Function Calling思路封装的。

不过Function Calling成本比较高，需要模型经过专门训练微调才能稳定支持。

这导致有些模型不支持某些插件的调用（例如Trae只有选择Sonnet、GPT等模型才可以处理图片）。

另外，Function Calling不是一项标准，许多模型的实现细节不一样。

Model Context Protocol

MCP是一项标准协议，简单来说就是通用的接口，使AI-外部工具/数据源交互标准化、可复用。

Claude Desktop、Cursor这样的工具在内部实现MCP Client，这个Client通过MCP协议与MCP Server（由服务提供公司自己开发，实现访问数据、浏览器、本地文件等功能，最终通过MCP返回标准格式）交互，最终在MCP Host上展示。

MCP 传输方式

STDIO，本地环境
SSE，并发量不高，单向通信
Streamable HTTP，高并发，需要维护长连接

文本格式转换

pandoc --from markdown --to docx source.md -o dest.docx
pandoc -f markdown source.md -t docx -o dest.docx
pandoc source.md -o dest.docx --ignore-args # 忽略参数

注意：为了最佳转换效果，markdown文件每行后都要空行

模板

pandoc --reference-doc template.docx source.md -o dest.docx

md2epub

# 首先把所有的md文件列出来
## 递归查找所有 .md 文件（排除 README.md 和 SUMMARY.md）
find . -name "*.md" ! -name "README.md" ! -name "SUMMARY.md" | sort > filelist.txt
## 然后编辑 `filelist.txt`，确保文件顺序正确（例如按 `SUMMARY.md` 的目录结构排序）。

pandoc --standalone --toc \
--metadata title="MIT6.824 分布式系统" \
--metadata author="Robert Morris" \
-o output.epub $(cat filelist.txt) 

注意：对于gitbook，pandoc可能不能正确处理路径，推荐使用honkit。

honkit

// book.json
{
  "title": "MIT6.824 分布式系统",
  "author": "Robert Morris",
  "plugins": ["hints"],
  "pluginsConfig": {
    "hints": {
      "info": "fa fa-info-circle",
      "warning": "fa fa-exclamation-triangle"
    }
  }
}

# 安装honkit
npm install honkit --save-dev
# 需要calibre转换
ebook-convert --version

npm init -y
npx honkit epub ./ ./mybook.epub

代理

代理对象通过invoke，实现类与非核心功能的解耦。

public static void main(String[] args) {
    Payment payment = new Payment("AliPay");
    Pay proxy = ProxyUtil.createProxy(payment);

    proxy.pay(amount);
}

class Payment implements Pay {

    @Overide
    public payResp pay(BigDecimal payAmount) {
        // Payment Business...
    }
}

interface Pay {

    abstract payResp pay(BigDecimal payAmount);
}

class ProxyUtils {
    public static Pay createProxy(Payment payment) {
        return (Pay) Proxy.newProxyInstance(
            ProxyUtil.class.getClassLoader(),
            new Class[]{ Pay.class },
            new InvocationHandler() {

                @Overide
                public Object invoke(Object proxy, Method method, Object[] args) throws Throwable {
                    // Payment Environment Init...
                    // Payment Safe Guard...
                    return method.invoke(payment, args);
                }
            }
        );
    }
}

反射

反射允许对成员变量、成员方法、构造方法信息进行编程访问。

例如，IDE的智能补全、参数提示，就是使用反射实现。

Class字节码获取

Class clazz;
clazz = Class.forName("com.yourpackage.TargetClass");
// 参数
clazz = TargetClass.class;
// 有实例时
clazz = instance.getClass();

场景

反射可以与配置文件结合，从而动态地创建对象。例如application.yml里数据库的配置、端口号等。

Properties prop = new Properties();
FileInputStream fis = new FileInputStream(ROOT + "src/main/resources/application.properties");
String dataSourceUrl = (String) perp.get("dataSource");
String dbName = (String) extractDbName(dataSourceUrl);

Class clazz = Class.forName(dbName);
Constructor con = clazz.getDeclaredConstructor();
Object o = con.newInstance();

...

HashMap

jdk1.7

jdk1.7的HashMap数据结构是：数组 + 单向链表

当哈希后，得到的数组槽位已经存放了其他元素，这时候就需要运用指针在同一个槽位存放多个元素。

头插法

jdk1.7使用的方法是头插法，这样就不需要遍历到链表尾部再插入，性能高。

void createEntry(int hash, K key, V value, int bucketIdx) {
    Entry<K, V> e = table[bucketIdx];
    // 这里使用头插法，在槽位头部插入新元素，并指向e，成为新的槽位引用
    table[bucketIdx] = new Entry<>(hash, key, value, e); 
    size++;
}

public Entry(int h, K k, V v, Entry<K, V> n) {
    this.value = v;
    this.next = n;
    this.key = k;
    this.hash = h;
}

这种方法需要最终更新槽位指向新插入的节点，否则单向链表找不到新插入的元素。

利用2次方机器特性

消息队列3大目标

异步

在生产者-消费者速度不匹配的情况下，使用异步可以减少等待，提高效率。

解耦

多个生产者可以通过消息队列管道集合成1条链路；也可以将1个生产者的消息负载均衡给多个消费者（只发送1条消息给MQ，MQ广播多份）。例如，增加了一个数据分析业务，这时候不需要修改业务代码，只需要配置MQ发送相应消息到大数据系统Server即可。
同时，生产者只需要关心将消息发送给MQ，无需关心后续处理（消费者挂了怎么办）；MQ会负责和消费者通信。

削峰（生产者-消费者速度不同步）

由于队列本身是一条管道，拥有一定容量，因此可以削峰填谷，解决一些瞬时高并发流量。

消息队列的关键问题

C 系统一致性

A系统通过MQ将消息发送给B、C完成后续业务，B成功而C失败，这时如何保证一致性？

A 系统可用性

MQ宕机，依赖MQ管道的服务就不可用。MQ应该有高可用性和稳定性，不应该成为系统薄弱环节。
因此需要MQ集群，这时候又需要新的中间层NameSrv来管理维护MQ集群。

系统复杂度

• 如何保证消费不丢失？
• 如何避免重复消费？
• 如何保证消息顺序？

幂等性

多次消费结果相当于只消费一次。

可以用业务id作为消息key，对key校验有没有消费过。
如果重复消费，确保多次消费和1次消费的结果相同。

• 发送消息重复：发送后，网络断开，没收到ACK，导致重复发送
• 消费消息重复：Consumer收到消息并处理完成，但是由于网络问题，Consumer应答没有发送到Broker；Broker遵从至少消费一次原则，重新发送。
• Rebalance消息重复：Consumer Group的Consumer数量发生变化，触发Rebalance，此时Consumer可能会收到曾经被消费过的消息。

解决方案

Message Queue产品

消息队列工作方式

RocketMQ和Kafka都使用Topic，每个Topic的内容会分发到多个管道（Partition或MessageQueue）。而Kafka在Topic过多的情况下，吞吐量会严重下降；RocketMQ解决了这个问题。

RocketMQ集群

在RocketMQ集群中，多台NameSrv是平等的，而Broker会组成多个主-从结构。
Slave只负责备份，只有Master(brokerId=0)才会发送消息。
然而主从结构的Slave，由于brokerId不为0，不会自动切换为Master，需要人工介入。

Dledger高可用集群

Dleger是一种Raft算法，实现了Leader选举。
Dledger会从Followers中自动选举Leader，从而保证高可用。

三种发送方式

单向发送

Producer只发送消息、不处理ACK；MQ也不发送ACK。消息可靠性没有保障。

// 返回值为null，不处理ACK。
public void sendOneWay(Message msg) throws ...Exception {
    msg.setTopic(withNamespace(msg.getTopic()));
    this.defaultMQProducerImpl.sendOneWay(msg);
}

同步发送

Producer等待MQ ACK，才继续操作。同步发送可能会发生阻塞。

public SendResult sendResult(
        Collection<Message> msgs) throws ...Exception {
    return this.defaultMQProducerImpl.send(batch(msgs));
}

异步发送

Producer不等待MQ ACK（异步ACK，也能保证不丢失消息），直接发送消息。
但是异步发送也有代价，我们不能发送完立刻producer.shutdown()，而需要设置一段延迟，使producer能够捕捉Exception并重发消息。

// send方法本身没有返回值，不会阻塞；但是能够处理Exception
public void send(Message msg, 
                 SendCallBack sendCallBack) throws ...Exception {
    msg.setTopic(withNamespace(msg.getTopic()));
    try {
        if (this.getAutoBatch() && !(msg instanceof MessageBatch)) {
            sendByAccumulator(msg, null, sendCallBack);
        } else {
            sendDirect(msg, null, sendCallBack);
        }
    } catch (Throwable e) {
        sendCallBack.onException(e);
    }
}

producer.send(msg, new SendCallBack() {
    @Override
    public void onSuccess(SendResult sendResult) {
        ...
    }

    @Override
    public void onException(Throwable e) {
        ...
    }
});

两种消费方式

Consumer拉取

Consumer维护一个轮询拉取，Broker收到拉取请求后发送消息。

Broker推送

一般只用推模式，因为Consumer需要轮询（即使Broker不一定有消息），会消耗部分资源。

消息类型

顺序消息

局部有序，实际上是序号相同的消息发送到同一个队列管道，然后消费者从一个管道中拿消息，从而保证有序性。

广播消息

正常情况下，多个Consumer是负载均衡模式，一条消息只会发到其中一个Consumer消费；而在广播模式下，所有的Consumer都会收到消息。
在代码层面，正常情况下服务端统一维护消费者位点；而在广播模式下客户端本地.rocket_offsets维护消费者位点

消息重试

顺序消息

顺序消息要拿到ACK才会发送下一条消息，否则会重发消息

无序消息

为了保障无需消息的消费，MQ设置了一个消息重试间隔时间。如果没有回复，间隔10s-30s-1m-2m…来重发消息，最多重试16次（默认）。
如果达到重试上限还未消费，该消息称为死信消息。死信消息会进入死信队列。

死信队列

死信队列不归属于Topic、Consumer，而是归属于Group Id。
死信队列的消息不会被再次重复消费，有效期为3天，过期删除。
可以手工在监控平台里处理死信，获取messageId后自己处理。

重复消费

网络闪断（成功执行，MQ没收到ACK）、生产者宕机（成功发送到MQ，生产者没收到ACK）会引发重复消费。

Mysql体系结构

DB与Instance

DB：数据库可以是ibd文件、放在内存的文件，是物理操作系统文件或其他形式文件类型的集合。
Instance：Mysql数据库由后台线程及一个共享内存区组成。

数据库实例才是真正操作数据库文件的。在集群情况下，可能存在一个DB被多个Instance使用的情况。

Mysql被设计为单进程多线程，在OS上的表现是一个进程。

插件式表存储引擎

存储引擎基于表，而不是DB。

存储引擎对开发人员透明。

索引原理

MySQL使用的是B+树作为索引的数据结构

B树是一个分支内按顺序存放多个节点数据的数据结构；而B+树在此基础上，在分支内只存储索引，只在叶子节点存储数据（这样每一层可以存储更多索引，减少层数），并且在叶节点之间用指针互相连接，提高访问效率。

索引分类

数据结构

• B+树索引
• 哈希索引
• 红黑树索引

功能

• 主键索引
• 唯一索引
• 普通索引（一般我们为优化sql建立的索引）
• 全文索引
• 联合索引

存储方式

• 聚簇索引
• 非聚簇索引（索引与数据分开，需要回表）

事务

原子性 Atomicity

BUSINESS
sql语句1
sql语句2
COMMIT

原子性：事务操作要么同时发生，要么同时失败，不存在中间情况

通过Undo Log回滚实现

一致性 Consistency

账户500元 -> 扣除1000元 -> 账户-500元
-- 非法操作

一致性：每个操作都必须是合法的，账户信息应该从一个有效状态到另一个有效状态。

隔离性 Isolation

商户1转账500元 -> 余额更新为500元
商户2转账500元 -> 余额更新为500元
-- 没有隔离性

隔离性：两个操作对同一个账户并发操作时，应该表现为不相互影响类似串行的操作。

持久性 Durability

转账500元到余额 --服务器宕机--> 余额0元

持久性：操作更新成功后，更新的结果应该永久地保留下来，不会因为宕机等问题而丢失。

单线程网络IO、KV读写

Redis的网络IO和KeyValue读写是由一个线程来完成的。
而Redis的持久化、异步删除、集群数据同步是额外的线程执行。

也由于Redis是单线程的，所以要特别小心耗时的操作，这些操作会阻塞后续指令。

简单来说就是处理事务一套、前台接待一套。不会因为前面办事导致人均等待时间太久。

Redis使用IO多路复用（epoll），将连接信息、事件放到队列中，使其能够处理并发的客户端连接。

socket: {
    s0
    s1
    s2
    s3
    "..."
}

IO多路复用: {
    s3 -> s2 -> s1 -> s0
}

事件处理器: {
    连接处理器
    命令请求处理器
    命令回复处理器
}

socket -> IO多路复用 -> 文件事件分派器 -> 事件处理器

详解GET key

Redis相当于HashMap，也由于Hash是无序的，因此scan这样的流式查询，在查改场景中，可能会漏扫中途插入到前面下标的元素。

Redis持久化

RDB Snapshot

默认情况下，Redis将内存数据快照保存为dump.rdb，可以使用

save <time_duration> <row_insertion>

指示Redis多少秒内插入多少条数据后持久化到数据库
也可以直接用save和bgsave命令写入数据库

bgsave 异步持久化

bgsave使用写时复制COW。bgsave从主线程fork出来，当主线程修改数据时，bgsave线程会将写入数据拷贝一份，然后写入rdb

Append-Only File

快照不能做到完全持久，假如服务宕机，可能会丢失几条写入。
这时候我们直接做个命令日志AOF，将执行的修改指令写入appendonly.aof中

appendonly yes
appendfilename "appendonly.aof"

aof有三种模式appendfsync：

• always：立刻写入磁盘
• everysec：每秒写一次
• no：交给OS调度
  但是，由于aof是记录命令，需要执行时间，对于持久化大量数据比较耗时间。
  对于连续操作（如自增）aof会优化为1条命令，可以用bgrewriteaof命令手动重写

# 最小重构大小
auto-aof-rewrite-min-size 64mb
# 增长了100%，即128mb就重构
auto-aof-rewrite-percentage 100

Redis4 混合持久化

由于Redis重启时优先使用aof恢复数据，rdb利用率不高。因此出现了混合持久化

# 必须同时开启aof
aof-use-rdb-preamle yes
# 可以直接把快照关掉，因为混合持久化都写在aof里面

开启后，当aof重写时，会直接写入rdb，将rdb快照和aof增量存储在一起。
于是Redis重启可以先读rdb，再执行增量aof恢复数据，提高效率。

Redis主从

# redis-<your_port>.conf
pidfile /var/run/redis_<your_port>.pid
logfile "<your_port>.log"
# 数据存放目录
dir /usr/local/redis/data/<your_port>

### 主从复制
replicaof <main_redis_ip> <port>
# 从节点，只读
replica-read-only yes


### 启动
# 启动从节点
redis-server redis-<your_port>.conf
# 连接到从节点
redis-cli -p <minor_redis_port>

主从原理

master: {
    rdb data
    repl buffer
}
slave

slave -> master: 1. psync全量复制同步数据（通过socket长连接）
master.rdb data -> master.rdb data: 2.1 收到psync命令，执行bgsave生成最新rdb快照
master.repl buffer -> master.repl buffer: 2.2 主节点将增量写语句更新到buffer
master.rdb data -> slave: 3. 发送rdb数据
slave -> slave: 4. 清空旧数据，加载主节点rdb
master.repl buffer -> slave: 5. 发送缓冲区写命令
slave -> slave: 6. 执行主节点buffer写命令
master -> slave: 7. 主节点通过socket长连接，持续发送写命令给从节点，保持数据一致

断点续传

master: {
    repl backlog buffer
}
slave

slave -> master: 1. 连接断开
master.repl backlog buffer -> master.repl backlog buffer: 2. 主节点增量写命令写入buffer
slave -> master: 3. 恢复socket长连接
slave -> master: 4. psync(offset)带偏移量
master -> slave: 5. 若offset在buffer中，断点以后的数据发送给从节点；否则，全量发送
master -> slave: 6. 持续发送buffer写命令，保持数据一致

如果存在很多从节点，那么主节点传输压力会比较大。可以采用树型架构，让从节点再给它的子节点传输数据。

哨兵高可用

sentinel_cluster: {
    sentinel1 <-> sentinel2 <-> sentinel3 <-> sentinel1
}

client -> master <-> sentinel_cluster
master -> slave1
master -> slave2
client -> sentinel_cluster
sentinel_cluster <-> slave1
sentinel_cluster <-> slave2

哨兵会动态监听redis主节点，如果主节点挂了，哨兵会选择一个新redis示例作为主节点（通知给client端）

开启哨兵

# sentinel.conf

port 26379
pidfile <your_file>
logfile <your_file>
dir "<your_dir>"

# quorm是指多少个sentinel同时认为主节点挂了，才让master失效，一般设置为一半以上
sentinel monitor mymaster <redis_ip> <redis_port> <quorm>

启动哨兵./redis-sentinel sentinel.conf

Redis Cluster

当哨兵集群选举新节点的时候，服务会宕机几秒钟。因此我们需要Cluster

client1 -> RedisCluster
client2 -> RedisCluster
RedisCluster: Hash slot: CRC16(key) % 16384
RedisCluster -> Redis集群
Redis集群: {
    master1 -> slave1-1
    master1 -> slave1-2
    
    master2 -> slave2-1
    master2 -> slave2-2
    
    master3 -> slave3-1
    master3 -> slave3-2
}

在Cluster中，每个master数据是不重叠的，数据会被分片储存。通过Hash算法来决定存储数据到哪一个master节点。
使用Cluster，可以避免Redis服务完全宕机。
2的幂次取模小技巧：

$X \mod 2^n = X \text{ \& } (2^n - 1)$

Redis集群搭建

redis-cluster/
|-- 8000
|   `-- redis.conf
|-- 8010
`-- 8020

1. Redis配置

# ...其他配置

daemonize yes
port 8000
dir /path/to/redis-cluster/8000/
# 启用集群
cluster-enabled yes
cluster-config-file nodes-8000.conf
cluster-node-timeout 5000
# 密码
requirepass <your_password>
masterauth <your_auth_password>

2. 启动所有master和slave节点

redis-server /path/to/redis-cluster/80*/redis.conf
ps aux | grep redis

3. 开启集群

# replicas表示节点的副本，配置为1，则1主1从
redis-cli -a <your_auth_password> --cluster create --cluster-replicas 1 \
localhost:8000 localhost:8001 localhost:8002 ...

注意，第二次启动集群后，就不需要这一步了。节点会自动读取nodes-8000.conf文件，恢复上次集群状态。

4. 进入redis节点验证配置

cluster info
cluster nodes

Redission原理

Thread1: {
    Redission
}
Thread2: {
    Redission
}

Thread1.Redission -> Try Lock
Try Lock -> 守护线程: 加锁成功
守护线程 -> Redis(Master): lock，每隔10s检查线程是否仍持有锁。如果持有，则延长锁失效时间

Thread2.Redission -> Try Lock
Try Lock -> Thread2.Redission: 加锁失败，使用while自旋尝试加锁

Redission利用了Redis Lua脚本保证原子操作。