Due to the highly distributed and dynamic features, service discovery is a key requirement in grid computing. The paper first introduces the existing service discovery mechanisms in distributed computing, and then points out the problems in MDS which is widely used in grid systems. In order to address these issues, GNSD, a novel service discovery mechanism is proposed, which is based on the OSPF (Open Shortest Path First) flooding mechanism and combines the advantages of tree architecture and flat architecture. The time and space complexity of both GNSD and MDS are also analyzed. Experimental results show that GNSD not only accelerates the service discovery but also relieves the burden of servers at the cost of little extra storage and communication traffic. Furthermore, it is more robust. As a conclusion, GNSD is an efficient service discovery mechanism