Turkey Belongs to Two Worlds

The Noiseless post said my Rails-named gems wait out a battle quarantine before they reach RubyGems. dag_me has no Rails name, and the gem skipped quarantine. The pattern inside it didn’t: I’ve run it in supply chain software for years, where bills of materials and supply links are DAGs whether the schema admits it or not.

The FAQ¶

closure_tree has a FAQ at the bottom of its README. Matthew McEachen started the gem in May 2011, two weeks before Twitter bought his startup, AdGrok, and he kept maintaining it after he joined Twitter. He wrote the FAQ in September 2012, and for fourteen years this entry read:

Does this gem support multiple parents?

No. This gem’s API is based on the assumption that each node has either 0 or 1 parent.

The underlying closure tree structure will support multiple parents, but there would be many breaking-API changes to support it. I’m open to suggestions and pull requests.

I’ve been committing to closure_tree since 2014. When I started, Matthew told me the closure table was the algorithm Twitter used internally. In 2016 he mentioned in an issue that he had built Twitter’s ads system four years earlier. acts_as_tree is easier to set up, with one table and a parent_id. The closure table costs a second table and pays it back on every read, and I’ll take the better algorithm over the easier setup.

The answer is still no, and I agree with it. closure_tree’s API gives every node a single parent and a single root. With a second parent, root can have more than one answer, and hash_tree has to repeat every shared subtree under each parent. Changing that breaks every app that already calls those methods.

So the yes is a second gem in the same organization. A tree stays on closure_tree. When the hierarchy stops being a tree, it moves to dag_me. Take a plan to rewrite an app in Rust:

flowchart TD
    subgraph tree ["closure_tree: one parent per node"]
        direction TB
        t_plan[the plan] --> t_announce[announce the rewrite] & t_read[read the old code]
        t_announce --> t_learn[learn Rust] & t_tokens[get unlimited tokens]
    end
    subgraph dag ["dag_me: as many parents as the data has"]
        direction TB
        d_announce[announce the rewrite] --> d_learn[learn Rust] & d_tokens[get unlimited tokens]
        d_learn --> d_rewrite[rewrite]
        d_tokens --> d_rewrite
        d_read[read the old code] --> d_rewrite
        d_rewrite --> d_post["blog post: 10x faster"]
        d_tokens --> d_post
    end

The tree has no place for the rewrite, which needs three parents. The DAG waits for all three, and the blog post has two parents of its own: the rewrite and the tokens.

Setup¶

bundle add dag_me
bin/rails generate dag_me:migration Step
bin/rails db:migrate

# config/application.rb: the graph lives in triggers and functions, which schema.rb can't hold
config.active_record.schema_format = :sql

# app/models/step.rb
class Step < ApplicationRecord
  dag_me
end

The migration installs two tables and the triggers that maintain them. One table holds the edges, the other every ancestor and descendant pair, so reads never recurse.

dag_me supports one database, PostgreSQL 18.

Why 18? Nothing in dag_me checks the server version. I installed 0.5.0 on PostgreSQL 12.22 and everything I tried worked, from cycle rejection to deletes. So technically dag_me runs on a database that got its last release in November 2024. I’d rather promote it as modern than as something that also runs on MS Access.

PostgreSQL is also learning graphs. SQL/PGQ, the SQL standard’s property graph queries, went into the PostgreSQL 19 development tree in March, and it was pulled from the release in September. When it comes back, dag_me will use it. Requiring 18 gives people a goal: upgrade, or stay behind.

A country on two continents¶

In closure_tree, Turkey has to pick a continent. So does Russia, and the Soviets already landed on this blog.

flowchart TD
    Europe --> Turkey & Russia
    Asia --> Turkey & Russia
    Turkey --> Istanbul
    Russia --> red_square["Red Square"] --> room_307["Room 307"]

The usual workaround is a hack: a second Russia row, or a join table the tree knows nothing about. dag_me needs no special military database operation. Russia gets one more add_parent:

