Ledger | A lockless, append-only DataStore library

Ledger

badge-github badge-docs

What is this?

A datastore library for Roblox with no session locks. You never write state. You write down
the change you want, a function you own decides whether it is valid, and state is what falls
out of replaying those changes.

local Store = Ledger.New({
	Name = "PlayerData",
	Default = { Gold = 100, Items = {} },
	Reducer = function(State, Op)
		if Op.Kind == "SpendGold" then
			if Op.Amount > State.Gold then
				return nil -- refused, on every server, forever
			end
			local Next = table.clone(State)
			Next.Gold -= Op.Amount
			return Next
		end
		return nil
	end,
})

Store:Load(Player)
Store:Expect(Player):Apply("SpendGold", { Amount = 25 })

Two servers spend the same 100 gold, both writes land, the fold accepts one and refuses the
other. Every server agrees, every time.

A session lock serializes writers. A validating fold makes the invalid state unreachable,
which is a stronger guarantee that also costs nothing when a server crashes: no lease to wait
out, no locked player join stall, no side channel to touch someone offline or on another
server. Changes are ops with names, and a reducer validates them.

Features

  • Lock free | every server, same result, no locks
  • Cross server | write to any player, even offline
  • Entity stores | clans, listings, world records
  • Transfers | escrowed, deduped, self-healing
  • Transactions | all keys move or none do
  • Migrations | old servers can’t corrupt new data
  • Recovery | 30 days of history, auto cleanup
  • Idempotent | retries never apply twice
  • Once | receipts and webhooks land exactly once
  • Loud misuse | bad code throws, immediately

Installing

Wally

[server-dependencies]
Ledger = "xoifaii/ledger@4.0.6"

Model file: insert the Ledger module anywhere server side.

License

This project is licensed under the MIT License.

10 Likes

This is an interesting concept, but I do have one concern. Wouldn’t a user’s log grow endlessly as they keep playing? The longer the game is released, the larger every user’s data becomes, which can get out of hand quickly.

No, it doesnt grow forever, it compacts. A key just holds your current snapshot (your state, same size as any normal document store) plus the few ops since the last one. Once it hits ~128 ops or ~1mb those fold back into the snapshot and the log goes short again.

The only thing that could pile up over time is the set of delivered transfer ids used for dedup. That wasnt bounded before, but with non player stores (a clan bank taking thousands of transfers on one key) it could creep toward the 4mb limit, so its now pruned to a 30 day window. nothing resolves a transfer later than that anyway.

So its a snapshot plus a short tail, never the whole history.

2 Likes

Are there any plans to support MockDataStoreService? I usually work on offline .rbxl places that haven’t been published, thus making access to DataStore impossible.

Anyway, I think I might switch over from Lyra to this. The method used for updating data (via reducer) is something I heavily prefer as someone who’s used to Rodux/Reflex. :eyes: Though without mocking it is kinda difficult to actually test anything…

1 Like

As of writing this im updating my tests to use mock db that you can toggle lol, be out in a few hours (hopefully)

Been making a deterministic simulator that lets me test a bunch of different scenarios (millions/s) to catch bugs and i can reproduce them by just using a seed hence deterministic

found bugs that only appeared after thousands of operations in a specific order that no amount of normal testing would have found

1 Like

great post i’ll definitely try this out in my games.

1 Like

A (untested) community made Reducer by cattalicic:

--!strict

local PARENT = "__parent"
local NAME = "__name"

type GeneratedContext = {
	Tree: { string },
	Args: { any },
}

local Chain = {}
Chain.prototype = {}

local function assembleTree(sender: any, tree: { string }): { string }
	local parent = rawget(sender, PARENT)
	local name = rawget(sender, NAME)
	if name then
		table.insert(tree, 1, name)
	end
	if parent then
		return assembleTree(parent, tree)
	end
	return tree
end

local function getRoot(sender: any): any
	local parent = rawget(sender, PARENT)
	if parent then
		return getRoot(parent)
	end
	return sender
end

function Chain.prototype:__index(key: string)
	return Chain.new(nil, self, key)
end

function Chain.new(callback: ((GeneratedContext) -> any)?, parent: any?, name: string?)
	return setmetatable({
		[NAME] = name,
		[PARENT] = parent,
		__callback = callback,
	}, Chain.prototype)
end

function Chain.prototype:__call(...)
	local root = getRoot(self)
	local callback = rawget(root, "__callback") :: ((GeneratedContext) -> any)?
	if not callback then
		error("LedgerOps: chain called without a root callback -- did you call Define() correctly?")
	end
	return callback({ Tree = assembleTree(self, {}), Args = { ... } })
end

function Chain.prototype:__tostring()
	return `Op<{table.concat(assembleTree(self, {}), ".")}>`
end

function Chain.prototype:__newindex()
	error("LedgerOps: cannot assign into an op namespace")
end

function Chain.prototype:__iter()
	error("LedgerOps: cannot iterate an op namespace, call a leaf op instead")
