Techniques are disclosed relating to storing location information about storage nodes in cookies. A cloud-based service may send location requests to an orchestration service that instantiated storage nodes included in a storage cluster of the cloud-based service. The cloud-based service may receive location information that identifies in which computer zone that a given storage node is located. The cloud-based service may store the location information in cookies at a metadata store that is shared among the storage nodes. The cloud-based service may receive, from a client node, a search request to identify ones of the storage nodes that store particular data. The cloud-based service may return a set of cookies corresponding to identified storage nodes. The set of cookies may enable the client node to determine whether there is a storage node that stores the particular data and is within the same computer zone as the client node.