图系统Hugegraph-缓存设计

在提升性能指标的路上, 缓存(Cache)占据了非常重要的地位, 从硬件到软件层面都是如此, 那么在图(Graph)里, 我们核心关注图的读写性能, 那缓存的设计, 以及它的合理使用就显得更加重要了. 接下来学习一下Hugegraph 中的缓存实现.

0x00. 前言

1. 简介

缓存本身也是一个比较容易在计算机各层混用的名词, 但是实际上很多人觉得 缓存 = 内存 , 或者Buffer = Cache , 这种理解是有很大问题的, 学习Huge的缓存设计之前, 可以看看这几篇帮助构建一下Cache的基本体系 (后续说的都是软件缓存).

然后之后有空 ,会接着补一下Guava 包中实现本地缓存的经典方式, 并对比一下和Huge 里实现的区别. (都是单机缓存 ?)

2. Huge的缓存

首先Huge的缓存设计思路采用的是经典的 LRU 淘汰模式, 也就是每次从缓存中把最长时间没人访问的数据T出去, 它和LFU最大的区别就在于. LRU根本判断条件是时间. 而LFU判断根本是使用次数.

当然, LRU也是一个大的分类, 可以结合一些其他的条件综合实现, 从而获得更好的缓存命中率, 比如相同时间删除数据大小更大的, 以及”使用时间+次数” 的LRU-K. , 或者是FIFO+LRU 的双队列实现, 详情可以参考一下LRU多种实现的对比 .

在Huge里有一个单独的cache 包, 里面有1个Cache 接口 + 3个封装 + 1个RamCache实现. 三个封装分别是:

  • CachedSchemaTransaction (缓存图的Schema信息)
  • CachedGraphTransaction (缓存图的点边数据)
  • CacheManager (缓存管理器)

那么这样看整个设计就很清晰了: (估计)

  1. “接口+实现”负责实现缓存本身
  2. 点/边数据通过缓存管理器调用CachedGraphTransaction的方法进行缓存
  3. Schema数据通过缓存管理器调用CachedSchemaTransaction缓存.
  4. CacheManger类似一个守护进程, 每隔一段时间去观察/更新一下缓存状态

接下来就是验证一下猜想是否正确的吧..

补充: 包下还有一个CachedBackendStore 看起来原本是用于缓存图的数据, 但是目前已弃用.

0x01. 结构

先看缓存本身的实现, 再看如何调用. 在Huge里, 定义了一个Cache 接口, 确定之后缓存实现所需的方法 (如下图) :

hugeCache00

可以看到核心就是缓存的CURD操作, 以及设置一些核心参数(缓存大小, 过期时间), 然后接着看看唯一的实现类RamCache的设计吧: (先看看概览图)

hugeCache01

  1. 初始化一个map, 一个队列: (核心结构)
    • map是 <100MB (100*1024*1024个)的ConcurrentHashMap<Id, LinkNode<Id, Object>>
    • 队列是自己实现的的双向链队列 (名为LinkedQueueNonBigLock<Id, Object>, 其中每个节点(LinkNode)都带有当前时间戳)
  2. 缓存的本质某个对象的Id和对象本身. 但是要注意的是, 这里Id除了常见的点/边Id, 还有比如某次查询对应的QueryId ,这样重复的查询, 就无需去缓存中多次查找每个点边, 而是一次把整个Query 对象都取出来.
  3. 通过包装的两个类来间接调用缓存的增删改查方法, 通过守护进程定时清理过期缓存.

0x02. 核心代码

先看看缓存最核心读写实现 (修改本质是覆盖写, 删除就是出队, 不单独说了~) :

1. 写入缓存

以下是精简后的核心过程.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private final void write(Id id, Object value) {
final Lock lock = this.keyLock.lock(id);
try { // 如果超过缓存个数限制,移除队头或清空map (capacity默认1024*1024个)
while (map.size() >= capacity) {
// 1.先从队列移出最长时间未访问元素
// 注意: 如果其他线程正在做出队操作或队列可能为空, 那么可能就会返回null(出队失败)
LinkNode<Id, Object> removed = queue.dequeue();
if (removed == null) {
// 如果与此同时有其他添加操作,map就会先被清空,然后跳出循环 (Q:why clear map?)
map.clear();
break;
}
// 2.然后从map里移出刚才的元素
map.remove(removed.key());
}

// 3.旧元素出队(如果存在)
LinkNode<Id, Object> node = map.get(id);
if (node != null) queue.remove(node);
// 4.新元素入队,然后放入map
map.put(id, queue.enqueue(id, value));
} finally {lock.unlock();}
}

这里其他过程都很清晰, 就是如果其他线程同一时间写入, 则导致出栈元素为空时, 为何要清空整个map. 这里还不太理解… 待确定

