Systems and methods for managing mapping information for objects maintained in a distributed storage system are provided. The distributed storage system can include a keymap subsystem that manages the mapping information according to object keys. Requests for specific object mapping information are directed to specific keymap coordinators within the keymap subsystem. Each keymap coordinator can maintain a cache for caching mapping information maintained at various information sources. To manage the cache, the keymap system can utilize generation identifiers that identify the component within the distributed storage system that last updated information sources. Each keymap coordinator can determine whether cached version of keymap information is valid based on an analysis of generation identifiers.