Resource limits

Automerge input is deflated and run-length encoded, so its size says little about what loading it takes: a 4 kB compressed save of a 4,000,000-character text takes 390 MB and 4.3 s to load, a 113-byte change chunk can describe 10,000,000 operations (about 5 GB), and memory grows with what the input describes (see Input amplification measurements). Automerge allocates with the Rust global allocator, and a failed Rust allocation aborts the backend, after which the postmaster restarts every session of the cluster. Anyone who can write an automerge value can send such input (input functions are called without an EXECUTE check, so REVOKE does not help), and a single load cannot be cancelled. So every path that takes client bytes prices the load from what can be read cheaply, before Automerge allocates anything, and refuses it with an ERROR when the estimate exceeds a limit.

The pg_automerge.max_load_memory setting#

An integer in kB (like work_mem; SET pg_automerge.max_load_memory = '512MB'), 2 GB by default, -1 for no limit, superuser-only (PGC_SUSET, for the reason verify_writes is: one session with a higher limit can abort a backend, which restarts the cluster for everyone; a superuser can set it per role or database, or GRANT SET ON PARAMETER). Like verify_writes, only the library defines it: SHOW works once the library is loaded, and SET before that leaves a placeholder that Postgres checks when the library loads.

_PG_init reserves the pg_automerge prefix (MarkGUCPrefixReserved, which pgrx does not call): a misspelled name such as pg_automerge.max_load_memroy is an error (42602, "pg_automerge" is a reserved prefix.) once the library is loaded, and a placeholder set before it loaded (from postgresql.conf, ALTER SYSTEM, ALTER ROLE/DATABASE .. SET or a SET in the session) is removed with a WARNING when it loads. Without that, a typo was accepted silently and the real setting kept its default.

It bounds an estimate of the peak memory of one load (or merge), in bytes. One setting, not separate caps on operations, changes or actors: memory has a changes × actors term, and the same operation costs 5 to 10 times more as a bare change than inside a saved document, so separate caps would either let through what the estimate refuses or refuse ordinary documents.

The default admits about 4.4 million characters of plain text (whose real peak is about 0.4 GB: the estimate over-counts plain text about five times, see below); the tests' 3,000,000-character document estimates at 1.38 GB, so a 1 GB default would refuse it. Time follows the estimate at up to about 8 s per GB on the test machine (release build; the core test asserts it for every input of its battery when run with --release), so at the default an uncancellable load takes at most about 16 s, except for many marks applied as changes, whose time grows with the square of their number (see What the limit cannot do). A dev build (cargo pgrx install without --release) does not optimize the extension's own crates, and its scan is about ten times slower. Every session can use up to the limit at once (plus the stored documents a merge loads, which are not priced), so size it like work_mem. Every estimate includes 64 kB, so a limit of 64 kB or less refuses every write (the tests use it for that).

The limit decides whether a write can be refused; it never changes a result's bytes, so the functions stay IMMUTABLE, as with verify_writes (a plan folded under one setting may raise, or not, under another, like statement_timeout).

What is checked where#

Refusals are 53400 (configuration_limit_exceeded):

ERROR:  estimated memory to load automerge input exceeds "pg_automerge.max_load_memory" (2048 MB)
DETAIL:  Loading it could take up to 9537 MB (10000001 operations, 1 change, 1 actor, 123 bytes uncompressed).
HINT:  A superuser can raise "pg_automerge.max_load_memory".

with "merged automerge document" for a merge result ("Loading it"), "for applying automerge changes" for the changes a merge applies ("Applying them"), "Loading the document it normalizes to" in the DETAIL of an input whose normalized form is over the limit, and "at least" when the scan stopped early (below). The limit is shown in MB when it is a whole number of them, otherwise in kB.

Why 53400 and not 54000 (program_limit_exceeded): Postgres raises 53400 when temp_file_limit is exceeded, the closest analogue, a limit an administrator configures; 54000 is for fixed limits and stays for the jsonb and nesting limits of the jsonb view. Retrying does not help unless the limit is raised.

