jonnifyelixir
F4 / F4.12 / grow

F4.12 · part 1 of 3 · put & partition

Watch a branded CHAMP grow

The store starts empty. Each put takes a branded id, reads its three-letter namespace, and drops the entry into that namespace’s partition — creating the partition the first time a namespace appears, and adding to its CHAMP every time after. No entry ever lands in the wrong partition, because the namespace that decides where it goes is part of the key itself.

Ten entities, inserted in order. Step through the inserts and watch the partitions appear and fill as each key routes itself by namespace.

Insert and route Advanced: put, and the 33rd entry

Insert and route

The same ten keys go in every time; what changes is how far through the sequence you are. Each key’s prefix — USR, SES, LSN, PGE — picks its partition. Step through the inserts.

Keys inserted · select a checkpoint

%{namespace => CHAMP} 10 entries · 4 partitions 

      

      
inserted: 10

      
partitions: 4

    

    
The store grows by partition. A key never has to be told where it belongs; its namespace routes
      it, and a partition springs into being the first time its namespace is seen.

  


  

    
Advanced: put, and the 33rd entry

    

      
put/2 is two steps: take the three-character prefix, then update that one
        partition. update_in with a default creates the partition’s CHAMP on first use
        and adds to it thereafter, and because each partition is an immutable CHAMP the write returns a new store map
        that shares every partition it did not touch — so the cost of a write is one partition’s path-copy,
        not a copy of the store.

      
Inside a partition, the CHAMP’s root node holds up to thirty-two entries directly, one per slot of its
        five-bit bitmap. The thirty-third entry to collide into a slot forces that slot to become a child node —
        a second level — and the depth a lookup walks is ceil(log₃₂ n): one
        level to thirty-two entries, two to about a thousand, three to about thirty thousand. The partitions in the
        demo hold a handful each, so each is a single level; the restructure is what keeps a partition shallow as it
        scales into the thousands.

    

    
# put/2 — route on the prefix, update one partition's CHAMP
def handle_call({:put, id, value}, _from, store) do
  ns = binary_part(id, 0, 3)                    # "USR0Nb..." -> "USR"
  store =
    update_in(store[ns], fn
      nil   -> Champ.new() |> Champ.put(id, value)  # first key of a namespace
      champ -> Champ.put(champ, id, value)             # add to the partition
    end)
  {:reply, :ok, store}                          # new store shares untouched partitions
end

    

      

        
a branded key

        
put("LSN0Nb...", v) — the namespace is in the key.

      

      
      

        
routed into its partition

        
The prefix selects the CHAMP; only that partition is rebuilt, the rest shared.

      

    

    
Next: a Snowflake registry
      — now that entries are in their partitions, resolving any id back to its entry and its creation time.

  


  

    
References

    
Primary sources for this lab, and the lessons it assembles.

    

      
Sources

      
      
Related in this course