Performance of IaaS Cloud and Stochastic Model

Dr. Aly, O.
Computer Science

Abstract

The purpose of this paper is to provide analysis of the Performance of IaaS Cloud with an emphasis on Stochastic Model. The project begins with a brief discussion on the Cloud Computing and its Deployment Models of IaaS, PaaS, and SaaS. It also discusses the available three options for the performance analysis of the IaaS Cloud of the experiment-based, discrete event-simulation-based, and the stochastic model-based. The discussion focuses on the most feasible approach which is the stochastic model. The discussion of the performance analysis also includes the proposed sub-models of the Resource Provisioning Decision Engine (RPDE) of CTMC, the Hot Physical Machine (PM) Sub-Model, the Closed-Form Solution for Hot PM Sub-Model, the Warm PM Sub-Model, and the Cold PM Sub-Model. The discussion and the analysis also include the Interactions among these sub-models and the impact on the performance. The Monolithic Model is also discussed and analyzed. The findings of this discussion and analysis are addressed comparing the scalability and accuracy with the one-level monothetic model, and the accuracy of the interacting sub-models with the monolithic model. The result also showed that when the number of PMs in each pool increased beyond three and the number of the VMs per PM increases beyond 38, the monolithic model runs into a memory overflow problem. The result also indicated that the state space size of the monolithic model increases quickly and becomes too large to construct the reachability graph even for a small number of PMs and VMs. When using the interacting sub-models, a reduced number of states and nonzero entries leads to a concomitant reduction in solution time needed. The findings of indicated that the values of the probabilities models (P_h, P_w, P_c) that at least one PM can accept a job in a pool are different in monolithic (“exact”) model and interacting (“approximate”) sub-models.

Keywords: IaaS Performance Analysis, Stochastic Model, Monolithic Model, CTMC.

Cloud Computing

Cloud Computing has attracted the attention of both the IT industry and the academia as it represents a new paradigm in computing and as a business model (Xiao & Xiao, 2013). The key concept of the Cloud Computing is not new (Botta, de Donato, Persico, & Pescapé, 2016; Kaufman, 2009; Kim, Kim, Lee, & Lee, 2009; Zhang, Cheng, & Boutaba, 2010). In accordance to (Kaufman, 2009) the technology of the Cloud Computing has been evolving for decades, “more than 40 years.” Licklider introduced the term of “intergalactic computer network” back in the 1960s at the Advanced Research Projects Agency (Kaufman, 2009; Timmermans, Stahl, Ikonen, & Bozdag, 2010). The term “cloud” goes back 1990s when the telecommunication world was emerging (Kaufman, 2009). The virtual private network (VPN) services also got introduced with the telecommunication (Kaufman, 2009). Although the VPN maintained the same bandwidth as “fixed networks,” the bandwidth efficiency got increased and the utilization of the network was balanced because these “fixed networks” supported “dynamic routing (Kaufman, 2009). The telecommunication with the VPN and the bandwidth efficiency using dynamic routing resulted in technology that was coined the term “telecom cloud” (Kaufman, 2009). The term of Cloud Computing is similar to the term “telecom cloud” as Cloud Computing also provides computing services using virtual environments that are dynamically allocated as required by consumers (Kaufman, 2009).

Also, the underlying concept of the Cloud Computing was introduced by John McCarthy, the “MIT computer scientist and Turning aware winner,” in 1961 (Jadeja & Modi, 2012; Kaufman, 2009). McCarthy predicted that “computation may someday be organized as a public utility” (Foster, Zhao, Raicu, & Lu, 2008; Jadeja & Modi, 2012; Joshua & Ogwueleka, 2013; Khan, Khan, & Galibeen, 2011; Mokhtar, Ali, Al-Sharafi, & Aborujilah, 2013; Qian, Luo, Du, & Guo, 2009; Timmermans et al., 2010). Besides, Douglas F. Parkhill as cited in (Adebisi, Adekanmi, & Oluwatobi, 2014), in his book called “The Challenge of the Computer Utility” also predicted that the computer industry will provide similar services like the public utility “in which many remotely located users are connected via communication links to a central computing facility” (Adebisi et al., 2014).

NIST (Mell & Grance, 2011) identifies three essential Cloud Computing Service Models as follows:

layer provides the capability to the consumers to provision storage, processing, networks, and other fundamental computing resources. Using IaaS, the consumer can deploy and run “arbitrary” software, which can include operating systems and application. When using IaaS, the users do not manage or control the “underlying cloud infrastructure.” However, the consumers have control over the storage, the operating systems, and the deployed application; and “possibly limited control of selected networking components such as host firewall” (Mell & Grance, 2011).
allows the Cloud Computing consumers to deploy applications that are created using programming languages, libraries, services, and tools supported by the providers. Using PaaS, the Cloud Computing users do not manage or control the underlying cloud infrastructure including network, servers, operating systems, or storage. However, the consumers have control over the deployed applications and possibly configuration settings for the application-hosting environment (Mell & Grance, 2011).
allows Cloud Computing consumers to use the provider’s applications running on the cloud infrastructure. Users can access the applications from various client devices through either a thin client interface, such as a web-based email from a web browser, or a program interface. Using SaaS, the consumers do not manage or control the underlying cloud infrastructure including network, servers, operating systems, storage, or even individual application capabilities, with the possible exception of limited user-specific application configuration settings (Mell & Grance, 2011).

Performance of IaaS Cloud

