The Freelist That Ate the Raft Log — JavaScript Bug Hunt

Briefing

Modelled on Roblox's 73-hour outage (October 28–31, 2021). Roblox's post-mortem traced it to its Consul cluster: a newly enabled streaming feature behaved badly under heavy load, and a pathological performance issue in BoltDB — the embedded database Consul uses for its Raft log — meant its list of free pages had grown very large, making every write progressively slower.

This project is a reconstruction of that second failure mode. freelist.js is the page allocator of a small log store; db.js persists the whole freelist on every commit, as BoltDB does. Freed pages are appended and never reclaimed, so after churn every commit pays for thousands of dead entries.

Fix release (and allocate) so the freelist holds only genuine holes, sorted, and pages at the end of the file are given back by truncating it.

Bug report

BUG-RBX-1028 · Priority: Critical · Reported by: storage on-call

The allocator state is { pageCount, free }. Page ids are 0..pageCount-1.

allocate(fl):

• if free is non-empty, remove and return the LOWEST free page id
• otherwise return pageCount and increment pageCount

release(fl, id):

• ignore ids outside 0..pageCount-1 and ids that are already free
• otherwise add id to free; free is always sorted ascending
• then, while the highest page of the file (pageCount - 1) is free, remove it from free and decrement pageCount (truncate the file)

So free never contains a duplicate, never contains an id >= pageCount, and never contains pageCount - 1.

db.commit(fl, meter) costs free.length + 1 units. After allocating 2,000 pages and releasing them all, 100 commits must cost exactly 100 units.

Observed: after the churn every commit costs 2,001 units and climbing.

Logs

[raft] commit took 38ms freelist=412,880 pages
[raft] commit took 51ms freelist=498,117 pages
[consul] leader election timed out; raft log append latency p99 9.2s

The code as shipped

src/raft/freelist.js (editable)

// Page allocator for the Raft log store. Page ids are 0..pageCount-1.
exports.create = function () {
  return { pageCount: 0, free: [] };
};

exports.allocate = function (fl) {
  if (fl.free.length > 0) {
    var best = 0;
    for (var i = 1; i < fl.free.length; i++) {
      if (fl.free[i] < fl.free[best]) best = i;
    }
    return fl.free.splice(best, 1)[0];
  }
  var id = fl.pageCount;
  fl.pageCount += 1;
  return id;
};

exports.release = function (fl, id) {
  fl.free.push(id);
};

Read-only context: src/raft/db.js.