A system for providing a mapping service for distributed data storage systems includes a plurality of computing devices configured to implement a service provider network. The service provider network includes a plurality of endpoints corresponding to a plurality of data servers. Each data server of the plurality of data servers is configured to receive, from a client, a request for client data stored at the plurality of data servers and send, to a mapping service, a mapping request. The data server receives, from the mapping service, a list of a subset of the plurality of data servers, where each data server of the subset stores at least a portion of the client data. The data server generates a response to the client data request including a data portion and a server identifier portion and sends the generated response to the client.