MIT 6.5840 Lab 2: Key/Value Server (2025)

func (ck *Clerk) Get(key string) (string, rpc.Tversion, rpc.Err) {
	// You will have to modify this function.
	args := rpc.GetArgs{Key: key}
	var reply rpc.GetReply

	for {
		ok := ck.clnt.Call(ck.server, "KVServer.Get", &args, &reply)
		if ok {
			return reply.Value, reply.Version, reply.Err
		}
		time.Sleep(100 * time.Millisecond)
	}
}

func (ck *Clerk) Put(key, value string, version rpc.Tversion) rpc.Err {
	// You will have to modify this function.
	args := rpc.PutArgs{Key: key, Value: value, Version: version}
	var reply rpc.PutReply

	for try := 0; ; try++ {
		ok := ck.clnt.Call(ck.server, "KVServer.Put", &args, &reply)
		if ok {
			switch reply.Err {
			case rpc.OK:
				return rpc.OK
			case rpc.ErrNoKey:
				return rpc.ErrNoKey
			case rpc.ErrVersion:
				if try == 0 {
					return rpc.ErrVersion
				} else {
					return rpc.ErrMaybe
				}
			}
		}
		time.Sleep(100 * time.Millisecond)
	}
}

type valueVersion struct {
	value   string
	version rpc.Tversion
}

type KVServer struct {
	mu sync.Mutex

	// Your definitions here.
	storage map[string]valueVersion
}

func MakeKVServer() *KVServer {
	kv := &KVServer{}
	// Your code here.
	kv.storage = make(map[string]valueVersion)
	return kv
}

// Get returns the value and version for args.Key, if args.Key
// exists. Otherwise, Get returns ErrNoKey.
func (kv *KVServer) Get(args *rpc.GetArgs, reply *rpc.GetReply) {
	// Your code here.
	kv.mu.Lock()
	defer kv.mu.Unlock()

	vv, ok := kv.storage[args.Key]
	if ok {
		reply.Err = rpc.OK
		reply.Value = vv.value
		reply.Version = vv.version
	} else {
		reply.Err = rpc.ErrNoKey
	}
}

// Update the value for a key if args.Version matches the version of
// the key on the server. If versions don't match, return ErrVersion.
// If the key doesn't exist, Put installs the value if the
// args.Version is 0, and returns ErrNoKey otherwise.
func (kv *KVServer) Put(args *rpc.PutArgs, reply *rpc.PutReply) {
	// Your code here.
	kv.mu.Lock()
	defer kv.mu.Unlock()

	if args.Version == 0 {
		if _, ok := kv.storage[args.Key]; ok {
			reply.Err = rpc.ErrVersion
		} else {
			kv.storage[args.Key] = valueVersion{value: args.Value, version: 1}
			reply.Err = rpc.OK
		}
	} else {
		if vv, ok := kv.storage[args.Key]; ok {
			if args.Version == vv.version {
				kv.storage[args.Key] = valueVersion{value: args.Value, version: args.Version + 1}
				reply.Err = rpc.OK
			} else {
				reply.Err = rpc.ErrVersion
			}
		} else {
			reply.Err = rpc.ErrNoKey
		}
	}
}

if args.Version == 0 {
	if _, ok := kv.storage[args.Key]; ok {
		reply.Err = rpc.ErrVersion
		return
	}

	kv.storage[args.Key] = valueVersion{value: args.Value, version: 1}
	reply.Err = rpc.OK
	return
}

if vv, ok := kv.storage[args.Key]; ok {
	if args.Version == vv.version {
		kv.storage[args.Key] = valueVersion{value: args.Value, version: args.Version + 1}
		reply.Err = rpc.OK
		return
	}

  	reply.Err = rpc.ErrVersion
	return
}

reply.Err = rpc.ErrNoKey

type Lock struct {
	// IKVClerk is a go interface for k/v clerks: the interface hides
	// the specific Clerk type of ck but promises that ck supports
	// Put and Get.  The tester passes the clerk in when calling
	// MakeLock().
	ck kvtest.IKVClerk
	// You may add code here
	key string
	id  string
}

// The tester calls MakeLock() and passes in a k/v clerk; your code can
// perform a Put or Get by calling lk.ck.Put() or lk.ck.Get().
//
// Use l as the key to store the "lock state" (you would have to decide
// precisely what the lock state is).
func MakeLock(ck kvtest.IKVClerk, l string) *Lock {
	lk := &Lock{ck: ck}
	// You may add code here
	lk.key = l
	lk.id = kvtest.RandValue(8)
	return lk
}

const FREE = "FREE"

func (lk *Lock) Acquire() {
	// Your code here
	for {
		state, version, errGet := lk.ck.Get(lk.key)
		switch errGet {
		case rpc.OK:
			switch state {
			case FREE:
				if lk.setLock(version) {
					return
				} else {
					// next round
				}
			case lk.id:
				// self already acquired the lock
				return
			default:
				// someone else acquired the lock, next round
			}
		case rpc.ErrNoKey:
			if lk.setLock(0) {
				return
			} else {
				// next round
			}
		}
		time.Sleep(100 * time.Millisecond)
	}
}

func (lk *Lock) setLock(version rpc.Tversion) bool {
	errPut := lk.ck.Put(lk.key, lk.id, version)
	switch errPut {
	case rpc.OK:
		return true
	case rpc.ErrNoKey:
		// should not happen, but if happens, then next round
		return false
	case rpc.ErrVersion:
		// someone else acquired the lock, next round
		return false
	case rpc.ErrMaybe:
		id, _, _ := lk.ck.Get(lk.key)
		if id == lk.id {
			return true
		} else {
			// FREE: the lock been acquired by others and released
			// OTHERID: someone else acquired the lock, next round
			return false
		}
	default:
		return false
	}
}

func (lk *Lock) Release() {
	// Your code here
	state, version, errGet := lk.ck.Get(lk.key)
	if errGet == rpc.OK && state == lk.id {
		lk.ck.Put(lk.key, FREE, version)
	}
}