Abstract: As users increasingly befriend others and interact online via their social media accounts, online social networks (OSNs) are expanding rapidly. Confronted with the big data generated by users, it is imperative that data storage be distributed, scalable, and cost-efficient. Yet one of the most significant challenges about this topic is determining how to minimize the cost without deteriorating system performance. Although many storage systems use the distributed key value store, it cannot be directly applied to OSN storage systems. And because users' data are highly correlated, hash storage leads to frequent inter-server communications, and the high inter-server traffic costs decrease the OSN storage system's scalability. Previous studies proposed conducting network partitioning and data replication based on social graphs. However, data replication increases storage costs and impacts traffic costs. Here, we consider how to minimize costs from the perspective of data storage, by combining partitioning and replication. Our cost-efficient data storage approach supports scalable OSN storage systems. The proposed approach co-locates frequently interactive users together by conducting partitioning and replication simultaneously while meeting load-balancing constraints. Extensive experiments are undertaken on two realworld traces, and the results show that our approach achieves lower cost compared with state-of-the-art approaches. Thus we conclude that our approach enables economic and scalable OSN data storage.