Bundle chunks (Automerge's experimental format that packs many changes into one chunk) in client input are refused with 0A000 (feature_not_supported) whatever the limit: pricing them would need a parser of their own, and Automerge does not write them unless asked to.

The estimate#

In bytes, saturating, from counts read from the chunks:

• A document chunk (a save, or the loaded document a merge result will be saved as): 450 per op + 30 per successor entry + 600 × Gmax + 1600 per change + min(130 × (ops + successors), 1600 × changes) + 200 per dependency entry + 200 per actor + 0.3 × changes × actors + 3 × min(changes, (ops + successors) / 16) × actors + 5 per rebuilt byte of messages and actor ids and 3 per rebuilt byte of keys and mark names (below) + 200 per extra column metadata entry (below).
• Change chunks, or changes about to be applied to a document with base changes and actors: 1000 per op + 80 per pred entry + 2500 per change + 200 per dependency + 200 per distinct actor + 100 per entry of a change's list of other actors (duplicates included) + 0.3 × (changes × (base actors + new actors) + base changes × new actors) + 8 per repeated byte (below) + 200 per extra column metadata entry.
• Plus 10 per byte of the chunks with their columns inflated, and 64 kB (Automerge's fixed structures, which the per-unit costs do not cover for tiny documents).

Rebuilt and repeated bytes. A load rebuilds every change of a document as a change chunk of its own, and applying changes turns their ops into Automerge's structures; both copy strings that the input may hold once for many rows, in a repeat run (n copies of a value, stored once). The scan computes what such runs expand to from their headers, without expanding them: a repeat run of n strings of len bytes expands to (n - 1) × len bytes beyond the input's own (literal values are input bytes, already charged 10 each).

• Rebuilt bytes of a document chunk: its change messages (every rebuilt change holds its message twice, in its bytes and as a String, and a load whose heads do not match clones every rebuilt change into its error: 4.0 bytes per byte measured, charged 5), its ops' mark names (3.0 bytes per byte measured, charged 5; priced with the keys at 3 until the neighbouring shapes were measured, see The estimate's neighbourhood), and the actor ids longer than the 16 bytes Automerge's ActorId holds inline (every rebuilt change holds its own actor and the other actors its ops refer to, in its bytes and as ActorIds: 4.0 bytes per byte measured, charged 5). A change's own actor is counted from the change actor column, run length × length; the others from the object and key actor columns, each run at most once per change (min(run length, changes) × length), plus three references of the longest actor per successor entry (the pred of a rebuilt op, or the delete Automerge rebuilds from it: its object, key and pred); a change holds every actor once at most, so its own and the others together are at most changes × the long actors' total length.
• Rebuilt key bytes of a document chunk: its ops' keys, which a rebuilt change holds once, in its bytes (2.0 bytes per byte measured with the error's clone, 1.6-1.7 for saves written by Automerge whose keys are overwritten many times; charged 3).
• Repeated bytes of changes: the keys and mark names of change chunks (importing a change's ops makes an owned String of every op's key and mark name, and the document holds a key literally wherever other keys come between its rows: 1.0 bytes per byte measured for one key, 2.0 for mark names, 4.0 for a key the document then holds literally, 5.9 with the save of the result that normalize makes; charged 8), and those of a document chunk turned into changes (its rebuilt bytes and rebuilt key bytes, which applying copies again: its keys can end up between the rows of the document they are applied to).

A load of input on its own is the first document chunk as a document plus everything after it as changes applied to it (Automerge turns a later document chunk into changes: it is charged both as a document and as its changes). Loading after a document (a ++ changes) or applying chunks to it charges every chunk of the input as changes, with the document as the base.

Extra column metadata entries. A chunk lists its columns in metadata blocks, an entry (spec, length) per column, and Automerge's parse keeps every entry in vectors that double as they fill (and copies the list as it checks the layout), while the entry of an empty column takes two input bytes: 5,000,000 of them made a 10 MB document chunk peak at 498 MB (it loaded) and a 9.7 kB compressed change chunk at 716 MB. Every entry beyond one per column Automerge writes (9 + 16 for a document chunk, 14 for a change chunk, which the per-op and per-change costs include) is charged 200: measured up to 120 per entry for a document chunk, 168 for a change chunk and 174 for a compressed one, at counts just past a power of two (4,200,000), where a doubling vector overshoots most.