The management of Big Data does require computing capacity. This computing capacity requirement is met by the IaaS clouds which are regarded to be the major enabler of data-intensive cloud application (Ghosh, Longo, Naik, & Trivedi, 2013; Sakr & Gaber, 2014). When using the IaaS Service Cloud Model, instances of Virtual Machines (VMs) which are deployed on physical machines (PMs) are provided to users for computing needs (Ghosh et al., 2013; Sakr & Gaber, 2014). Providing the basic functionalities for processing Big Data is important. However, the performance of the Cloud is regarded to be another important factor (Ghosh et al., 2013; Sakr & Gaber, 2014). IaaS cloud providers offer Service Level Agreement (SLA) to guarantee availability (Ghosh et al., 2013; Sakr & Gaber, 2014). However, performance SLA is as important as the availability SLA (Ghosh et al., 2013; Sakr & Gaber, 2014). Performance analysis of the Cloud is complex process because performance is impacted by various things such as the hardware components of CPU speed, disk properties, or software such as the nature of hypervisor, or the workload such the arrival rate, or the placement policies (Ghosh et al., 2013; Sakr & Gaber, 2014).

There are three major techniques which can be used to evaluate the performance of the Cloud (Ghosh et al., 2013; Sakr & Gaber, 2014). The first technique involves the experimentation for measurement-based performance quantification (Ghosh et al., 2013; Sakr & Gaber, 2014). However, this approach is not a practical approach due to the scale of the cloud which becomes prohibitive in term of time and cost when using this measurement-based analysis (Ghosh et al., 2013; Sakr & Gaber, 2014). The second approach involves discrete event simulation (Ghosh et al., 2013; Sakr & Gaber, 2014). However, this approach is not practical approach either because the simulation can take a long time to provide statistically significant results (Ghosh et al., 2013; Sakr & Gaber, 2014). The third approach is the stochastic technique which can be used as a low-cost option where the model solution time is much less the experimental approach and the simulation approach (Ghosh et al., 2013; Sakr & Gaber, 2014). However, with the stochastic approach, the cloud may not scale giving the complexity and the size of the Cloud (Ghosh et al., 2013; Sakr & Gaber, 2014). Scalable stochastic modeling approach which can preserve accuracy is important (Ghosh et al., 2013; Sakr & Gaber, 2014).

As indicated in (Ghosh et al., 2013; Sakr & Gaber, 2014), three pools identified for the Cloud architecture; hot, warm and cold. The hot pool is the busy and running pool (running status), while the warm pool is turned on but not ready (turned on but not ready status) and it is saving power, and the cold pool is turned off (turned off status) (Ghosh et al., 2013; Sakr & Gaber, 2014). There is no delay with the hot pool, while there is a little delay in the warm pool and the delay gets increased with the cold pool (Ghosh et al., 2013; Sakr & Gaber, 2014). When a request arrived, the Resource Provisioning Decision Engine (RPDE) tried to find a physical machine from the hot pool, which can accept the request (Ghosh et al., 2013; Sakr & Gaber, 2014). However, if all machines are all busy in the hot pool, the RPDE tries to find a physical machine from the warm pool (Ghosh et al., 2013; Sakr & Gaber, 2014). If the warm pool can not meet the request, the RPDE will go to the cold pool to meet that request (Ghosh et al., 2013; Sakr & Gaber, 2014).

There are interacting sub-models for performance analysis. A scalable approach using interacting stochastic sub-models are proposed where iteration composes an overall solution over individual sub-model solutions (Ghosh et al., 2013; Sakr & Gaber, 2014).

RPDE Sub-Model of the Continuous-Time MarkovChains (CTMC)

The first model is the RPDE sub-model of the Continuous-Time Markov Chains (CTMC) which is designed to capture the resource providing decision process (Ghosh et al., 2013; Sakr & Gaber, 2014). In this submodel, a finite length decision queue is considered where decisions are made on a first-come, first-serve (FMFS) basis (Ghosh et al., 2013; Sakr & Gaber, 2014). Under this sub-model, there is a closed form solution for RPDE sub-model and VM provisioning sub-model solutions.

1.1 The Closed Form Solution for RPDE Sub-Model

Using this closed form sub-model, a numerical solution can be obtained in two steps which start with some value of π_(0,0), and compute all the state probabilities as a function of π_(0,0)(Ghosh et al., 2013; Sakr & Gaber, 2014). The second step includes the actual steady state probability which gets calculated and normalized (Ghosh et al., 2013; Sakr & Gaber, 2014). The calculation of the steady state is found in (Ghosh et al., 2013; Sakr & Gaber, 2014). Using the Markov reward approach, the outputs from the RPDE sub-model are obtained by appropriate reward rate assigned to each state of the CTMC and then computing the expected reward rate in the steady state (Ghosh et al., 2013; Sakr & Gaber, 2014). There are three scenarios for the outputs from this RPDE sub-model: The job rejection probability, the mean queuing delay, and the mean decision delay. Each of these outputs has its calculations which can be found in details in (Ghosh et al., 2013; Sakr & Gaber, 2014).

1.2 The VM Provisioning Sub-Models

The VM provisioning sub-models capture the instantiation, configuration, and provision of a VM on a physical machine (PM) (Ghosh et al., 2013; Sakr & Gaber, 2014). For each hot, warm, and cold physical machine pool, there is CTMC which keeps track of the number of assigned and running VMs (Ghosh et al., 2013; Sakr & Gaber, 2014). The VM provisioning sub-models include various sub-models: (1) the hot PM sub-model, (2) the closed form solution for hot PM sub-model, (3) the warm PM sub-model, and (4) the cold PM sub-model (Ghosh et al., 2013; Sakr & Gaber, 2014).

