Hi everyone,
I’d like to share a Go library I’ve built called go-lrutree. It’s a small, thread-safe, generic cache designed specifically for tree-structured data.
The Problem It Solves:
Popular LRU cache implementations (like hashicorp/golang-lru) work well for flat key-value pairs.
But when you’re working with hierarchical data - think org charts, file paths, category trees, or geo-locations - flat caching can fall short.
For example: if you cache a city, you likely want its state and country to remain cached too. But traditional LRU eviction might evict a parent while children remain, breaking the logical structure.
go-lrutree solves this by enforcing the rule: if a node is in the cache, all its ancestors are too. When you access a node, its entire ancestry is marked as recently used — keeping the chain intact and eviction-safe.
Usage Example:
package main
import (
"fmt"
"github.com/vasayxtx/go-lrutree"
)
type OrgItem struct {
Name string
}
func main() {
// Create a new cache with a maximum size of 4 entries and an eviction callback.
cache := lrutree.NewCache[string, OrgItem](4, lrutree.WithOnEvict(func(node lrutree.CacheNode[string, OrgItem]) {
fmt.Printf("Evicted: %s (key=%s, parent=%s)\n", node.Value.Name, node.Key, node.ParentKey)
}))
// Add nodes to the cache.
_ = cache.AddRoot("company", OrgItem{"My Company"})
_ = cache.Add("engineering", OrgItem{"Engineering department"}, "company")
_ = cache.Add("frontend", OrgItem{"Frontend team"}, "engineering")
_ = cache.Add("backend", OrgItem{"Backend team"}, "engineering")
// Get the value by key.
// "frontend" node and all its ancestors ("engineering" and "company" nodes) are marked as recently used.
if cacheNode, ok := cache.Get("frontend"); ok {
fmt.Printf("Get: %s (key=%s, parent=%s)\n", cacheNode.Value.Name, cacheNode.Key, cacheNode.ParentKey)
// Output: Get: Frontend team (key=frontend, parent=engineering)
}
// Get the full branch from the root to the node with key "backend".
// "backend", "engineering", and "company" nodes are marked as recently used.
branch := cache.GetBranch("backend")
for i, node := range branch {
fmt.Printf("GetBranch[%d]: %s (key=%s, parent=%s)\n", i, node.Value.Name, node.Key, node.ParentKey)
}
// Output:
// GetBranch[0]: My Company (key=company, parent=)
// GetBranch[1]: Engineering department (key=engineering, parent=company)
// GetBranch[2]: Backend team (key=backend, parent=engineering)
// Peek the value by key without updating the LRU order.
if cacheNode, ok := cache.Peek("frontend"); ok {
fmt.Printf("Peek: %s (key=%s, parent=%s)\n", cacheNode.Value.Name, cacheNode.Key, cacheNode.ParentKey)
// Output: Peek: Frontend team (key=frontend, parent=engineering)
}
// Add a new node exceeding the cache's maximum size.
// The least recently used leaf node ("frontend") is evicted.
_ = cache.Add("architects", OrgItem{"Architects team"}, "engineering")
// Output: Evicted: Frontend team (key=frontend, parent=engineering)
}
Looking for Feedback!
I’d love to hear from the Go community:
- Does this hierarchical caching concept resonate with you? Can you envision use cases for it?
- Any feedback on the API design or the implementation approach?
- Suggestions for improvements or features?
Thanks for checking it out!