A highly available large-scale service cluster often requires the system to discover new nodes and identify failed nodes quickly in order to handle a high volume of traffic. Determining node membership promptly in such an environment is critical to location-transparent service invocation, load balancing, and failure shielding. In this paper, we present a topology-adaptive hierarchical membership service which dynamically divides the entire cluster into membership groups based on the network topology among nodes so that the liveness of a node within each group is published to others in a highly efficient manner. The proposed approach has been compared with two alternatives: an allto-all multicast approach and a gossip based approach. The results show that the proposed approach is scalable and effective in terms of high membership accuracy, short view convergence time, and low communication cost.