Base stations have been widely deployed to satisfy the service coverage and explosive demand increase in today's cellular networks. Their reliability and availability heavily depend on the electrical power supply. Battery groups are installed as backup power in most of the base stations in case of power outages due to severe weathers or human-driven accidents, particularly in remote areas. The limited numbers and capacities of batteries, however, can hardly sustain a long power outage without a well-designed allocation strategy. As a result, the service interruption occurs along with an increasing maintenance cost. Meanwhile, a deep discharge of a battery in such case can also accelerate the battery degradation and eventually contribute to a higher battery replacement cost. In this paper, we closely examine the base station features and backup battery features from a 1.5-year dataset of a major cellular service provider, including 4,206 base stations distributed across 8,400 square kilometers and more than 1.5 billion records on base stations and battery statuses. Through exploiting the correlations between the battery working conditions and battery statuses, we build up a deep learning based model to estimate the remaining lifetime of backup batteries. We then develop BatAlloc, a battery allocation framework to address the mismatch between the battery supporting ability and diverse power outage incidents. We present an effective solution that minimizes both the service interruption time and the overall cost. Our real trace-driven experiments show that BatAlloc cuts down the average service interruption time from 4.7 hours to nearly zero with only 85 percent of the overall cost compared to the current practical allocation.