In this paper, we introduce Z-Ring, a fast prefix routing protocol for peer-to-peer overlay networks. Z-Ring incorporates cost-efficient membership protocol to achieve fast routing with small maintenance cost. Z-Ring achieves routing in logGN steps, where N is the network size and G is the size of a group that can be maintained by a membership protocol with low cost. With G=4096, it translates to one-hop routing for intranet environments (N<4096), two-hop routing for mid-scale internet applications (N<16 million), and three-hop routing for ultra-large internet applications (N<64 billion). Z-Ring maintains good routing success rate under churn and low maintenance cost even at large network size. Its modularized use of the membership protocol also makes it adaptive to dynamic and wide-range network size changes.