Method and apparatus for monitoring and maintaining group health and membership in a searchable data service. The searchable data service may provide a searchable index to a backend data store, and an interface to build and query the searchable index, that enables client applications to search for and retrieve locators for stored entities in the backend data store. Embodiments of the searchable data service may implement a group health mechanism that may allow one or more components of the searchable data service to identify sets of nodes that the components may monitor. A group health component may be queried by the other components for automatically-refreshed health information about those nodes. The group health component may perform as a node failure detection mechanism. Node health information may be communicated among nodes at least in part using a gossip protocol.