[Day 16] Profiling with mutex lock

redis-benchmark uses the same key if -r not specified, it makes mutex lock waiting when set/get paralleling.

That why we can get a flame graph with redis-benchmark -p 16379 -t SET -P 16 below:

It wastes 40% CPU time for trying to get mutex lock, and get the same result even if we use redis-benchmark -p 16379 -t SET -P 16 -r 1000000.

Note: redis-benchmark uses radom key format in key:{12 bytes number} when -r <keyspacelen> specified, the 12 bytes number in range $[0, \<keyspacelen\>]$

We can get more information about what blocks service by getting report from http://localhost:6060/debug/pprof/block after benchmarking.

It takes 1464.62 seconds for waiting mutex lock.

Lock Striping

“Lock striping” is a pattern for concurrent programming: lock a part of resource instead of lock resource completely.

Defines some “slots” and decide which slot stores the given key by hashing.

Refactor mapStorage

func NewStorage() Storage {
	s := mapStorage{}
	for i := range lockStripeCount {
		s.storage[i] = make(map[string]object.Object)
	}

	return &s
}

const lockStripeCount = 16

type mapStorage struct {
	storage [lockStripeCount]map[string]object.Object
	stripes [lockStripeCount]sync.Mutex
}

const lockStripeCount = 16, it is a balance value of slot count.

func (s *mapStorage) stripe(k string) uint64 {
	return xxh3.HashString(k) & (lockStripeCount - 1)
}

Use xxh3.HashString(k) for hashing the key, it returns a uint64. There’s only 16 slots, it can be fit by hashed % lockStripeCount.

Note: hashed % lockStripeCount equals hashed & (lockStripeCount-1) if lockStripeCount is $2^n$.

Refactor (*mapStorage).Set() and (*mapStorage).Get()

We should get which slot will be operated before getting or setting.

func (s *mapStorage) setString(param SetStringParam) error {
	obj := param.Obj()

	slot := s.stripe(obj.Key())
	s.stripes[slot].Lock()
	defer s.stripes[slot].Unlock()

	cur, exists := s.storage[slot][obj.Key()]

func (s *mapStorage) Get(_ context.Context, k string) (v object.Object, err error) {
	slot := s.stripe(k)
	s.stripes[slot].Lock()
	defer s.stripes[slot].Unlock()

	var ok bool
	if v, ok = s.storage[slot][k]; !ok {
		return nil, fmt.Errorf("%w: miss", ErrNotFound)
	}
	if v.ExpiresAt() != nil && time.Now().After(*v.ExpiresAt()) {
		delete(s.storage[slot], k) // remove key from storage when expired
		return nil, fmt.Errorf("%w: expired", ErrNotFound)
	}

	return
}

Result

The flame graph of profiling after refactoring:

It costs CPU time from 47.33s(37.7%) to 8.58s(4.7%).

Otherwise, it blocks from 1464.62s to 22.53s.