1.2.1 The Hot PM Sub-Model

The hot PM sub-model include the overall hot pool which is modeled by a set of independent hot PM sub-models (Ghosh et al., 2013; Sakr & Gaber, 2014). The VMs are assumed to be provisioned serially (Ghosh et al., 2013; Sakr & Gaber, 2014).

1.2.2 The Closed-Form Solution for Hot PM Sub-Model

The closed form solution for hot PM sub-model is derived for the steady state probabilities of the hot PM CTMC where the hot PM is modeled as a two-stage tandem network of queues (Ghosh et al., 2013; Sakr & Gaber, 2014). In the closed form solution for hot PM sub-model, the queuing system consists of two nodes (1) node A , and node B. Node A has only one server with service rate of β_h, while Node B has infinite servers with service rate of each server of µ (Ghosh et al., 2013; Sakr & Gaber, 2014). The server in node A denotes the provisioning engine within the PM while the servers in node B denote the running VMs. The service time distribution at both nodes A and B is exponential (Ghosh et al., 2013; Sakr & Gaber, 2014). The calculation for the external arrival process is demonstrated in (Ghosh et al., 2013; Sakr & Gaber, 2014). If the buffer of PM is full, it cannot accept a job for provisioning (Ghosh et al., 2013; Sakr & Gaber, 2014). The steady state probability can be computed after solving the hot PM sub-model (Ghosh et al., 2013; Sakr & Gaber, 2014).

1.2.3 The Warm PM Sub-Model

In the warm PM sub-model, there are three main differences from the hot PM sub-model. The effective arrival rate is the first difference. In the warm PM sub-mode, the effective arrival rate is different because jobs arrive at the warm PM pool only if they are not provisioned on any of the hot PMs (Ghosh et al., 2013; Sakr & Gaber, 2014). The second difference is the time required to provision VM. When there is no VM running or being provisioning, warm PM is turned on but not ready for use yet. Upon a job arrival in this state, the warm PM requires some additional time for startup which causes delay to make it ready to use (Ghosh et al., 2013; Sakr & Gaber, 2014). The time to make a warm PM ready for use is assumed to be exponential. The third difference is the mean time to provision a VM on a warm PM is 1/β_w for the first VM to be deployed on this PM. The mean time to provision VMs for subsequent jobs is the same as that for a hot PM (Ghosh et al., 2013; Sakr & Gaber, 2014). After solving the warm PM sub-model, the steady-state probability is computed detailed in (Ghosh et al., 2013; Sakr & Gaber, 2014).

1.2.4 The Cold PM Sub-Model

The cold PM sub-model had differences from the hot and cold PM sub-models discussed above (Ghosh et al., 2013; Sakr & Gaber, 2014). The effective arrival rate, the rate at which startup is executed, and the initial VM provisioning rates and the buffer sizes (Ghosh et al., 2013; Sakr & Gaber, 2014). In (Ghosh et al., 2013; Sakr & Gaber, 2014), the computations for these factors are provided in details.

Once the job is successfully provisioned using either hot, cold or warm, the job utilizes the resources until the execution of the job is completed (Ghosh et al., 2013; Sakr & Gaber, 2014). The run-time sub-model is utilized to determine the mean time for job completion. The Discrete Time Markov Chain (DTMC) is used to capture the details of a job execution (Ghosh et al., 2013; Sakr & Gaber, 2014). The job can complete its execution with a probability of P₀ or go for some local I/O operations with a probability of ( 1 – P₀ ) (Ghosh et al., 2013; Sakr & Gaber, 2014). The full calculation is detailed in (Ghosh et al., 2013; Sakr & Gaber, 2014).

2. The Interactions Among Sub-Models

The sub-models discussed above can interact. The interactions among these sub-models are illustrated in Figure 1, adapted from (Ghosh et al., 2013).

Figure 1: Interactions among the sub-models, adapted from (Ghosh et al., 2013).

In (Ghosh et al., 2013), this interaction is discussed briefly. The run-time sub-model yields the mean service time (1/µ) which is needed as an input parameter to each type; hot, warm, or cold of the VM provisioning sub-model (Ghosh et al., 2013). The VM provisioning sub-models compute the steady state probabilities as (P_h, P_w, and P_c) which at least on PM in a hot pool, warm pool, or cold pool respectively can accept a job for provisioning (Ghosh et al., 2013). These probabilities are used as input parameters to the RPDE sub-model (Ghosh et al., 2013). From the RPDE sub-model, rejection probability due to buffer full as (P_block), or insufficient capacity (P_drop), and their sum (P_reject) are obtained (Ghosh et al., 2013). This (P_block) is an input parameter to the three VM provisioning sub-models discussed above. Moreover, the Mean Response Delay (MRD) is computed from the overall performance model (Ghosh et al., 2013). There are two components of the MRD; Mean Queuing Delay (MQD) in RPDE, and Mean Decision Delay (MDD) which are obtained from the RPDE sub-model (Ghosh et al., 2013). Two more components are calculated; MQD in a PM and Mean Provisioning Delay (MPD) are obtained from VM provisioning sub-models (Ghosh et al., 2013). There are dependencies among the sub-models. The (P_block) which is computed in the RPDE sub-model is utilized as an input parameter in VM provisioning sub-models (Ghosh et al., 2013). However, to solve the RPDE sub-model, outputs from VM provisioning sub-models (P_h, P_w, P_c) are required as input parameters (Ghosh et al., 2013). This cyclic dependency issue is resolved by using fixed-point iteration using a variant of the successive substitution method (Ghosh et al., 2013).

