Skip to content

perf(kv-router): linear scan improvements [DYN-2164]#6363

Merged
PeaBrane merged 24 commits into
mainfrom
rupei/flash-indexer-blog-docs
Mar 2, 2026
Merged

perf(kv-router): linear scan improvements [DYN-2164]#6363
PeaBrane merged 24 commits into
mainfrom
rupei/flash-indexer-blog-docs

Conversation

@PeaBrane

@PeaBrane PeaBrane commented Feb 18, 2026

Copy link
Copy Markdown
Contributor

Summary

  • Add early-exit guard and empty-active-set check in linear_scan_drain to skip unnecessary iterations
  • Extract drain_active helper for cleaner scoring of drained workers
  • Pre-allocate seq_hashes Vec with capacity for fewer reallocations
  • Update ConcurrentRadixTree doc comments to reflect DashMap-based lookup
  • Add test_double_divergence_convergence_across_jumps test for multi-chain jump boundary correctness

🤖 Generated with Claude Code

@github-actions github-actions Bot added docs documentation Improvements or additions to documentation labels Feb 18, 2026
PeaBrane added a commit that referenced this pull request Feb 18, 2026
Signed-off-by: PeaBrane <[email protected]>
Co-authored-by: Cursor <[email protected]>
@PeaBrane PeaBrane marked this pull request as draft February 18, 2026 07:49
@coderabbitai

coderabbitai Bot commented Feb 18, 2026

Copy link
Copy Markdown
Contributor

Walkthrough

This pull request adds comprehensive documentation for the Flash Indexer architecture, including a technical Markdown narrative, an HTML presentation, supporting Mermaid diagrams, and tooling for converting documentation to PDFs via Pandoc with Mermaid diagram rendering capabilities.

Changes

Cohort / File(s) Summary
Flash Indexer Documentation
blog/flash_indexer.md, blog/flash_indexer.html
New technical documentation and styled HTML page describing the Flash Indexer's design evolution across six iterations, from naive dictionaries to a concurrent positional indexer architecture for KV cache block management in LLM inference.
Mermaid Tooling & Styling
blog/mermaid.lua, blog/mermaid_header.html
Introduces a Lua Pandoc filter to process Mermaid code blocks into PNG images and an HTML header snippet for styling and initializing Mermaid diagrams with Water.css integration.
Architecture Diagrams
blog/mermaid_images/diagram_*.mmd
Four Mermaid flowchart diagrams illustrating the Flash Indexer architecture: multi-worker event flow, block locality hashing, read/write path concurrency patterns, and positional indexing with jump-search mechanics.
PDF Build Documentation
blog/PRETTY_PDF.md
New guide documenting how to convert Markdown to formatted PDFs using Pandoc, the Eisvogel template, XeLaTeX, and Mermaid diagram rendering with customization instructions.

Estimated code review effort

🎯 3 (Moderate) | ⏱️ ~25 minutes

Poem

🐰 In the meadow of code, where diagrams bloom,
Flash Indexers dance through the LLM room,
From nested dicts to radix trees so tall,
Mermaid lines draw the architecture's call!
Pretty PDFs spring from Pandoc's might—
Documentation complete, the design shines bright!

🚥 Pre-merge checks | ❌ 3

❌ Failed checks (3 warnings)

Check name Status Explanation Resolution
Docstring Coverage ⚠️ Warning Docstring coverage is 0.00% which is insufficient. The required threshold is 80.00%. Write docstrings for the functions missing them to satisfy the coverage threshold.
Description check ⚠️ Warning The PR description lists specific code optimization changes (early-exit guards, helper extraction, pre-allocation, doc comments, and tests) that are not present in the changeset, which only contains documentation files and no production code modifications. Align the description with the actual changes in the PR. Either add the described optimization commits or revise the description to accurately reflect that this PR adds flash indexer documentation without code optimizations.
Title check ⚠️ Warning The PR title mentions 'linear scan improvements' and references a Jira ticket (DYN-2164), but the actual changes are documentation additions for a flash indexer blog post with mermaid diagrams and no code changes. Update the title to reflect the actual changes, such as 'docs: add flash indexer blog post with mermaid diagrams' to accurately represent the documentation-focused nature of this PR.

✏️ Tip: You can configure your own custom pre-merge checks in the settings.


Thanks for using CodeRabbit! It's free for OSS, and your support helps us grow. If you like it, consider giving us a shout-out.

❤️ Share

Comment @coderabbitai help to get the list of available commands and usage tips.

@coderabbitai coderabbitai Bot left a comment

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Actionable comments posted: 8

