瞎想系列第一期增量Map

这里有个需求

将一个Map从Master同步到Slave

最终达到一致就行
value变动的频率 >> key增加的频率 >> key减少的频率

简单粗暴

最直接的想法就是直接使用推模式和拉模式：

推模式：Master的Map发生变化，就往各个Slave推送整个Map
拉模式：Slave间隔向Master请求最新的Map数据

这两种方式虽然简单粗暴易于实现，但每当Map有更新时，传输的是全量的Map的数据。在Map数据量小的时候尚可接受，但当Map数据量“大”、变动频繁和Slave数目过多时，就（大概）会对Master的带宽和负载造成巨大的压力。

为了解决这个问题，首先想到的是全量同步变增量同步。既然Slave有老的Map了，那Slave只需要拿到一个不定Patch，将补丁打入老的Map，就可以生成新的Map。那么问题又转变成如何生成补丁和如何打入补丁。

伪“增量”Map

为啥叫伪“增量”Map呢？呃，因为它的核心原理是Slave的key只增加和变更，不减少，然后通过其他补偿方案来删除key。

核心设计

结构

{
    mapVersion: long // map的版本
    map: {
        key1: {
            keyVersion: long, // key的版本
            value: Object // key对应的value
        },
        key2: {
            keyVersion: long,
            value: Object
        }, ...
    }
}

map的版本 mapVersion

mapVersion需要满足以下规约：

mapVersion在map发生变更时版本会增大
mapVersion一定大于等于所有的keyVersion

map发生变更：添加新的key；key的value变化

key的版本 keyVersion

keyVersion需要满足以下规约：

keyVersion在key对应的value发生变更时版本会增大
keyVersion增大一定会比原来的mapVersion大
新增key的版本设置和key发生变更的规则一致

mapVersion和keyVersion更新流程

先更新keyVersion再更新mapVersion。

举个栗子

{
    mapVersion: 2
    map: {
        key1: { keyVersion: 1, value: Object },
        key2: { keyVersion: 2, value: Object },
        key3: { keyVersion: 1, value: Object }
    }
}

map的key1和key2的value都发生了变化
更新key1和key2大于原来的mapVersion，设置为3
更新mapVersion为最大的keyVersion，设置为3

同步策略

初次拉取设置mapVersion为空，Master返回全量map，Slave用全量map覆盖本地map
Master map发生变更，广播带mapVersion的oneway请求到Slave
Slave以本地map的mapVersion请求Master
Master根据mapVersion生成补丁返回给Slave

Slave定时以mapVersion为空请求Master，Master返回全量map，Slave用全量map覆盖本地map

为了清除已删除的key
防止广播没有收到

如何生成补丁

Slave请求的时候会带上Slave当前的mapVersion

if slave.mapVersion == master.mapVersion
    // 说明slave和master的map是一致的，无需变更
	return noChangePatch
else 
	patch = { mapVersion: master.mapVersion, map: {所有keyVersion比slave.mapVersion的项} }
	return patch

如何打入补丁

if patch.mapVersion < slave.mapVersion
	return
for k, v in path.map
	// 这里的比较是为了即使是一个大补丁，也可以各取所需，例如slave本来只需要4和5之间的patch，master却返
	// 回了2和5之间的patch
	if v.keyVersion > slave.map.map[k].keyVersion
		slave.map.map[k] = v

优化

每次slave请求都要生成补丁？No！No！No！

可以对补丁进行缓存。例如缓存分别和最新mapVersion相差1、4、16的补丁，请求补丁都返回大于等于版本差距的补丁，例如master.mapVersion - slave.mapVersion == 2，则返回补丁4。若相差超过16，就返回全量map。

真增量Map

如果key删除的还算比较频繁，而且我想相对即使的知道key被删掉了。呃，那伪增量Map可能就不那么适用了。这时候就要请出人民的好伙伴好同志奥义-无敌-旋风-真增量Map。

真增量Map其实是对伪增量Map的一个改造，主要的不同点如下：

map发生变更新增“key的删除”
key被删除的时候在Master这不会真的删除，只是标记DELETED，且keyVersion的变更流程和key的value发生变更的流程一致
打补丁的时候，Slave如果看到key标记为DELETED，则把key从map中移除

加了DELETED标记就能解决key的删除，看起来这个方案很完美。

那么问题来了，Master map的key都不真正删除了，那之后Master的map不会越来越来大么？因此需要某种策略来裁剪map，移除掉已经删除的key。

裁剪map核心思想

越早标记为DELETED的key，越早删除，删除后，设置minPullMapVersion为最大已删的deleted key.keyVersion + 1。

如果slave拉取补丁的slave.mapVersion < minPullMapVersion && slave.mapVersion != master.mapVersion，则返回全量map，slave使用全量map覆盖本地map。

瞎想系列第一期 增量Map