3. The Monolithic Model

In (Ghosh et al., 2013), a monolithic model for IaaS cloud is constructed using the variant of stochastic Petric Net (SPN) called stochastic reward net (SRN) (Ghosh et al., 2013). In this model, the SRN is used to construct a monolithic model for IaaS Cloud (Ghosh et al., 2013). The SRNs are extensions of GSPNs (Generalized Stochastic Petri Nets) (Ajmone Marsan, Conte, & Balbo, 1984) and the key features of SRNs are:

(Ghosh et al., 2013).

Using this monolithic model, the findings of (Ghosh et al., 2013) showed that the outputs were obtained by assigning an appropriate reward rate to each marking of the SRN and then computing the expected reward rate in the steady state. The measures that were used by (Ghosh et al., 2013) are the Job Rejection Probability (P_reject), the Mean Number of Jobs in the RDPE (E(N_RPDE)). The (P_reject) has two components as discussed earlier (P_block) which is rejection probability due to buffer full, and (P_drop), which insufficient capacity (Ghosh et al., 2013), when the RPDE buffer is full and when all (hot, warm, cold) PMs are busy respectively (Ghosh et al., 2013). The (E(N_RPDE)), which is a measure of mean response delay, is given by the sum of the number of jobs that are waiting in the RPDE queue and the job that is currently undergoing provisioning decision (Ghosh et al., 2013).

4. The Findings

In (Ghosh et al., 2013; Sakr & Gaber, 2014), the SHARP software package is used to solve the interacting sub-models to compute two main calculations: (1) the Job Rejection Probability, and (2) the Mean Response Delay (MRD) (Ghosh et al., 2013; Sakr & Gaber, 2014). The result of (Ghosh et al., 2013; Sakr & Gaber, 2014) showed that the job rejection probability gets increased with longer Mean Service Time (MST). Moreover, if the PM capacity in each pool is increased, the job rejection probability gets reduced at a given value of mean service time (Ghosh et al., 2013; Sakr & Gaber, 2014). The result also showed that with the increasing MST, the MRD increased for a fixed number of PMs in each pool (Ghosh et al., 2013; Sakr & Gaber, 2014).

In comparison with one-level monolithic model, the scalability and accuracy of the proposed approach by (Ghosh et al., 2013; Sakr & Gaber, 2014), the result also showed that when the number of PMs in each pool increased beyond three and the number of the VMs per PM increases beyond 38, the monolithic model runs into a memory overflow problem (Ghosh et al., 2013; Sakr & Gaber, 2014). The result also indicated that the state space size of the monolithic model increases quickly and becomes too large to construct the reachability graph even for a small number of PMs and VMs (Ghosh et al., 2013; Sakr & Gaber, 2014). The findings of (Ghosh et al., 2013; Sakr & Gaber, 2014) also showed that the non-zero elements in the infinitesimal generator matrix of the underlying CTMC of the monolithic model are hundreds to thousands in orders of magnitude larger compared with the interacting sub-models for a given number of PMs and VMs. When using the interacting sub-models, a reduced number of states and nonzero entries leads to a concomitant reduction in solution time needed (Ghosh et al., 2013; Sakr & Gaber, 2014). As demonstrated by (Ghosh et al., 2013; Sakr & Gaber, 2014), the solution time for monolithic model increased almost exponentially with the increase in model size, while the solution time for interacting sub-models remains almost constant with the increase in model size. Thus, the findings of (Ghosh et al., 2013; Sakr & Gaber, 2014) indicated that the proposed approach is scalable and tractable compared with the one-level monolithic model.

In comparison with the monolithic modeling approach, the accuracy of interacting sub-models showed when the arrival rate and maximum number of VMs per PM is changed, the outputs obtained from both the modeling approaches are near similar using the two performance measures of the Job Rejection and Mean Number of Jobs in RPDE (Ghosh et al., 2013; Sakr & Gaber, 2014). Thus, the errors introduced by the decomposition of the monolithic model are negligible, and interacting sub-models approach preserves accuracy while being scalable (Ghosh et al., 2013; Sakr & Gaber, 2014). These errors are the result of solving only one model for all the PMs in each pool, and the aggregation of the obtained results to approximate the behavior of the pool as a whole (Ghosh et al., 2013; Sakr & Gaber, 2014). The findings of (Ghosh et al., 2013; Sakr & Gaber, 2014) indicated that the values of the probabilities models (P_h, P_w, P_c) that at least one PM can accept a job in a pool are different in monolithic (“exact”) model and interacting (“approximate”) sub-models (Ghosh et al., 2013; Sakr & Gaber, 2014).

Conclusion

