Практическая реализация локального кеша — статьи по реализации

задняя часть Go
Практическая реализация локального кеша — статьи по реализации

Оригинальная ссылка:Практическая реализация локального кеша — статьи по реализации

предисловие

Всем привет, яasong"После введения в предыдущие две статьи мы в основном поняли, как спроектировать локальный кеш. Эта статья является завершением этой серии. Реализуйте локальный кеш самостоятельно. Далее слушайте меня подробно! ! !

Код этой статьи выложен на github:GitHub.com/Assong2020/…

Сейчас это версия 1.0, и в будущем она будет оптимизирована и доработана.

Шаг 1: Абстрактный интерфейс

Первый шаг очень важен. Основываясь на принципе интерфейсно-ориентированного программирования, мы сначала абстрагируем методы, которые должны быть представлены пользователям, и предоставляем пользователям простые и понятные методы. Поэтому результаты, которые я абстрагировал, следующие:

// ICache abstract interface
type ICache interface {
	// Set value use default expire time. default does not expire.
	Set(key string, value []byte) error
	// Get value if find it. if value already expire will delete.
	Get(key string) ([]byte, error)
	// SetWithTime set value with expire time
	SetWithTime(key string, value []byte, expired time.Duration) error
	// Delete manual removes the key
	Delete(key string) error
	// Len computes number of entries in cache
	Len() int
	// Capacity returns amount of bytes store in the cache.
	Capacity() int
	// Close is used to signal a shutdown of the cache when you are done with it.
	// This allows the cleaning goroutines to exit and ensures references are not
	// kept to the cache preventing GC of the entire cache.
	Close() error
	// Stats returns cache's statistics
	Stats() Stats
	// GetKeyHit returns key hit
	GetKeyHit(key string) int64
}
  • Set(key string, value []byte): данные, хранящиеся с помощью этого метода, используют время истечения срока действия по умолчанию. Если асинхронная задача, очищающая просроченные данные, не включена, срок их действия никогда не истечет. В противном случае срок действия по умолчанию составляет 10 минут.
  • Get(key string) ([]byte, error):согласно сkeyПолучите содержимое объекта, если срок действия данных истечет, он будет удален на этом шаге.
  • SetWithTime(key string, value []byte, expired time.Duration): Объект хранилища должен использовать настраиваемый срок действия.
  • Delete(key string) error: удалить соответствующие кэшированные данные по ключу
  • Len() int: получить количество кэшированных объектов
  • Capacity() int: получить текущую емкость кэша
  • Close() error: закрыть кеш
  • Stats() Stats: данные мониторинга кэша
  • GetKeyHit(key string) int64:Получатьkeyданные о частоте попаданий

Шаг 2: Определите объект кеша

Первым шагом является абстрагирование интерфейса. Далее нам нужно определить экземпляр объекта кеша для реализации интерфейса. Давайте сначала посмотрим на структуру определения:

type cache struct {
	// hashFunc represents used hash func
	hashFunc HashFunc
	// bucketCount represents the number of segments within a cache instance. value must be a power of two.
	bucketCount uint64
	// bucketMask is bitwise AND applied to the hashVal to find the segment id.
	bucketMask uint64
	// segment is shard
	segments []*segment
	// segment lock
	locks    []sync.RWMutex
	// close cache
	close chan struct{}
}
  • hashFunc: хеш-функцию, которая будет использоваться для сегментирования, которую пользователь может определить и реализовать.HashFuncИнтерфейс можно использовать по умолчаниюfnvалгоритм.
  • bucketCount: количество осколков, которое должно быть четным числом.Количество осколков по умолчанию равно256.
  • bucketMask: поскольку количество сегментов четное, вместо операций с остатком можно использовать битовые операции, чтобы повысить эффективность производительности, когда возможно сегментирование.hashValue % bucketCount == hashValue & bucketCount - 1.
  • segments: объект сегмента, структура объектов каждого сегмента будет представлена ​​позже.
  • locks: Блокировка чтения-записи для каждого сегмента
  • close: уведомлять других, когда кешированный объект закрываетсяgoroutineПауза

