KV disk cache can be made O(N) instead of O(N^2)
- Lenguaje dominante
- C
- Estrellas
- 22.3k
- Forks
- 2.1k
- Merge medio
- 1 d 3 h
- PR fusionados (30 d)
- 4
Descripción
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?
Guía de contribución
Evaluación
Este issue todavía no se ha evaluado.