MIT 6.5840-分布式系统 Lab2

相关资料

Lab要求

总结

• 如何保证只执行一次

  • 每次请求时携带一个token，用于标识请求

    // DoOnce 每次请求时携带
    type DoOnce struct {
    	// 标识本次请求
    	Token string
    }
    
    // GetToken 获取本次请求的标识符
    func (ck *Clerk) GetToken(operation string) string {
    	return fmt.Sprintf("%s_%d", operation, nrand())
    }
    

  • server记录所有的token，对于put和append，先校验token是否存在，如果已存在，就不要再修改

    _, done := kv.tokenMap[token]
    kv.tokenMap[token] = struct{}{}
    return done
    

• 如何确保相同append请求的返回值一致

  • 由于append请求需要返回修改前的值，那么存在这样一种情况，同一个append发送了两次，第一次先到，server修改了结果，在第二次append到达之前，server收到了put命令，此时第二次append返回的oldVal就会不正确，因此需要在server用一个map记录append命令的oldVal，其中key为每次append请求的token，value为某次请求对应的oldVal

  • 在执行append命令时额外做判断，如果此前已经执行过，就从appendMap获取oldVal，否则从cache中获取

    func (kv *KVServer) Append(args *PutAppendArgs, reply *PutAppendReply) {
    	// Your code here.
    	kv.mu.Lock()
    	defer kv.mu.Unlock()
    
    	oldVal := kv.m[args.Key]
    	if !kv.judgeDone(args.Token) {
    		kv.appendMap[args.Token] = oldVal
    		kv.m[args.Key] = oldVal + args.Value
    	} else {
    		oldVal = kv.appendMap[args.Token]
    	}
    	reply.Value = oldVal
    }
    

代码

https://github.com/Wonder-Forever/6.5840-2024/pull/7/commits/74dd50ec727952dd100a628b40cef866fb5aac48

知识补充

• sync.Cond

  • sync.Cond 是 Go 语言中用于协调想要访问共享资源的多个 goroutine 的同步原语。它可以让一个或多个 goroutine 等待某个条件，而在条件达成时接收通知并继续执行

  • 使用方式

    // 创建一个 sync.Cond 实例。这通常通过传递一个已存在的锁（sync.Mutex 或 sync.RWMutex）给 sync.NewCond 函数来完成
    var mu sync.Mutex
    cond := sync.NewCond(&mu)
    
    // 在等待条件时，goroutine 需要首先获取锁，然后调用 cond.Wait() 方法。在调用 Wait() 之前，应该检查条件是否已经满足，如果不满足，则等待。Wait() 方法会自动释放锁，并阻塞当前 goroutine 直到收到通知。
    mu.Lock()
    for !condition { // 检查条件是否满足
        cond.Wait()
    }
    // 处理条件满足后的逻辑
    mu.Unlock()
    
    // 当条件发生变化，可能满足其他 goroutine 的等待条件时，应该发送通知。这可以通过 cond.Signal() 或 cond.Broadcast() 方法来完成。Signal() 唤醒等待 Cond 的一个 goroutine，而 Broadcast() 唤醒所有等待的 goroutine。
    mu.Lock()
    // 改变条件
    cond.Signal() // 或者 cond.Broadcast()，根据需要唤醒 goroutine
    mu.Unlock()
    

  • 注意：

    • 总是在锁的保护下使用 Wait(), Signal(), 和 Broadcast() 方法。
    • Wait() 方法在返回时会重新获取锁，因此不需要手动重新锁定。
    • 在发送通知之前，确保已经改变了条件，否则可能导致等待的 goroutine 再次进入等待状态。
    • 使用 Signal() 还是 Broadcast() 取决于你想唤醒多少等待的 goroutine。如果只需要唤醒一个，用 Signal()；如果要唤醒所有等待的 goroutine，用 Broadcast()。
    • 如果调用 Signal() 还是 Broadcast() 时如果没有等待的 goroutine，这个调用不会有任何效果，也不会报错或阻塞。当后续有 goroutine 调用 Wait 方法时，它将正常等待，直到下一次 Signal 或 Broadcast 被调用。

• 管道

  • 发送者可通过 close 关闭一个信道来表示没有需要发送的值了。接收者可以通过为接收表达式分配第二个参数来测试信道是否被关闭:v, ok := <-ch
  • 循环 for i := range c 会不断从信道接收值，直到它被关闭
  • 向已关闭的chan写数据会引发panic，向已关闭的chan读数据会先读取缓冲区的值，没有缓冲数据后会返回零值
  • select 语句使一个 Go 程可以等待多个通信操作，它会阻塞到某个分支可以继续执行为止，当 select 中的其它分支都没有准备好时，default 分支就会执行。