游戏服务器冷热数据分离方案

冷热数据分离

当前场景：

gamserver启动时，会将所有数据加载到内存中，提高读取数据的性能。但是有很多数据很可能是不常用甚至再也用不到的数据，将这些数据加载到内存中需要占用更多的内存，极大的浪费了内存的使用。

目标：

对冷热数据进行分离，减少非必要数据对内存的占用，节约内存资源。

主要工作：

数据监控
冷热数据识别
数据迁移

1.数据监控：

监控与统计数据的使用，为冷热数据识别服务
监控数据读取的命中率和数据存储的百分比
统计每次数据库读取和写入的命中，定期收集数据读取的命中率和数据存储比例，以便更加直观了解使用冷热数据分离后，节约多少内存，包括百分比和大小，数据读取的命中率，为以后优化冷热数据识别算法提供对比数据。

2.冷数据与热数据：

定义冷数据与热数据
按玩家区分/按数据的引用区分
目前主要用的还是LRU算法来识别冷热数据，知网上有看到基于温度模型的缓存替换策略TCR(Temperature Cache Replacement)论文,可能会有更高的缓存命中率。
或者我们也可根据玩家活跃行为来定义冷热数据，但是非活跃玩家的数据也可能会被读取，所以效果不能保证。

3.数据迁移：

主要是对冷热数据的数据迁移处理。
冷数据处理：
冷数据压缩/冷数据逐出
大部分都是采用冷数据逐出的方法，把冷数据放到存储系统中的低性能层级，节约高性能存储空间。
也有少部分采用冷数据压缩的方法，把冷数据压缩存储，还是放在内存中，等需要用的时候解压就行，可以节约一点内存，并且读取冷数据时不需要等待IO。具体压缩效率需要试验，相关文档也比较少，网上看到的基本上是基于gzip压缩数据。但是我觉得对于我们的架构模型还蛮适用，因为我们的全局唯一锁的架构，当读取冷数据时，需要等待IO，这时候释放锁和不释放锁都比较尴尬。

LRU：

LRU全称是Least Recently Used，即最近最久未使用的意思。
LRU算法的设计原则是：如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。
LRU的变形算法：

1. LRU-K
   LRU-K中的K代表最近使用的次数，因此LRU可以认为是LRU-1。LRU-K的主要目的是为了解决LRU算法“缓存污染”的问题，其核心思想是将“最近使用过1次”的判断标准扩展为“最近使用过K次”。
   相比LRU，LRU-K需要多维护一个队列，用于记录所有缓存数据被访问的历史。只有当数据的访问次数达到K次的时候，才将数据放入缓存。当需要淘汰数据时，LRU-K会淘汰第K次访问时间距当前时间最大的数据。
2. two queue
   Two queues（以下使用2Q代替）算法类似于LRU-2，不同点在于2Q将LRU-2算法中的访问历史队列（注意这不是缓存数据的）改为一个FIFO缓存队列，即：2Q算法有两个缓存队列，一个是FIFO队列，一个是LRU队列。当数据第一次访问时，2Q算法将数据缓存在FIFO队列里面，当数据第二次被访问时，则将数据从FIFO队列移到LRU队列里面，两个队列各自按照自己的方法淘汰数据。
3. Multi Queue(MQ)
   MQ算法根据访问频率将数据划分为多个队列，不同的队列具有不同的访问优先级，其核心思想是：优先缓存访问次数多的数据。详细的算法结构图如下，Q0，Q1....Qk代表不同的优先级队列，Q-history代表从缓存中淘汰数据，但记录了数据的索引和引用次数的队列。
4. 其他
   LRU算法有很多变种，innoDB也是采用LRU算法来提高缓存命中率，innoDB的LRU把表分为两个部分，old和yount，中间用modpoint隔开，modpoint值可以自己设置，默认值为37，距离表尾端37%的位置。数据第一次读区的时候会被放在midpoint的位置，这个位置是old表的头部，但是如果再次被读取，下次就会直接放在young表的头部。另外一个数据页里面可能会有多条记录，在做全表扫描的时候，一个数据页可能会一瞬间被访问多次，这时候可能刚放入列表的时候就再次被访问，导致直接挪到young区头部但是其实数据只访问过一次，这时候有个innodb_old_blocks_time的值来控制，innodb_old_blocks_time设置一个时间，当数据第一次放入列表中后，只有经过一段时间后再次读取才能触发把数据移动到young表头部的行为。

go语言Demo实现

LRUCache.go

package main

import (
    "container/list"
    "sync"
    "time"
)

type LRUCache struct {
    list     *list.List
    cacheMap map[NodeKey]*list.Element
}

var RWLock sync.RWMutex

//数据在内存中存活时间 单位秒
const DATA_LIVE_TIME = 5

type Node struct {
    key  NodeKey
    time int64
}

