jonnifyelixir
F4 / F4.09 / trie

F4.09 · part 2 of 3 · progress snapshots

Structural sharing

Inside a partition, the CHAMP is a trie keyed on the lesson’s Snowflake. Portal.Progress tracks which lessons a user has finished, and marking one complete does not mutate the map — it returns a new one that shares every sub-tree except the path to the lesson that changed. The previous snapshot stays intact and valid, so a history of progress, and a cheap diff between any two points, comes for free.

A progress trie of four lessons. Mark one complete and watch which nodes are copied and which the new snapshot shares with the old — counted from the tree itself.

Copy one path, share the rest Advanced: snapshots and diffs for free

Copy one path, share the rest

The four lessons sit two levels down, under two sub-nodes. Marking one complete copies the root, the one sub-node on its path, and that leaf; everything else is the same memory the old snapshot points at. Select the lesson to mark complete.

Mark complete · select one

root n0 n1 L1 L2 L3 L4 copied shared marking L1 complete copies 3 nodes and shares 4 

      

      
copied: 3 nodes (the path)

      
shared: 4 nodes

    

    
One update touches one path. The new snapshot is the copied path plus pointers into the old tree,
      so it costs a few nodes — and the old snapshot is untouched, still a valid map.

  


  

    
Advanced: snapshots and diffs for free

    

      
Because complete/2 returns a new root and leaves the old one intact, holding onto a
        root is a snapshot. “What had this user finished on Tuesday?” is answered by keeping
        Tuesday’s root — no copy, no log table, only a pointer to a tree that shares almost everything with
        today’s. And a diff between two snapshots is cheap for the same reason CHAMP made equality cheap in
        F4.06: sub-trees shared by identity are equal without inspection, so a diff only descends the few nodes that
        actually differ.

      
The cost of an update is the depth of the trie, not its size: a path is copied, the rest is shared. For a
        partition of even millions of lessons that is a handful of nodes per complete/2, and
        any number of past snapshots can coexist, each sharing the bulk of its structure with its neighbours. This is
        the F4.05 path-copy property and the F4.06 canonical shape, put to work on a user’s progress.

    

    
# Portal.Progress.complete/2 returns a new snapshot; the old stays valid
v1 = Progress.complete(v0, "LSN0NbCMKoAopE")   # lesson 1 done
v2 = Progress.complete(v1, "LSN0NbD94T0Qtu")   # lesson 3 done

Progress.percent_complete(v0)   # the original snapshot, unchanged
Progress.diff(v1, v2)               # cheap: only the changed path is inspected

    

      

        
mark a lesson complete

        
A change to one key in the progress map.

      

      
      

        
a new snapshot, shared

        
The path is copied, the rest is shared; the old snapshot is still a valid map.

      

    

    
Next: own it with a
      GenServer — how the session store serializes writes and lets reads run lock-free.

  


  

    
References

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

    

      
Sources

      
      
Related in this course