The purpose of this project was to provide analysis of the Performance of IaaS Cloud with an emphasis on Stochastic Model. The project began with a brief discussion on the Cloud Computing and its Deployment Models of IaaS, PaaS, and SaaS. It also discussed the available three options for the performance analysis of the IaaS Cloud of the experiment-based, discrete event-simulation-based, and the stochastic model-based. The discussion focused on the most feasible approach which is the stochastic model. The discussion of the performance analysis also included the proposed sub-models of RPDE of CTMC, which the Hot PM Sub-Model, the Closed-Form Solution for Hot PM Sub-Model, the Warm PM Sub-Model, and the Cold PM Sub-Model. The discussion and the analysis also included the Interactions among these sub-models and the impact on the performance. The Monolithic Model was also discussed and analyzed. The findings of this analysis are addressed comparing the scalability and accuracy of them with the one-level monothetic model, and the accuracy of the interacting sub-models with the monolithic model. The result also showed that when the number of PMs in each pool increased beyond three and the number of the VMs per PM increases beyond 38, the monolithic model runs into a memory overflow problem. The result also indicated that the state space size of the monolithic model increases quickly and becomes too large to construct the reachability graph even for a small number of PMs and VMs. The findings of also showed that the non-zero elements in the infinitesimal generator matrix of the underlying CTMC of the monolithic model are hundreds to thousands in orders of magnitude larger compared with the interacting sub-models for a given number of PMs and VMs. When using the interacting sub-models, a reduced number of states and nonzero entries leads to a concomitant reduction in solution time needed(Ghosh et al., 2013; Sakr & Gaber, 2014). As demonstrated by, the solution time for monolithic model increased almost exponentially with the increase in model size, while the solution time for interacting sub-models remains almost constant with the increase in model size. Thus, the findings indicated that the proposed approach is scalable and tractable compared with the one-level monolithic model. The findings of (Ghosh et al., 2013; Sakr & Gaber, 2014)indicated that the values of the probabilities models (P_h, P_w, P_c) that at least one PM can accept a job in a pool are different in monolithic (“exact”) model and interacting (“approximate”) sub-models.

References

Adebisi, A. A., Adekanmi, A. A., & Oluwatobi, A. E. (2014). A Study of Cloud Computing in the University Enterprise. International Journal of Advanced Computer Research, 4(2), 450-458.

Ajmone Marsan, M., Conte, G., & Balbo, G. (1984). A class of generalized stochastic Petri nets for the performance evaluation of multiprocessor systems. ACM Transactions on Computer Systems (TOCS), 2(2), 93-122.

Botta, A., de Donato, W., Persico, V., & Pescapé, A. (2016). Integration of Cloud Computing and Internet Of Things: a Survey. Future Generation computer systems, 56, 684-700.

Foster, I., Zhao, Y., Raicu, I., & Lu, S. (2008). Cloud Computing and Grid Computing 360-Degree Compared. Paper presented at the 2008 Grid Computing Environments Workshop.

Ghosh, R., Longo, F., Naik, V. K., & Trivedi, K. S. (2013). Modeling and performance analysis of large-scale IaaS clouds. Future Generation computer systems, 29(5), 1216-1234.

Jadeja, Y., & Modi, K. (2012). Cloud Computing-Concepts, Architecture and Challenges. Paper presented at the Computing, Electronics and Electrical Technologies (ICCEET), 2012 International Conference on.

Joshua, A., & Ogwueleka, F. (2013). Cloud Computing with Related Enabling Technologies. International Journal of Cloud Computing and Services Science, 2(1), 40. doi:10.11591/closer.v2i1.1720

Kaufman, L. M. (2009). Data Security in the World of Cloud Computing. IEEE Security & Privacy, 7(4), 61-64.

Khan, S., Khan, S., & Galibeen, S. (2011). Cloud Computing an Emerging Technology: Changing Ways of Libraries Collaboration. International Research: Journal of Library and Information science, 1(2).

Kim, W., Kim, S. D., Lee, E., & Lee, S. (2009). Adoption Issues for Cloud Computing. Paper presented at the Proceedings of the 7th International Conference on Advances in Mobile Computing and Multimedia.

Mell, P., & Grance, T. (2011). The NIST Definition of Cloud Computing.

Mokhtar, S. A., Ali, S. H. S., Al-Sharafi, A., & Aborujilah, A. (2013). Cloud Computing in Academic Institutions. Paper presented at the Proceedings of the 7th International Conference on Ubiquitous Information Management and Communication.

Qian, L., Luo, Z., Du, Y., & Guo, L. (2009). Cloud Computing: an Overview. Paper presented at the IEEE International Conference on Cloud Computing.

Sakr, S., & Gaber, M. (2014). Large Scale and Big Data: Processing and Management: CRC Press.

Timmermans, J., Stahl, B. C., Ikonen, V., & Bozdag, E. (2010). The Ethics of Cloud Computing: A Conceptual Review.

Xiao, Z., & Xiao, Y. (2013). Security and Privacy in Cloud Computing. IEEE Communications Surveys & Tutorials, 15(2), 843-859.

Zhang, Q., Cheng, L., & Boutaba, R. (2010). Cloud Computing: State-of-the-Art and Research Challenges. Journal of internet services and applications, 1(1), 7-18.

NoSQL Data Storage System

Dr. Aly, O.
Computer Science

Introduction: For decades, the traditional database such as MySQL, PostgreSQL, SQL Server and Oracle are regarded to be a one-size-fits-all approach for data persistence and retrieval (Sakr & Gaber, 2014). However, these traditional databases are challenged by the increasing demand for scalability, the requirement for new applications, and some web-scale applications (Sakr & Gaber, 2014). The most common architecture to develop enterprise web application is based on the three-tier framework: the server layer, the application layer, and the data layer (Sakr & Gaber, 2014). The data partitioning and the data replication are two commonly used approaches to achieve the availability, scalability, and performance enhancement goals in the distributed data management. There are two main approaches to achieve scalability at the database layer to be able to handle the client requests when the load of the application is increased (Sakr & Gaber, 2014). The first approach is to scale up allocating a bigger machine to act as database servers. The second approach is to scale out replicating and partitioning data across more machines (Sakr & Gaber, 2014). However, the traditional database suffers from serious limitations. Database systems are not easy to scale as they cannot exceed a certain limit. The database systems are not easy to configure and maintain. The specialized database systems for main memory systems as the case with OLTP and column stores as the case with OLAP add more complication and cost when selecting the database system in addition to the peak provisioning unnecessary cost (Sakr & Gaber, 2014).

