Content Distribution Networks (CDN) are fundamental, yet expensive technologies for distributing the content of web-servers to large audiences. The P2P model is a perfect match to build a low-cost and scalable CDN infrastructure for popular websites by exploiting the underutilized resources of their user communities. However, building a P2P-based CDN is not a straightforward endeavor. In contrast to traditional CDNs, peers are autonomous and volunteer participants with their own heterogeneous interests that should be taken into account in the design of the P2P system. Moreover, churn rate is much higher than in dedicated CDN infrastructures, which can easily destabilize the system and severely degrade the performance. Finally and foremostly, while many P2P systems abstract any topological information about the underlying network, a top priority of a CDN is to incorporate localityawareness in query routing in order to locate close-by content. This paper aims at building a P2P CDN with high performance, scalability and robustness. Our proposed protocols combine DHT e ciency with gossip robustness and take into account the interests and localities of peers. In short, Flower-CDN provides a hybrid and locality-aware routing infrastructure for user queries. PetalUp-CDN is a highly scalable version of Flower-CDN that dynamically adapts to variable rates of participation and prevent overload situations. In addition, we ensure the robustness of our P2P CDN via low-cost maintenance protocols that can detect and recover from churn and dynamicity. Our extensive performance evaluation shows that our protocols yield high performance gains under both static and highly dynamic environments. Furthermore, they incur acceptable and tunable overhead. Finally we provide main guidelines to deploy Flower-CDN for the public use.