Some embodiments provide a non-transitory machine-readable medium that stores a program. The program receives a query for data from a client device. The program further generates a key based on the query for the data. The program also selects a cache service instance in a plurality of cache service instances. The program further sends the cache service instance the key and a request for a cached version of the data. The program also receives the cached version of the data from the cache service instance. The program further processes the query based on the cached version of the data. The program also sends a result set for the query to the client device.