Thus, new systems called NoSQL started to emerge as an alternative mode for the traditional database systems to be able to deal and handle Big Data (Moniruzzaman & Hossain, 2013; Pokorny, 2013; Sakr & Gaber, 2014). Not Only SQL” known as NoSQL databases emerged to deal with Big Data. NoSQL database systems were developed by major internet companies such as Facebook, Amazon, and Google, when they were confronted with the Big Data challenges (Moniruzzaman & Hossain, 2013). NoSQL databases are found to be suitable for massive scheme-free datasets for Big Data management (Hu, Wen, Chua, & Li, 2014). NoSQL database systems are considered to be the potential data management solution for Big Data (Abbasi, Sarker, & Chiang, 2016).

NoSQL Data Storage and the Tradeoff between Consistency and Availability

The ACID properties are regarded to be one of the basic features of the traditional relational databases (Moniruzzaman & Hossain, 2013; Pokorny, 2013; Sakr & Gaber, 2014). ACID stands for “Atomicity,” “Consistency,” “Isolation,” and “Durability” (Pokorny, 2013). These ACID properties indicate “all or nothing” concept behind the traditional database (Pokorny, 2013). The relational database has been full compliance with ACID principle (Pokorny, 2013). In addition to the ACID properties, there is also CAP theorem which states that for any system sharing data it is impossible to guarantee all of these three properties simultaneously (Pokorny, 2013). These three properties of CAP include “consistency,” “availability,” and “partition tolerance” (Pokorny, 2013; Sakr & Gaber, 2014). Moreover, the traditional relational database is also characterized by a schema, where data is structured in tables, tuples, and fields (Moniruzzaman & Hossain, 2013; Sadalage & Fowler, 2013). The traditional consistency model is not adequate for distributed systems such as the Cloud environment (Sakr & Gaber, 2014).

There are two major consistency models; the strong consistency which includes the linearizability and serializability, and weak consistency which includes the eventual the causal, eventual, and timeline consistency model (Sakr & Gaber, 2014). The causal consistency model ensures total ordering between operations which have causal relations. The eventual consistency model ensures all replicas will gradually and eventually become consistent in the absence of updates (Sakr & Gaber, 2014). The timeline consistency model guarantees all replicas perform operations on one record in the same “correct order” (Sakr & Gaber, 2014).

As indicated in (Pokorny, 2013), the NoSQL database systems scale nearly linearly with the number of servers used (Pokorny, 2013). The reason for such capability for scaling nearly linearly is due to the use of “data partitioning” (Pokorny, 2013). In NoSQL database systems, the method of distributed hash tables (DHT) is often used, in which couples of (key, value) are hashed into buckets – partial storage spaces, each from that placed in a node (Pokorny, 2013). NoSQL is not characterized by a schema or structured data (Hu et al., 2014; Sadalage & Fowler, 2013). NoSQL systems are fast, highly scalable, and reliable (Hu et al., 2014). The term of “NoSQL” database indicates the loosely specified class of non-relational data stores (Pokorny, 2013). NoSQL databases mostly do not use SQL as their query language (Pokorny, 2013). They do not support operations of “JOIN” and “ORDER BY.” The reason is that because portioning data is done horizontally (Pokorny, 2013). The data in NoSQL is often organized into tables on a logical level and accessed only through the Primary Key (Pokorny, 2013).

NoSQL database systems are organized by data models (Hu et al., 2014). They are categorized as (1) key-value stores, (2) column-oriented databases, and (3) document databases (Hu et al., 2014). Most NoSQL database systems are key-value stores or big hash tables, which contain a pair of the key-value dataset (Pokorny, 2013). This approach of the key-value or big hash table increases the efficiency of the lookup (Pokorny, 2013). The key uniquely identifies a value typically a string but it can also be a pointer, where the value is stored. The value can be structured or completely unstructured typically in BLOB (binary large object) format (Pokorny, 2013). The pair of key-value can be of different types, and may not come from the same table (Pokorny, 2013). These characteristics of the NoSQL database using the pair of key-value concept, increase efficiency and scalability of the NoSQL database systems (Pokorny, 2013). Column-oriented databases store and process data by column instead of by row (Hu et al., 2014). The rows and columns will get split over multiple nodes to achieve scalability (Hu et al., 2014). The document-oriented databases support more complex data structures than the key-value stores (Hu et al., 2014). The document-oriented database systems are the most general models of the NoSQL databases (Pokorny, 2013). There are other data models for NoSQL dataset systems, including the graph databases that are not discussed in this paper. Table 1 illustrates some of these data models of the NoSQL databases reflecting the name of the databases for each model, producer, CAP option, and consistency, derived from (Hu et al., 2014).

Table 1: NoSQL Database Models. Adapted from (Hu et al., 2014)