end

export type FieldType = "number" | "string" | "boolean" | "table" | "any"
export type Validator = (value: any) -> boolean
export type FieldSpec = { [string]: FieldType | Validator }

export type Leaf = {
	__isLeaf: true,
	Fields: FieldSpec,
}

export type SchemaNode = Leaf | { [string]: SchemaNode }
export type Schema = { [string]: SchemaNode }

export type OpDescriptor = {
	Kind: string,
	Fields: { [string]: any },
}

local LedgerOps = {}

--[=[
	Marks a table as a real op kind (a "leaf") rather than a namespace level.
	Usage:
		LedgerOps.Define({
			SpendGold = LedgerOps.Leaf({ Amount = "number" }),
			Pets = {
				Fuse = LedgerOps.Leaf({ PetIds = "table", PetId = "string" }),
			},
		})
--]=]
function LedgerOps.Leaf(fields: FieldSpec): Leaf
	return { __isLeaf = true, Fields = fields }
end

local function checkType(value: any, spec: FieldType | Validator): (boolean, string?)
	if type(spec) == "function" then
		-- `type(spec) == "function"` refines `spec` to the Validator arm of the
		-- union right here, so no manual cast is needed (see Luau's docs on
		-- type refinements: type guards narrow lvalues on the checked branch).
		if not spec(value) then
			return false, "failed its validator"
		end
		return true
	end
	if spec == "any" then
		return true
	end
	if type(value) ~= spec then
		return false, `expected {spec}, got {type(value)}`
	end
	return true
end

local function findLeaf(schema: Schema, tree: { string }): Leaf?
	local node: SchemaNode = schema :: any
	for _, key in tree do
		if type(node) ~= "table" then
			return nil
		end
		local nextNode = (node :: any)[key]
		if nextNode == nil then
			return nil
		end
		node = nextNode
	end
	-- SchemaNode = Leaf | { [string]: SchemaNode } isn't a clean tagged union
	-- (per Luau's docs: a tagged union needs a differently-typed discriminant
	-- shared across every arm) -- the indexer arm can also resolve .__isLeaf,
	-- just typed SchemaNode? instead of the literal `true` Leaf has. So this
	-- stays an explicit cast rather than a refined narrow; it's not provably
	-- removable without running luau-analyze against it directly.
	if type(node) == "table" and (node :: any).__isLeaf then
		return node :: any
	end
	return nil
end

local function resolve(schema: Schema, tree: { string }, args: { any }): OpDescriptor
	local path = table.concat(tree, ".")
	local leaf = findLeaf(schema, tree)
	if not leaf then
		error(`LedgerOps: '{path}' is not a defined op kind`)
	end

	local fields = args[1]
	if fields ~= nil and type(fields) ~= "table" then
		error(`LedgerOps: '{path}' expects a Fields table, got {type(fields)}`)
	end
	fields = fields or {}

	for fieldName, spec in leaf.Fields do
		local ok, why = checkType((fields :: any)[fieldName], spec)
		if not ok then
			error(`LedgerOps: '{path}' field '{fieldName}' {why}`)
		end
	end

	return { Kind = path, Fields = fields :: any }
end

--[=[
	Builds a chainable namespace of op constructors from a schema. Calling a
	leaf returns a plain { Kind, Fields } descriptor -- it does not touch
	Ledger at all, so these are cheap to build, test, and pass around.
--]=]
function LedgerOps.Define(schema: Schema): any
	return Chain.new(function(context: GeneratedContext): OpDescriptor
		return resolve(schema, context.Tree, context.Args)
	end)
end

--[=[
	Same as Define, but calling a leaf commits it immediately against a live
	Session or Store instead of just building a descriptor.
		local Ops = LedgerOps.Bind(Schema, Session)
		Ops.SpendGold({ Amount = 50 }):Wait()
--]=]
function LedgerOps.Bind(schema: Schema, target: { Commit: (any, string, any) -> any }): any
	return Chain.new(function(context: GeneratedContext)
		local descriptor = resolve(schema, context.Tree, context.Args)
		return target:Commit(descriptor.Kind, descriptor.Fields)
	end)
end

--[=[
	Turns a descriptor into a Tx leg table, filling in the target key.
		Store:Tx(`trade:{id}`, {
			LedgerOps.LegOf(Ops.SpendGold({ Amount = 500 }), { UserId = Buyer }),
			LedgerOps.LegOf(Ops.GiveItem({ Item = "Sword" }), { UserId = Seller }),
		})
--]=]
function LedgerOps.LegOf(
	descriptor: OpDescriptor,
	target: { UserId: number?, Key: string?, Store: any? }
): { UserId: number?, Key: string?, Store: any?, Kind: string, Fields: any }
	return {
		UserId = target.UserId,
		Key = target.Key,
		Store = target.Store,
		Kind = descriptor.Kind,
		Fields = descriptor.Fields,
	}
end

return LedgerOps