Далее пишемcacheКонструктор объекта:

// NewCache constructor cache instance
func NewCache(opts ...Opt) (ICache, error) {
	options := &options{
		hashFunc: NewDefaultHashFunc(),
		bucketCount: defaultBucketCount,
		maxBytes: defaultMaxBytes,
		cleanTime: defaultCleanTIme,
		statsEnabled: defaultStatsEnabled,
		cleanupEnabled: defaultCleanupEnabled,
	}
	for _, each := range opts{
		each(options)
	}

	if !isPowerOfTwo(options.bucketCount){
		return nil, errShardCount
	}

  if options.maxBytes <= 0 {
		return nil, ErrBytes
	}
  
	segments := make([]*segment, options.bucketCount)
	locks := make([]sync.RWMutex, options.bucketCount)

	maxSegmentBytes := (options.maxBytes + options.bucketCount - 1) / options.bucketCount
	for index := range segments{
		segments[index] = newSegment(maxSegmentBytes, options.statsEnabled)
	}

	c := &cache{
		hashFunc: options.hashFunc,
		bucketCount: options.bucketCount,
		bucketMask: options.bucketCount - 1,
		segments: segments,
		locks: locks,
		close: make(chan struct{}),
	}
    if options.cleanupEnabled {
		go c.cleanup(options.cleanTime)
	}
	
	return c, nil
}

Здесь для лучшего расширения мы используемOptionsВ режиме программирования наш конструктор в основном делает три вещи:

  • Предварительная проверка параметров, для параметров, переданных извне, нам еще нужно выполнить базовую проверку
  • Инициализация объекта Shard
  • Создать объект кеша

При построении объекта кеша здесь нам нужно сначала рассчитать емкость каждого сегмента, по умолчанию весь локальный кеш256MЗатем данные равномерно распределяются по каждой области, и пользователь может выбрать размер кэшируемых данных.

Шаг 3: Определите структуру сегментирования

Структура каждого шарда следующая:

type segment struct {
	hashmap map[uint64]uint32
	entries buffer.IBuffer
	clock   clock
	evictList  *list.List
	stats IStats
}
  • hashmp:место храненияkeyСоответствующий индекс хранения
  • entries:место храненияkey/valueБазовая структура, которую мы представили на четвертом шаге, также является основной частью кода.
  • clock: определить метод времени
  • evicList: здесь мы используем очередь для записиoldИндексировать, сбрасывать при недостаточном объеме (временное решение, текущая структура хранилища не подходит для использования)LRUалгоритм исключения)
  • stats: Кэшированные данные мониторинга.

Далее давайте взглянем на конструктор каждого шарда:

func newSegment(bytes uint64, statsEnabled bool) *segment {
	if bytes == 0 {
		panic(fmt.Errorf("bytes cannot be zero"))
	}
	if bytes >= maxSegmentSize{
		panic(fmt.Errorf("too big bytes=%d; should be smaller than %d", bytes, maxSegmentSize))
	}
	capacity := (bytes + segmentSize - 1) / segmentSize
	entries := buffer.NewBuffer(int(capacity))
	entries.Reset()
	return &segment{
		entries: entries,
		hashmap: make(map[uint64]uint32),
		clock:   &systemClock{},
		evictList: list.New(),
		stats: newStats(statsEnabled),
	}
}

Здесь главное отметить:

Нам нужно рассчитать емкость в соответствии с размером кэшированных данных каждого сегмента, что соответствует шагам инициализации объекта кэша, описанным выше.

Шаг 4: Определите структуру кеша

Теперь объект кеша создан, и следующим шагом является ядро ​​локального кеша: определение структуры кеша.

bigcache,fastcache,freecacheОба вместо этого используют массивы байтовmapСохраняйте кешированные данные, тем самым уменьшаяGCдавление, поэтому мы также можем продолжать использовать байтовые массивы для справки, здесь мы используем двумерные байтовые срезы для хранения кэшированных данныхkey/value; нарисуйте картинку, чтобы показать:

Использование двумерного массива для хранения данных по сравнению сbigcacheПреимущество в том, что соответствующие данные могут быть удалены непосредственно в соответствии с индексом.Хотя будут проблемы с червоточиной, мы можем записать индекс червоточины и постоянно его заполнять.

Структура инкапсуляции каждого кеша выглядит следующим образом:

Основная идея прояснилась, давайте взглянем на нашу инкапсуляцию уровня хранения:

type Buffer struct {
	array [][]byte
	capacity int
	index int
	// maxCount = capacity - 1
	count int
	// availableSpace If any objects are removed after the buffer is full, the idle index is logged.
	// Avoid array "wormhole"
	availableSpace map[int]struct{}
	// placeholder record the index that buffer has stored.
	placeholder map[int]struct{}
}
  • array [][]byte: сохранить 2D-срез кэшированного объекта
  • capacity: максимальная емкость структуры кэша
  • index: индекс, который записывает индекс места, где находится кеш.
  • count: записать количество буферов
  • availableSpace: Запишите «червоточину», когда объект кеша будет удален, запишите индекс свободного места, чтобы «червоточину» можно было использовать позже, когда емкость будет заполнена.
  • placeholder: Запишите индекс кэшированного объекта, который можно использовать для многократной очистки кэша с истекшим сроком действия.

В направленииbufferПроцесс записи данных (код не выложен):

Шаг 5. Улучшите метод записи данных в кеш

Выше мы определили все необходимые структуры, следующим шагом будет заполнение нашего метода кэширования записи:

func (c *cache) Set(key string, value []byte) error  {
	hashKey := c.hashFunc.Sum64(key)
	bucketIndex := hashKey&c.bucketMask
	c.locks[bucketIndex].Lock()
	defer c.locks[bucketIndex].Unlock()
	err := c.segments[bucketIndex].set(key, hashKey, value, defaultExpireTime)
	return err
}

func (s *segment) set(key string, hashKey uint64, value []byte, expireTime time.Duration) error {
	if expireTime <= 0{
		return ErrExpireTimeInvalid
	}
	expireAt := uint64(s.clock.Epoch(expireTime))

	if previousIndex, ok := s.hashmap[hashKey]; ok {
		if err := s.entries.Remove(int(previousIndex)); err != nil{
			return err
		}
		delete(s.hashmap, hashKey)
	}

	entry := wrapEntry(expireAt, key, hashKey, value)
	for {
		index, err := s.entries.Push(entry)
		if err == nil {
			s.hashmap[hashKey] = uint32(index)
			s.evictList.PushFront(index)
			return nil
		}
		ele := s.evictList.Back()
		if err := s.entries.Remove(ele.Value.(int)); err != nil{
			return err
		}
		s.evictList.Remove(ele)
	}
}

Анализ процесса выглядит следующим образом:

  • согласно сkeyВычислите хеш-значение, а затем получите соответствующее расположение осколков в соответствии с количеством осколков.
  • Если текущий кеш существует с таким жеkey, затем сначала удалите, а затем снова вставьте, время истечения срока действия будет обновлено
  • Инкапсулировать структуру хранения в соответствии с отметкой времени истечения срока действия,keyДлина, размер хеша, объект кеша для инкапсуляции
  • Сохраните данные в кеше, если кеш не работает, удалите самые старые данные и повторите попытку.

Шаг 6: Улучшите метод чтения данных из кеша

Первый шаг основан наkeyВычислите хэш-значение, а затем получите соответствующую позицию осколка в соответствии с количеством осколков:

func (c *cache) Get(key string) ([]byte, error)  {
	hashKey := c.hashFunc.Sum64(key)
	bucketIndex := hashKey&c.bucketMask
	c.locks[bucketIndex].RLock()
	defer c.locks[hashKey&c.bucketMask].RUnlock()
	entry, err := c.segments[bucketIndex].get(key, hashKey)
	if err != nil{
		return nil, err
	}
	return entry,nil
}