In accordance (Hu et al., 2014; Moniruzzaman & Hossain, 2013; Pokorny, 2013), some of these NoSQL databases do not implement ACID fully, and can only be eventually consistent (Hu et al., 2014; Moniruzzaman & Hossain, 2013; Pokorny, 2013). NoSQL databases implement “eventual consistency” concept instead of “strong consistency,” where any updates and changes are replicated to the entire database eventually, but at any given time (Hu et al., 2014; Moniruzzaman & Hossain, 2013; Pokorny, 2013). The “eventually consistent” term means that the system will eventually become consistent but after some time (Hu et al., 2014; Moniruzzaman & Hossain, 2013; Pokorny, 2013). This principle of “eventual consistency” indicate more availability and greatly improve scalability at the expense of the full and immediate consistency (Hu et al., 2014; Moniruzzaman & Hossain, 2013; Pokorny, 2013). NoSQL database has particular architectures that use different possibilities of distribution, ensuring the availability of the data, and the access to the data using replication techniques. Figure 1 illustrates the characteristics of NoSQL databases, derived from (Moniruzzaman & Hossain, 2013).

Figure 1: Characteristics of NoSQL databases. Adapted from (Moniruzzaman & Hossain, 2013)

In accordance to (Chen & Zhang, 2014), the most popular NoSQL database is Apache Cassandra. Facebook in 2008 released Cassandra as open source (Chen & Zhang, 2014). Other NoSQL implementations include Apache Hadoop, MapReduce, MemcacheDB, and Voldemort (Chen & Zhang, 2014).

References

Abbasi, A., Sarker, S., & Chiang, R. (2016). Big data research in information systems: Toward an inclusive research agenda. Journal of the Association for Information Systems, 17(2), 3.

Chen, C. P., & Zhang, C.-Y. (2014). Data-intensive applications, challenges, techniques, and technologies: A survey of Big Data. Information Sciences, 275, 314-347.

Hu, H., Wen, Y., Chua, T.-S., & Li, X. (2014). Toward scalable systems for big data analytics: A technology tutorial. IEEE Access, 2, 652-687.

Moniruzzaman, A., & Hossain, S. A. (2013). NoSQL database: New era of databases for big data analytics-classification, characteristics, and comparison. arXiv preprint arXiv:1307.0191.

Pokorny, J. (2013). NoSQL databases: a step to database scalability in a web environment. International Journal of Web Information Systems, 9(1), 69-82.

Sadalage, J. P., & Fowler, M. (2013). NoSQL: A Brief Guide to the Emerging World of Polyglot Persistence (1st Edition ed.): Addison-Wesley.

Sakr, S., & Gaber, M. (2014). Large Scale and big data: Processing and Management: CRC Press.

Traditional Distributed Models and Cloud Computing

Dr. Aly, O.
Computer Science

Introduction

The traditional distributed models involve the Shared Memory and the Message Passing programming models. The SM and the MP techniques are two major parallel computing architecture models (Coulouris, Dollimore, & Kindberg, 2005; Manoj, Manjunath, & Govindarajan, 2004). They provide the basic interaction model for distributed tasks and lack any facility to automatically parallelize and distribute tasks or tolerate faults (Hammoud, Rehman, & Sakr, 2012; Sakr & Gaber, 2014). Advanced models such as MapReduce, Pregel, and GraphLab are introduced to overcome the inefficiencies and challenges of these traditional distributed models especially when porting them to the Cloud environment (Fernández et al., 2014; Low et al., 2012; Sakr & Gaber, 2014). These new models are built upon these two traditional models of the SM and MP and offer various key properties for the Cloud environment (Sakr & Gaber, 2014). These models are also referred to as “distributed analytics engines” (Sakr & Gaber, 2014).

Shared Memory Distributed Programming

The SM system has a global memory that is accessible to all the processors in the system (Manoj et al., 2004). The SM techniques include two models based on the nature of sharing of this global memory across processors. The first model is the Uniform-Memory-Access (UMA) (Manoj et al., 2004; Pulipaka, 2016). The second model is the Non-Uniform-Memory-Access (NUMA) (Coulouris et al., 2005; Dean & Ghemawat, 2004; Hennessy & Patterson, 2011; Manoj et al., 2004; Mishra, Dehuri, & Kim, 2016). The access time to the memory in UMA model from two processors is equal. The access time to the memory in NUMA varies for different processors (Manoj et al., 2004). Hardware Distributed Shared Memory (DSM) is an example of the NUMA including Stanford DASH, SCI, DDM, and KSRI (Manoj et al., 2004). When using a uniprocessor environment, the programming in SM systems involves updating shared data, which is regarded to be a simple programming process (Manoj et al., 2004). However, with the increasing number of processors, the environment experiences increased contention and long latencies in accessing the shared memory (Manoj et al., 2004). The contention and latencies diminish the performance and limit scalability (Manoj et al., 2004). Additional issues with the SM systems involve data access synchronization, cache coherency, and memory consistency (Manoj et al., 2004). The developers must ensure appropriate memory access order through synchronization primitives (Manoj et al., 2004). Moreover, when using hardware in the implementation of the SM abstraction, the cost of the system gets increased (Manoj et al., 2004).

In SM programming model, the data is not explicitly communicated but implicitly exchanged via sharing which entails the use of synchronization techniques within the distributed programs (Sakr & Gaber, 2014). The tasks can communicate by reading and writing to the shared memory or disks locations. The tasks can access any location in the distributed memories/disk which is similar to the threads of a single process in operating systems, where all threads share the process address space and communicate by reading and writing to that space (Sakr & Gaber, 2014). The distributed tasks are prevented from simultaneously writing to a shared data to avoid inconsistent or corrupted data when using synchronization which is required to control the order in which read/write operations are performed by various tasks (Sakr & Gaber, 2014). The communication between two tasks is implicit through reads and writes to shared arrays and variables and synchronization is explicit through locks and barriers (Sakr & Gaber, 2014).