🧹 Nitpick comments (3)
blog/mermaid_header.html (1)

11-14: Consider adding SRI hashes and pinning the exact CDN versions.

Both CDN resources — mermaid@11 and water.css@2 — float to the latest patch/minor within their major range. A breaking change in either could silently break rendering. Additionally, without Subresource Integrity hashes, a CDN compromise could inject arbitrary script/style into the page.

🛡️ Suggested hardening
-  import mermaid from 'https://cdn.jsdelivr.net/npm/mermaid@11/dist/mermaid.esm.min.mjs';
+  import mermaid from 'https://cdn.jsdelivr.net/npm/[email protected]/dist/mermaid.esm.min.mjs';
-<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/water.css@2/out/light.min.css">
+<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/[email protected]/out/light.min.css"
+      integrity="sha384-<hash>" crossorigin="anonymous">

(Generate SRI hashes via openssl dgst -sha384 -binary <file> | openssl base64 -A or https://www.srihash.org)

🤖 Prompt for AI Agents
Verify each finding against the current code and only fix it if needed.

In `@blog/mermaid_header.html` around lines 11 - 14, Pin the CDN imports to exact
versions and add SRI integrity+crossorigin attributes for both the mermaid
import (the import statement referencing mermaid@11 and the mermaid.initialize
usage) and the water.css link (the <link rel="stylesheet"> tag) so the browser
verifies content; replace floating specifiers like "mermaid@11" and
"water.css@2" with the exact release filenames (including full semver) and
compute & insert SHA384 SRI hashes (and add crossorigin="anonymous") for both
resources. Ensure the import path used by the mermaid import and the href used
by the water.css link are updated together with their respective integrity
attributes so mermaid.initialize still runs against the pinned bundle and the
stylesheet loads under the integrity check.
blog/mermaid.lua (1)

4-6: ensure_dir() is called for every mermaid block; a one-time guard is cleaner.

mkdir -p is idempotent so this isn't broken, but repeatedly shelling out for each block wastes a fork/exec per diagram.

♻️ Proposed refactor
 local counter = 0
 local img_dir = "mermaid_images"
+local dir_created = false
 
 local function ensure_dir()
-    os.execute("mkdir -p " .. img_dir)
+    if not dir_created then
+        os.execute("mkdir -p " .. img_dir)
+        dir_created = true
+    end
 end

Also applies to: 13-13

🤖 Prompt for AI Agents
Verify each finding against the current code and only fix it if needed.

In `@blog/mermaid.lua` around lines 4 - 6, The ensure_dir function currently
shells out on every mermaid block; make it run once by adding a one-time guard:
introduce a local boolean (e.g., dir_created) at module scope and update
ensure_dir to check that flag, call os.execute("mkdir -p " .. img_dir) only if
dir_created is false, then set dir_created = true; also replace any other direct
mkdir calls (the other ensure_dir call referenced at line 13) to use this
guarded ensure_dir so the directory creation is idempotent without repeated
fork/execs.
blog/flash_indexer.md (1)

413-421: "Scan back" label is misleading — the scan proceeds forward

The diagram arrow labelled "scan back" and the algorithm step 5 both describe scanning the skipped range (positions 65 → 96 in increasing order). The scan is not backward; it fills in drain scores for the range that the failed jump skipped over. Consider renaming to "scan skipped range" or similar to match how linear_scan_drain actually traverses.

🤖 Prompt for AI Agents
Verify each finding against the current code and only fix it if needed.

In `@blog/flash_indexer.md` around lines 413 - 421, The "scan back" label on the
arrow from P64 to scan is misleading because the function linear_scan_drain
actually scans the skipped range forward (positions 65→96); update the diagram
text to reflect that (e.g., change the edge label from "scan back" to "scan
skipped range" or "scan forward (skipped range)") and ensure any accompanying
caption or node label referring to this traversal (scan, P64, P96, and
linear_scan_drain) uses the same terminology so the diagram matches the
algorithm description.
🤖 Prompt for all review comments with AI agents
Verify each finding against the current code and only fix it if needed.

Inline comments:
In `@blog/flash_indexer.html`:
- Around line 463-470: Update the embedded Mermaid diagrams in the HTML so they
exactly match the standalone .mmd files: change IDX label to "IDX[Flash
Indexer]" and add the router→engine edge (R --> E1) in the workload diagram (the
block containing IDX and R), replace the colon in the radix-tree label `"block
0: W0, W1, W2"` with an em dash `"block 0 — W0, W1, W2"`, and in the read/write
diagram move the edges pointing to TREE back inside the writes subgraph and add
the reads subgraph grouping so writers and readers visually target the shared
TREE component; easiest fix is to regenerate the HTML from the updated
Markdown/.mmd sources (e.g., re-run the Pandoc build) so all three diagrams are
synchronized.