func NewLRUCache() (*LRUCache) {
    return &LRUCache{
        list:     list.New(),
        cacheMap: make(map[NodeKey]*list.Element)}
}

//返回LRU的存储数据长度
func (lru *LRUCache) Size() int {
    return lru.list.Len()
}

func (lru *LRUCache) Set(key NodeKey) {
    RWLock.Lock()
    defer RWLock.Unlock()
    //节点已存在
    if element, ok := lru.cacheMap[key]; ok {
        lru.list.MoveToFront(element)
        element.Value.(*Node).time = time.Now().Unix()
    } else {
        // 节点不存在，生成新节点
        newElement := lru.list.PushFront(&Node{key, time.Now().Unix()})
        lru.cacheMap[key] = newElement
    }
    lru.CheckList()
}

// 获取数据是否在LRU中，如果存在则更新时间
func (lru *LRUCache) Get(key NodeKey) bool {
    /**
      由于在RLock中，其他线程也能读数据，并且WLock需要等待才能将数据移除，所以此处使用RLock就足够
      如果修改时间时用WLock，需要先释放RLock，反而可能出现释放RLock后被其他线程抢占WLock的情况
    */
    RWLock.RLock()
    defer RWLock.RUnlock()
    if element, ok := lru.cacheMap[key]; ok {
        lru.list.MoveToFront(element)
        element.Value.(*Node).time = time.Now().Unix()
        return true
    } else {
        return false
    }
}

func (lru *LRUCache) Remove(key NodeKey) {
    if element, ok := lru.cacheMap[key]; ok {
        delete(lru.cacheMap, key)
        lru.list.Remove(element)
        //TODO：将数据在内存中移除
        println("将数据从内存中移除：", key)
    }
}

// 从列表尾端开始检查数据，将过期的冷数据从内存移除
func (lru *LRUCache) CheckList() {
    dList := lru.list
    if dList.Len() == 0 {
        return
    }
    node := dList.Back()
    for {
        if CheckData(node.Value.(*Node)) {
            break
        } else {
            lru.Remove(node.Value.(*Node).key)
            if node.Prev() != nil {
                node = node.Prev()
            } else {
                break
            }
        }
    }
}

// 判断数据是否应该存留, 该存留返回true
func CheckData(node *Node) bool {
    if node.time < time.Now().Unix()-DATA_LIVE_TIME {
        return false
    } else {
        return true
    }
}

DataCenter.go

package main

import "sync/atomic"

type CacheDataCenter struct {
    readCount int64 //总读取数据次数
    hitCount  int64 //热数据读取命中次数
    lruCache  ILRU
}

type NodeKey int64

type ILRU interface {
    Set(key NodeKey)
    Get(key NodeKey) (bool)
    Remove(key NodeKey)
    Size() int
}

func NewCacheDataCenter() *CacheDataCenter {
    return &CacheDataCenter{
        readCount: 0,
        hitCount:  0,
        lruCache:  NewLRUCache(),
    }
}

func (center *CacheDataCenter) AddReadNum(isHit bool) {
    atomic.AddInt64(&center.readCount, 1)
    if isHit {
        atomic.AddInt64(&center.hitCount, 1)
    }
}

// 总数据量
func (center *CacheDataCenter) GetTotalCount() int {
    return 0
}

// 内存中数据量
func (center *CacheDataCenter) GetCacheCount() int {
    return center.lruCache.Size()
}

func (center *CacheDataCenter) GetData(key NodeKey) {
    if center.lruCache.Get(key) {
        center.AddReadNum(true)
        //TODO: 从内存中取数据
        println("从内存读取数据：", key)
    } else {
        center.AddReadNum(false)
        center.lruCache.Set(key)
        //TODO: 操作数据库取数据
        println("从数据库读取数据：", key)
    }
}

main.go

package main

import (
    "math/rand"
    "sync"
    "time"
)

func main() {
    cacheDataCenter := NewCacheDataCenter()
    wg := sync.WaitGroup{}
    wg.Add(3)
    for i := 0; i < 3; i++ {
        go func() {
            readData(cacheDataCenter)
            wg.Done()
        }()
    }
    wg.Wait()
    println("test结束，总共读取次数:", cacheDataCenter.readCount, "命中次数:", cacheDataCenter.hitCount, "内存中最终剩余数据:", cacheDataCenter.GetCacheCount())
}

func readData(center *CacheDataCenter) {
    for i := 0; i < 10; i++ {
        time.Sleep(1 * time.Second)
        r := rand.Int63n(30)
        center.GetData(NodeKey(r))
    }
}

demo中三个线程每一秒会随机生成一个数据，并且尝试在LRUCache中读取，假如未命中，则插入，假如命中，则更新时间。每次写数据的时候，会执行一次Check()来检查旧数据，检查的时候从底往上检查，如果数据为冷数据则移除，直到检查到热数据为止。