文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

动手实现一个Localcache-实现篇

2024-12-02 11:02

关注

本文代码已经上传到github:https://github.com/asong2020/go-localcache

现在这一版本算是一个1.0,后续会继续进行优化和迭代。

第一步:抽象接口

第一步很重要,以面向接口编程为原则,我们先抽象出来要暴露给用户的方法,给用户提供简单易懂的方法,因此我抽象出来的结果如下:

  1. // ICache abstract interface 
  2. type ICache interface { 
  3.  // Set value use default expire timedefault does not expire. 
  4.  Set(key string, value []byte) error 
  5.  // Get value if find it. if value already expire will delete
  6.  Get(key string) ([]byte, error) 
  7.  // SetWithTime set value with expire time 
  8.  SetWithTime(key string, value []byte, expired time.Duration) error 
  9.  // Delete manual removes the key 
  10.  Delete(key string) error 
  11.  // Len computes number of entries in cache 
  12.  Len() int 
  13.  // Capacity returns amount of bytes store in the cache. 
  14.  Capacity() int 
  15.  // Close is used to signal a shutdown of the cache when you are done with it. 
  16.  // This allows the cleaning goroutines to exit and ensures references are not 
  17.  // kept to the cache preventing GC of the entire cache. 
  18.  Close() error 
  19.  // Stats returns cache's statistics 
  20.  Stats() Stats 
  21.  // GetKeyHit returns key hit 
  22.  GetKeyHit(key string) int64 

第二步:定义缓存对象

第一步我们抽象好了接口,下面就要定义一个缓存对象实例实现接口,先看定义结构:

  1. type cache struct { 
  2.  // hashFunc represents used hash func 
  3.  hashFunc HashFunc 
  4.  // bucketCount represents the number of segments within a cache instance. value must be a power of two. 
  5.  bucketCount uint64 
  6.  // bucketMask is bitwise AND applied to the hashVal to find the segment id. 
  7.  bucketMask uint64 
  8.  // segment is shard 
  9.  segments []*segment 
  10.  // segment lock 
  11.  locks    []sync.RWMutex 
  12.  // close cache 
  13.  close chan struct{} 

接下来我们来写cache对象的构造函数:

  1. // NewCache constructor cache instance 
  2. func NewCache(opts ...Opt) (ICache, error) { 
  3.  options := &options{ 
  4.   hashFunc: NewDefaultHashFunc(), 
  5.   bucketCount: defaultBucketCount, 
  6.   maxBytes: defaultMaxBytes, 
  7.   cleanTime: defaultCleanTIme, 
  8.   statsEnabled: defaultStatsEnabled, 
  9.   cleanupEnabled: defaultCleanupEnabled, 
  10.  } 
  11.  for _, each := range opts{ 
  12.   each(options) 
  13.  } 
  14.  
  15.  if !isPowerOfTwo(options.bucketCount){ 
  16.   return nil, errShardCount 
  17.  } 
  18.  
  19.   if options.maxBytes <= 0 { 
  20.   return nil, ErrBytes 
  21.  } 
  22.    
  23.  segments := make([]*segment, options.bucketCount) 
  24.  locks := make([]sync.RWMutex, options.bucketCount) 
  25.  
  26.  maxSegmentBytes := (options.maxBytes + options.bucketCount - 1) / options.bucketCount 
  27.  for index := range segments{ 
  28.   segments[index] = newSegment(maxSegmentBytes, options.statsEnabled) 
  29.  } 
  30.  
  31.  c := &cache{ 
  32.   hashFunc: options.hashFunc, 
  33.   bucketCount: options.bucketCount, 
  34.   bucketMask: options.bucketCount - 1, 
  35.   segments: segments, 
  36.   locks: locks, 
  37.   close: make(chan struct{}), 
  38.  } 
  39.     if options.cleanupEnabled { 
  40.   go c.cleanup(options.cleanTime) 
  41.  } 
  42.   
  43.  return c, nil 

这里为了更好的扩展,我们使用Options编程模式,我们的构造函数主要做三件事:

这里构造缓存对象时我们要先计算每个分片的容量,默认整个本地缓存256M的数据,然后在平均分到每一片区内,用户可以自行选择要缓存的数据大小。

第三步:定义分片结构

每个分片结构如下:

  1. type segment struct { 
  2.  hashmap map[uint64]uint32 
  3.  entries buffer.IBuffer 
  4.  clock   clock 
  5.  evictList  *list.List 
  6.  stats IStats 

接下来我们再来看一下每个分片的构造函数:

  1. func newSegment(bytes uint64, statsEnabled bool) *segment { 
  2.  if bytes == 0 { 
  3.   panic(fmt.Errorf("bytes cannot be zero")) 
  4.  } 
  5.  if bytes >= maxSegmentSize{ 
  6.   panic(fmt.Errorf("too big bytes=%d; should be smaller than %d", bytes, maxSegmentSize)) 
  7.  } 
  8.  capacity := (bytes + segmentSize - 1) / segmentSize 
  9.  entries := buffer.NewBuffer(int(capacity)) 
  10.  entries.Reset() 
  11.  return &segment{ 
  12.   entries: entries, 
  13.   hashmap: make(map[uint64]uint32), 
  14.   clock:   &systemClock{}, 
  15.   evictList: list.New(), 
  16.   stats: newStats(statsEnabled), 
  17.  } 

这里主要注意一点:

我们要根据每个片区的缓存数据大小来计算出容量,与上文的缓存对象初始化步骤对应上了。

第四步:定义缓存结构

缓存对象现在也构造好了,接下来就是本地缓存的核心:定义缓存结构。

bigcache、fastcache、freecache都使用字节数组代替map存储缓存数据,从而减少GC压力,所以我们也可以借鉴其思想继续保持使用字节数组,这里我们使用二维字节切片存储缓存数据key/value;画个图表示一下:

使用二维数组存储数据的相比于bigcache的优势在于可以直接根据索引删除对应的数据,虽然也会有虫洞的问题,但是我们可以记录下来虫洞的索引,不断填充。

每个缓存的封装结构如下:

基本思想已经明确,接下来看一下我们对存储层的封装:

  1. type Buffer struct { 
  2.  array [][]byte 
  3.  capacity int 
  4.  index int 
  5.  // maxCount = capacity - 1 
  6.  count int 
  7.  // availableSpace If any objects are removed after the buffer is full, the idle index is logged. 
  8.  // Avoid array "wormhole" 
  9.  availableSpace map[int]struct{} 
  10.  // placeholder record the index that buffer has stored. 
  11.  placeholder map[int]struct{} 

向buffer写入数据的流程(不贴代码了):

第五步:完善向缓存写入数据方法

上面我们定义好了所有需要的结构,接下来就是填充我们的写入缓存方法就可以了:

  1. func (c *cache) Set(key string, value []byte) error  { 
  2.  hashKey := c.hashFunc.Sum64(key
  3.  bucketIndex := hashKey&c.bucketMask 
  4.  c.locks[bucketIndex].Lock() 
  5.  defer c.locks[bucketIndex].Unlock() 
  6.  err := c.segments[bucketIndex].set(key, hashKey, value, defaultExpireTime) 
  7.  return err 
  8.  
  9. func (s *segment) set(key string, hashKey uint64, value []byte, expireTime time.Duration) error { 
  10.  if expireTime <= 0{ 
  11.   return ErrExpireTimeInvalid 
  12.  } 
  13.  expireAt := uint64(s.clock.Epoch(expireTime)) 
  14.  
  15.  if previousIndex, ok := s.hashmap[hashKey]; ok { 
  16.   if err := s.entries.Remove(int(previousIndex)); err != nil{ 
  17.    return err 
  18.   } 
  19.   delete(s.hashmap, hashKey) 
  20.  } 
  21.  
  22.  entry := wrapEntry(expireAt, key, hashKey, value) 
  23.  for { 
  24.   index, err := s.entries.Push(entry) 
  25.   if err == nil { 
  26.    s.hashmap[hashKey] = uint32(index
  27.    s.evictList.PushFront(index
  28.    return nil 
  29.   } 
  30.   ele := s.evictList.Back() 
  31.   if err := s.entries.Remove(ele.Value.(int)); err != nil{ 
  32.    return err 
  33.   } 
  34.   s.evictList.Remove(ele) 
  35.  } 

流程分析如下:

根据key计算哈希值,然后根据分片数获取对应分片位置

如果当前缓存中存在相同的key,则先删除,在重新插入,会刷新过期时间

封装存储结构,根据过期时间戳、key长度、哈希大小、缓存对象进行封装

将数据存入缓存,如果缓存失败,移除最老的数据后再次重试

第六步:完善从缓存读取数据方法

第一步根据key计算哈希值,再根据分片数获取对应的分片位置:

  1. func (c *cache) Get(key string) ([]byte, error)  { 
  2.  hashKey := c.hashFunc.Sum64(key
  3.  bucketIndex := hashKey&c.bucketMask 
  4.  c.locks[bucketIndex].RLock() 
  5.  defer c.locks[hashKey&c.bucketMask].RUnlock() 
  6.  entry, err := c.segments[bucketIndex].get(key, hashKey) 
  7.  if err != nil{ 
  8.   return nil, err 
  9.  } 
  10.  return entry,nil 

第二步执行分片方法获取缓存数据:

  1. func (s *segment) getWarpEntry(key string, hashKey uint64) ([]byte,error) { 
  2.  index, ok := s.hashmap[hashKey] 
  3.  if !ok { 
  4.   s.stats.miss() 
  5.   return nil, ErrEntryNotFound 
  6.  } 
  7.  entry, err := s.entries.Get(int(index)) 
  8.  if err != nil{ 
  9.   s.stats.miss() 
  10.   return nil, err 
  11.  } 
  12.  if entry == nil{ 
  13.   s.stats.miss() 
  14.   return nil, ErrEntryNotFound 
  15.  } 
  16.  
  17.  if entryKey := readKeyFromEntry(entry); key != entryKey { 
  18.   s.stats.collision() 
  19.   return nil, ErrEntryNotFound 
  20.  } 
  21.  return entry, nil 
  22.  
  23. func (s *segment) get(key string, hashKey uint64) ([]byte, error) { 
  24.  currentTimestamp := s.clock.TimeStamp() 
  25.  entry, err := s.getWarpEntry(key, hashKey) 
  26.  if err != nil{ 
  27.   return nil, err 
  28.  } 
  29.  res := readEntry(entry) 
  30.  
  31.  expireAt := int64(readExpireAtFromEntry(entry)) 
  32.  if currentTimestamp - expireAt >= 0{ 
  33.   _ = s.entries.Remove(int(s.hashmap[hashKey])) 
  34.   delete(s.hashmap, hashKey) 
  35.   return nil, ErrEntryNotFound 
  36.  } 
  37.  s.stats.hit(key
  38.  
  39.  return res, nil 

第七步:来个测试用例体验一下

先来个简单的测试用例测试一下:

  1. func (h *cacheTestSuite) TestSetAndGet() { 
  2.  cache, err := NewCache() 
  3.  assert.Equal(h.T(), nil, err) 
  4.  key := "asong" 
  5.  value := []byte("公众号:Golang梦工厂"
  6.  
  7.  err = cache.Set(key, value) 
  8.  assert.Equal(h.T(), nil, err) 
  9.  
  10.  res, err := cache.Get(key
  11.  assert.Equal(h.T(), nil, err) 
  12.  assert.Equal(h.T(), value, res) 
  13.  h.T().Logf("get value is %s", string(res)) 

运行结果:

  1. === RUN   TestCacheTestSuite 
  2. === RUN   TestCacheTestSuite/TestSetAndGet 
  3.     cache_test.go:33: get value is 公众号:Golang梦工厂 
  4. --- PASS: TestCacheTestSuite (0.00s) 
  5.     --- PASS: TestCacheTestSuite/TestSetAndGet (0.00s) 
  6. PASS 

大功告成,基本功能通了,剩下就是跑基准测试、优化、迭代了(不在文章赘述了,可以关注github仓库最新动态)。

参考文章

总结

实现篇到这里就结束了,但是这个项目的编码仍未结束,我会继续以此版本为基础不断迭代优化,该本地缓存的优点:

待优化点:

迭代点:

本文代码已经上传到github:https://github.com/asong2020/go-localcache

 

好啦,本文到这里就结束了,我是asong,我们下期见。

 

来源:Golang梦工厂内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