2. 读取缓存

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
private final Object access(Id id) {
// map中元素 < 缓存上限一半, 则直接返回元素值, 不移动队列
if (map.size() <= this.halfCapacity) {
LinkNode<Id, Object> node = map.get(id);
if (node == null) return null;
return node.value();
}

final Lock lock = this.keyLock.lock(id);
try {
LinkNode<Id, Object> node = map.get(id);
if (node == null) return null;

// 如果map中元素 > 缓存上限数一半, 则需要更新队列,读取的元素重新入队
if (map.size() > halfCapacity) {
// 把元素从中间移至尾部 (元素可能被其他线程通过出队调用移除)
if (queue.remove(node) == null) return null;
queue.enqueue(node);
}
return node.value();
} finally {lock.unlock();}
}

这里跟标准的LRU的区别就在于设置了一个halfCapacity . 原本LRU每次读取都会在链表里移动这个元素到队尾, 而链表的查询效率是很低的. 如图所示:

hugeCacheLRU00

可能这里为了减少移动次数, 就设定当缓存还算充裕(多于一半)的时候, 退化FIFO… 不去重新移动和计算队列, 也不加锁, 这样读取效率理论上会提高许多, 它的主要缺点是? 待确定

3. 缓存过期

之前接口里其实有一个方法名比较奇怪, 名为tick() (Tick-Tok) , 我想了想, 翻译为标记(过期元素数)….可能比较合适?

LinkNode 的结构里, 每个节点初始化的时候都会携带一个当前时间戳, 它就是在tick() 函数中被用来计算过期时间的, 然后它又是CacheManager 初始化的时候调用的, 借助Timer对象后台执行, 达到定时检查缓存是否过期, 以及移除过期对象的效果 :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
  public long tick() {
long expireTime = this.expire; //默认过期时间
int expireItems = 0; //过期元素个数
long current = now();
if (expireTime <= 0) return 0L;

for (LinkNode<Id, Object> node : map.values()) {
if (current - node.time() > expireTime) {
remove(node.key()); //删除缓存元素
expireItems++;
}
}
return expireItems;
}

// CacheManager的核心定时执行方法
private TimerTask scheduleTimer(float period) {
TimerTask task = new TimerTask() {
@Override
public void run() {
for (Entry<String, Cache> entry : caches().entrySet()) tick(entry.getKey(), entry.getValue());
}

private void tick(String name, Cache cache) {
long start = System.currentTimeMillis();
long items = cache.tick(); //调用上面的tick清理过期元素
long cost = System.currentTimeMillis() - start;
LOG.debug("Cache '{}' expiration tick cost {}ms", name, cost);
}
};
// 30s定时执行一次
timer.schedule(task, 0, (long) (period * 1000.0));
return task;
}

至于双向链队的结构, 除了加了一个自己封装的KeyLock 锁对象, 其他暂时没看到有什么特殊设计, 就不单独讲数据结构了.. 有兴趣可以参考源码1,源码2

0x03. 图使用缓存

上面已经把Hugegraph中的缓存设计和实现大体说完了, 这里再举个具体的例子, 比如之前说的K步邻居查询, 或者某条gremlin查询后, 在Huge里是如何缓存的? 当然这里其实只是一个函数调用了.

以K步邻居核心过程, 查某个点的所有边为例, 最后会调用queryEdgesFromBackend() , 这种操作都是属于GraphTransaction ,而这些都在CachedGraphTransaction 中进行了重写, 例如下面就同时展示了读写缓存在图里的使用方式:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
@Override
protected Iterator<HugeEdge> queryEdgesFromBackend(Query query) {
// 通过page查询的边不存入缓存.直接使用父类
if (query.empty() || query.paging()) return super.queryEdgesFromBackend(query);

Id id = new QueryId(query);
List<HugeEdge> edges = (List<HugeEdge>) this.edgesCache.get(id); //先从缓存里查,存在则返回
if (edges == null) {
// 迭代器不方便直接缓存,转为集合缓存.
edges = ImmutableList.copyOf(super.queryEdgesFromBackend(query));
if (edges.size() <= MAX_CACHE_EDGES_PER_QUERY) {
this.edgesCache.update(id, edges); //缓存这次查询的所有边.标记为一个QueryId
}
}
return edges.iterator();
}

至于Schema的缓存读写, 大体也是类似的, 细节稍有不同, 就不重复说了. (gremlin缓存的例子待补, 还没看)

0x04. 总结

总体来说, Hugegraph里的缓存设计是实现了传统的LRU的淘汰策略, 并做了一些小改进, 然后缓存过期通过原生的Timer 定时检查并剔除的, 那么我们之前的假想, 如果想通过内存(空间)换时间. 就等于是给了一个非常大的HashMap ,而Java在处理一个如此大的HashMap对象的时候, JVM在内存管理应该会变得很难处理, 也容易出现问题.. (待确认)

所以如果想在Huge里比如用很大(100G+)内存来做缓存, 可能还是用redis/memcache 这样的分布式缓存, 或者存储自身的缓存要好的多, 图本身则可以用来缓存更结构化的数据, 例如:

  1. 图的Schema信息. (缓存命中率极高, 频繁)
  2. 图的Query/Path/Traverser信息. (比如上面的例子, 但是不缓存实际大量的点边数据)
  3. 子图信息 (…如果之后支持子图相关算法, 包括社群发现, Pagerank迭代的时候复用?)

参考资料:

主要见前言-简介部分, 其它参考Hugegraph源码实现.