antirez / antirez/ds4

KV disk cache can be made O(N) instead of O(N^2)

未关闭
#771 0 条评论 0 个 reaction 已指派 0 人 在 GitHub 查看
主要语言
C
星标
22.3k
派生
2.1k
平均合并
1 天 3 小时
30 天内合并 PR
4

描述

Currently each checkpoint in KV disk cache contains a full snapshot, including compressed part and non-compressed part. So, overall disk usage grows quadratically when a number of checkpoints grow.

However, compressed parts of the KV cache are the same between checkpoints, it is not necessary to store them multiple times. Deduplicating them should decrease disk usage of KV cache a lot (as they take most space), and make KV cache use O(N) space.

It should also allow to make checkpoints more frequently. I like an approach where checkpoints are aligned to turns (i.e. API call boundaries), with some minimal size (e.g. 4K - if it's less than that, wait for turn where it becomes more) - it seems it should allow for much smaller prefill.

There are several possible ways to implement it - initially I was thinking about "mechanical" deduplication: KV checkpoint becomes "metadata + non-compressed part (~23MB fixed overhead)", compressed parts are stored separately (hashed, deduplicated), and metadata links to them. But there are other approaches possible, like using some kind of a tree (e.g. https://github.com/Dango233/ds4/issues/4 - probably better than "mechanical" version). Either way, we should store these parts once.

Fixed overhead can be reduced from ~23MB to ~13MB per checkpoint with https://github.com/antirez/ds4/pull/767 (a pre-requisite, gives 17MB instead of 23MB) + aligning checkpoint boundaries so that there are no unfinished parts to store (brings it to ~13MB per checkpoint fixed overhead). Can be further reduced to ~11MB by handling ratio-4 layer, not just ratio-128.

Regardless of approach, this should allow to reduce KV cache disk usage ~5x in some reasonable scenarios, together with more frequent checkpoints (i.e. better resume / less prefill). It should help with issues like https://github.com/antirez/ds4/issues/444, just because it'd be much less likely to trigger eviction.

Thoughts?

贡献指南

打开贡献指南

评估

这个 Issue 还没有评估数据。

把新 issue 发到你的邮箱

精选适合新手参与的 GitHub issue 摘要。