For a merge result, the rebuilt bytes of the bound (see Merge results) add the bytes and the repeated bytes of the changes applied: a rebuilt change is the change that was applied, so this bounds what loading the result copies. It does not always bound what a scan of the saved result counts: the actor term is not additive (a run of the object actor column that new rows split counts up to min(run, changes) twice), so, like the bytes term, a result can be stored with a scanned estimate somewhat over the limit when its bound is under it; its load copies no more than the bound says.

The counts: ops are the largest row count of the known op columns (not the members of a group); Automerge sizes some allocations by one column's length before it checks the columns against each other, so the largest counts. Successors, preds and dependencies are the sums of their group columns (or the member columns' rows, if larger). Ops of every action are counted alike (deletes too; the flat 450 covers them). Actors of change chunks are counted by name, once each, for the 200 (and the clock-cache terms); besides, every entry of a change's list of other actors costs 100, duplicates included: Automerge's parse keeps one 32-byte ActorId per entry in a vector that doubles as it fills, and an entry (an empty actor id) takes one input byte, so a 10 kB compressed change listing 10,000,000 empty actors peaked at 627 MB while pricing them by name and bytes said 100 MB (measured up to 73 per entry; 100 leaves room for the old and new buffer of a growth step both being held). Dependencies (32 bytes each, 320 through the bytes) and heads already cost more per entry than their vectors take. Gmax is the largest number of successor entries in one (object, key) group of rows: a new group starts at the first row, at an insert row, when the object changes, or when the key changes and the previous row was not an insert (a key overwritten or deleted many times, which Automerge resolves with a pending queue per key).

