jonnifyelixir
F4 · Algorithms & Data Structures / F4.09 · branded-champ

F4 · Persistent maps · module 9

Branded CHAMP maps & GenServer

One store, partitioned by namespace Three uses in the Portal Advanced: immutable reads, serialized writes

This module folds the chapter together. Take the compressed, canonical map of F4.06, key it on the branded Snowflakes of F4.07, partition it by the three-letter namespace, and own it from a GenServer. The result is an in-memory store the Portal uses everywhere: immutable, so reads need no lock; structurally shared, so a snapshot is cheap; and partitioned, so each kind of record lives in its own shallow sub-trie.

The Portal runs three of these stores, all the same shape. Route a record’s id and watch the namespace prefix send it to the right partition.

A GenServer owns a partitioned CHAMP

cast {:put, "USR0Nb…"} GenServer · Portal.Store one mailbox state: %{ns => CHAMP} USR CHAMP 1 entry USR0NbAb1x → SES CHAMP 0 entries %{} empty

USR: 1 entry · SES: empty
The 3-letter prefix routes a put to its partition — O(1).

One store, partitioned by namespace

The top level is a small map from a three-letter namespace to a CHAMP; each CHAMP holds one kind of record, keyed by the id’s 64-bit integer. A lookup reads the prefix, picks the partition, then descends that sub-trie. Select a record to route it.

Record · select one

lookup store.get("USR0NbAb1xcFCy") ↓ route by prefix USR CHAMP · users SES CHAMP · sessions LSN CHAMP · lessons PGE CHAMP · pages %User{email: "ada@portal.dev"} the USR prefix routes to the users partition 

      

      
partition: USR · users

      
created: —

    

    
One map of namespaces over many CHAMPs: the prefix routes in constant time, and each partition stays
      shallow because it holds one kind of key. The id you already have is the whole address.

  


  

    
Three uses in the Portal

    

      
The same store appears three times in the book’s running project, each leaning on a different one of
        its traits. Each is a deep dive.

    


    

      
        
F4.09.1 · the entity registry

        
Partition by namespace 

        
One store holds users, sessions, lessons, and pages at once; the USR/SES/LSN/PGE prefix picks the partition, so key spaces never collide and each sub-trie stays shallow.

      
      
        
F4.09.2 · progress snapshots

        
Structural sharing 

        
Marking a lesson complete copies one root-to-leaf path and shares the rest, so Portal.Progress keeps every prior snapshot for free and a diff is cheap.

      
      
        
F4.09.3 · the session store

        
Own it with a GenServer 

        
A GenServer owns writes and publishes each new snapshot; because the map is immutable, Portal.Auth.current_user/1 reads it lock-free on every request.

      
    

  


  

    
Advanced: immutable reads, serialized writes

    

      
A GenServer has one mailbox, so messages it handles are serialized — which is what you want for
        writes: put and delete go through it one at a time
        and each produces a new root. Reads are the opposite problem, and immutability solves it. The store publishes
        its current root (in :persistent_term or an ETS cell), and because a CHAMP is never
        mutated in place, any number of processes can traverse that root at once with no lock and no copy — a
        writer building the next snapshot cannot disturb a reader walking the last one.

      
Partitioning keeps each sub-trie shallow and lets a whole kind be snapshotted or evicted on its own; keying on
        the Snowflake means a partition is also time-ordered, so a range scan within it is the F4.08 query in memory.
        The structural sharing of F4.05 and F4.06 is what makes the published snapshots affordable: each new root
        shares almost every sub-tree with the one before it.

    

    
# the store: a map of namespace -> CHAMP, owned by a GenServer
defmodule Portal.Store do
  use GenServer

  def get("USR" <> _ = id), do: lookup(:USR, id)   # lock-free read of the published root
  def put(id, value), do: GenServer.call(__MODULE__, {:put, id, value})  # serialized write

  def handle_call({:put, id, v}, _from, parts) do
    parts = Map.update!(parts, ns(id), &Champ.put(&1, id, v))  # new snapshot, shared
    publish(parts); {:reply, :ok, parts}
  end
end

    

      

        
F4.06 + F4.07 + F4.08

        
A compressed map, a branded id key, and a persistence story.

      

      
      

        
F4.09 · the live store

        
One partitioned, immutable CHAMP behind a GenServer — the Portal’s in-memory state.

      

    

    
Start with partition by namespace, then
      structural sharing, then
      own it with a GenServer. Predecessor:
      F4.08 — Branded ids & persistence. Next
      module: F4.10 — Practical recipes in Elixir, which turns these structures
      into everyday patterns.

  


  

    
References

    
Primary sources for this lesson, and where it connects in the course.

    

      
Sources

      
      
Related in this course