Understanding LSM Trees: What Powers Write-Heavy Databases

• 500lines

  2 28 10.0 Python

  500 Lines or Less (by kragen)

Groom seems to have forgotten to mention the "merge" part of "log-structured merge" trees, and consequently the "log-structured" part too. He does talk about a "compaction process," but he sort of just doesn't mention the process of selecting when and what to compact, or why the compaction process can use purely sequential I/O, which are the crucial aspects of LSM-tree performance.

My unfinished attempt from 02014 to explain LSM-trees (and, in particular, full-text search engines using them) with an implementation in 250 lines of Python 2 is at https://github.com/kragen/500lines/tree/master/search-engine. I think it's a more complete explanation (except for tombstones), but it's longer (half an hour of reading) and there aren't as many illustrations.

On the plus side, you can actually run it:

    $ make

• go-sstables

  4 255 4.0 Go

  Go library for protobuf compatible sstables, a skiplist, a recordio format and other database building blocks like a write-ahead log. Ships now with an embedded key-value store.

• SurveyJS

  surveyjs.io featured

  Open-Source JSON Form Builder to Create Dynamic Forms Right in Your App. With SurveyJS form UI libraries, you can build and style forms in a fully-integrated drag & drop form builder, render them in your JS app, and store form submission data in any backend, inc. PHP, ASP.NET Core, and Node.js.

  

• peg-bootstrap

  6 74 0.0 JavaScript

  A PEG that compiles itself.

Oh goodness, I never thought about using LuaLaTeX for that! I wrote handaxeweb.lua originally for https://github.com/kragen/peg-bootstrap/peg.md but have used it for various things since then.

Suggest a related project