The constants are the worst measured cost of each unit (the appendix); every generated and crafted input tried stays below the estimate, at most 0.80 of it (ops prepended to a list of maps; a document whose 2,000 changes share one 100 kB message or actor id). Known over-estimates: plain text about 5 times (appended characters cost about 90 bytes, the 450 per op is forced by out-of-order ops at about 335; a tighter bound would mean simulating Automerge's per-change reorder queue), and a key overwritten many times in one change about 10 times (Gmax cannot tell deletes from successors that are rows). The estimate is only as good as its measurements: upgrading Automerge means re-running crates/pg_automerge_core/tests/memory_bounds.rs and the fuzz harness (below), which check it.

So that an upgrade cannot skip that step, budget::MEASURED_AUTOMERGE (0.12.0) and budget::MEASURED_HEXANE (1.0.0-alpha.5) name the versions the constants were measured with, and a core test (the_cost_model_was_measured_for_this_automerge in tests/memory_bounds.rs, part of cargo test -p pg_automerge_core and so of mise run ci) reads Cargo.lock and fails on any other version with a message that says to re-measure the cost model and how. Hexane is Automerge's column store, where most of a load's memory goes; Automerge 0.12.0 requires ^1.0.0-alpha.5, so a cargo update can move it while Automerge (pinned with =0.12.0 in Cargo.toml) stays. To upgrade: change the pin, run cargo test --release -p pg_automerge_core --test memory_bounds -- --nocapture (peaks and ratios are printed per input; under ulimit -v, so that an estimate too low shows as a failed allocation rather than swapping) and mise run fuzz, raise the constants whose ratios are over the estimate or near it, update the tables here, then the two constants.

What the estimate covers#

Where a load or apply allocates in proportion to something the input describes, the term that prices it, and the worst peak / estimate of the inputs of tests/memory_bounds.rs (release build):

The rebuilt, repeated and extra-column terms were added after the load limit shipped (see Rebuilt copies and column metadata): before them, the same inputs peaked at 63 to 167 times their estimate (5 to 9 times for the metadata entries).

The scan#

pg_automerge_core::budget::scan_input reads the chunk headers, the actors and dependency lists, and the column metadata and data of every chunk:

• Deflated columns and compressed change chunks are inflated one at a time, and in total at most to a tenth of the limit: each inflated byte costs 10 in the estimate, so more than that exceeds it whatever else the input holds, and the scan stops there (a deflate bomb costs a tenth of the limit in scan memory, at most, and is reported "at least"). An uncompressed chunk is read in place.
• Columns are counted run by run, never expanded: a run of n values is one step whatever n is, and literal values are only stepped over, numbers by the last byte of each LEB128 value, eight bytes at a time, strings by their lengths. (An over-long number, at which Automerge's decoders stop, is stepped over like any other: for malformed input the scan can count more rows than Automerge reads, never fewer.) Decoding is lenient, as Automerge's streaming decoders are: a run that cannot be read ends the column.
• Gmax is first taken at its upper bound, the chunk's successor entries (0 when there are none). Only when that bound is what puts an estimate over the limit is the input scanned again with Gmax computed exactly: the object, key, insert and successor columns merged by runs (within a stretch where each is one run, the rows are either all groups of their own, being inserts or a key counter that changes every row, or all add to the current group). A property test checks it against the row-by-row definition. Documents far below the limit never pay for it (on the 877 kB list document the exact pass costs about as much as the rest of the scan).
• Column metadata is validated in place and read again entry by entry with the columns' data: nothing is allocated per entry. Only the columns the exact Gmax pass merges are held (the first of each spec; one listed twice makes Gmax its bound).
• The loops run the interrupt check (a cancel stops a scan), per run of a column and per entry of an actor list or a column metadata block.
• A change whose list of other actors is longer than the limit pays for (110 per entry, its byte and the 100) stops the scan before its entries are read, like a deflate bomb ("at least"): 20,000,000 empty actors deflate to 19 kB, and stepping through them would take seconds. So does a column metadata block whose extra entries alone exceed the limit (200 each): 12,000,000 empty columns deflate to 24 kB.
• It keeps every distinct actor id of change chunks (and of document chunks after the first) once, to count them by name: at most the input's bytes (each charged 10), so refusing input with many long actor ids costs up to its size (1 MB for 1,000 actor ids of 1 kB in a change chunk), still a small fraction of its estimate.
• It never fails. Framing it cannot parse (bad magic, lengths, column metadata, a column that does not inflate, an unknown chunk type) stops it with the counts of what came before, which is all Automerge can allocate before it fails on the same bytes (it parses a chunk completely before it reconstructs or applies it); the caller checks those and lets Automerge reject the input with its own message (22P02, as before). The fuzz harness checks that input Automerge loads is never taken for unparseable.

The same pass answers whether a single document chunk passes Automerge's chunk parse (header::document_parses, the condition of the no-op answers of merge(automerge, bytea) and automerge_contains), so those paths inflate a compressed save once, as before. A compressed save that is loaded (text or binary input, the bytea cast, merge(automerge, bytea) with a save loaded on its own) keeps the columns the scan inflated until the normalized save has been compared with them (see Invariants), so it is inflated twice, by the scan and by Automerge's load, as it was before the limit (by the load and by the comparison); what is held meanwhile is at most the inflated bytes, each charged 10 in the estimate, and they are held only once that estimate has been checked: merge(automerge, bytea) drops them before it loads a stored a to look for the heads of a save with no more changes than a (the save is priced only after that load, and may still be rejected), and without a limit nothing is kept (nothing charges them), the comparison inflates the input again. Without a limit, input and the bytea cast walk only the chunk types (for bundles), merges of documents count nothing, and merge(automerge, bytea) and automerge_contains(automerge, bytea) still scan the input (without a cap) for the parse check and the bundle check.

Merge results#

Each loaded document carries its counts (LoadedDoc, the merge_agg state): exact when scanned from a save (a stored value, the input it was loaded from), and for a merge result an upper bound, the target's counts plus the changes applied (ops and dependencies added, every pred a successor entry and possibly all on one key, so added to Gmax too, every actor possibly new, the bytes added). Only when that bound exceeds the limit is the result saved and scanned exactly, and refused if that is over too; the save is kept and becomes the value's stored bytes (after the check of verify_writes, for a result of client bytes). So PL/pgSQL chains and merge_agg pay no save per step, and a merge that stays well within the limit costs a scan of the changes applied (and of the stored target, to know its counts).

Consequences: merging two documents that each fit can fail with 53400 (the result would not), and so can merge_agg; repeated small writes cannot grow a document past the limit. The bytes term of the bound is an approximation (the merged columns may encode less compactly than the sum), so a result can be stored somewhat over the limit when its bound is just under it; every other term is an upper bound.

Stored values and lowering the limit#

Every stored value fit the limit when it was written (or was written with a higher limit, or none), and loading a stored value is never checked: reads peak at 1.0 to 1.5 times a load of the value, which was accepted when it was written. A separate ceiling for reads was considered and rejected: it would make data unreadable after the fact, which is worse than the memory the read takes. So lowering the limit never makes data unreadable, and writes that add nothing are not refused either: UPDATE .. SET doc = doc, merge(doc, doc), re-sent change chunks, an older save, and a re-sent uncompressed save (parsed in place) load nothing new. A re-sent compressed save costs its inflation (once), refused only when that alone exceeds a tenth of the limit.

What does get refused under a lower limit is writing such a value again as new input, which is what a restore does:

• Dump and restore: pg_restore, psql < dump and COPY FROM validate every value against the restoring session's limit. To restore documents written under a higher limit (or none), raise it for the restore: PGOPTIONS='-c pg_automerge.max_load_memory=-1' pg_restore ... as a superuser, or ALTER ROLE restorer SET pg_automerge.max_load_memory = ... beforehand.
• Logical replication: the subscriber validates every replicated value with the apply worker's setting; set it for the subscription's owner or the database (ALTER ROLE .. SET, ALTER DATABASE .. SET) at least as high as the publisher's, otherwise the apply worker fails on such a row and retries until the setting is fixed.

What the limit cannot do#

• Turn an allocation failure into an ERROR. std::alloc:: set_alloc_error_hook is unstable in Rust 1.98, a #[global_allocator] must not unwind, and allocating through palloc would longjmp over Automerge's frames on failure (or abort anyway). The estimate before the load is the only defence; memory beyond it (a bug in the estimate, an Automerge upgrade that costs more) still aborts.
• Bound what concurrent sessions take together (each can use up to the limit), or the stored documents a merge loads besides the changes it applies.
• Make a load cancellable; it bounds its length (about 8 s per GB of the estimate).
• Bound the time of applying many marks (open, found by the neighbouring-shapes round, see The estimate's neighbourhood). Applying changes whose mark ops overlap (marks of one text that are open at the same point, such as marks that all start after the same character) takes time quadratic in their number, and with different names also in proportion to the names' length: Automerge's MarkStateMachine (marks.rs) keeps the open marks in a vector it searches by name for every mark op, and clones the current mark set (Arc::make_mut) while it is shared. A 122-byte change chunk of 32,000 marks with one 8-byte name takes 3.1 s (estimate 33 MB: 96 s per GB); 8,000 marks with different 2 kB names (16 MB) take 16.5 s (estimate 161 MB); 1,000,000 marks, about 1 GB of estimate and within the default limit, would take about 50 minutes, uncancellable. The memory stays within the estimate (0.77 at most). Every path that applies changes is affected (merge(doc, changes), ||, merges of two documents and merge_agg that apply such changes, a later document chunk in the input); loading a save is not (4,000 overlapping marks with different names: 21 ms as a save, 222 ms as change chunks). Not priced because the cheap bound, the number of mark ops squared, would refuse ordinary rich text: a document with 100,000 marks that never overlap applies in linear time, and could then no longer be merged or sent as changes. The options are a quadratic term all the same (about 0.4 bytes per pair of mark ops in one apply refuses more than about 70,000 at the default limit), a cap on the mark ops of one apply, or a fix in Automerge.

Tests#

• crates/pg_automerge_core/tests/memory_bounds.rs: a counting allocator (per thread) measures the peak of every path (normalize of saves, compressed saves and change chunks, merge_changes, contains_changes, merge of two documents, the accumulator) on generated documents of every shape the estimate prices differently and on crafted chunks (RLE op, change, dependency, successor and pred bombs, many actors, change headers listing millions of empty or duplicate other actors and duplicate dependencies, plain and compressed, a save with 2,000 trailing change chunks, strings repeated by a run (change messages, keys, mark names; interleaved keys the document then holds literally), long actor ids, millions of empty column metadata entries; the crafted document chunks again with a made-up head, after another save and through merge_changes, where a load rebuilds and applies them (without heads it skips them as already contained); and the same strings and actor ids in saves written by Automerge, on their own and after another save, through normalize and merge_changes), and ordinary documents with long keys overwritten many times or 32-byte actor ids: at the limit set to the estimate the input is accepted (or refused by Automerge, for crafted input that does not load) with a peak below it; one byte lower it is refused before loading with a peak that is a small fraction of it; when the document an input normalizes to is priced higher than the input, normalize at the input's own estimate stays below it and refuses the result as the normalized document; merge_changes of the crafted inputs into a stored document stays below the two estimates. Also deflate bombs (256 MB of zeros, as a deflated column and as a compressed change chunk) refused quickly with a small peak, a 19 kB change listing 20,000,000 empty actors and a 24 kB one listing 12,000,000 empty columns refused at the default limit without their entries being read, the scan's counts against Automerge's stats() and its own change parser, Gmax against the row-by-row definition on random histories, merge results outgrowing the limit, the guarantees under a lowered limit, bundles, and the messages. The neighbouring shapes of the string and actor terms (see The estimate's neighbourhood), with the same checks: every string-valued column (document change messages, keys, mark names, string values and extra bytes; change-chunk keys, mark names, values, messages and extra bytes) as one repeat run, as different strings and as runs interleaved with literals, plain and deflated or compressed, as a document chunk, a change chunk and after another save (a crafted document chunk also with a made-up head); actor ids of 17 bytes, 1 kB and 100 kB from every actor column of a document chunk (change, op id, object, key, pred, successor, an actor table no op refers to) and of a change chunk (its own actor; another one its ops refer to by object, key or pred, after the long actor's document; many others no op refers to); each through merge_changes onto a stored document too; and the same columns and actor ids in documents written by Automerge, as saves, compressed saves and change chunks, on their own and after another save. Inputs with many marks are exempt from the time bound only (see What the limit cannot do). And a guard that fails when Cargo.lock has another Automerge or hexane than the cost model was measured with.
• The fuzz harness (tests/fuzz.rs): input Automerge loads is never marked unparseable by the scan, normalize's measured peak stays below the estimate whether Automerge accepts the input or refuses it, and it refuses input only when the estimate is over. Its seeds include change chunks with repeated header list entries, and small versions of the neighbouring shapes (strings interleaved with runs in document and change columns, extra bytes, a chain of change chunks with messages, long actor ids referred to by key and by pred).
• src/tests/limits.rs (pg_tests): the setting's default, unit and privileges; 53400 with its message, DETAIL and HINT on every SQL path (text input, COPY text and binary, the bytea cast, merge and || with a save, a compressed save and change chunks, PL/pgSQL, automerge_contains, a literal refused before decoding, a deflate bomb); merge results over the limit through merge, ||, merge_agg and a PL/pgSQL chain (whose variable survives the failed step); stored values readable and no-op writes accepted under a lowered limit; -1; bundles refused whatever the limit.
• tests/limits.sh (mise run limits, part of mise run test): a scratch cluster with its address space capped (ulimit -v, about 1 GB). With the limit off, the 12 kB compressed save of a 12,000,000-character text, a 113-byte crafted change chunk and a 19 kB compressed change chunk listing 20,000,000 empty other actors each abort the backend ("memory allocation of 1543503872 bytes failed", signal 6) and the cluster restarts, which shows the inputs and the cap reproduce the crash; so do a 1 kB compressed save of 6,000 changes sharing one 100 kB message, a 100 kB document chunk of 6,000 changes by a 100 kB actor id, a 100 kB change chunk of 16,000 puts of one 100 kB key, and a 24 kB compressed change chunk listing 12,000,000 empty columns. With the default limit, the same inputs through text input, the bytea cast, merge, ||, automerge_contains, INSERT and COPY get 53400 with DETAIL and HINT, no backend is terminated by a signal, a session opened before is still connected, pg_postmaster_start_time() is unchanged and ordinary writes work.
• tests/extension.sh: the setting stays superuser-only for a non-superuser database owner (as verify_writes).
• The pg_regress example shows the error.