QoS-aware replica placement decides how many replicas are needed and where to deploy them to meet every request from individual clients. In this paper, a novel three-phase algorithm, namely CPI, is proposed. By dividing candidate nodes into proper medium-scale partitions, CPI is capable to handle with large-scale QoS-aware replica placement problem. Pharos-based clustering algorithm obtains ideal grouping, and partition integrating method is developed to obtain final replica policy. Theoretical analysis and experiments show that CPI has lower computation complexity and good scalability. The replicating cost and updating cost remains acceptable under different simulating conditions.