GenStore: a high-performance in-storage processing system for genome sequence analysis

Most DNA reads shipped from the SSD to the processor are discarded after a cheap check — GenStore puts that check inside the SSD itself, filtering exact matches and hopeless non-matches at internal flash bandwidth so only the reads that need real work ever leave the drive.

Why this problem is worth solving

Sequencing machines cannot read a genome end to end. They emit reads — randomly sampled fragments, either short and accurate (Illumina: a few hundred base pairs, 99–99.9% accurate) or long and noisy (PacBio, Nanopore: thousands to millions of base pairs, 85–90% accurate) — with the original location lost. Read mapping recovers it: for each read, find where in a known reference genome it belongs, tolerating differences from both sequencing errors and real genetic variation. That tolerance requires approximate string matching (ASM) — dynamic-programming alignment that is the costly heart of the process — applied to millions of reads against a 3.2-billion-base-pair human reference.

Mappers fight this cost with an index of the reference’s k-mers (length-k subsequences, often thinned to representative minimizers): seeding looks up each read’s k-mers to find candidate locations, chaining scores how well seed hits line up (discarding hopeless reads), and only survivors reach full alignment. A rich ecosystem of filters and accelerators optimizes every one of these stages.

What nobody counted, the paper argues, is the I/O. Read sets are gigabytes on an SSD; every existing filter and accelerator first ships the whole set to main memory — including the large fraction that a cheap test then discards, never to be touched again. Two production facts size the waste: about 80% of human short reads match the reference exactly (needing no alignment at all), and read sets from fast-evolving organisms like SARS-CoV-2 average 36% (up to 99.9%) reads that align nowhere. The motivational study lands the punch: with an ideal in-storage filter, a software mapper would speed up 3.12×; with a hardware accelerator, even the best PCIe-4 SSD leaves 23% on the table versus DRAM-resident data — the faster the compute, the more the storage pipe is the bottleneck.

What people did before, and where it broke

Filtering itself is well-developed: exact-match filters (like GenCache’s) detect reads that need no alignment; location filters prune bad candidate positions; chaining discards reads with no plausible region. Accelerators (FPGAs, ASICs, processing-in-memory) attack seeding, filtering and alignment. All of it reduces computation — none of it reduces movement, because the filters themselves run on the host, after the full read set has crossed the storage interface.

Why not just move filtering into the SSD? Two genuine obstacles. First, workload diversity: short accurate reads and long noisy reads behave completely differently (a long read’s higher error rate means almost none match exactly; its length makes chaining costly), and genetic variation between sample and reference changes which filter pays off. One rigid in-storage function would serve only a slice of genomics. Second, and more fundamental, the access-pattern mismatch: every standard filter is built on index lookups — several random accesses per read into a multi-gigabyte k-mer index. An SSD is architecturally the wrong place for that: internally it excels at wide sequential streaming across many flash channels, while random access is its weakness, and its internal DRAM is small (mostly consumed by address-mapping tables). Naively porting a host filter into the drive would run it on the drive’s weakest resource.

GenStore’s design answer: don’t port the algorithms — reshape them until their access patterns are sequential scans, which the SSD’s internal parallelism serves magnificently.

The idea

GenStore-EM: exact-matching by merge-scan, not lookup

The insight that unlocks in-storage exact-match filtering is a data- structure inversion. Instead of looking up each read’s many k-mers in a random-access index, GenStore-EM prepares two sorted structures: a sorted read table (all reads in alphabetical order) and a new sorted, read-sized k-mer index — every distinct read-length subsequence of the reference, also in order. Finding exact matches then becomes the classic merge of two sorted lists: stream both sequentially, advance two pointers, compare. One comparison step per read, zero random accesses, and both streams flow at full internal flash bandwidth across channels, double- buffered through 8 MB of SSD DRAM so the comparator never starves.