Второй шаг — выполнить метод шардинга для получения кешированных данных:

  • Сначала судите по хэш-значениюkeyСуществует ли он в кеше, если не возвращаетсяkeyне смог найти
  • Считайте данные из кеша, чтобы получить данные в кешеkeyОпределить, происходит ли коллизия хэшей
  • Определите, истек ли срок действия кэшированного объекта, и удалите кэшированные данные после истечения срока действия (могут ли быть возвращены текущие просроченные данные в соответствии с потребностями оптимизации бизнеса)
  • Кэшировать данные мониторинга в каждой записи
func (s *segment) getWarpEntry(key string, hashKey uint64) ([]byte,error) {
	index, ok := s.hashmap[hashKey]
	if !ok {
		s.stats.miss()
		return nil, ErrEntryNotFound
	}
	entry, err := s.entries.Get(int(index))
	if err != nil{
		s.stats.miss()
		return nil, err
	}
	if entry == nil{
		s.stats.miss()
		return nil, ErrEntryNotFound
	}

	if entryKey := readKeyFromEntry(entry); key != entryKey {
		s.stats.collision()
		return nil, ErrEntryNotFound
	}
	return entry, nil
}

func (s *segment) get(key string, hashKey uint64) ([]byte, error) {
	currentTimestamp := s.clock.TimeStamp()
	entry, err := s.getWarpEntry(key, hashKey)
	if err != nil{
		return nil, err
	}
	res := readEntry(entry)

	expireAt := int64(readExpireAtFromEntry(entry))
	if currentTimestamp - expireAt >= 0{
		_ = s.entries.Remove(int(s.hashmap[hashKey]))
		delete(s.hashmap, hashKey)
		return nil, ErrEntryNotFound
	}
	s.stats.hit(key)

	return res, nil
}

Шаг 7: Приходите на тестовый пример, чтобы испытать

Давайте проверим это на простом тестовом примере:

func (h *cacheTestSuite) TestSetAndGet() {
	cache, err := NewCache()
	assert.Equal(h.T(), nil, err)
	key := "asong"
	value := []byte("公众号：Golang梦工厂")

	err = cache.Set(key, value)
	assert.Equal(h.T(), nil, err)

	res, err := cache.Get(key)
	assert.Equal(h.T(), nil, err)
	assert.Equal(h.T(), value, res)
	h.T().Logf("get value is %s", string(res))
}

результат операции:

=== RUN   TestCacheTestSuite
=== RUN   TestCacheTestSuite/TestSetAndGet
    cache_test.go:33: get value is 公众号：Golang梦工厂
--- PASS: TestCacheTestSuite (0.00s)
    --- PASS: TestCacheTestSuite/TestSetAndGet (0.00s)
PASS

Готово, основные функции пройдены, а остальное — прогонять бенчмарки, оптимизировать и итерировать (в статье не буду вдаваться в подробности, можете обратить на это вниманиеgithubобновления склада).

Справочная статья

Суммировать

На этом глава реализации закончена, но кодирование этого проекта еще не закончено.Я буду продолжать итерации и оптимизацию на основе этой версии.Преимущества этого локального кеша:

  • Простота реализации и легкость понимания
  • Использование двумерных срезов в качестве структуры хранения позволяет избежать того недостатка, что лежащие в основе данные не могут быть удалены, а также в определенной степени позволяет избежать проблемы «червоточины».
  • Полные тестовые примеры, подходящие в качестве проекта начального уровня для Xiaobai.

Точки, которые нужно оптимизировать:

  • Неиспользование эффективного алгоритма удаления кеша может привести к частому удалению горячих данных.
  • Регулярное удаление данных с истекшим сроком действия приведет к тому, что блокировка будет удерживаться слишком долго, и ее необходимо оптимизировать.
  • Закрытие экземпляров кеша требует оптимизированной обработки
  • Оптимизирован в соответствии с бизнес-сценариями (конкретными бизнес-сценариями)

Точка итерации:

  • Добавить функцию кэширования асинхронной загрузки
  • ...... (думая)

Код этой статьи выложен на github:GitHub.com/Assong2020/…

Что ж, на этом статья заканчивается, яasong, увидимся в следующий раз.

Добро пожаловать в публичный аккаунт: [Фабрика грез Golang]

Категории