V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
The Go Programming Language
http://golang.org/
Go Playground
Go Projects
Revel Web Framework
PungentSauce
V2EX  ›  Go 编程语言

这个 go 实现的 cache 为什么性能不理想

  •  
  •   PungentSauce · 302 天前 · 2578 次点击
    这是一个创建于 302 天前的主题,其中的信息可能已经有所发展或是发生改变。
    package cache
    
    import (
    	"sync"
    	"time"
    )
    
    type Item struct {
    	value      interface{}
    	expiration int64
    }
    
    type Cache struct {
    	items             map[string]Item
    	mu                sync.RWMutex
    	defaultExpiration time.Duration
    	cleanupInterval   time.Duration
    }
    
    func NewCache(defaultExpiration, cleanupInterval time.Duration) *Cache {
    	cache := &Cache{
    		items:             make(map[string]Item),
    		defaultExpiration: defaultExpiration,
    		cleanupInterval:   cleanupInterval,
    	}
    	go cache.cleanupExpired()
    	return cache
    }
    
    func (c *Cache) Set(key string, value interface{}, expiration time.Duration) {
    	c.mu.Lock()
    	defer c.mu.Unlock()
    
    	var exp int64
    	now := time.Now().UnixNano()
    	if expiration > 0 {
    		exp = now + int64(expiration)
    	} else {
    		exp = now + int64(c.defaultExpiration)
    	}
    
    	item := Item{
    		value:      value,
    		expiration: exp,
    	}
    	c.items[key] = item
    }
    
    func (c *Cache) Get(key string) (interface{}, bool) {
    	c.mu.RLock()
    	defer c.mu.RUnlock()
    
    	item, found := c.items[key]
    	if !found {
    		return nil, false
    	}
    	if time.Now().UnixNano() > item.expiration {
    		c.mu.Lock()
    		defer c.mu.Unlock()
    		delete(c.items, key)
    		return nil, false
    	}
    	return item.value, true
    }
    
    func (c *Cache) cleanupExpired() {
    	for {
    		time.Sleep(c.cleanupInterval)
    		now := time.Now().UnixNano()
    
    		c.mu.Lock()
    		for key, item := range c.items {
    			if now > item.expiration {
    				delete(c.items, key)
    			}
    		}
    		c.mu.Unlock()
    	}
    }
    
    
    func TestCache1(t *testing.T) {
    
    	cache := NewCache(2*time.Second, 2*time.Second)
    
    	start := time.Now()
    	for i := 1; i < 9999999; i++ {
    		cache.Set(fmt.Sprintf("%d", i), cast.ToString(i), 2*time.Second)
    		//if i%2 == 0 {
    		//	endTime := time.Now()
    		//	duration := endTime.Sub(start)
    		//	if duration.Milliseconds() > 100 {
    		//		fmt.Println("timeUnit", duration.Milliseconds(), "ms")
    		//	}
    		//	start = time.Now()
    		//}
    		if i%100000 == 0 {
    			var m runtime.MemStats
    			runtime.ReadMemStats(&m)
    			fmt.Println(cast.ToString(m.Alloc/1024/1024)+"MB",
    				cast.ToString(m.TotalAlloc/1024/1024)+"MB")
    		}
    	}
    	endTime := time.Now()
    	duration := endTime.Sub(start)
    	fmt.Println("timeUnit", duration.Milliseconds(), "ms")
    
    }
    
    
    1551MB 1940MB
    1555MB 1944MB
    timeUnit 5759 ms
    

    还有一个基于 sync.map 的

    package cache
    
    import (
    	"sync"
    	"time"
    )
    
    //var cacheStd = NewCache(time.Second*5, time.Second*10)
    
    type Item struct {
    	value      interface{}
    	expiration int64
    }
    
    type Cache struct {
    	items             sync.Map
    	defaultExpiration time.Duration
    	cleanupInterval   time.Duration
    }
    
    func NewCache(defaultExpiration, cleanupInterval time.Duration) *Cache {
    	cache := &Cache{
    		defaultExpiration: defaultExpiration,
    		cleanupInterval:   cleanupInterval,
    	}
    	go cache.cleanupExpired()
    	return cache
    }
    
    func (c *Cache) Set(key string, value interface{}, expiration time.Duration) {
    	var exp int64
    	now := time.Now().UnixNano()
    	if expiration > 0 {
    		exp = now + int64(expiration)
    	} else {
    		exp = now + int64(c.defaultExpiration)
    	}
    
    	item := Item{
    		value:      value,
    		expiration: exp,
    	}
    	c.items.Store(key, item)
    }
    
    func (c *Cache) Get(key string) (interface{}, bool) {
    	item, found := c.items.Load(key)
    	if !found {
    		return nil, false
    	}
    	cachedItem := item.(Item)
    	if time.Now().UnixNano() > cachedItem.expiration {
    		c.items.Delete(key)
    		return nil, false
    	}
    	return cachedItem.value, true
    }
    
    func (c *Cache) cleanupExpired() {
    	for {
    		time.Sleep(c.cleanupInterval)
    		now := time.Now().UnixNano()
    
    		c.items.Range(func(key, value interface{}) bool {
    			item := value.(Item)
    			if now > item.expiration {
    				c.items.Delete(key)
    			}
    			return true
    		})
    	}
    }
    
    //func GetFromCache[T any](key string, action func() T) T {
    //	data, ok := cacheStd.Get(key)
    //	if ok {
    //		return data.(T)
    //	}
    //	res := action()
    //	cacheStd.Set(key, res, 0)
    //	return res
    //}
    

    测试结果差了一倍

    2461MB 3114MB
    2473MB 3126MB
    timeUnit 12503 ms
    

    想对应的 java 代码

    package com.example.jtool.controller;
    import java.util.concurrent.ConcurrentHashMap;
    import java.util.concurrent.Executors;
    import java.util.concurrent.ScheduledExecutorService;
    import java.util.concurrent.TimeUnit;
    
    public class Cache {
        private ConcurrentHashMap<String, Item> items;
        private long defaultExpiration;
        private long cleanupInterval;
        private ScheduledExecutorService executor;
    
        public Cache(long defaultExpiration, long cleanupInterval) {
            this.items = new ConcurrentHashMap<>();
            this.defaultExpiration = defaultExpiration;
            this.cleanupInterval = cleanupInterval;
            this.executor = Executors.newSingleThreadScheduledExecutor();
            this.executor.scheduleAtFixedRate(this::cleanupExpired, cleanupInterval, cleanupInterval, TimeUnit.NANOSECONDS);
        }
    
        public void set(String key, Object value, long expiration) {
            long exp = expiration > 0 ? System.nanoTime() + expiration : System.nanoTime() + defaultExpiration;
            Item item = new Item(value, exp);
            items.put(key, item);
        }
    
        public Object get(String key) {
            Item item = items.get(key);
            if (item == null || System.nanoTime() > item.getExpiration()) {
                items.remove(key);
                return null;
            }
            return item.getValue();
        }
    
        private void cleanupExpired() {
            long now = System.nanoTime();
            items.forEach((key, value) -> {
                Item item = value;
                if (now > item.expiration) {
                    items.remove(key);
                }
            });
        }
    
    
        public static void main(String[] args) {
            long startTime = System.currentTimeMillis();
    
            // 在这里放置需要测量时间的代码
    
            Cache cache = new Cache(2000000000L, 20000000000L); // 5 seconds, 10 seconds
            for (Integer i = 1; i < 9999999; i++ ){
                cache.set(i.toString(), i.toString(), 2000000000L);
    
                if( i%100000 == 0 ){
                    Runtime runtime = Runtime.getRuntime();
                    long memoryUsed = runtime.totalMemory() - runtime.freeMemory();
                    System.out.println("Memory used: " + memoryUsed/1024/1024 + "MB");
                }
            }
            System.out.println("end");
    
            long endTime = System.currentTimeMillis();
            long elapsedTime = endTime - startTime;
            System.out.println("程序运行时间:" + elapsedTime + " 毫秒");
        }
    }
    
    class Item {
        private Object value;
        public long expiration;
    
        public Item(Object value, long expiration) {
            this.value = value;
            this.expiration = expiration;
        }
    
        public Object getValue() {
            return value;
        }
    
        public long getExpiration() {
            return expiration;
        }
    }
    
    Memory used: 1632MB
    Memory used: 1648MB
    Memory used: 1664MB
    Memory used: 1680MB
    Memory used: 1680MB
    end
    程序运行时间:3020 毫秒
    

    更加不能理解的是,go 版本的 cache 测试过程中会有明显的阻塞感。有时候可能达到几十上百。有没有同学清楚 go 版本的 cache 哪里写的有问题

    16 条回复    2024-01-25 19:41:53 +08:00
    mengzhuo
        1
    mengzhuo  
       302 天前   ❤️ 1
    锁范围太大了,而且你这个定时清理要遍历并阻碍全部读写,能快就有鬼了……上个最小堆或者时间轮还能加速一下。
    if time.Now().UnixNano() > item.expiration 这段还重新上锁,你确定代码能执行么?
    其他的话,没有预分配,没有对象池化,GC 压力会很大。
    大小 key 没分开处理,hash 算法对 64 和 32 位有特殊处理,是我的话会手动 padding 对齐
    mason961125
        2
    mason961125  
       302 天前
    跑一下 CPU Profiling 就能知道你要的答案了。
    wqtacc
        3
    wqtacc  
       302 天前
    github 上找前几个实现,大多都对内存分配,key 、value 存储结构,锁的粒度做了优化
    q1450718943
        4
    q1450718943  
       302 天前
    这 go 代码 get 方法难道没死锁?
    Ipsum
        5
    Ipsum  
       302 天前
    为啥要自己造轮子呢?
    hahadaxigua834
        6
    hahadaxigua834  
       302 天前
    哈哈 这个问题我来回答,之前正好看了 java 的 concurrent hashmap 。

    简单的讲就是 java 的 concurrentHashmap 是无锁算法实现的,做了无数优化,最早 1.多少甚至就了桶碰撞过多的链表转树优化,而 go 的 sync.map 我记得只是加了一把大锁。

    在标准库中并发容器方面的实现真的差的不是一点半点,可以看看这个 https://github.com/dgraph-io/ristretto ,给数据库用的 cache ,应该差不到哪去。
    rekulas
        7
    rekulas  
       302 天前
    求速度至少得用 atomic 实现吧 直接一个 syncmap 套上去能快才是奇事
    icy37785
        8
    icy37785  
       302 天前 via iPhone   ❤️ 1
    首先不理解再有很多优秀的轮子的情况下要自己造轮子了,其次不能理解的是既然一定要自己造轮子了,为什么不先看看那些优秀的轮子,随便看一个轮子的实现就不会这样加锁了。
    Rehtt
        9
    Rehtt  
       301 天前
    试着调了一下你的 set 和 get 锁的位置就优化了 0.5 秒
    PungentSauce
        10
    PungentSauce  
    OP
       301 天前
    @icy37785 sync.map 的那个是第一版,原生 map 的是第二版,sync.map 在我现在写的数据量上也够用。只是测了一下数据量一大就有点离谱了
    PungentSauce
        11
    PungentSauce  
    OP
       301 天前
    @Rehtt 啊哈,怎么改的
    PungentSauce
        12
    PungentSauce  
    OP
       301 天前
    PungentSauce
        13
    PungentSauce  
    OP
       301 天前
    @q1450718943 原生 map 是后来写的,一开始写的是第二个版本,因为只是一些小量数据的缓存,就自己搞了。
    keakon
        14
    keakon  
       301 天前
    sync.Map 适合读多写少的,一旦要写就会重新复制整个 map ,开销挺大的。

    真正的高并发写需要避免多个 CPU 核同时访问一个 cacheline 地址。最简单的方式是先对 key 进行 hash ,然后分成多个 map ,这样并发访问不同的 key 大概率不会同时对一个 map 加锁。
    PungentSauce
        15
    PungentSauce  
    OP
       301 天前
    @mengzhuo 还真是,囧,那个原生 map 实现的锁位置还真是有问题。
    1194129822
        16
    1194129822  
       301 天前
    java 本身性能本身不弱于 go ,其次 CHM 是 java 里面最优秀的并发结构,最优秀的实现算法,是一个完全无锁并行的 Map 。你把 CHM 换成 Hashtable 或者其他同步 Map 结果可能就不一样了。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   960 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 21:23 · PVG 05:23 · LAX 13:23 · JFK 16:23
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.