The Peer-to-Peer (P2P) technology being widely adopted in today’s both academic research and practical service providing, has many potential advantages and achieves a great success in Information Technology scope. Recently some researchers have proposed that P2P inspired architecture also might be one choice for the telecom network evolution. Most of such works adopted structured P2P (DHT) as the basic solutions, but they seldom discussed how to eliminate the huge gap between the telecom underlay performance requirement and the performance of existed DHT which mainly originated from the Internet applications. This paper presents the design and implementation of SandStone, a DHT based key-value storage system with carrier grade performance, such as good scalability, strong consistency and high reliability, which could be deployed as the cornerstone in such new P2P inspired networking architectures.