The SM programming model must meet two main requirements: developers do not need to explicitly encode functions to send/receive messages, and the underlying storage layer provides a shared view of all tasks. MapReduce satisfies these two requirements using a map and reduce, and the communications occur only between the map and reduce phases under the full control of the MapReduce engine. Moreover, the synchronization is also handled by the MapReduce engine (Sakr & Gaber, 2014). For the storage layer, MapReduce utilizes the Hadoop Distributed File System (HDFS) which provides a shared abstraction for all tasks, where any task transparently access any location in HDFS (Sakr & Gaber, 2014). Thus, MapReduce provides the shared-memory abstraction which is provided internally by Hadoop that entails MapReduce engine and HDSF (Sakr & Gaber, 2014). GraphLab also offers a shared-memory abstraction by eliminating the need for users to send/receive messages in update functions explicitly and provides a shared view among vertices in a graph (Fernández et al., 2014; Low et al., 2012; Sakr & Gaber, 2014). GraphLab allows scopes of vertices to overlap and vertices to read and write from and to their scopes which can cause a conflict of read-write and write-write between vertices sharing scope (Fernández et al., 2014; Low et al., 2012; Sakr & Gaber, 2014).

Message Passing Distributed Programming

In MP programming model the distributed tasks communicate by sending and receiving messages where the distributed tasks do not share an address space at which they can access each other’s memories (Sakr & Gaber, 2014). The MP programming model provides the abstraction which is similar to that of the process and not the threads in the operating system (Sakr & Gaber, 2014). This model incurs communications overheads for explicitly sending and receiving messages that contain data such as variable network latency, potentially excessive data transfer (Hammoud et al., 2012; Sakr & Gaber, 2014). When using MP programming model, no explicit synchronization is needed because for every send operation; there is a corresponding receive operation (Sakr & Gaber, 2014). Moreover, no illusion for single shared address space is required for the distributed system for tasks to interact (Sakr & Gaber, 2014).

Message Passing Interface (MPI) is a popular example of the MP programming model, which is an industry-standard library for writing message-passing programs (Hammoud et al., 2012; Sakr & Gaber, 2014). Pregel is regarded the common analytics engine which utilizes the message-passing programming model (Malewicz et al., 2010; Sakr & Gaber, 2014). In Pregel, vertices can communicate only by sending and receiving messages, which should be explicitly encoded (Malewicz et al., 2010; Sakr & Gaber, 2014). The SM programs are easier to develop than the MP programs (Manoj et al., 2004; Sakr & Gaber, 2014). The code structure of SM programs is often not much different than its respective sequential one, with only additional directives to be added to specify parallel/distributed tasks, the scope of variables, and synchronization points (Manoj et al., 2004; Sakr & Gaber, 2014). Large-scale distributed systems such as the Cloud imply non-uniform access latencies such as accessing remote data takes more time than accessing local data, thus enforcing programmers to lay out data close to relevant tasks (Sakr & Gaber, 2014).

References

Coulouris, G. F., Dollimore, J., & Kindberg, T. (2005). Distributed systems: concepts and design: pearson education.

Dean, J., & Ghemawat, S. (2004). MapReduce: simplified data processing on large clusters. OSDI’04 Proceedings of the 6th conference on Symposium on Opearting Systems Design and Implementation” dalam: International Journal of Engineering Science Invention. 10-100.

Fernández, A., del Río, S., López, V., Bawakid, A., del Jesus, M. J., Benítez, J. M., & Herrera, F. (2014). Big Data with Cloud Computing: an insight on the computing environment, MapReduce, and programming frameworks. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 4(5), 380-409.

Hammoud, M., Rehman, M. S., & Sakr, M. F. (2012). Center-of-gravity reduce task scheduling to lower mapreduce network traffic. Paper presented at the Cloud Computing (CLOUD), 2012 IEEE 5th International Conference on.

Hennessy, J. L., & Patterson, D. A. (2011). Computer architecture: a quantitative approach: Elsevier.

Low, Y., Bickson, D., Gonzalez, J., Guestrin, C., Kyrola, A., & Hellerstein, J. M. (2012). Distributed GraphLab: a framework for machine learning and data mining in the cloud. Proceedings of the VLDB Endowment, 5(8), 716-727.

Malewicz, G., Austern, M. H., Bik, A. J., Dehnert, J. C., Horn, I., Leiser, N., & Czajkowski, G. (2010). Pregel: a system for large-scale graph processing. Paper presented at the Proceedings of the 2010 ACM SIGMOD International Conference on Management of data.

Manoj, N., Manjunath, K., & Govindarajan, R. (2004). CAS-DSM: A compiler assisted software distributed shared memory. International Journal of Parallel Programming, 32(2), 77-122.

Mishra, B. S. P., Dehuri, S., & Kim, E. (2016). Techniques and Environments for Big Data Analysis: Parallel, Cloud, and Grid Computing (Vol. 17): Springer.

Pulipaka, G. (2016). Distributed Shared Memory Programming for Hadoop, MapReduce, and HPC Architecture. Retrieved from https://medium.com/@gp_pulipaka/distributed-shared-memory-programming-for-hadoop-mapreduce-and-hpc-357a1b226ff6.

Sakr, S., & Gaber, M. (2014). Large Scale and big data: Processing and Management: CRC Press.