Server consolidation is the allocation or hosting of tenants on a minimum number of cloud server machines. Given a sequence of data analytics tenant loads defined by the amount of resources that the tenants require and a service-level agreement (SLA) between the customer and the cloud service provider, significant resource cost savings can be achieved by consolidating multiple tenants on server machines. Since server machines can fail causing their tenants to become unavailable, service providers can place replicas of each tenant on different servers and reserve capacity to ensure that tenant failover will not result in overload on any remaining server. We propose the CUBEFIT algorithm for multi-tenant server consolidation that saves resource costs by utilizing fewer servers than existing approaches for data analytics workloads. Unlike existing consolidation algorithms, CUBEFIT can tolerate multiple server failures while ensuring that no server becomes overloaded. We provide extensive theoretical analysis and experimental evaluation of CUBEFIT. We show that compared to existing algorithms, the average case and worst case behavior of CUBEFIT is superior and that it produces near-optimal tenant allocation when the number of tenants is large. Through evaluation and deployment on a cluster of up to 73 machines as well as through simulation studies, we experimentally demonstrate the efficacy of CUBEFIT.