In `@blog/flash_indexer.md`:
- Around line 432-435: The loop condition can underflow when len == 0; change
the guard to check len first (e.g., while len > 0 && current_pos < len - 1) and
similarly ensure computing next_pos uses a guarded expression (e.g., let
next_pos = (current_pos + self.jump_size).min(len - 1) only when len > 0) so
that current_pos, len, active, and next_pos do not cause usize underflow; update
the while condition and any related min(len - 1) usage in the same scope (the
loop using current_pos, active, and next_pos) to perform the len > 0 check
first.
- Around line 23-26: Add a language specifier to the fenced code block
containing the rolling-hash pseudocode so markdownlint MD040 is satisfied;
update the fence from ``` to something like ```text (or ```pseudo) for the block
that shows seq_hash[0] = local_hash[0] and seq_hash[i] = hash(seq_hash[i-1] ||
local_hash[i]) so the code is treated as plain text/pseudocode and the linter
warning is resolved.
- Around line 466-515: Add concrete benchmark results and reproducibility links:
update the Benchmarking section to include a concise achieved-vs-offered
throughput summary (e.g., a sentence reporting threshold throughput and the
achieved peak ops/s for the final Positional Indexer with jump search and
optionally per-iteration ops/s), include or reference the ops vs offered curve
inflection point used to define threshold throughput, and add direct links to
the mooncake_bench harness and the public Mooncake trace data so readers can
reproduce the >10 million ops/s claim; mention the exact benchmark configuration
(worker count, duplication factor, block size) used to produce the cited number
so the claim is verifiable.
- Around line 340-353: The send on self.channels inside async fn apply_event is
currently unhandled and may be a dropped future or silently fail; update
apply_event to properly await and handle the send result for the channel type
used: if channels are tokio::sync::mpsc::Sender then call .await on
self.channels[thread_idx].send(Some(event)) and at minimum assign or log the
Result (e.g., let _ = ... .await or log Err), and if channels are synchronous
senders use send(...) and check/handle the return value (unwrap or log on Err);
ensure you modify the send call associated with apply_event and keep the sticky
assignment logic using worker_assignments, counter, and num_workers unchanged.
- Around line 197-226: In find_matches: guard against an empty query by
returning an empty scores map when query.is_empty() (or use query.first() to
safely get the initial LocalHash) instead of indexing query[0]; seed active from
that safe first element, record depth 0 scores for any workers that drop out at
the first position, and then start the for loop from the second element (i.e.,
iterate over query.iter().enumerate().skip(1) or equivalent) so you avoid a
redundant probe at depth 0 and correctly assign scores for workers removed at
position 0; update references to query length when inserting final scores for
remaining workers.

In `@blog/mermaid.lua`:
- Around line 19-29: The code calls io.open(infile) and io.popen(cmd) without
checking for errors, so f or handle can be nil and :write()/:read() will crash;
change the fopen and popen calls to capture both return values (e.g., local f,
ferr = io.open(infile, "w") and local handle, perr = io.popen(cmd)), check if f
or handle is nil, log/report the error string (ferr or perr) using the existing
stderr/error path used elsewhere in this file, and bail out gracefully (skip
converting or return the original block) instead of calling :write() or :read()
on nil; ensure you still close handles only when they are non-nil (f:close(),
handle:close()).

In `@blog/PRETTY_PDF.md`:
- Around line 1-4: The YAML frontmatter in PRETTY_PDF.md uses Cursor rule-style
fields ("name" and "description" with an instruction phrase) which makes it
appear as an AI agent rule rather than normal document metadata; either move
this frontmatter to a Cursor rules file (e.g., create
.cursor/rules/pretty-pdf.mdc and place the "name" and "description" blocks
there) or convert it into standard doc metadata in PRETTY_PDF.md (replace "name"
with "title" and rewrite "description" to a normal human-facing summary) so the
file renders correctly in Markdown viewers and Cursor picks up rules from the
proper location.

---

Nitpick comments:
In `@blog/flash_indexer.md`:
- Around line 413-421: The "scan back" label on the arrow from P64 to scan is
misleading because the function linear_scan_drain actually scans the skipped
range forward (positions 65→96); update the diagram text to reflect that (e.g.,
change the edge label from "scan back" to "scan skipped range" or "scan forward
(skipped range)") and ensure any accompanying caption or node label referring to
this traversal (scan, P64, P96, and linear_scan_drain) uses the same terminology
so the diagram matches the algorithm description.

In `@blog/mermaid_header.html`:
- Around line 11-14: Pin the CDN imports to exact versions and add SRI
integrity+crossorigin attributes for both the mermaid import (the import
statement referencing mermaid@11 and the mermaid.initialize usage) and the
water.css link (the <link rel="stylesheet"> tag) so the browser verifies
content; replace floating specifiers like "mermaid@11" and "water.css@2" with
the exact release filenames (including full semver) and compute & insert SHA384
SRI hashes (and add crossorigin="anonymous") for both resources. Ensure the
import path used by the mermaid import and the href used by the water.css link
are updated together with their respective integrity attributes so
mermaid.initialize still runs against the pinned bundle and the stylesheet loads
under the integrity check.

In `@blog/mermaid.lua`:
- Around line 4-6: The ensure_dir function currently shells out on every mermaid
block; make it run once by adding a one-time guard: introduce a local boolean
(e.g., dir_created) at module scope and update ensure_dir to check that flag,
call os.execute("mkdir -p " .. img_dir) only if dir_created is false, then set
dir_created = true; also replace any other direct mkdir calls (the other
ensure_dir call referenced at line 13) to use this guarded ensure_dir so the
directory creation is idempotent without repeated fork/execs.

Comment thread blog/flash_indexer.html Outdated
Comment thread blog/flash_indexer.md Outdated
Comment thread blog/flash_indexer.md Outdated
Comment thread blog/flash_indexer.md Outdated
Comment thread blog/flash_indexer.md Outdated
Comment thread blog/flash_indexer.md Outdated
Comment thread blog/mermaid.lua Outdated
Comment thread blog/PRETTY_PDF.md Outdated
Signed-off-by: PeaBrane <[email protected]>
Signed-off-by: PeaBrane <[email protected]>
Use cardinality check (workers.len() < active.len()) to skip the
set intersection when all active workers are still present. Extract
drain_active helper and denest linear_scan_drain control flow.

Add test_double_divergence_convergence_across_jumps covering
multi-sequence-per-worker with wrong-chain entries at jump boundaries.

Co-Authored-By: Claude Opus 4.6 <[email protected]>
Signed-off-by: PeaBrane <[email protected]>
Signed-off-by: PeaBrane <[email protected]>
Signed-off-by: PeaBrane <[email protected]>
Signed-off-by: PeaBrane <[email protected]>
@github-actions github-actions Bot added the perf label Feb 24, 2026
Signed-off-by: Rui Peng <[email protected]>
Co-Authored-By: Claude Opus 4.6 <[email protected]>
@PeaBrane PeaBrane changed the title perf(kv-router): flash indexer optimizations — Vec+DashMap index, linear scan improvements, benchmarking [DYN-2164] perf(kv-router): flash indexer optimizations — Vec+DashMap index, linear scan improvements [DYN-2164] Feb 24, 2026
@PeaBrane PeaBrane marked this pull request as ready for review February 24, 2026 08:11
@PeaBrane PeaBrane requested a review from a team as a code owner February 24, 2026 08:11
Bench improvements extracted to rupei/mooncake-bench-improvements (#6631).

Co-Authored-By: Claude Opus 4.6 (1M context) <[email protected]>
Signed-off-by: PeaBrane <[email protected]>
@PeaBrane PeaBrane changed the title perf(kv-router): flash indexer optimizations — Vec+DashMap index, linear scan improvements [DYN-2164] perf(kv-router): flash indexer early-exit and linear scan optimizations Mar 2, 2026
@PeaBrane PeaBrane changed the title perf(kv-router): flash indexer early-exit and linear scan optimizations perf(kv-router): linear scan improvements [DYN-2164] Mar 2, 2026
Comment thread blog/flash_indexer.md Outdated
Comment thread lib/kv-router/src/concurrent_radix_tree.rs Outdated
@PeaBrane PeaBrane merged commit d24cfbe into main Mar 2, 2026
88 of 89 checks passed
@PeaBrane PeaBrane deleted the rupei/flash-indexer-blog-docs branch March 2, 2026 23:56
yao531441 pushed a commit to yao531441/dynamo that referenced this pull request May 13, 2026
Signed-off-by: PeaBrane <[email protected]>
Co-authored-by: Cursor <[email protected]>
Co-authored-by: Claude Opus 4.6 <[email protected]>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

documentation Improvements or additions to documentation perf size/M

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants