You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@hudi.apache.org by vh...@apache.org on 2026/03/20 09:21:37 UTC
(hudi) branch rfc-blob-cleaner updated: Fix derivation and assumptions
This is an automated email from the ASF dual-hosted git repository.
vhs pushed a commit to branch rfc-blob-cleaner
in repository https://gitbox.apache.org/repos/asf/hudi.git
The following commit(s) were added to refs/heads/rfc-blob-cleaner by this push:
new e94e7eed7e41 Fix derivation and assumptions
e94e7eed7e41 is described below
commit e94e7eed7e4169459446ef834a7a817a0bf8e850
Author: voon <vo...@gmail.com>
AuthorDate: Fri Mar 20 17:21:28 2026 +0800
Fix derivation and assumptions
---
rfc/rfc-100/rfc-100-blob-cleaner-design.md | 60 ++++++++++++-------
rfc/rfc-100/rfc-100-blob-cleaner.md | 95 +++++++++++++++++-------------
2 files changed, 91 insertions(+), 64 deletions(-)
diff --git a/rfc/rfc-100/rfc-100-blob-cleaner-design.md b/rfc/rfc-100/rfc-100-blob-cleaner-design.md
index db65d648d498..18919658c2b2 100644
--- a/rfc/rfc-100/rfc-100-blob-cleaner-design.md
+++ b/rfc/rfc-100/rfc-100-blob-cleaner-design.md
@@ -347,13 +347,29 @@ for path in candidate_paths:
**Cost model.** The lookup is a three-step process: (1) batched prefix scan on the secondary index,
(2) batched record index lookup for all record keys in a single sorted HFile scan, (3) in-memory
resolution with per-candidate short-circuit. Steps 1 and 2 are each a single I/O pass; step 3 is
-pure in-memory hash set lookups (~0ms).
-
-| Step | I/O | Cost |
-|---------------------------|---------------------------------------|--------------------------|
-| 1. Prefix scan (batched) | Single MDT call for N candidate paths | ~2-5s for 2K candidates |
-| 2. Record index (batched) | Single sorted HFile forward-scan | ~1-2s for 6K record keys |
-| 3. In-memory resolution | Hash set checks (cleaned_fg_ids) | ~0ms |
+pure in-memory hash set lookups.
+
+**I/O assumptions.** Both MDT calls perform sorted forward scans through HFile blocks. The
+dominant costs are HFile open (block index + metadata) and sequential block reads. Estimates
+assume cloud object storage (S3/GCS/ADLS) with ~10-100ms per-read latency and ~50-200 MB/s
+sequential throughput, and HFile block size of 64-256KB (Hudi defaults). These are estimates
+pending benchmarking; actual latency depends on storage backend, block cache state, and HFile
+size.
+
+| Step | I/O | Estimated cost (2K candidates) |
+|---------------------------|-----------------------------------------------|--------------------------------|
+| 1. Prefix scan (batched) | 1 HFile open + forward scan of N prefix keys | ~2-5s (see derivation below) |
+| 2. Record index (batched) | 1 HFile open + forward scan of 6K sorted keys | ~1-2s (see derivation below) |
+| 3. In-memory resolution | Hash set checks (cleaned_fg_ids) | ~0ms |
+
+**Derivation.** Step 1: the secondary index HFile for a table with 250K external blob references
+at ~200 bytes/entry is ~50MB. A sorted forward scan for 2K prefixes reads a subset of 64KB
+blocks (~200-500 blocks). At cloud storage latencies, with read-ahead amortization:
+1 HFile open (~100-200ms) + block reads (~50MB at 50-200 MB/s = ~0.25-1s) + per-block latency
+overhead (~0.5-2s for cold cache) = ~1-3s. With margin for larger indexes or multiple HFiles
+(pending MDT compaction): ~2-5s. Step 2: the record index HFile is larger, but the forward scan
+touches only blocks containing the 6K sorted keys. Similar I/O profile, fewer blocks hit relative
+to index size: ~1-2s.
**Index definition.** Uses the existing `HoodieIndexDefinition` mechanism with
`sourceFields = ["<blob_col>", "reference", "external_path"]`. The nested field path is supported
@@ -388,7 +404,7 @@ sequenceDiagram
Note over C: Step 1: Batch prefix scan
C->>SI: All candidate paths (N paths, single call)
- SI-->>C: Map<path, List<recordKey>>
+ SI-->>C: Map<path, List<recordKey>>
Note over C: Step 2: Batch record index lookup
C->>C: Collect all record keys from all candidates
@@ -679,20 +695,20 @@ cleaning:
### Back-of-Envelope: Example 7 (50K FGs, 2K External Candidates)
-| Parameter | Value | Notes |
-|-------------------------------------|-----------|-----------------------------------------------|
-| FGs cleaned this cycle | 500 | 1% of table |
-| Stage 1: reads per FG | ~6 | 3 retained + 3 expired slices |
-| Stage 1: total reads | 3,000 | Parallelized across executors, ~20s |
-| External blob candidates | 2,000 | Locally orphaned in cleaned FGs |
-| Avg refs per candidate | 3 | Typical: video in a few playlists |
-| Total record keys | 6,000 | 2,000 * 3 |
-| **Stage 2 cost** | | |
-| Step 1: batched prefix scan | 1 call | Returns 6K record keys, ~2-5s |
-| Step 2: batched record index lookup | 1 call | 6K keys sorted, single HFile scan, ~1-2s |
-| Step 3: in-memory resolution | 6K checks | Hash set lookups against cleaned_fg_ids, ~0ms |
-| **Total Stage 2** | **~3-7s** | |
-| Comparison: naive full-table scan | 12.5TB | 50K FGs * 5 slices * 50MB = prohibitive |
+| Parameter | Value | Notes |
+|-------------------------------------|-----------|------------------------------------------------------|
+| FGs cleaned this cycle | 500 | 1% of table |
+| Stage 1: reads per FG | ~6 | 3 retained + 3 expired slices |
+| Stage 1: total reads | 3,000 | Parallelized across executors, ~20s |
+| External blob candidates | 2,000 | Locally orphaned in cleaned FGs |
+| Avg refs per candidate | 3 | Typical: video in a few playlists |
+| Total record keys | 6,000 | 2,000 * 3 |
+| **Stage 2 cost (estimated)** | | |
+| Step 1: batched prefix scan | 1 call | Returns 6K record keys, ~2-5s estimated |
+| Step 2: batched record index lookup | 1 call | 6K keys sorted, single HFile scan, ~1-2s estimated |
+| Step 3: in-memory resolution | 6K checks | Hash set lookups against cleaned_fg_ids, ~0ms |
+| **Total Stage 2** | **~3-7s** | Estimated; see I/O assumptions in Stage 2 cost model |
+| Comparison: naive full-table scan | 12.5TB | 50K FGs * 5 slices * 50MB = prohibitive |
### Memory Budget
diff --git a/rfc/rfc-100/rfc-100-blob-cleaner.md b/rfc/rfc-100/rfc-100-blob-cleaner.md
index 6365f6807d4d..4fe0e3dee124 100644
--- a/rfc/rfc-100/rfc-100-blob-cleaner.md
+++ b/rfc/rfc-100/rfc-100-blob-cleaner.md
@@ -358,26 +358,37 @@ adjacent blocks. No per-key random I/O.
**Back-of-envelope for Example 7 (revised):**
-| Parameter | Value | Notes |
-|------------------------------------|--------------|--------------------------------------------------|
-| Candidate paths (N) | 2,000 | Locally orphaned in 500 cleaned FGs |
-| Avg refs per candidate (R_avg) | 3 | Typical: video in a few playlists |
-| Total record keys (R_total) | 6,000 | N * R_avg |
-| Popular blob refs (viral example) | 10,000 | A viral video in many playlists |
-| **Step 1: batched prefix scan** | 1 MDT call | Returns 6K record keys (or 10K+ with viral), ~2-5s |
-| **Step 2: batched record index** | 1 MDT call | 6K keys sorted, single HFile scan, ~1-2s |
-| **Step 3: in-memory resolution** | 6K checks | Hash set lookups, ~0ms |
-| **Total Stage 2** | **~3-7s** | Two I/O passes + in-memory |
-| **Viral blob (10K refs)** | | |
-| Step 1: prefix scan | 1 MDT call | Returns 10K record keys, ~2-3s |
-| Step 2: record index | 1 MDT call | 10K keys sorted, single HFile scan, ~2-3s |
-| Step 3: in-memory resolution | 10K checks | ~0ms |
-| **Total for viral blob** | **~4-6s** | Sequential scan, not 10K random seeks |
+| Parameter | Value | Notes |
+|-----------------------------------|------------|--------------------------------------------------------------|
+| Candidate paths (N) | 2,000 | Locally orphaned in 500 cleaned FGs |
+| Avg refs per candidate (R_avg) | 3 | Typical: video in a few playlists |
+| Total record keys (R_total) | 6,000 | N * R_avg |
+| Popular blob refs (viral example) | 10,000 | A viral video in many playlists |
+| **Step 1: batched prefix scan** | 1 MDT call | Returns 6K record keys (or 10K+ with viral), ~2-5s estimated |
+| **Step 2: batched record index** | 1 MDT call | 6K keys sorted, single HFile scan, ~1-2s estimated |
+| **Step 3: in-memory resolution** | 6K checks | Hash set lookups, ~0ms |
+| **Total Stage 2** | **~3-7s** | Estimated; two I/O passes + in-memory |
+| **Viral blob (10K refs)** | | |
+| Step 1: prefix scan | 1 MDT call | Returns 10K record keys, ~2-3s estimated |
+| Step 2: record index | 1 MDT call | 10K keys sorted, single HFile scan, ~2-3s estimated |
+| Step 3: in-memory resolution | 10K checks | ~0ms |
+| **Total for viral blob** | **~4-6s** | Estimated; sequential scan, not 10K random seeks |
Both steps use batch APIs (`readSecondaryIndexDataTableRecordKeysWithKeys` and
`readRecordIndexLocations`) that sort keys internally and perform sequential forward-scans
through HFile blocks. No per-key random I/O.
+**I/O assumptions and derivation.** Estimates assume cloud object storage (S3/GCS/ADLS) with
+~10-100ms per-read latency, ~50-200 MB/s sequential throughput, and HFile block size of
+64-256KB (Hudi defaults). Step 1: a secondary index HFile for 250K external blob references at
+~200 bytes/entry is ~50MB. A sorted forward scan for 2K prefixes reads ~200-500 blocks. With
+read-ahead amortization: 1 HFile open (~100-200ms) + block reads (~50MB at 50-200 MB/s) +
+per-block latency overhead (~0.5-2s cold cache) = ~1-3s; with margin for larger indexes or
+multiple HFiles: ~2-5s. Step 2: record index HFile is larger but forward scan touches only
+blocks containing the 6K sorted keys, similar I/O profile: ~1-2s. These are estimates pending
+benchmarking; actual latency depends on storage backend, block cache state, and HFile size.
+(Need proper benchmarking to actually confirm these numbers)
+
Even in the viral blob case, this is far cheaper than the fallback table scan (12.5TB for Example 7).
**Index definition.** The index is defined as a secondary index on the blob reference's
@@ -1444,22 +1455,22 @@ HFile forward-scan, (3) in-memory resolution with per-candidate short-circuit.
The I/O is sequential (sorted forward-scans through HFiles), not random per-key lookups. See
Section 3.2.1 for the detailed cost model and analysis.
-**Scaling analysis for Example 7 (media company, revised):**
-
-| Parameter | Value | Notes |
-|---------------------------------|--------------|----------------------------------------------|
-| Total videos | 10M | Stored in s3://media-library/ |
-| Total file groups | 50K | Across 1K partitions |
-| FGs cleaned this cycle | 500 | 1% of table |
-| External blob candidates | 2,000 | Locally orphaned in cleaned FGs |
-| Avg refs per candidate | 3 | Typical: video in a few playlists |
-| Total record keys (R_total) | 6,000 | N * R_avg |
-| **Stage 2 (batched pipeline)** | | |
-| Step 1: batched prefix scan | 1 MDT call | Returns 6K record keys, ~2-5s |
-| Step 2: batched record index | 1 MDT call | 6K keys sorted, single HFile scan, ~1-2s |
-| Step 3: in-memory resolution | 6K checks | Hash set lookups, ~0ms |
-| **Total Stage 2 time** | **~3-7s** | |
-| Comparison: naive table scan | 12.5TB read | 50K FGs * 5 slices * 50MB = prohibitive |
+**Scaling analysis for Example 7:**
+
+| Parameter | Value | Notes |
+|--------------------------------|-------------|-----------------------------------------------|
+| Total videos | 10M | Stored in s3://media-library/ |
+| Total file groups | 50K | Across 1K partitions |
+| FGs cleaned this cycle | 500 | 1% of table |
+| External blob candidates | 2,000 | Locally orphaned in cleaned FGs |
+| Avg refs per candidate | 3 | Typical: video in a few playlists |
+| Total record keys (R_total) | 6,000 | N * R_avg |
+| **Stage 2 (batched pipeline)** | | |
+| Step 1: batched prefix scan | 1 MDT call | Returns 6K record keys, ~2-5s estimated |
+| Step 2: batched record index | 1 MDT call | 6K keys sorted, single HFile scan, ~1-2s est. |
+| Step 3: in-memory resolution | 6K checks | Hash set lookups, ~0ms |
+| **Total Stage 2 time** | **~3-7s** | Estimated; see Section 3.2.1 for derivation |
+| Comparison: naive table scan | 12.5TB read | 50K FGs * 5 slices * 50MB = prohibitive |
The index maintenance cost is borne by the existing MDT write pipeline via
`SecondaryIndexRecordGenerationUtils.convertWriteStatsToSecondaryIndexRecords()`. When a record
@@ -1812,20 +1823,20 @@ The lookup is a three-step pipeline with two batched I/O passes and one in-memor
lookup for all record keys in a single sorted HFile forward-scan, (3) in-memory resolution with
per-candidate short-circuit.
-| Parameter | Value | Notes |
-|---------------------------------------|----------------------|------------------------------------------------------|
-| Candidates (N) | N | Only locally-orphaned external blobs |
-| Step 1: batched prefix scan | 1 MDT call | readSecondaryIndex...WithKeys for N paths |
-| Record keys returned (R_total) | N * R_avg | R_avg = avg refs per candidate |
-| Step 2: batched record index | 1 MDT call | readRecordIndexLocations: sorted forward-scan |
-| Step 3: in-memory resolution | R_total checks | Hash set lookups against cleaned_fg_ids |
-| Memory | O(N * R_avg) | Record keys + lookup results (in-memory after batch) |
+| Parameter | Value | Notes |
+|--------------------------------|----------------|------------------------------------------------------|
+| Candidates (N) | N | Only locally-orphaned external blobs |
+| Step 1: batched prefix scan | 1 MDT call | readSecondaryIndex...WithKeys for N paths |
+| Record keys returned (R_total) | N * R_avg | R_avg = avg refs per candidate |
+| Step 2: batched record index | 1 MDT call | readRecordIndexLocations: sorted forward-scan |
+| Step 3: in-memory resolution | R_total checks | Hash set lookups against cleaned_fg_ids |
+| Memory | O(N * R_avg) | Record keys + lookup results (in-memory after batch) |
For Example 7 (2,000 candidates, R_avg=3, R_total=6K):
-- Step 1: batched prefix scan returning 6K record keys, ~2-5s.
-- Step 2: batched record index lookup, 6K keys sorted, single HFile scan, ~1-2s.
+- Step 1: batched prefix scan returning 6K record keys, ~2-5s (estimated).
+- Step 2: batched record index lookup, 6K keys sorted, single HFile scan, ~1-2s (estimated).
- Step 3: in-memory resolution, ~0ms.
-- **Total: ~3-7s.**
+- **Total: ~3-7s (estimated; see Section 3.2.1 for I/O assumptions and derivation).**
For a viral blob (10K refs):
- Step 1: prefix scan for that blob returns 10K keys, ~2-3s.