Epic: implement selective tiering for hmap and lists

[romange]

This issue serves as a placeholder for brainstorming the design, surfacing concerns, and outlining potential solutions for selective tiering in hmap.

I prioritized HMAP over other collection types due to its higher priority and relative simplicity. Please refer to the current async tiering design: https://github.com/dragonflydb/dragonfly/blob/main/docs/async-tiering.md

Goal: Support selective offloading of hashmap values that are relatively big (> 1KB).
Non-goal: Grouping and offloading of multiple small values on the same page.

My early impressions are based on HMapWrap, which exposes the minimal required API:

1. Find (return key and value)
2. Return (entire) iterable Range
3. Erase(k)
4. Add(k, v)
5. UpdateExisting(k)

There's also Get<T>, which leaks implementation but appears to be used similarly to Range().

Initial analysis:

1. Element additions work similarly to Strings and are not problematic, as we write into memory first and then trigger offloading.
2. Deletions are CPU-only operations and do not require I/O .

The major challenge lies in reads: we need to issue multiple reads in a single operation, especially for high-level APIs like HMGET, HGETALL, HGET, HSCAN, HVALS. There is also a challenge of tracking a two-level taxonomy key -> hmap-key while handling contending IO requests (double-reads, delete-after-read, etc).

But in a way we already have a taxonomy as we support multiple databases.

Assignees: @dranikpg (design phase involvement: @romange too)

[romange]

The goal is to have a detailed design here.

[romange]

Things that need to think about: placement policy, cooling queue

[dranikpg]

The main problem is quite simple. Referring to my addition to async-tiering.md

It is important to note that only a single read is issued for all pending asynchronous commands for a given key. Once the read finished, all callbacks are executed consecutively and atomically. This guarantees correctness of operation order and outside observers.

Now, with separate fields offloaded to different places you can have mutiple operations - but you need a linearized order of operations, so op_manager needs to become more complicated and act as an intermediary coordinator

[romange]

So, take hmap for example. I assume that hmap is either fully external, or fully in memory or a map<key, StringOrExternal>.

Then op_manager needs to track between fields (key->field). We could do it naively by extending std::variant<unsigned, KeyRef> to hold key->field as well. But I think we can even do something even simpler: we can use uintptr_t as unique id.
uintptr_t as each entry in dense_set is allocated on heap, we can use its pointer as a tracking id.

Similarly, with quicklist, assuming we want to offload selectively its nodes, we can use uintptr_t = node* as tracking id.
(Note, maybe it's not possible - the question - how we update the tiering state inside NotifyFetched - this is the central piece that needs to update an entry back based on a read completion).

There are also some technical things that needs to polished that tiered_manager is tightly coupled with PrimeValue's state but it's solvable if we pass/receive the relevant tiered state explicitly.

In short, I do not see immediate blockers if we extend PendingId, and introduce TryStash, Delete, CancelStash that are not coupled with PrimeValue.

Next step - to think how we can hold the tiering state for dense_map entry or QList::Node.

[romange]

Implementation Analysis: Selective Offloading for Collections

It appears we need only a single bit to mark items as "hot" during the offloading process. Once items are offloaded, we can replace their values with special tiered records. We have considerable implementation flexibility depending on the data structure:

• Lists (quicklist nodes): High flexibility for record replacement
• Dense sets: We can replace values with custom tiered records, requiring an additional tag bit for identification
• OAH Sets: More complex, as we may need to reallocate both keys and values. However, this shouldn't be a dealbreaker (cc @BorysTheDev)

Narrowing Scope: Queue Tiering Product

Placement policy heuristics remain an open question. To make progress, I propose starting with a narrow, well-defined product: queue offloading.

Goal: Prevent OOM scenarios (or over-provisioning of in-memory storage) by selectively offloading queue data to disk.

---

Job Queue Offloading

Product Overview

A localized, simple heuristic that prevents OOM when job queues "overflow" beyond their typical working set.

Overflow Definition: node_count > K (where K is a configurable threshold)

Typical Access Pattern: Most job management operations push and pop from the tail, primarily accessing the last node(s).

State Machine

stateDiagram-v2
    [*] --> InMemory: Queue created
    InMemory --> Offloading: node_count > K
    Offloading --> Hybrid: First M nodes offloaded
    Hybrid --> InMemory: node_count ≤ K
    Hybrid --> Offloading: node_count increases
    
    note right of InMemory
        All nodes in RAM
        Fast operations
    end note
    
    note right of Hybrid
        Head: M nodes on disk
        Tail: active nodes in RAM
    end note

Loading

graph TB
    subgraph Queue ["List Structure"]
        N1["Node 1<br/>(oldest)<br/>TIERED"]
        N2["Node 2<br/>TIERED"]
        N3["..."]
        NM["Node M<br/>TIERED"]
        NM1["Node M+1<br/>IN-MEMORY"]
        NK["Node K<br/>(newest)<br/>IN-MEMORY"]
    end
    
    subgraph Disk ["Tiered Storage"]
        D1[Segment 1]
        D2[Segment 2]
        DM[Segment M]
    end
    
    N1 -.-> D1
    N2 -.-> D2
    NM -.-> DM
    
    style N1 fill:#e1f5ff,stroke:#0078d4
    style N2 fill:#e1f5ff,stroke:#0078d4
    style NM fill:#e1f5ff,stroke:#0078d4
    style NM1 fill:#d4f4dd,stroke:#107c10
    style NK fill:#d4f4dd,stroke:#107c10

I will open a list related sub-task.

[BorysTheDev]

@romange "OAH Sets: More complex, as we may need to reallocate both keys and values. However, this shouldn't be a dealbreaker".
It uses the same mechanism as DenseSet, so no difference. Merge key and values together is an option that can be controlled via one bit. We even can turn off keys and value merging if we need