Sorted string tables (SST) from first principles

https://www.bitsxpages.com/p/sorted-string-tables-sst-from-first

71•apurvamehta•1mo ago

Comments

craftkiller•4w ago

The diagrams on this page are stunning! My only complaint is leaving the close/maximize/minimize buttons in the top left was unnecessary but this is the kind of clarity I always strive for (and fail to achieve) every time I make diagrams.

Did you use a tool to create them, and if so, what is that tool?

agavra•4w ago

Thanks! I use https://monodraw.helftone.com/ which is my favorite one-time-purchase software of all time. I definitely agree the buttons on the top left are unnecessary but ... it's cute and it makes me happy so I can't help it. Maybe I'll come up with a different style for the next blog

cipehr•4w ago

Thanks for sharing. I also like the diagrams for this.

epistasis•4w ago

> There are several ways to organize immutable data durably that meet these requirements, the simplest of which is an append-only log.

This is also a fairly good way to handle large amounts of data with maximum performance on spinning rust, and at the heart of systems like Kafka.

I had assumed that the story would be very different with SSDs, so it's surprising to see append only logs show up again.

agavra•4w ago

We haven't even started to discuss Object Storage, but it ends up looking very very similar if you're building data systems that use that instead of raw filesystems (not so much for physics reasons, but because of the way object storage require immutable objects and penalize you for many API calls)

mac3n•4w ago

see https://gitlab.com/mac3n/ksip binary search on mmpa'd sorted text files no index needed

mac3n•4w ago

what this could really use is a compression format that compresses variable amount of text into fixed-size blocks. with that, it could binary-search compressed text

agavra•4w ago

RocksDB actually does something somewhat similar with its prefix compression. It prefix-compresses texts and then "resets"the prefix compression every N records so it stores a mapping of reset point -> offset so you can skip across compressed records. It's pretty neat

agavra•4w ago

this is pretty different but reminds me of https://en.wikipedia.org/wiki/Bitcask - if you're storing it all in memory why not just use a hash index?

mac3n•4w ago

The trick is, it's not all in memory - it's a memory-mapped file If you look at the cache (with `fincore` or similar) you'll see that the buinary search only loads the pages it examines, roughly logarithmetic in the file size.

And a text file is the most useful general format - easy to write, easy to process with standard tools.

I've used this in the past on data sets of hundreds of millions of lines, maybe billions.

It's also true that you could use a memory-mapped indexed file for faster searches - I've used sqlite for this.

agavra•4w ago

So cool to see this make the front page of hacker news! I'm the author, I'll be online here throughout the weekend to answer any questions you might have :) excited for the next post which is in the works about LSM trees.

Show HN: LocalGPT – A local-first AI assistant in Rust with persistent memory

SectorC: A C Compiler in 512 bytes (2023)

Haskell for all: Beyond agentic coding

Speed up responses with fast mode

Software factories and the agentic moment

Brookhaven Lab's RHIC concludes 25-year run with final collisions

IBM Beam Spring: The Ultimate Retro Keyboard

Hoot: Scheme on WebAssembly

Stories from 25 Years of Software Development

LLMs as the new high level language

First Proof

Vocal Guide – belt sing without killing yourself

Show HN: I saw this cool navigation reveal, so I made a simple HTML+CSS version

FDA intends to take action against non-FDA-approved GLP-1 drugs

Al Lowe on model trains, funny deaths and working with Disney

Show HN: A luma dependent chroma compression algorithm (image compression)

Start all of your commands with a comma (2009)

Show HN: Axiomeer – An open marketplace for AI agents

Vouch

The AI boom is causing shortages everywhere else

Microsoft account bugs locked me out of Notepad – Are thin clients ruining PCs?

The silent death of good code

Selection rather than prediction

I write games in C (yes, C) (2016)

OpenCiv3: Open-source, cross-platform reimagining of Civilization III

Learning from context is harder than we thought

Reinforcement Learning from Human Feedback

Where did all the starships go?

Unseen Footage of Atari Battlezone Arcade Cabinet Production

Show HN: Look Ma, No Linux: Shell, App Installer, Vi, Cc on ESP32-S3 / BreezyBox

Show HN: LocalGPT – A local-first AI assistant in Rust with persistent memory

SectorC: A C Compiler in 512 bytes (2023)

Haskell for all: Beyond agentic coding

Speed up responses with fast mode

Software factories and the agentic moment

Brookhaven Lab's RHIC concludes 25-year run with final collisions

IBM Beam Spring: The Ultimate Retro Keyboard

Hoot: Scheme on WebAssembly

Stories from 25 Years of Software Development

LLMs as the new high level language

First Proof

Vocal Guide – belt sing without killing yourself

Show HN: I saw this cool navigation reveal, so I made a simple HTML+CSS version

FDA intends to take action against non-FDA-approved GLP-1 drugs

Al Lowe on model trains, funny deaths and working with Disney

Show HN: A luma dependent chroma compression algorithm (image compression)

Start all of your commands with a comma (2009)

Show HN: Axiomeer – An open marketplace for AI agents

Vouch

The AI boom is causing shortages everywhere else

Microsoft account bugs locked me out of Notepad – Are thin clients ruining PCs?

The silent death of good code

Selection rather than prediction

I write games in C (yes, C) (2016)

OpenCiv3: Open-source, cross-platform reimagining of Civilization III

Learning from context is harder than we thought

Reinforcement Learning from Human Feedback

Where did all the starships go?

Unseen Footage of Atari Battlezone Arcade Cabinet Production

Show HN: Look Ma, No Linux: Shell, App Installer, Vi, Cc on ESP32-S3 / BreezyBox

Sorted string tables (SST) from first principles

Comments