I'm confused how you find the data again in this cache? It seems like you're randomly salting your cache keys, so I don't understand how subsequent requests find cached data.

Naively (and naive is often fine), you can query each node in parallel. The number of nodes is usually very small relative to the amount of data per node and reading is usually much faster than writing.