Abstract: Online video service needs the support of CDN (content delivery network) which can be costly. Using cloud storage nodes to deliver video content can help solve the problem. To guarantee the users QoS, CDN should pre-deploy the content files of online video service to the edge nodes which are close to the users. The existing GS (greedy site) placement algorithm can satisfy the QoS requirements at a relatively smaller cost when the historical log is provided. However, the GS algorithm will result in bad load balance among cloud storage nodes. A novel replica placement algorithm named GUCP (greedy user core preallocation) was proposed to solve this problem. The algorithm assigned users on overloaded nodes to lightly-loaded ones using the k-means algorithm, in order to balance the load. The numerical experimental results show that the cost and QoS performance of GUCP are very close to those of GS, while its performance of load balance is much better than that of GS.