turkey.add_parent(europe)
turkey.add_parent(asia)
russia.add_parent(europe)
russia.add_parent(asia)
istanbul.add_parent(turkey)
red_square.add_parent(russia)
room_307.add_parent(red_square)

russia.parents.order(:name).pluck(:name)                             # => ["Asia", "Europe"]
europe.children.where(id: asia.children).order(:name).pluck(:name)   # => ["Russia", "Turkey"]
room_307.ancestors.order(:name).pluck(:name)                         # => ["Asia", "Europe", "Red Square", "Russia"]
europe.ancestor_of?(istanbul)                                        # => true
Region.roots.order(:name).pluck(:name)                               # => ["Asia", "Europe"]

europe.add_parent(room_307)                                          # raises DagMe::CycleError

ancestors and descendants return relations, so they compose with the rest of ActiveRecord.

Rewrite mayhem¶

This year everything got rewritten in Rust. Bun left Zig in May, with a million lines in one pull request. HEY’s backend is leaving Ruby, as DHH announced at Rails World. I moved Kaunta off Go myself. TerminalTextEffects went from Python to Rust as ttfx, and then DHH had an agent rewrite the Rust in x86-64 assembly.

flowchart TD
    Python -->|ttfx| Rust
    Ruby -->|HEY| Rust
    Zig -->|Bun| Rust
    Go -->|Kaunta| Rust
    Rust -->|ttfx, again| asm["x86-64 assembly"]

Rust has more parents than Turkey has continents:

rust.parents.order(:name).pluck(:name)          # => ["Go", "Python", "Ruby", "Zig"]
assembly.ancestors.order(:name).pluck(:name)    # => ["Go", "Python", "Ruby", "Rust", "Zig"]
Language.leaves.pluck(:name)                    # => ["x86-64 assembly"]

ruby.add_parent(assembly)                       # raises DagMe::CycleError

The one rewrite dag_me refuses is the assembly back into Ruby. Somebody will try.

What blocks the blog post¶

The DAG in the first diagram is a rewrite plan. Each step waits for its parents.

Step.topologically.pluck(:name)
# => ["announce", "read_old_code", "learn_rust", "get_tokens", "rewrite", "blog_post"]

announce.update!(status: "done")
learn_rust.update!(status: "done")

# What stands between us and the blog post?
blog_post.ancestors.where.not(status: "done").order(:name).pluck(:name)
# => ["get_tokens", "read_old_code", "rewrite"]

# What can start right now?
Step.where(status: "pending").order(:id)
    .select { |step| step.parents.where.not(status: "done").none? }
    .map(&:name)
# => ["read_old_code", "get_tokens"]

# Every step on some path from the announcement to the blog post
Step.dag.between(announce, blog_post).topologically.pluck(:name)
# => ["announce", "learn_rust", "get_tokens", "rewrite", "blog_post"]

Reading the old code sits on no path from the announcement to the blog post. It’s a parent of the rewrite, and nobody has started it.

topologically puts every step after all of its parents, and it composes with any relation:

blog_post.self_and_ancestors.where.not(status: "done").topologically.pluck(:name)
# => ["read_old_code", "get_tokens", "rewrite", "blog_post"]

Two writers¶

A graph stays acyclic if you check one thing before inserting an edge from a to b: that b can’t already reach a.

closure_tree also has to work on MySQL and SQLite, so it maintains its tree in Ruby callbacks under with_advisory_lock. Its README is honest about what that costs. Turn the lock off while writing from several threads, and “you will eventually have data corruption.” On SQLite, which has no advisory locks, the gem falls back to lock files, “which will only work if the FLOCK_DIR is set consistently for all ruby processes.”

Every ActiveRecord DAG gem I read runs the cycle check in Ruby. It’s a validation or a query before the insert. Here is the pattern, reduced to its core:

def add_edge(parent_id, child_id)
  transaction do
    raise CycleError if reaches?(child_id, parent_id)  # WITH RECURSIVE walk over the edges
    insert_edge(parent_id, child_id)
  end
end

Run it one call after another and it works: a -> b commits, and b -> a is rejected. Then I ran a -> b and b -> a at the same moment from two threads, 200 times. Both edges committed in 179 of the 200 rounds:

sequenceDiagram
    participant A as Writer A
    participant DB as PostgreSQL
    participant B as Writer B
    A->>DB: does b reach a? no
    B->>DB: does a reach b? no
    A->>DB: INSERT a → b, COMMIT
    B->>DB: INSERT b → a, COMMIT
    Note over DB: a → b → a

Neither transaction sees the other’s edge until it commits, so both checks find no path.

dag_me runs the check in a PostgreSQL trigger on the edges table. The trigger takes the graph’s lock itself, so no caller can skip it. The second writer waits until the first commits, then checks against the edge that just landed:

sequenceDiagram
    participant A as Writer A
    participant DB as PostgreSQL
    participant B as Writer B
    A->>DB: INSERT a → b (takes the graph lock)
    B->>DB: INSERT b → a (waits for the lock)
    A->>DB: COMMIT
    Note over DB: B's check now sees a → b
    DB-->>B: DagMe::CycleError

Same race, 200 rounds: one edge committed and the other raised DagMe::CycleError every time. From Ruby it’s an exception like any other:

begin
  b.add_child(a)
rescue DagMe::CycleError
  # the database refused the edge
end

Step.transaction(isolation: :repeatable_read) { a.add_child(b) }
# raises DagMe::IsolationError: the check has to see what the last writer committed

Since it’s a trigger, it fires for every writer that leaves triggers on. insert_all skips your model callbacks, and it still hits the trigger. So does a raw INSERT typed into psql at 3 a.m. Rails fixtures turn triggers off, which is what rebuild! is for.

Org charts lie¶

A developer reports to an engineering manager and a product lead. A staff engineer outside both lines mentors them. One model can carry several graphs, and scope: keeps each company in its own:

class Person < ApplicationRecord
  dag_me :reports, scope: :company_id
  dag_me :mentorship, scope: :company_id
end

dev.add_parent(eng_manager, dag: :reports)
dev.add_parent(product_lead, dag: :reports)
dev.add_parent(staff_engineer, dag: :mentorship)

dev.reports_parents.order(:name).pluck(:name)      # => ["eng_manager", "product_lead"]
dev.mentorship_parents.pluck(:name)                # => ["staff_engineer"]
cto.ancestor_of?(dev, dag: :reports)               # => true
cto.ancestor_of?(dev, dag: :mentorship)            # => false

dev.add_parent(rival_cto, dag: :reports)           # raises DagMe::ScopeError

flowchart TD
    subgraph reports ["dag_me :reports"]
        cto[CTO] --> eng[eng manager]
        cpo[CPO] --> lead[product lead]
        eng --> dev1[dev]
        lead --> dev1
    end
    subgraph mentorship ["dag_me :mentorship"]
        staff[staff engineer] --> dev2[dev]
    end

Each named graph gets its own tables and its own cycle check. The company comes from the node rows, so even raw SQL can’t draw an edge between two companies.

Counting paths¶

For every pair, the closure stores how many distinct paths connect them and how long the shortest one is. The announcement reaches the blog post three ways:

flowchart LR
    announce --> learn_rust --> rewrite --> blog_post
    announce --> get_tokens --> rewrite
    get_tokens --> blog_post

path = Step::DagPath.find_by(ancestor_id: announce.id, descendant_id: blog_post.id)
path.path_count.to_i   # => 3
path.min_depth         # => 2

The shortest path from announcing a rewrite to the blog post about it is two steps, and neither of them is the rewrite. Make the blog post wait for the rewrite:

get_tokens.remove_child(blog_post)
path.reload
path.path_count.to_i   # => 2
path.min_depth         # => 3

