As the amount of digital data growing explosively, data deduplication becomes an attractive technique to conserve the storage and network requirements for the mass storage systems. However, data deduplication achieves data compression at the cost of error resilience. A high availability data replication strategy is proposed to improve data availability for the deduplication storage systems. Data availability optimization model is proposed to calculate the optimal replication degrees for the individual data object. Then several acceleration techniques are proposed to reduce the computational cost of the model and make the proposed scheme feasible and effective.