This book constitutes the thoroughly refereed post-conference proceedings of the Second International Workshop on Algorithmic Aspects of Cloud Computing, ALGOCLOUD 2016, held in Aarhus, Denmark, in August 2016. The 11 revised full papers presented together with one tutorial paper were carefully reviewed and selected from 30 initial submissions. They deal with the following topics: algorithmic aspects of elasticity and scalability for distributed, large-scale data stores (e.g. NoSQL and columnar databases); search and retrieval algorithms for cloud infrastructures; monitoring and analysis of elasticity for virtualized environments; NoSQL, schemaless data modeling, integration; caching and load-balancing; storage structures and indexing for cloud databases; new algorithmic aspects of parallel and distributed computing for cloud applications; scalable machine learning, analytics and data science; high availability, reliability, failover; transactional models and algorithms for cloud databases; query languages and processing programming models; consistency, replication and partitioning CAP, data structures and algorithms for eventually consistent stores.