Cloud computing is a recently developed new technology for complex systems with massive-scale service sharing, which is different from the resource sharing of the grid computing systems. Cloud reliability analysis and modeling are not easy tasks because of the complexity and large scale of the system. This paper systematically analyzes cloud computing and models the reliability of the cloud services. Various types of failures are interleaved in the cloud computing environment, such as overflow failure, timeout failure, resource missing failure, network failure, hardware failure, software failure, and database failure. This paper investigates all of them to achieve a comprehensive picture about cloud service reliability, and models those failures in a holistic manner using Markov models, Queuing Theory and Graph Theory. In accordance with the proposed model, a new evaluation algorithm is further developed in this paper integrating the Bayesian approaches together with the Graph Theory.