The count is what makes deletes exact. When an edge goes, the paths through it are subtracted, and a pair disappears only when its count reaches zero.

The counts grow fast. I chained 64 diamonds, each one’s bottom being the next one’s top. That’s 193 nodes and 256 edges, and the path count from the first node to the last is 18,446,744,073,709,551,616, which is 2^64. PostgreSQL’s bigint stops at 9,223,372,036,854,775,807, so the column is numeric, and the count stays exact.

Closure or CTE¶

The closure is a trade, and dag_me lets you refuse it:

class Maneuver < ApplicationRecord
  dag_me maintain: :recursive_cte   # edges only, walked with WITH RECURSIVE at read time
end

The API stays the same, and the cycle check stays in a trigger either way. I built the same graph in both modes on my workstation: 20 layers of 50 nodes, each node with three random parents in the layer above. The closure for it holds 337,198 rows.

Reads get 6 to 42 times faster. No Rust required: PostgreSQL is written in C, from code no LLM can hallucinate. Ruby just waits for the reply.

A write in the middle of a dense graph touches every pair it connects, so it takes hundreds of milliseconds instead of a dozen or less. Other writers to that graph wait for it. Most hierarchies are read far more often than they change, so the closure is the default. A graph that changes all day belongs on the CTE.

Checking itself¶

Step.dag.validate   # => [] when the closure matches the edges
Step.dag.valid?     # => true
Step.dag.rebuild!   # after a bulk import that skipped the triggers

validate recomputes the closure from the edges without walking paths one by one, so the 2^64 chain checks in 0.04 seconds. bin/rails dag_me:status runs it for every graph in the app, and the gem ships Minitest assertions for yours:

class RewritePlanTest < ActiveSupport::TestCase
  include DagMe::TestHelper

  setup { Step.dag.rebuild! }   # fixtures load with triggers off

  test "the rewrite plan is a healthy DAG" do
    assert_dag_valid Step
    assert_dag_reachable steps(:announce), steps(:blog_post)
    assert_topological_order Step, Step.topologically.to_a
  end
end

The gem’s own suite calls validate after every random insert and delete it throws at the graph.

From pattern to gem¶

For years the pattern lived inside each app, wired by hand. Then I moved about ten applications onto dag_me, and the same fixes kept coming back. Two of them became options:

class Station < ApplicationRecord
  self.table_name = "orbital.stations"   # node tables in a named schema
  dag_me
end

class MaterialTracking::ProductBillOfMaterial < ApplicationRecord
  dag_me prefix: "bom_dag"   # generated names past PostgreSQL's 63 bytes
end

When the same fix shows up in every app, it belongs in the gem. That’s why you build a framework.

In the first app, the graphs that moved were workflow steps with their prerequisites, where the database used to stop a step from depending on itself and nothing more, and the geography from the Turkey example. Some of those models came off closure_tree, and most of that app’s hierarchies still use it.

Next is ActiveMatrix, the Rails-native Matrix SDK I maintain. In Matrix, a room’s history is a DAG. The spec says the prev_events field of an event “identifies the ‘parents’ of the event”, linking the room’s events “into a Directed Acyclic Graph (DAG)”. When two servers post at the same moment, the next event lists both of their events as parents:

flowchart LR
    create["m.room.create"] --> hello["alice: hello"]
    hello --> bob["bob, on server A"]
    hello --> carol["carol, on server B"]
    bob --> next["alice: welcome, both of you"]
    carol --> next

Management Engine¶

Directed Acyclic Graph Management Engine. Like the Intel Management Engine, it runs below your application with privileges you can’t revoke. Unlike it, you asked for it, and the only ring it operates in is pg_advisory_xact_lock.

It’s also the macro. A model that wants to be a graph says dag_me.

Still no¶

closure_tree’s FAQ still answers no. The invitation for pull requests is gone. The answer now links to dag_me, and so does a note at the top of the README.

dag_me supports one database, because the cycle check has to run where the writes land.