deven96 / deven96/ahnlich

Investigate safe cleanup of empty predicate-index buckets

Open
#416 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Rust
Stars
244
Forks
29
Avg merge
2d 41m
Merged PRs (30d)
19

Description

## Problem

PR #415 changes predicate-index deletion to use each deleted entry's metadata to locate and update only the relevant buckets.

Predicate indexes use the following nested structure:

```rust
HashMap>
```

Under the proposed implementation, when a store entry is deleted, its `StoreKeyId` is removed from the corresponding inner set, while the `MetadataValue -> empty HashSet` bucket is deliberately retained. This avoids adding unsafe concurrent cleanup to the deletion hot path, but it can retain substantial memory for high-cardinality predicate indexes.

## Worst-Case Impact

Consider an indexed metadata field containing 10,000 unique values, each referenced by one store entry. After deleting every entry, the index retains:

- 10,000 `MetadataValue` keys
- 10,000 empty `papaya::HashSet` instances
- each set's backing table and sharded counter
- the outer Papaya table

On an arm64 machine with 10 logical CPUs, the estimated retained-memory lower bound is approximately 30.3 MiB:

| Allocation | Estimated size |
| --- | ---: |
| Outer entries (`MetadataValue` + `HashSet`) | 10.56 MB |
| Papaya counter shards | 20.48 MB |
| Minimum inner table slot arrays | 0.72 MB |
| **Lower bound** | **31.76 MB** |

This excludes table headers, metadata string/byte allocations, allocator bookkeeping, the outer table, and deferred reclamation state.

Papaya creates a cache-padded counter shard per logical CPU, rounded to the next power of two. Consequently, the retained memory per empty bucket increases with the machine's CPU count.

## Correctness Constraint

A naive cleanup is unsafe:

```rust
store_key_ids.remove(store_key_id);

if store_key_ids.is_empty() {
buckets.remove(metadata_value);
}
```

A concurrent insertion could obtain the existing set before the outer bucket is removed, insert into the now-detached set, and lose the index update.

Any cleanup implementation must coordinate insertion and deletion so that a bucket cannot be removed while another operation can still mutate it without detecting and retrying.

## Investigation

Evaluate approaches such as:

1. Concurrent bucket removal with identity checks and insertion retries.
2. Periodic compaction or index rebuilding when the empty-bucket ratio exceeds a threshold.
3. Deferred cleanup under exclusive access to the predicate index.
4. A different bucket representation with cheaper empty-state overhead.

The investigation should measure:

- retained memory at increasing cardinalities
- deletion and insertion latency
- concurrent delete/insert behavior for the same metadata value
- cleanup or rebuild cost
- low-cardinality and high-cardinality workloads
- sensitivity to logical CPU count

## Acceptance Criteria

- Empty predicate buckets can be reclaimed without losing concurrent index updates.
- Concurrent insertion and deletion tests cover the same metadata value.
- Memory benchmarks quantify retained and reclaimed memory at representative cardinalities.
- The selected strategy does not materially regress normal predicate ingestion, deletion, or lookup performance.
- Snapshot serialization and restoration remain behaviorally equivalent.

Contributor guide

Open the contributing guide

Research direction

Start with PR #415 and the predicate-index insertion and deletion paths described in this issue. Measure retained memory, operation latency, concurrent same-value insert/delete behavior, cleanup cost, and CPU-count sensitivity at representative cardinalities. Done means empty buckets are safely reclaimed without lost updates, performance remains acceptable, and concurrent tests, benchmarks, and snapshot behavior meet the acceptance criteria.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
databases
Issue type
Refactor
Difficulty
5/5
Estimated time
Over a week
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.