Two refinements keep it lean. Entries store 32-bit fingerprints (hashes) instead of raw sequences, shrinking the index 3.9× and making the comparator trivial — with a collision rate so low that mapping accuracy is untouched. And the whole scan is embarrassingly pipeline-able: batches stream, one comparator per SSD suffices, and filtering overlaps with the host’s mapping of unfiltered reads. For short read sets where 80% match exactly, four fifths of the dataset never crosses the storage interface.

GenStore-NM: discard the hopeless, defer the hopeful

Non-matching reads (dominant when comparing across high genetic variation, or with noisy long reads) would ideally be caught by chaining — but full chaining is a dynamic-programming pass over all of a read’s seed hits, far too heavy for in-SSD hardware when long reads carry thousands of k-mers. GenStore-NM’s twist is selective chaining: count each read’s exactly-matching minimizer k-mers first (per-channel k-mer windows plus a hash accelerator, again streaming); a read with many matching k-mers almost certainly aligns — send it straight to the host, no in-storage work needed. Only reads with few matching seeds get the small in-storage chaining engine’s attention, and most of those score below threshold and are discarded on the spot. The expensive middle ground is deliberately outsourced; the hardware handles only the cheap extremes — which is precisely why the accelerator fits in fractions of a square millimeter.

Both modes are coordinated by the SSD firmware alongside its normal duties, use technology-aware data placement (structures striped for multi-channel concurrency), and — critically — are filters, not approximations: every discarded read is one the host mapper would also have discarded, so final mapping output is bit-identical.

SRTable: reads, sorted
SKIndex: reference k-mers (read-sized), sorted, fingerprinted (3.9× smaller)
layout: striped across channels for concurrent streaming

Why it works

Because a large, quantifiable fraction of genomic reads needs only a cheap verdict — exact match (~80% of human short reads) or hopeless non-match (up to 99.9% in divergent samples) — filtering them before they travel converts wasted bandwidth into free performance. → Because the filters were redesigned around sorted, stream-once data structures, they run on what an SSD is best at (wide sequential internal streaming, up to 19.2× external bandwidth) and avoid what it is worst at (random access on a small DRAM). → Because selective chaining routes confident reads past the in-storage engine, the hardware only handles trivially cheap cases — keeping the added silicon at 0.006% of a controller and never becoming the new bottleneck. → Because filtering overlaps host mapping in a pipeline, its latency hides; and because filters only discard what the mapper would discard, correctness is structural, not statistical. → Therefore every class of system gains — modest SSDs gain most from saved external bandwidth, accelerated systems gain most because their compute no longer waits on I/O — and the gains scale with exactly the trends genomics is on: faster accelerators, bigger read sets, cheaper flash.

What it costs

• Preprocessing and preparation. The sorted structures must be built when a read set is written (amortized over many mapping runs, but real); the read-sized k-mer index is per-reference and per-read-length.
• SSD vendor buy-in. GenStore needs modified firmware, small added logic, and a share of the drive’s DRAM (8 MB of buffers) — trivial in silicon, non-trivial as a product decision.
• Wrong-workload cases degrade to baseline. A read set with few exact matches gives GenStore-EM little to filter; a set that aligns almost entirely gives GenStore-NM little. The two modes cover complementary regimes, and the host mapper always remains the fallback.
• Evaluation is simulation. Performance comes from synthesized Verilog (65 nm) plus Ramulator and MQSim models of three SSD classes, with host baselines measured on a real EPYC server — rigorous, but not a shipping drive.
• Filters address mapping’s front end. Alignment of the surviving reads is untouched; on read sets where most reads genuinely need alignment, end-to-end gains shrink toward the accelerator’s own limits.

The evaluation

Three SSD classes (SATA3 at 500 MB/s external; PCIe-3 at 3.5 GB/s; PCIe-4 at 7 GB/s — with internal bandwidths 19.2×, 5.48× and 2.74× external, respectively), real genomic datasets (human short and long reads, SARS-CoV-2 and other divergent samples), and three host mappers: Minimap2 (software), GenCache (short-read accelerator), Darwin (long-read accelerator).