Olivine: Building a Redis-Compatible Service in Go. · 章節目錄

第 14 章

[Day 14] SET with exists KEYs

SET Redis command supports some options needs stored value.

  • NX: only set value when key doesn’t exist
  • XX: only set value when key exists
# because key "foo" doesn't exist, SET successful.
(redis-cli) > SET foo bar NX
OK
(redis-cli) > GET foo
"bar"
# because key "foo" exists, SET failed.
(redis-cli) > SET foo baz NX
(nil)
(redis-cli) > GET foo
"bar"
  • IFEQ {val}: only set value when stored value equals {val}
  • IFNE {val}: only set value when stored value not equals {val}
(redis-cli) > SET foo bar
OK
# SET successful
(redis-cli) > SET foo baz IFEQ bar
OK
# SET failed
(redis-cli) > SET foo bax IFEQ bar

Code Review and Refactor

I’ve implemented some prototype of this feature, but incomplete.

const (
	nx    = iota + 1 // set value only not exists
	xx               // set value only exists
	ifeq             // set only value == cond.Val
	ifne             // set only value != cond.Val
	ifdeq            // set only XXH3(value) == cond.Val
	ifdne            // set only XXH3(value) != cond.Val
)

type parseSetCond struct {
	Typ int
	Val string
}

type parsedSet struct {
	K    string
	V    string
	Cond parseSetCond
	Get  bool
	Exp  *time.Time
}

var _ repo.SetParam = parsedSet{}

func (parsed parsedSet) Obj() object.Object {
	return object.NewString(parsed.K, parsed.V, parsed.Exp)
}

It just parses with condition options (NX, XX, IFEQ, IFNE, …) but useless; in the other hand, it defined in cmd, but should be used in repo.

Otherwise, the repo.SetParam{} handles all data type inputs: object.String, object.Hash, … maybe add object.List or object.OrderedSet in future. However, it stores by s.storage[param.Obj().Key()] = param.Obj() directly.

It’s time to refactor code.

SetStringParam{} interface

I defined a SetStringParam{} interface which composition with SetParam{}:

const (
	CondNX    Cond = iota + 1 // set value only not exists
	CondXX                    // set value only exists
	CondIFEQ                  // set only value == cond.Val
	CondIFNE                  // set only value != cond.Val
	CondIFDEQ                 // set only XXH3(value) == cond.Val
	CondIFDNE                 // set only XXH3(value) != cond.Val
)

type SetStringParam interface {
	SetParam

	CondType() Cond
	CondValue() string
	ExpiresAt() *time.Time
	KeepTTL() bool

	GetCurrent() bool
	SetCurrent(*object.String)
}

Rename cmd.parsedSet{} to cmd.setparams{}, and be a SetStringParam{}:

type setparams struct {
	key string
	val string

	// NX|XX|IFEQ|IFNE|IFDEQ|IFDNE
	condType  repo.Cond
	condValue string

	// GET
	get bool
	cur *object.String

	// EX|PX|EXAT|PXAT
	exp     *time.Time
	keepTTL bool
}

var _ repo.SetStringParam = &setparams{}

func (p *setparams) Obj() object.Object {
	return object.NewString(p.key, p.val, p.exp)
}

func (p *setparams) CondType() repo.Cond {
	return p.condType
}

func (p *setparams) CondValue() string {
	return p.condValue
}

func (p *setparams) ExpiresAt() *time.Time {
	return p.exp
}

func (p *setparams) KeepTTL() bool {
	return p.keepTTL
}

func (p *setparams) GetCurrent() bool {
	return p.get
}

func (p *setparams) SetCurrent(cur *object.String) {
	p.cur = cur
}

Don’t forget to update parse() for cmd.setparams{}.

Handle mapStorage.Set() with SetStringParam{}

func (s *mapStorage) Set(_ context.Context, param SetParam) error {
	if strparam, ok := param.(SetStringParam); ok {
		return s.setString(strparam)
	}

	return errors.New("unimplemented")
}

func (s *mapStorage) setString(param SetStringParam) error {
	s.mu.Lock()
	defer s.mu.Unlock()

	s.storage[param.Obj().Key()] = param.Obj()

	return nil
}

setString() implementation

There’s some features when setString():

  • Delete expired key when getting current value (passive way deletion).
  • Attach current value if GET option set and it is *object.String.
  • Check conditions (NX, XX, IFEQ, IFNE, …) before setting.
  • object.SetExpiresAt() with current value if KEEPTTL is set.
func (s *mapStorage) setString(param SetStringParam) error {
	s.mu.Lock()
	defer s.mu.Unlock()

	obj := param.Obj()

	cur, exists := s.storage[obj.Key()]
	if cur != nil && cur.Expired() {
		delete(s.storage, obj.Key())
		cur = nil
		exists = false
	}

	if param.GetCurrent() {
		if !exists {
			param.SetCurrent(nil)
		} else {
			if curstr, ok := cur.(*object.String); !ok {
				return ErrTypeMismatch
			} else {
				param.SetCurrent(curstr)
			}
		}
	}
	if err := s.checkStringCond(param, cur, exists); err != nil {
		return fmt.Errorf("%w: %w", ErrCondMismatch, err)
	}
	if param.KeepTTL() && cur != nil {
		obj.SetExpiresAt(cur.ExpiresAt())
	}

	s.storage[obj.Key()] = obj

	return nil
}

func (s *mapStorage) checkStringCond(param SetStringParam, current object.Object, exists bool) error {
	switch param.CondType() {
	case 0:
		return nil
	case CondNX:
		if exists {
			return errors.New("data found")
		}
	case CondXX:
		if !exists {
			return errors.New("data not found")
		}
	case CondIFEQ:
		if !exists {
			return errors.New("data not found")
		}
		if str, ok := current.(*object.String); !ok {
			return ErrTypeMismatch
		} else if !str.Equals(param.CondValue()) {
			return errors.New("data mismatch")
		}
	case CondIFNE:
		if !exists {
			return errors.New("data not found")
		}
		if str, ok := current.(*object.String); !ok {
			return ErrTypeMismatch
		} else if str.Equals(param.CondValue()) {
			return errors.New("data match")
		}
	case CondIFDEQ:
		if !exists {
			return errors.New("data not found")
		}
		if str, ok := current.(*object.String); !ok {
			return ErrTypeMismatch
		} else if !str.EqualsDigest(param.CondValue()) {
			return errors.New("data match")
		}
	case CondIFDNE:
		if !exists {
			return errors.New("data not found")
		}
		if str, ok := current.(*object.String); !ok {
			return ErrTypeMismatch
		} else if str.EqualsDigest(param.CondValue()) {
			return errors.New("data match")
		}
	default:
		panic(fmt.Sprintf("unknow condition type: %d", param.CondType()))
	}

	return nil
}

Note: setString() is a workaround at this moment, the better way is factory method pattern to handle SET, HSET, ZSET, … and more.

About AOF and KEEPTTL

Option KEEPTTL is a challenge with AOF.

I’ve rewritten commands for AOF when EX and PX options. However, the KEEPTTL is too hard to handle: we cannot ensure the current expiration in command parsing stage.

Therefore, it is an unexpected behavior of using KEEPTTL and AOF in the same time, we’ll try to solve it in future.

IFDEQ and IFDNE

The value in storage could be very large, IFEQ or IFNE costs O(n)O(n) time complexity which nn means stringn length.

Redis supports IFDEQ and IFDNE options to compare with digest. Redis uses XXH3 for digest algorithm.

Add digest uint64 in *object.String{}:

type String struct {
	*base

	val    string
	digest uint64
}
func (str *String) EqualsDigest(v string) bool {
	n, err := strconv.ParseUint(v, 10, 0)
	if err != nil {
		return false
	}

	return n == str.digest
}

Generate digest when set in storage:

func NewString(k, v string, expiresAt *time.Time) *String {
	return &String{
		val:    v,
		digest: xxh3.HashString(v),
		base:   &base{key: k, expiresAt: expiresAt},
	}
}

Note: I’m using github.com/zeebo/xxh3 to generate XXH3 hash with string, it is fast because SIMD.