Citation
Study of resource management for multitenant database systems in cloud computing

Material Information

Title:
Study of resource management for multitenant database systems in cloud computing
Creator:
Martinez, Christine G
Publication Date:
Language:
English
Physical Description:
1 electronic file : ;

Subjects

Subjects / Keywords:
Cloud computing ( lcsh )
Databases ( lcsh )
Cloud computing ( fast )
Databases ( fast )
Genre:
bibliography ( marcgt )
theses ( marcgt )
non-fiction ( marcgt )

Notes

Review:
Cloud computing can offer the business community higher availability, guaranteed throughput and service rate, higher reliability, security, and cost-effective maintenance. These very attractive benefits create the growing popularity of cloud computing, and make many companies eager to migrate their existing database applications to the cloud. In the cloud, most of these applications share processors, memory, disk spaces, and databases with other companies' applications. The cloud service providers run multiple tenants' databases in the cloud and therefore needs an effective resource sharing management method in order to allow users to keep lower overall costs without loss or degrading quality of their services. Thus, developing an efficient resource management for multi-tenant database system in cloud is essential for both business community and cloud providers. To build an efficient resource management, two key technical components that must be addressed. First, is how to create a workload aware system, this means being able to monitor resource consumption, predict a combined workload of multitenant databases and finally identify which workloads can be co-located on a database server to achieve the best consolidation and performance that is possible. The second component is having the capability to scale-out. Elastic scalability allows for the support of multiple databases and workloads, which range in size. When processing exceeds the capabilities of one node, we must be able to spread the workload across multiple nodes in order to achieve higher throughput. This thesis attempts to provide a comprehensive look at current technical issues surrounding efficient resource management of multitenant databases in cloud computing so that we are able to answer the above two questions. To achieve our goal, we will explore how a database management system operates and performs work. This will enable a better sense of the atmosphere where the multitenant databases will reside and why clouds are becoming so popular. Finally, we will present our study result of multi-tenant database, including possible architectures, current resource management issues, and proposed solutions and lastly, new ideas on how to solve these problems.
Bibliography:
Includes bibliographical references.
Statement of Responsibility:
by Christine G. Martinez.

Record Information

Source Institution:
Auraria Library
Holding Location:
Auraria Library
Rights Management:
All applicable rights reserved by the source institution and holding location.
Resource Identifier:
858024136 ( OCLC )
ocn858024136

Auraria Membership

Aggregations:
Auraria Library

Downloads

This item has the following downloads:


Full Text
STUDY OF RESOURCE MANAGEMENT
FOR MULTITENANT DATABASE SYSTEMS IN
CLOUD COMPUTING
By
Christine G. Martinez
B.S., University of Colorado, Denver, 2004
A thesis submitted to the
Faculty of the Graduate School of the
University of Colorado in partial fulfillment
of the requirements for the degree of
Masters of Science
Computer Science and Engineering
2012


This thesis for the Masters of Science degree by
Christine G. Martinez
has been approved for the
Computer Science and Engineering
by
Ilkyeun Ra, Advisor
Gita Alaghband, Chair
Tom Altman
Date 4/10/2012


Martinez, Christine, G. (M.S., Computer Science and Engineering)
Study Of Resource Management for Multitenant Database Systems in Cloud Computing
Thesis directed by Professor Ilkyeun Ra.
ABSTRACT
Cloud computing can offer the business community higher availability,
guaranteed throughput and service rate, higher reliability, security, and cost-effective
maintenance. These very attractive benefits create the growing popularity of cloud
computing, and make many companies eager to migrate their existing database
applications to the cloud. In the cloud, most of these applications share processors,
memory, disk spaces, and databases with other companies applications.
The cloud service providers run multiple tenants databases in the cloud and
therefore needs an effective resource sharing management method in order to allow users
to keep lower overall costs without loss or degrading quality of their services. Thus,
developing an efficient resource management for multi-tenant database system in cloud is
essential for both business community and cloud providers. To build an efficient
resource management, two key technical components that must be addressed. First, is
how to create a workload aware system, this means being able to monitor resource
consumption, predict a combined workload of multitenant databases and finally identify
which workloads can be co-located on a database server to achieve the best consolidation
and performance that is possible. The second component is having the capability to
scale-out. Elastic scalability allows for the support of multiple databases and workloads,
m


which range in size. When processing exceeds the capabilities of one node, we must be
able to spread the workload across multiple nodes in order to achieve higher throughput.
This thesis attempts to provide a comprehensive look at current technical issues
surrounding efficient resource management of multitenant databases in cloud computing
so that we are able to answer the above two questions. To achieve our goal, we will
explore how a database management system operates and performs work. This will
enable a better sense of the atmosphere where the multitenant databases will reside and
why clouds are becoming so popular. Finally, we will present our study result of multi-
tenant database, including possible architectures, current resource management issues,
and proposed solutions and lastly, new ideas on how to solve these problems.
Approved: Ilkyeun Ra
IV


DEDICATION
I dedicate this work to my husband, Andres Martinez.
v


TABLE OF CONTENTS
CHAPTER
I. INTRODUCTION..............................................................1
What is being researched and investigated...........................1
Thesis Layout.......................................................1
II. DATABASE MANAGEMENT SYSTEM ARCHITECTURE...................................4
Introduction to database management systems.........................4
Processing models...................................................5
Buffers.............................................................8
Memory architectures...............................................10
Shared memory...............................................10
Share-Nothing...............................................11
Shared disk.................................................12
Query Processor....................................................13
Parsing.....................................................13
Rewrite.....................................................13
Optimizer...................................................14
Executor....................................................15
Indexing and Partitioning..........................................15
Indexing....................................................16
Partitioning................................................17
Storage Management.................................................17
Location....................................................17
Buffering...................................................18
Transactions.......................................................19
vi


Understanding Shared DBMS Components................................19
Catalog manager..............................................19
Memory allocator.............................................20
III. CLOUD COMPUTING..........................................................21
What is cloud computing.............................................21
Benefits and Motivation of Cloud Computing..........................25
Basic Trends in Cloud Computing.....................................25
Rise of Multitenancy................................................27
IV. MULTITENANT DATABASES IN CLOUD COMPUTING..................................28
Benefits of multitenant databases in cloud computing................28
Shared Machine Multitenancy Database Architecture...................28
Shared Process Multitenant Database Architecture....................29
Shared Table Multitenant Database Architectures.....................30
Multitenant Architectures and Cloud Service.........................31
V. CURRENT CHALLENGES IN MULTITENANT DATABASES IN CLOUD
COMPUTING.....................................................................33
Overview of database type challenges................................33
Overview of Multitenant Architectural Challenges....................33
Shared machine/hardware architecture challenges..............33
Shared process architecture challenges.......................34
Shared table architecture challenges.........................35
Resource Allocation and Workload Balancing..........................35
Monitoring resources.........................................36
Predicting combined workload.................................36
Workload consolidation.......................................37
Scaling/Elasticity..................................................37
vii


Database Schema Design Issues.......................................38
Challenges Recognized But Not Resolved In This Paper................38
Transactional databases......................................38
Security.....................................................39
Network latency..............................................39
Administrative issues........................................41
Data warehouses..............................................41
VI. CURRENT SOLUTIONS TO CHALLENGES..........................................44
Resource allocation and workload balancing..........................44
Scalability/Elasticity..............................................48
Database Schema Issues..............................................51
VII. CONCLUSION...............................................................56
Overview............................................................56
Best Architecture...................................................56
DBMS architecture............................................56
Database normalization.......................................59
Resource Allocation & Load Balancing................................60
Monitoring resources.........................................60
Predicting combined workload.................................61
Workload consolidation.......................................62
Live Migration......................................................62
Partitioning and Indexing...........................................64
REFERENCES....................................................................66
viii


LIST OF FIGURES
Figure
II. 1 Main Components of a Database Management System. [1]..........................4
11.2 Process Per DBMS Worker.[l]....................................................6
11.3 Thread Per DBMS Worker. 111....................................................7
11.4 Process Pool.[l]...............................................................8
11.5 Shared Memory Architecture.[l]................................................10
11.6 Shared-Nothing Architecture.!!]...............................................11
11.7 Shared Disk Architecture.!!]..................................................12
II. 8 Query Plan. [1]..............................................................15
III. 1 Cloud Diagram. [3].........................................................21
III. 2 Cloud Stack. [5]...........................................................23
IV. 1 Shared Memory Architecture [12]............................................28
IV.2 Shared Process Architecture [12].............................................30
IV.3 Shared Table Architecture [12]...............................................31
IV.4 Multitenant Database Architecture and Cloud Services. [14]...................32
VI. 1 Database Migration Timeline. [29]...........................................49
VI.2 Chunk Folding Example. [8]...................................................52
VI.3 Extension Table Layout. [8]..................................................53
VI.4 Chunk Table. [8].............................................................53
VI.5 Chunk Folding. [8]...........................................................54
IX


VII. 1 Database Architecture Model [29]
57
x


LIST OF EQUATIONS
Equation
VI. 1 Consolidation Precition Function [28]
47
xi


LIST OF ABBREVIATIONS
1. ACID Atomicity, Consistency, Isolation, and Durability
2. AMI Amazon Machine Image
3. CPU Central Processing Unit
4. DaaS Database as a Service
5. DBA Database Administrator
6. DBMS Database Management System
7. EBS Elastic Block Store
8. EC2 Amazon Elastic Compute Cloud
9. FIFO First In First Out
10. GB Gigabyte
11. I/O Input/Output
12.IaaS Infrastructure as a Service
13. KB Kilobyte
14. MB Megabyte
15. NAS Network Area Storage
16. NF Normal Form
17. NIST National Institute of Standards and Technology
18. OS Operating System
19. PaaS Platform as a Service
20. RAM Random Access Memory
21. RDS Amazon Relational Database Service
22. SaaS Software as a Service
23. SAN Service Area Network
24. SDSS Sloan Digital Sky Survey
25. SLA Service Level Agreement
26. SQL Structured Query Language
27. VM Virtual Machine
28. WAN Wide Area Network


CHAPTER
I. INTRODUCTION
What is being researched and investigated
Cloud computing has become increasingly popular and relational databases are
essential to almost every computing environment today. Making the two closely
intertwined. Cloud computing is an attractive concept due to the fact that it moves the
burden of provisioning, configuring, scaling, backing up and access control away from
the company (or tenant) to the service provider. This allows for lower overall costs for
the users. Therefore, companies are able to deploy large numbers of web applications to
the cloud effortlessly. These web applications have different database schemas as well
as erratic load patterns. In order for the service provider to lower the costs, they must co-
locate multiple tenants databases onto a single server for effective resource sharing.
The two key resource management features that must be addressed in a
multitenant database, which resides in a cloud are efficient multitenancy and elastic
scalability. There are also key database architectural details that can be implemented in
order to help efficiently utilize resources such as data normalization, partitioning and
indexing. Thus the concept of a query router, which monitors the database management
system, is introduced.
Efficient Multitenancy evaluates a set of databases and workloads making the
determination as to what is the best possible way to service them. The cloud provider
wants to find the minimum number of nodes that can service the databases while still
maintaining service level agreements on query performance. There are three critical
pieces to efficient multitenancy, monitoring resource consumption of individual
databases, predicting combined workloads and the method of combining the databases.
Monitoring resources involves evaluating a combination of database management system
and operating system resources. The resources that need to be monitored are CPU,
RAM, and disk I/O. Monitoring RAM in a DBMS is difficult due to the fact that most
operating systems over provision the memory that is allocated to the database. Thus, a
methodology must be put into place to evaluate the amount of RAM a database requires.
1


This is done be evaluating the working set of the application. When predicting the
combined workload for multiple databases, determining I/O is burdensome since the
DBMS exploits unused bandwidth. Different solutions for each of these three pieces are
presented as well as specific enhancements, which would further help in maintaining
efficient multitenancy.
Elastic scalability specifically deals with supporting multiple databases with
varying workloads. The approach taken for elastic scalability is live migration. The
system must be workload aware and quickly make the determination that a given
workload has exceeded the capacity of a single node. Once this has been identified, the
system needs a method to scale out and process against multiple nodes such that higher
throughput can be achieved. Scaling out must also go undetected by the users and
happen as quickly as possible thus as transactions come into the system, they must
execute against a source node until a destination node has been warmed up and made
ready to accept transactions. The method that can be utilized to achieve this will be
evaluated as well as improvements that can be made to further maximize the efficiency of
resource management.
Finally, this paper will introduce the concept of a query router and monitor. This
abstraction has the ability to mask how queries from different tenants are routed to the
correct database node hosting their data so that tenants need not know where their data
resides. It also monitors SQL statements so that it can identify their access patterns. This
information allows for more precise data partitioning, indexing and potential query
optimizations. The query router also estimates the cost of queries based on available
resources and compare them to service level agreements. This allows for the query
monitor to provide a degree of performance isolation by controlling the rate at which
queries are dispatched to nodes. As well as it allows for easy identification of situations
where the workload has exceeded current capacities. All of these details provide a
foundation for comprising a tenant specific architecture that is workload aware and
scalable.
The aspiration of this paper is to propose a comprehensive multitenant database
architecture that can reside in a cloud environment, which is elastic, workload aware and
specifically supports the resource issues that are encountered with multitenant database.
2


Thesis Layout
The rest of this paper is laid out into the following sections, 2, database
management system architecture. In order to be able to make knowledgeable suggestions
for how to handle resource allocation within a database, there first must be an
understanding of how a database management system functions and utilizes memory.
Section 3 will provide an overview of cloud computing with some preliminary
information pertaining to cloud computing and infrastructure in order to understand the
environment where the problem resides. Section 4 is dedicated to understanding the
different multitenant database architectures. Understanding these is key to understanding
resource implications. Section 5 examines the current challenges with multitenant
databases in cloud computing. Section 6 will provide possible solutions to resource
issues and finally section 7 are my evaluations, conclusions and possible solutions.
3


CHAPTER
II. DATABASE MANAGEMENT SYSTEM ARCHITECTURE
Introduction to database management systems
Database management systems (DBMS) are complex. There are five main
components of a relational DBMS, the process manager, client communication manager,
relational query processor, transactional storage manager and the shared components and
utilities.
Figure II. 1 Main Components of a Database Management System. [1]
This section will serve as an overview of some of these components.
4


Processing models.
Many times, when evaluating a database management system, there is an
execution of concurrent user requests, which must be mapped to operating system
processes or threads. In order to understand how the different processing models work,
we must understand some basic components within the database system as well as the
operating system.
The operating system process is a single unit of program execution that is
scheduled by the operating system kernel. It is essentially combining an
operating system execution unit with an address space private to the
process.
The operating system thread is scheduled by the operating system kernel
and is an operating system execution unit that does not contain the
additional private operating system address space.
The lightweight thread package is scheduled at the application level in the
user-space without the kemeTs involvement. The user-space scheduler as
well as its lightweight threads all run within a single operating system
process as a single thread of execution. A drawback of lightweight threads
is that any blocking operation will block all threads in the process,
preventing any threads from making progress.
The DBMS client implements the API that is used by application programs
in order to communicate with the DBMS.
The DBMS Worker is a thread that resides within the DBMS, which does
work for the DBMS client. There must be a one to one correspondence
between a DBMS worker and a DBMS client. The worker takes care of all
SQL requests from one DBMS client by sending the request to the DBMS
server and returns the results to the client.
There are three process models that are utilized by DBMS, process per DBMS
worker, thread per DBMS worker and process pool. The process per DBMS worker is an
implementation where the DBMS workers are mapped directly onto OS processes. Here,
the OS scheduler must manage the timesharing of DBMS workers. What complicates
5


this process model is the fact that the in-memory data structures are shared across the
DBMS connections; this includes the lock table and the buffer pool. [1]
Figure II.2 Process Per DBMS Worker.[l]
Its important to note this model requires substantial use of shared memory and it
also diminishes the advantages of address space separation. This process model also does
not scale very well when there are large numbers of concurrent connections this is due to
the fact that a process has more state than a thread and consequently consumes more
memory.
The next process model is thread per DBMS worker. In this model, a single
multi-threaded process hosts all of the DBMS worker activity. This model relies on a
dispatcher thread to listen for new DBMS connections; each connection is thus allocated
to a new thread. SQL requests, which are submitted by clients, are executed entirely by
the corresponding thread running a DBMS worker.
6


Figure II.3 Thread Per DBMS Worker. [1]
The thread runs inside the DBMS process, returns the results to the client and waits
for the next request from that same client. There are many multithreading challenges
with this specific process model; the OS does not protect the threads from each others
memory overruns and stray pointers; debugging is difficult due to race conditions; there
is also a difficulty when it comes to porting across OS due specifically to the differences
in the threading interfaces.
The last process model is the process pool. This model is the most complex and
difficult to implement. In this model, rather than allocating an entire process per DBMS
worker, they are hosted by a pool of processes.
7


Figure II.4 Process Pool.[l]
Now, the central process supports all DBMS client connections. Hence, as SQL
requests are made, they are allocated to one of the processes within the process pool. The
statement is executed, the results are returned to the client and the process is returned to
the pool so that it can once again be allocated to another request as needed. There are
many advantages to this process model, there are a smaller number of processes that are
required and is much more efficient. [1]
Buffers
The objective of these different models is to execute as many concurrent requests
as possible while being as independent as possible. But, full isolation is not possible
since they are operating on the same database and thus, shared memory is used to share
data structures and states. In all of the processing models, data is migrated from the
DBMS to the requesting client, this implies that requests are moved to the server
processes, results are returned to clients and then must be moved back out. All of this is
done utilizing buffers, disk I/O buffers and client connection buffers. Buffers are an
8


important concept in DBMS. Disk I/O buffers read and write to shared data stores.
There are two different scenarios when evaluating disk I/O buffers, there are either
database I/O requests or log I/O requests. Database I/O requests, also known as the
buffer pool, is where all persistent database data is staged. In thread per DBMS worker,
the buffer pool is a heap data structure that is available for all threads to utilize. Whereas
in the other two models, the buffer pool is allocated within shared memory and available
to all processes. Ultimately, the buffer pool is a data structure, which is available to all
database threads and processes. The way that the buffer pool works is that when a thread
requires that a page be read from the database, it creates an I/O request that specifies the
disk address as well as a handle to a free memory location, or rather frame in the buffer
pool for where the result can be placed. To flush a buffer pool page to disk, then a thread
must generate an I/O call that indicates the pages current frame in the buffer pool as well
as its destination address on disk.
Log I/O requests, commonly called the log tail, is an in-memory queue that is
flushed to the log disk in FIFO order. The queue consists of an array of entries, which
are generated during transaction processing. Thus, one type of flushing is the commit
transaction flush. A transaction is not successful until a commit log record is flushed to
the log device. Again, if we evaluate the different processing models, we can see that for
the thread per DBMS worker, the log tail is a heap data structure. In the other two
models, there are two different options, a separate process manages the log or the log tail
is allocated in shared memory like the buffer pool.
Its important to note that understanding these different process models as well as
the different buffers and requests that can be made will allow for the correspondence
between multitenant systems and workload. As the workload increases, throughput will
increase to a maximum point and beyond that point, the throughput will decrease. This is
a direct correlation with the memory pressures that exist in database management. In
these scenarios, the DBMS cannot maintain the working set of database pages in the
buffer pool and begins to waste all of its time replacing pages. We will see that these
issues become more prevalent with query processing, which tends to consume a large
amount of main memory. Thrashing in these instances can be directly related to
contention for locks, where transactions continuously deadlock. [1]
9


Memory architectures
Shared memory.
In a parallel system, shared memory means that all processors can access the same RAM
as well as disk with the same performance. The process model for shared memory, the
OS supports the transparent assignment of processes or threads across the processors.
Figure II.5 Shared Memory Architecture.il]
All three of the different process models run efficiently on this type of a system,
but the main challenge is to alter the query execution layer such that it can take full
advantage of the ability to parallelize a single query across multiple CPUs.
Failure of a processor in this type of architecture results in the shutdown of the
machine and ultimately the entire DBMS. [1]
10


Share-Nothing.
In a shared-nothing parallel system, there exist a cluster of independent machines, which
communicate via a high-speed network.
Figure II.6 Shared-Nothing Architecture.[1]
In this type of a system, there is not a way to directly access the memory or disk
of another system. In shared-nothing memory architectures, the coordination of the
various machines is left up to the DBMS. Generally, the DBMS runs one of the standard
process models on each machine. Thus, each machine has the capability to accept SQL
requests from clients. But each machine only stores a portion of the data locally. This
means that once a query request is received, the request is sent to additional machines
such that they all execute the query in parallel against the data they are locally storing. In
essence, the underlying data structure is dictating that the data is partitioned between each
machine such that each processor has the ability to execute independently of the others.
There are different options to partitioning data, which will be discussed later. Thus, it is
easy to see that this memory architecture allows unsurpassable scalability.
11


Finally, its important to note that a failure of a machine in this system will
typically does not result in the entire DBMS being shut down. But, does result in lose of
access to some data. [1]
Shared disk.
The shared disk memory architecture in a parallel system allows for all processors to
access disks with roughly the same performance, but they are unable to access each
others RAM. We can see this type of memory architecture in Oracle DBMS as well as
some DB2 DBMS.

Figure II.7 Shared Disk Architecture.[1]
This architecture allows for lower cost of administration since partitioning of data
does not have to necessarily be a consideration when setting up this model. Here, failure
of a single DBMS processing node does not affect the other nodes ability to still access
the entire database. But, shared disk is still susceptible to a single point of failure. If data
is corrupted before reaching storage or while in storage, then all nodes have access to
only this corrupt page.
Since data is copied into RAM and modified on multiple machines, each machine
must have its own local memory for locks and buffer pool pages and thus data is shared
across machines, explicit coordination is required. There must be distributed locks and
cache-coherency to manage the different buffer pools. [1]
12


Query Processor
Ultimately, a query processor takes the SQL statement, validates it, optimizes it
into an execution plan, and finally executes it. The client program, which issued the
query, then pulls the result tuple. Understanding how a query is actually processed
within a DBMS will directly correspond to how resources are utilized when a SQL
statement is issued and how we might eventually be able to achieve higher throughput
and allocate work to additional nodes when necessary.
Parsing.
For every SQL statement that is submitted, the parser must verify that the query is
correctly defined, resolve names and references, convert the query into the internal
format, which is utilized by the optimizer and finally verify that the user has security to
execute the query.
The parser first must consider every table that is referenced in the FROM clause
of the SQL statement and verify that the name is accurate and valid. After doing this, the
parser invokes the catalog manager in order to verify that the table is in the system
catalog. The, utilizing the catalog, it establishes that every attribute that is referenced is
accurate. If the query is parsed successfully, to this point, there is an authorization check
to make sure that the user has the necessary permissions on the tables to perform the
query. Once the user passes security and the parser is thus successful, the query is
handed off to the query rewriter for processing. [1]
Rewrite.
The query rewriter simplifies and normalizes the query without changing
semantics. It does this by only relying on the query and metadata in the catalog and not
by actually accessing any data within the tables. The rewriter generates an internal
representation of the query in the same internal format it accepted at its input. In more
detail, the rewriters responsibilities are to handle view expansion by rewriting the query
to replace the view with tables and predicates referenced by the view. It then substitutes
all references to the view with column references to tables within the view. This is done
until there are no references to any views within the SQL statement. It also functions to
13


perform constant arithmetic evaluations in order to simplify the expressions. The list
continues on with what the rewriter is tasked with, logical rewriting of predicates,
semantic optimization, and subquery flattening. [1]
Optimizer.
Once the internal representation of the query has been created, the optimizer
takes it and develops an efficient query plan for the execution of the query. In many
instances, the query plan can be thought of as a dataflow diagram. Queries are divided
into SELECT-FROM-WHERE blocks where the optimization of each block takes place.
Sort (AvgSal)
Group By/AVG
SELECT
14


Figure II.8 Query Plan.[l]
Only the main physical operators are shown. [1]
The query plan can be generated in different ways, it can be compiled into
machine code or interpretable. Currently, the query plan is compiled into some type of
interpretable data structure so that it can be more portable between different platforms.
Some of the main components of the query plan are plan space, selectivity estimation,
search algorithms, parallelism and auto-tuning. [1]
Executor.
The query executor is a runtime interpreter of the query plan. Ultimately, the
query executor takes in the dataflow graph and recursively invokes actions for the
operators. Therefore, most executors utilized an itorator. Every iterator has an input,
which defines an edge in the dataflow graph, as well as operators, which are the nodes of
the dataflow graph. The operators are executed within a subclass of the iterator.
The iterator must deal with memory allocation for in-flight data. Normally, the iterator is
pre-allocated a fixed number of tuple descriptors. It never allocates memory
dynamically. A tuple descriptor is an array of column references. Every column
reference is a reference to a tuple in memory as well as a column offset for that tuple.
There are two possible locations where the actual tuple that is referenced is stored in
memory. The first possible location is within the pages in the buffer pool and the second
possibility is that the iterator allocated space for the tuple on the memory heap. In the
first instance, where tuples reside in the buffer pool, these are called BP-tuples. The
iterator creates a tuple descriptor which references a BP-tuple, it increments the count of
active references to the tuple on that page and decrements the count when the tuple
descriptor is cleared. In the second option, the tuple is an M-tuple. In order to construct
an M-tuple, the iterator copies columns from the buffer pool. [1]
Indexing and Partitioning
The response time of a transactional database is substantially affected by the rate
that data can be retrieved from disk. Therefore, having indexing and partitioning in place
15


will help to speed up the retrieval of data substantially and ultimately lead to a better
performing system that requires less resources to execute.
Indexing.
Database indexes are utilized to improve the speed of data retrieval but cause for
slower writes and increased storage requirements. Generally, indexes enable sub-linear
lookup time. If we compare a non-indexed database to an indexed database, we would
see the following; a non-indexed database, which contains N data objects where there it is
desired to retrieve only one of the objects, would examine each object until a match was
found. This would cause for on average the retrieval of half the objects before the
desired one is found and a lookup of all the objects for an unsuccessful lookup attempt,
making the worst case linear time. But, an indexed data structure improves the
performance of the lookup. It can be thought of the same way as an index page in a
book, where there would no longer be a need to scan the entire book to find what you are
looking for but instead just quickly find what you want and go directly to that page.
There are two main index architectures, clustered and non-clustered. Clustered indexes
change the data block into a very specific order to match the index. Which therefore
results in the row data being stored in that order. This means that only one clustered
index can be created on a table. The main feature of clustered index is the ordering of the
physical data rows in compliance with the index blocks that point to them. Ultimately,
this allows for the next row item in the sequence to be immediately before or after the last
one, and so fewer data block reads are needed. Non-clustered indexes allow for the data
to be presented in an arbitrary order but the logical ordering is specified by the index.
The index tree has the index keys in sorted order where the leaf level of the index has the
pointer to the record. Non-clustered indexes also allow for more than one index to be on
any given table.
With indexes, it is very important to note that the order in which columns are
listed in the index definition is crucial. It is possible to retrieve a set of row identifiers
using only the first indexed column, but it is not possible to retrieve the set of row
identifiers using only the second or greater indexed column. [34]
16


Partitioning.
Partitioning is a division of logical databases into distinct independent parts. The
partitions may be laid out over multiple nodes. There are two types of partitioning,
horizontal or vertical. Horizontal partitioning means that different rows from within a
table are divided up among the different nodes. A good example of this would be
partitioning customers by zip code. If their zip code is less than 50000 they are stored on
node 1 and customers with a zip code greater than 50000 are stored on node 2. Vertical
partitioning is dividing the data by columns instead of rows. In many cases, different sets
of hardware are utilized to store the separate columns; storing infrequently used or wide
columns on slower devices and columns that are continuously accessed on faster devices.
Generally, the method utilized to understand how to split the data is to divide up the
dynamic data from the static data, where dynamic data is not used as often as static data.
There are many different partitioning criteria: range, list, hash, or composite. [33]
Storage Management
Deciphering what implications there are when dealing with the locality of data is
critical in the process of formulating the best possible solution for resource management.
Clearly all these factors play a role in efficient resource management.
Location.
The location of the actual data is important to consider when evaluating
performance of a database. Since sequential access is much faster than random access,
the DBMS needs to control where and how the data is laid out across disks. The best
way for it to control spatial locality is to store the data directly to raw disk devices,
alleviating the additional requirements of a file system all together. Part of the reason
that this works well is due to location proximity. The raw devices addresses generally
correspond to physical proximity of the storage location. Using raw disk devices does
have pitfalls, the DBA must allocate an entire disk partition to the DBMS and access
interfaces are OS specific which can cause for the database to be less portable. Another
17


possible way fro the DBMS to control spatial locality of its data is to create a large file in
the OS file system and manage the positioning of the data as offsets in that file.
Inherently, the file is a linear array of disk-resident pages. [1]
Buffering.
When or rather the frequency at which data is physically written to the disk must
be taken into consideration. Many OS have come with I/O buffering mechanisms to
make the determination as to when to do reads and writes of the file blocks. The issue
with the OS doing this is that is could ultimately postpone or reorder writes which will
cause for the DBMS to become discombobulated. Since we are primarily concerned
with relational databases, we must evaluate the correctness of the database. It can now
no longer guarantee recovery after a failure unless the DBMS is controlling the timing
and ordering of writes. The next issue with the OS controlling the buffering mechanism
has to do with performance. The OS has support for read-ahead and write-behind
mechanisms which do not work well with DBMS access patterns. The last issue is what
is known as double buffering and the large CPU overhead of memory copies. Since the
DBMS must do its own buffering, any buffering by the OS is redundant. This not only
wastes system memory, it also wastes time and processing resources since on reads it
copies the data from disk to the OS buffer and then again to the DBMS buffer pool and
on writes both of the copies are required in reverse. This can create a major bottleneck
because essentially it is contributing to latency, consuming CPU cycles and flooding the
CPU data cache. Thus, it is very important that the DBMS controls the page replacement
techniques as well as double buffering is avoided and writes are sent to disk based on the
requests of the DBMS.
One of the main components of a DBMS is the buffer pool. It can have a
profound affect on the overall DBMS. Every DBMS has a large shared buffer pool in its
own memory space with a dynamically adjustable size depending on the system needs
and available resources. The buffer pool is simply an array of frames in which each
frame is an area of memory that is the size of a database disk block. Blocks are copied to
the buffer pool from disk, with no format changes. It is then manipulated within memory
18


and later written back. There also exists a hash table that works with the array of buffer
pool frames. The hash table maps page numbers currently in memory to their location in
the frame table, the location of the page on backing disk storage, and metadata about the
page. The metadata generally includes a dirty bit so that it can be determined whether or
not the page has changed since it was last read from disk as well as additional
information for page replacement policies so that the page can be evicted when the buffer
pool is full. [1]
Transactions
This will be a brief discussion on transactions since the topic is extremely
complex and having an overview will provide enough information to understand the
remaining componenets.
The largest section of a DBMS is the transactional storage manager. There are
generally four components within the transactional storage manager, a lock manager for
concurrency control, a log manager for recovery, a buffer pool for database I/O and
access methods for organizing data on disk.
First, it is important to understand the notion ACID, Atomicity, Consistency,
Isolation, and Durability. Isolation within a DBMS is done via a locking protocol, while
durability is through logging and recovery. Atomicity is accomplished by a combination
of locking and logging. Finally, consistency is completed by runtime checks in the query
executor. [1]
Understanding Shared DBMS Components
There are many different shared components within a DBMS, but the two that are
of most interest for this thesis are described below.
Catalog manager.
The catalog manager actually holds information pertaining to the data as well as
the overall system in the form of metadata. Essentially, the catalog manager keeps track
of the names of entities within the database, such as users, schemas, tables, columns,
19


indexes, etc. and their relationships. It is in and of itself stored as a set of tables within
the database. High-traffic areas of the catalog are generally materialized within main
memory as needed. In addition to that, the catalog data is cached in query plans at
parsing time, often in a denormalized form. [1]
Memory allocator.
Database management systems memory management should not be completely
focused on the buffer pool. Database systems also allocate large amounts of memory to
other tasks. Things such as query joins and sorts require a significant amount of memory
at runtime. As a rule, most DBMS use a context-based memory allocator. A memory
context is an in-memory structure, which maintains a list of regions of contiguous virtual
memory or rather memory pools. [1] Every region can have a header that contains a
context label or a pointer to the context header structure. The basic API for memory
contexts include calls to create a context with a given name or type, allocate a chunk of
memory within a context, delete a chunk of memory within a context, delete a context, or
reset a context, clearly providing software engineering advantages. But, memory
contexts also provide performance advantages where the overhead for malloc() and free()
are high. This is due to the fact that memory contexts have the ability to use semantic
knowledge on how memory will be allocated and deallocated and thus can accordingly
call malloc() and free() to minimize OS overhead.
Another advantage to memory allocators is that it can call malloc() to allocate
large regions. This will eliminate the issue of needing to call free() for many small
objects, incurring a high expense. [1]
20


CHAPTER
III. CLOUD COMPUTING
What is cloud computing
There are thousands of different definitions and explanations as to what cloud
computing is and that many opinions to go along with the subject matter. A most
infantile definition of cloud computing would be that it is Internet based computing. It
allows users to access technology-enabled services over the Internet. The National
Institute of Standards and Technology (NIST) gives a more precise definition of cloud
computing as,
Cloud computing is a model for enabling convenient, on-demand access
to a shared pool of configurable computing resources (e.g., networks,
servers, storage, applications, and services) that can be rapidly provisioned
and released with minimal management effort or service provider
interaction. [2]
Mobile
PC

A
Internet
<
PDA\Phones
Figure III.l Cloud Diagram. [3]
21


Cloud computing provides computational software, data access as well as storage
services to end-users. It typically involves providing dynamically scalable and more
often than not, virtualized resources. Generally, the cloud architecture contains multiple
components, which must communicate with each other over different application
programming interfaces. The two most significant components of a cloud computing
architecture are the front end and the back end. The front end is the piece that the normal
end user will see and the back end is the cloud itself. [2]
Typically the goals and characteristics of a cloud are to be highly scalable,
available, reliable, secure, flexible, serviceable, and efficient. A cloud must be scalable
or also known as elastic. This may be the most important characteristic of a cloud. This
means that it would be anticipated that applications within a cloud environment would
scale to meet the demands of the workload automatically. This way, performance as well
as service levels are not compromised. Its important to note that the cloud should not
just scale up, but also down in times where the demands are lower. Availability is
another critical characteristic of a cloud. An application deployed in a cloud is up and
running 24/7/365, basically every minute of every day. The next characteristic is
reliability. A cloud must always be reliable. Applications cannot fail or lose data when
they are in the cloud. Upon a server crashing, the users should not notice any degradation
in service. The next characteristic is security. Security within a cloud is an extremely
controversial topic with many complex issues surrounding it. Here it simply means that
an application inside the cloud must be resilient to unauthorized access. Users must be
able to feel confident that their data is secure. Flexiblility in a cloud dictates that the
cloud must be compatible with the most efficient means to deploy an application.
Another important aspect of a cloud is that it must be serviceable. Serviceable implies
that in the event it is necessary to modify any of the underlying cloud architecture, the
application is not disrupted during this time period. Finally, the last common goal and
characteristic of cloud computing is to be efficient. Users must have the ability to
quickly deploy applications in the cloud. This allows for users to reduce operational
costs and provide its customers with greater transparency through technology. [4]
22


Cloud 'Stack'
Target
Customer
SaaS
PaaS
laaS
End Users
Developers
Operators/
IT
Figure III.2 Cloud Stack. [5]
As depicted above, the cloud architecture is made up of multiple layers, the client,
application, platform infrastructure and server. It is possible to share services within any
of the layers and often times, service providers offer services that are either at the
software, platform or infrastructure layer. The client layer consists of computer hardware
and software that is dependent on the cloud for application delivery. Cloud application
services, also known as software as a service (SaaS), sometimes referred to as on-demand
software, has the ability to deliver software to users over the Internet. This eliminates the
necessity to install and run applications on a customers computer. This also helps to
simplify the maintenance and support of the application. The vast majority of SaaS
solutions are based n multitenant architectures where there is one version of the
application, which is used for all customers (rather tenants). Many times in SaaS, the
applications do not support customization but instead promote configuration. This means
that the tenants have the ability to set options that affect functionality and the look and
feel of the application. SaaS also promotes accelerated feature delivery where
23


applications are updated more frequently than traditional software, open integration
protocols and collaborative functionality. [6]
Cloud platform services, platform as a service (PaaS), allow for users to have a
computing platform and solution stack as a service. This helps in the deployment of
application due to the fact that users do not have to purchase the required underlying
hardware to support the application. Many also feel that PaaS helps to facilitate
application design, development, testing, deployment, and hosting.
Cloud infrastructure as a service (IaaS) provides the computer infrastructure,
which is more often than not a platform virtualization. It supplies users with basic
storage and computational capabilities. Finally, servers layer consists of the products,
which are necessary to deliver the cloud to the end user.
There is one final layer that is up and coming and will be covered more in the
trends section of the document, which is database as a service. Database as a service
(DaaS) attempts to move the operational burden of provisioning, configuration, scaling,
performance tuning, backup, privacy, and access control away from database users to the
service provider. DaaS is so appealing because it promises to offer scalability as well as
being an economical solution. It will allow for users to take advantage of the lack of
correlation between workloads of different applications, the service can also be run using
fewer machines than if each workload was individually provisioned for its peak. [7]
The final piece in understanding cloud computing is the different infrastructure
models, which consist of public, private, and hybrid clouds. Generally, third party
vendors develop public clouds. In the majority of public clouds, applications from
multiple different customers are mingled together on the clouds servers, storage system
and networks. One of the benefits of a public cloud is that it can be much larger than a
private cloud could aspire to be. It has the ability thus to offer scaling up or down on
demand. Private clouds are built for one specific company, which allows for better data
control and security. The company therefore owns the infrastructure and maintains
complete control of the cloud. Lastly is the hybrid cloud. This cloud infrastructure
model combines both the public and the private clouds in order to provide on-demand,
externally provisioned scalability. This type of cloud model has additional complexities
such as determining how to distribute applications across both a public and private cloud.
24


Thus, the relationship between the data and the application must be understood for best
performance in this type of cloud. [4]
Benefits and Motivation of Cloud Computing
Many companies want to utilize clouds because they are cheaper, scalable,
provide easy remote access, faster provisioning of applications, the list goes on and on.
Getting up and running within a cloud is quick and easy. When you consider that you do
not need to invest in any type of infrastructure, hardware, technical support, and all users
need in order to access information and data is the Internet. There is also no need to
worry about storage in a cloud since storage is virtually limitless. Clouds additionally
provide the scalability that many companies need with just the click of a button.
Basic Trends in Cloud Computing
The different service cloud layers and ultimately the available services within
those layers are driving many of the trends in cloud computing. The first trend is the
utilization of virtual machines in clouds. Virtual machines are the standard deployment
model now for cloud computing. Especially when running a relational database in the
cloud. Many IaaS as well as PaaS utilized virtual machines to accommodate for demand.
This is evident when looking at Amazon Elastic Compute Cloud (EC2). EC2 allows for
its customers to basically rent virtual computers to run their applications on. EC2 utilizes
Xen virtualization where each virtual machine, or rather instance, functions as a virtual
private server.
SaaS is driving the trend of multitenancy in the cloud. With multitenancy in the
database, this allows for effective resource sharing for customer applications that have
small but varying resource requirements. Multitenancy thus obliterates the need for
separate systems for each tenant. This means lower subscription fees for individual
tenants and higher hardware/system utilization for the service provider. Looking at a
real-world example of multitenancy, Salesforce.com is probably the most familiar service
provider that utilizes multitenancy in both the application and the database. [8]
Cloud computing has started the trend of everything must be on-demand and users
want to pay as they go. The very essence of cloud computing refers to the provisioning
25


of computational resources on demand. Again, the primary influence in this area is
Amazon EC2. They specifically state that they have on demand instances that let you
pay for compute capacity by the hour with no long-term commitments. They promote
that this allows for the users to alleviate the costs and complexities of planning,
purchasing, as well as maintaining hardware, which are incredibly expensive. [9] The
reason that this trend is important is that it has given rise to the need for elastic
scalability/load balancing. Users expect for a vendor to have the ability to automatically
distribute incoming traffic across multiple instances. Now, users want their applications
to scale up when necessary and down when the demand is not warranted. Thus, only
paying for what they absolutely need.
Finally, a trend that is taking place by many of the large vendors is offering DaaS.
DaaS hosts databases in the cloud environment and also provides database features like
data definition, storage and retrieval. Such vendors as Amazon, Microsoft, and Google
have begun offering this service. Amazon Relational Database Services (RDS) is
available to users for when an application requires a relational database and users want to
reduce the time spent on data management. Amazon also offers Amazon EC2, with a
relational database Amazon Machine Image (AMI) for when applications require a
particular relational database and the customer would like to maintain complete control
over the database. The instance runs the database and the data is actually stored within
an Amazon Elastic Block Store (EBS) volume. As previously mentioned, Microsoft also
offers a similar feature, SQL Azure. This is their cloud-based relational database service,
which is built on SQL Server technologies. It is highly available, scalable, multi-tenant
database service that is hosted in the cloud. It is beneficial to users because it helps to
ease provisioning and development of multiple databases. Finally, Google AppEngine
Datastore offers DaaS. It was built on BigTable (which is non-relational) and has the
ability to store richer data types including lists, which contain collections within a single
item. [10]
As a follow up on the previous trend, Amazon will be making Oracle 1 lg
available via Amazon RDS in the near future. This will be the first time that Oracle is
available in a public cloud. This is a huge accomplishment since Oracle is the king of
26


relational databases management systems it brings us one step closer to having a full
relational database in the cloud. [11]
Rise of Multitenancy
Multitenant database architecture is where many users, typically unrelated when
placed into the context of a cloud, make use of shared resources. In a cloud, this allows
for multiple customer applications to be consolidated, removing the need for separate
systems for each tenant. Multitenant database architectures can reduce the total cost of
ownership because multiple businesses are consolidating onto the same operational
system.
Sharing resources at different levels of abstraction and distinct isolation levels
allows for various mutitenancy models. These levels are shared machine, shared process
and shared table.
27


CHAPTER
IV. MULTITENANT DATABASES IN CLOUD COMPUTING
Multitenant databases in a cloud can handle high traffic volumes at low cost. It
can reduce the total cost of ownership by aggregating customers together and leveraging
economy of scale. This includes money for hardware, software, operational expenditures
for bandwidth and personnel. Multitenancy allows for pooling of resources. This
improves the utilization by eliminating need to provision each customer for maximum
load. The goal of a multitenant database in a cloud is to minimize the number of
machines required while still maintaining query and application performance goals.
Ultimately, multitenant data platforms must minimize operating cost by efficient resource
sharing. [7]
Shared Machine Multitenancy Database Architecture
In this multitenant architecture, each customer receives their own database
process but multiple customers can share the same machine. This means that each tenant
has their own set of data that is logically isolated from data, which belongs to other
tenants.
Benefits of multitenant databases in cloud computing
Tenant
132
Tenant
680
Tenant
4711
Figure IV.l Shared Memory Architecture [12]
28


This approach does not require that the implementation of the database be
modified. It also does not does not reduce customer isolation. A draw back of this is that
executing administrative operations in bulk is not possible each database can and will
execute queries on its own. In this multitenant architecture, the primary limitation is that
it does not pool memory, each database requires is own connection pool for every
application server thus, sockets cannot be shared among customers. Here though,
customer migration is more straightforward due to the fact that each customer receives
his or her own database process. This can also mean that if the vendor pre-allocates a
specific amount of space for the database, there could end up being a large amount of
wasted space when the database is smaller. [13]
Shared Process Multitenant Database Architecture
Shared process architecture gives each customer their own tables but multiple
customers share the same database process. This method still offers a logical degree of
isolation for each tenant. In general, it does not matter whether or not customers receive
their own schema but it is useful for them to receive their own physical table space. This
enables the customer to easily migrate their data by simply moving a file from one server
to another. This approach is better at pooling memory than the previous architecture.
Since only one database exists in the shared process architecture, customers can easily
share connection pools. It also opens the door to the fact that one customer could
possibly access another customers data or prevent the other customer from getting a
reasonable amount of resources. [13]
29


Database
Tenant 132
Tenant 680
asss**^ iggsags




Tenant 4711
Figure IV.2 Shared Process Architecture [12]
This method can support a larger number of tenants per database server. This
method makes restoring a tenants data in the event of a failure much more difficult.
Since each tenant only has their own schema, restoring the entire database could mean
overwriting the data of every other tenant on the same database. [12]
Shared Table Multitenant Database Architectures
The final multitenant architecture, shared table allows for data from different
customers to be stored in the same table. Here, a column is added to every table so that
the owner of each row can be identified. This means that every query must specify a
value to reflect which tenant should be evaluated. In order for customers to be able to
extend the database schema, every table contains a fixed number of generic columns.
30


TenantlD ICustName j Address
4j TenantlD I ProductID 1 ProductNanv
1 4| TenantlD Shipment Date
6 l] 4711 324965 2006-02-21
4 6| 132 115468 2006-04-08 '
4} 680 654109 2006-03-27 '
4711 324956 2006-02-23^
Figure IV.3 Shared Table Architecture [12]
The shared table architecture is the best at pooling resources and has the ability to scale
up as needed, due to the fact that it is only limited to the number of rows that the database
can hold. Another benefit to this architecture is that since there is only one table,
administrative tasks can be executed in bulk by simply executing the queries that range
over a specific tenants rows. On the other hand, a downside to this approach is that
migrating a users data to the table can be difficult and require executing data
manipulation language against the production table. The intermingling of different
customers data can also cause for performance issues since one customers data can be
spread out across many different pages. One of the significant drawbacks to this
architecture is that queries intended for a single customer must contend with data from all
the customers, ultimately compromising any query optimization. Continuing to evaluate
the fact that there is only one shared table, it must be understood that if one customer
wants to place an index on their specific column(s) then all customers must have that
index.[13]
Multitenant Architectures and Cloud Service
In these different models, the tenants data can be stored in different forms. The
following table makes the connection between the database multitenancy architecture and
the cloud computing service.
31


# Sharing Mode Isolation IaaS PaaS SaaS
1. Shared hardware VM / /
2. Shared VM OS User /
3. Shared OS DB Instance /
4. Shared instance Database /
5. Shared database Schema /
6. Shared table Row / /
Figure IV.4 Multitenant Database Architecture and Cloud Services. [14]
While exploring the suitability of the architecture with the various scenarios, IaaS
provides the lowest level of abstraction such as raw computation, storage and networking.
Supporting multitenancy in the IaaS layer is much more flexible and allows for different
schemas for sharing. PaaS providers give a higher level of abstraction to its tenants. For
PaaS providers that have a single data store API, a shared table or instance can meet data
needs for the platform. But, PaaS providers, which have the ability to support a variety
of data stores, have the potential to leverage any multitenant database model. Finally,
SaaS, which has the highest level of abstraction, the shared table architecture is the most
optimal. [14]
32


CHAPTER
V. CURRENT CHALLENGES IN MULTITENANT DATABASES
IN CLOUD COMPUTING
Overview of database type challenges
There are many issues surrounding multitenant databases in cloud computing as
well as databases in general existing in cloud computing. One of the biggest issues, is
that multitenancy introduces contention for shared resources, such as CPU, RAM and
I/O. This also makes it more difficult to support scalability due to the fact that the
resources are shared. Other issues surrounding databases and cloud computing include,
database schema consolidation, partitioning, indexing, query optimization, security,
network latency, whether or not a transactional database should even exist in a cloud and
more.
Overview of Multitenant Architectural Challenges
In evaluating the three previously mentioned multitenant architectures, shared
machine, shared process, shared table, there are faults or specific implications with
resource sharing, which pertain to each of them.
Shared machine/hardware architecture challenges
The shared machine architecture, where each customer receives their own
database process and multiple customers share the same machine, is very popular due to
the fact that it does not require any modifications to an existing database and provides
great tenant isolation. [13] Unfortunately, scalability is poor since running independent
database instances not only wastes memory but also CPU cycles. It is obvious to see that
the number of instances grows linearly with the number of tenants. Thus, this model
cannot scale beyond tens of customers per server. We can start to get a vivid
33


understanding of the sheer numbers required to simply startup independent databases
instances if we evaluate MySQL DBMS. MySQL consumes 30 MB of memory on
startup alone. We can also see that there is a large amount of disk space that is wasted
since each database instance must be allocated a finite amount of disk space to even run.
[24]
Since this architecture requires sharing resources at the machine level, this could
potentially mean using multiple virtual machines or sharing virtual machines by using
different user accounts or different database installations. Here, there is no database
resource sharing only sharing of machine resources. Each database instance and VM is
sharing a common pool of physical computing resources. Utilizing the machine in such a
way requires 2 to 3 times more machines to consolidate the same number of workloads,
which ultimately offers 6 to 12 times less performance. [7]
One of the major implications to this architecture is that there is a substantial cost
incurred due to redundant components and lack of coordination using limited machine
resources in an unoptimized way. Each VM must contain a separate copy of the
operating system and database. The database therefore has its own buffer pool and each
database must have its own logs to disk, etc. Therefore, a way and method to dictate how
the shared resources will be dived up to the different instances must be established. Its
obvious from this potential architecture that shared hardware is not the most efficient way
to share and utilize resources. [13]
Shared process architecture challenges
In the shared process architecture, customers get their own tables within the
database instance. [13] Thus, multiple customers share the same database processes. We
can clearly see with this architecture the number of private tables grows linearly with the
number of tenants. Therefore, we are limited by the number of tables a database can
store/handle and the amount of available memory. As an example, IBM DB2 allocates
4KB of memory for each table; so 100,000 tables consume 400MB of memory right off
the bat. [8] Since memory buffers are allocated in per-table manner, buffer space
34


contention occurs among the tables for the remaining cache. I/O can be balanced by
distributing customers across different disks.
Similar to the previous architecture, the shared process architecture can involve
sharing database processes at various isolation levels. This could imply sharing only the
installation binary, or sharing database resources such as logging, buffer pools to sharing
the same schema and tables.
An example of shared processes would be RelationalCloud, SQLAzure or
ElasTranS. [14]
Shared table architecture challenges
The shared table architecture data from a tenant is not only in the same database
schema, but data from many customers is stored in same table. Generally, this
architecture is achieved by appending a tenant id attribute to tuples in order for them to
be recognized as belonging to a specific tenant. This provides the best pooling of
resources and has the ability to scale up is only limited by the number of rows a database
can handle. Which itself is dependent on the amount of available memory. [24]
But, this architecture also allows for tables to be extremely sparse due to the fact
that there are a large number of attributes that not all tenants utilize. Hence leaving a
large number of null vales in any given table. This leads to wasted disk space and poor
performance since it is difficult to index any of the data due to the fact that it is unlikely
tenants are using the same columns. [24]
There is a large hit with shared table when it comes to the basic necessary
functionality of a database. There must be query optimization, table scans, explain plans
and statistics are very costly in this architecture. There is a large contention for cache
pools, but cache pools do not work as effectively since queries from multiple tenants
could potentially be hitting the database at any given time. An example of shared table
would be Salesforce.com. [14]
Resource Allocation and Workload Balancing
The goal of efficient multitenancy is to minimize the number of machines
required, while still meeting performance goals. Given a group of databases and their
35


associated workloads, what is the best way to serve them from a designated set of
machines? Therefore, the system must understand the resource requirements of each
separate workload. [7] Resource allocation within a multitenant database, means multiple
things, verifying that each tenant has enough resources to properly function as well as
load balancing and scaling to meet the needs of each tenant. The multitenant architecture
must be able to handle ill-behaved tenants. When a tenant begins to consume an
excessive amount of resources, there must be a way to validate that other tenants do not
experience slow down, blocking or throttling.
Monitoring resources.
There is a combination of DBMS and OS resources that must be evaluated. The
resources that ultimately need to be monitored are CPU, RAM and disk I/O including
buffer pool utilization and log flushes. Its crutial to decipher how an individual database
is consuming each resource so that it is readily apparent how the database will behave
once it is combined with other databases and what databases are good candidates to be
consolidated onto the same machines.
One of the issues with resource monitoring and DBMS is gauging how much
RAM is truly being used. RAM is a resource that is difficult to monitor within a DBMS.
When the DBMS is the primary service on a machine, the OS tends to overestimate the
actual resources, which are required and reports back the total memory that is allocated to
the database process. The database will fill the buffer pool even if the working set is
smaller than the buffer pool. This means that unless the application is actively accessing
the entire buffer pool at maximum throughput, the DBMS can operate identically with
less RAM. Thus, a way to verify the actual usage of RAM for a DBMS is required. [28]
Predicting combined workload
Combining the workloads of multiple databases means that there must be a way to
predict the combined resource requirements when multiple workloads are consolidated
onto a single server. Unfortunately, it is very difficult to determine the combined
workload for disk I/O.
36


There are multiple reasons as to why predicting disk performance of a set of
database workloads is difficult. First, a DBMS tends to exploit unused disk bandwidth to
flush dirty buffer pool pages back to disk when it notices that the disk is underutilized.
This makes it difficult to estimate minimum I/O requirements. Secondly, disk I/O grows
sub-linearly with workload size. Next, complex interaction between the DBMS, OS and
disk controller makes it strenuous to predict how sequential or random the combined set
of workloads will be. Finally, there are many hardware and software configurations,
which impact the I/O throughput a system can achieve. [28]
Workload consolidation.
After monitoring the resources and predicting combined workload, the final task
left to do is the actual combining of the different databases. This could mean that we are
given hundreds of databases that should be combined and now it is up to us to decide
which hardware they should all be placed on. This activity is strenuous since we are
trying to minimize the number of machines required to support a specific workload
combination as well as balance the entire load across machines while not exceeding their
capacities. We have to take into account each workloads disk, memory, and CPU
necessities while looking at a given machines available resources. [28]
Scaling/Elasticity
Elastic scalability refers to the ability to accommodate for databases of different
size and workload requirements. When the workload of the database exceeds the
capacity of a single machine, then it must support scaling out. [7]
A multitenant database in a cloud system must be able to support scale-out. This
is an important concept for resource allocation and keeping operational costs negligible.
Elasticity allows for the query processing to be partitioned amongst multiple nodes so
that the maximum throughput can be achieved. The system must therefore be able to
determine when to migrate, which cells or databases should migrate and where they
should relocate. The scaling/migration must also be done efficiently so that there is very
minimal disruption and no impact in service. [29]
37


Database Schema Design Issues
It is common practice for a cloud service provider to map multiple single-tenant
logical schemas to one multitenant physical schema in the database. This can be very
difficult and fundamentally there are limitations as to the number of tables that a database
can handle. In order to achieve acceptable consolidation, certain tables must be shared
among tenants and certain tables must be mapped into fixed generic structures.
Determining which should be shared and which should not be is not a trivial task. [8]
In the cloud, multitenant data management must also be able to account for an
increasing number of tenants without performance degradation. Thus, the system must
be scalable. This gives rise to additional issues, tables are too sparse and indexing on
shared tables is not effective. When data is stored in large shared tables, this produces an
extensive number of NULL values in each row. NULL values waste disk bandwidth and
undermine the efficiency of query processing. Secondly, since the amount of data is
quite large in a multitenant architecture, it is especially important to develop an efficient
indexing technique to efficiently retrieve data from a shared table. If the index were to be
created where they encompass the entire table, performing an index scan would be
incredibly inefficient and degradable to performance. [24]
Challenges Recognized But Not Resolved In This Paper
There were many different aspect and challenges of cloud computing and
databases that were recognized and investigated. All of which are legitimate concerns
within the area, but for this thesis, their possible solutions were not investigated. Below
the challenges are laid out.
Transactional databases.
There has been must debate as to whether or not a transactional database belongs
in the cloud. For good reasoning, the authors of Data Management in the Cloud:
Limitations and Opportunities make the conclusion that they should not reside in the
cloud. As the authors look at the main characteristics of a cloud, which in essence are
38


the previously discussed benefits of cloud computing, it is possible that transactional
databases may not have the ability to take advantage of many of those benefits.
First, a cloud is meant to have elastic computing power. This means that when
there are changes in the environment, additional computational resources can be allocated
on the fly to handle the new demands. These resources are generally in the way of
additional server instances. A transactional database is typically not a share-nothing
architecture, which means that it might not be able to take advantage of the additional
server resources to handle the load. Thus, scalability might be extremely difficult.
Second, data in a cloud is stored at an untrusted site. Though this paper is not
looking into the security of cloud computing, this is still an important concept especially
when it comes to transactional databases. This means that there is an increase in potential
security risks, making the need to encrypt the data in the database a must. The majority
of data in a transactional database is mission-critical business data. This data needs to be
protected and secure which is much more difficult in the cloud.
Third, a cloud is able to provide high availability and durability, which is done by
replicating the data across large geographic distances. In a transactional database, this
would make maintaining ACID (Atomicity, Consistency, Isolation and Durability
guarantees that a databases transactions are processed reliably) impossible. [15]
Maintaining ACID compliancy is most notably the largest issue that transactional
databases have with existing in a cloud. ACID complicates elastic load balancing,
scalability, live migration and performance of the database as noted above.
Security.
The multitenant architecture must be able to isolate one tenants database from
anothers. This includes verifying that a tenant only has access to their specific data and
that the database itself is secure from outside access. As the number of tenants grows,
securing the database can become more and more complicated.
Network latency.
39


Though we understand that network latency is an issue that plagues all types of
databases whether transactional or a data warehouse (or even multitenant which we will
get to in a minute) that reside in a cloud, we will not be researching a solution for this
issue. There are multiple reasons for latency. One reasons for latency in a cloud
database is the physical proximity of the user, database and application to each other.
When evaluating the location of the database and the application, it is found that latency
in the cloud is proportional to how far apart the application and the database are to each
other. As the application and the database get further and further apart, latency increases.
Thus, it is important to try and migrate not only the database to the cloud but also the
application. [20] An example of this issue can be seen with Salesforce.com.
Salesforce.com began to offer its users a new relational database as a service (DaaS),
Database.com. This database only serves as a backend for applications that are running
on say, Amazon, Google or elsewhere. This means that the database and the application
are not close in proximity to each other and thus, users have found issues with latency
when running their applications. In order to best utilize Database.com, users must have
their applications running on Force.com. [21] This appears to be a spectacularly
orchestrated business move by Salesforce.com.
Latency can also play a factor when we look at the physical location of the
customer relative to the cloud, which houses their applications and/or database.
Customers should always try to use a cloud that is closes to their physical location. The
more routers and distance between the customer and the cloud, the higher the latency will
be. Finally, customers should strive to take advantage of WAN (Wide Area Network)
optimizations. This can help to minimize the impact of bandwidth restrictions and work
to give users the best possible link between themselves and their data and application.
Understanding this type of information better helps us to better understand what we must
do in order to optimize our applications and databases in the cloud. [22]
The above latency issues deal strictly with locality and infrastructure, but there
are other reasons for latency in the cloud. The number of concurrent users can directly
impact the number of transactions that can occur per second. Its important to correctly
configure a database to only allow for a maximum number of concurrent users as to not
40


degrade performance. Latency can also be attributed to I/O bottlenecks. These
bottlenecks can be directly related to high disk latency as the service provider. [23]
Administrative issues.
As previously mentioned, depending on the multitenant architecture,
administrative functions can be difficult. When the architecture is shared machine, the
isolation between customers causes executing administrative operations in bulk
impractical. It is necessary to execute the administrative queries on each database
individually. In the shared process architecture, executing administrative operations in
bulk is doable. But, operations such as adding customers, removing customer and
extending the base schema entail executing DDL statements. This is problematic for
databases, which behave poorly when their schemas are modified. Finally, shared table,
administrative operations can be executed in bulk but queries must include the correct
range over the necessary tenant columns.
Data warehouses.
A data warehouse can be thought of as a database that is mainly utilized for
reporting. It is a snapshot of a production database at some point in time. These types of
databases do not generally have transactions and can be integrated with different business
intelligence tools in order to more easily extract data. One of the largest issues
surrounding placing a data warehouse into a cloud is the size/amount of the data that
resides in the database. There are limitations on how much data a specific cloud service
provider will allot any one customer as well as there are issues with actually migrating
the data into the cloud. When dealing with a small amount of data, lets say under
100GB, there are more options available to customers than dealing with larger data sets
that can be in the terabytes of data range. With 100GB or less, users can make decisions
to have their data warehouse as consistent with production data as desired. When users
have multiple terabytes of data, then there is less flexibility in what can be easily
accomplished as far as consistency is concerned. There is also a need here to evaluate the
different options that service providers have in order to migrate the data into the cloud.
41


Amazon AWS offers an import/export tool, which allows for 60TB or more to be loaded
in less than 1 days time but the data must be sent to Amazon, via snail mail for them to
actually load it. If a user has less than 5 TB of data and an Internet connection that was
100Mbps, then it would take them 1 to 2 days to load the data into the cloud at any given
moment themselves. [17] These same types of issues surround Google App Engine as
well as Microsofts Azure. Google App Engine simply suggests utilizing test or .csv files
to migrate data into the cloud. But, does not offer any type of assistance to migrate large
amounts of data. This could cause tremendous time delays and make any type of
consistency of data between production data and the data warehouse difficult. [16]
Microsofts Azure has a 50GB maximum database size limit at this point in time. Azure
suggests that data is divided into smaller sizes so that it can more easily be loaded. It is
speculated that Azure has a 50GB limit so that performance is always maintained.
Keeping the data size small makes backups and recovery easier. [18]
These limitations proved to be too much for John Hopkins University as they
attempted to put an existing scientific (astronomical) database known as the Sloan Digital
Sky Survey (SDSS) in the cloud. They attempted this with two separate cloud providers,
Amazon (EC2) and Microsoft (SQL Azure). When the users attempted to migrate the
data to EC2, they utilized a 100GB subset of the database (which is approximately 1/3 5th
size of the actual data). They were also unsuccessful in actually getting queries on the
data to run faster than on a single server. The users had even less luck when they tried to
migrate the data to Azure. They were unable to load all the data and the migrating tools
that were provided by Microsoft automatically stripped out several features that rendered
the data unusable such as functions and stored procedures. [19] This simply proves the
validity of the data set size limitation.
Other issues which plague data warehouses in clouds are fault tolerance and the
ability to run in a heterogeneous environment. Due to the fact that many times in data
warehouses, there is a large amount of data and/or queries against the data, which are
extracting a large data set, its important that the DBMS/ architecture surrounding the
data warehouse is fault tolerant. Fault tolerance for a data warehouse means that a query
does not have to be restarted if one of the nodes involved in the query process fails.
When we evaluate how often a node in a cloud environment fails and the fact that
42


extremely complex queries on large amounts of data could utilize hundreds (or even
thousands) of server instances for hours, the likelihood for failure is extremely high. If
the cloud and data warehouse cannot handle these faults, it will be extremely difficult to
complete any query or analysis. [15] Finally, the data warehouse must be ability to run in
a heterogeneous environment. The performance of the nodes in a cloud may not be
consistent, which means that some nodes will out perform other nodes by an order of
magnitude. Ideally, work that needs to be executed in a query will be equally divided
across all nodes. Upon one node degrading in performance, the cloud should have the
ability to take the appropriate measures to offload the work of the failing node to a
different node(s). This ability would also help to improve the total query latency. This is
not an easy feat for many service providers. But, is a necessity for customers
contemplating placing their data warehouse into the cloud. [15]
43


CHAPTER
VI. CURRENT SOLUTIONS TO CHALLENGES
Resource allocation and workload balancing
One of the first challenges that cloud providers are faced with is making the
determination of where to place the different databases/tenants within the system in order
to minimize the number of machines required, while still meeting performance goals.
There are consequently three keys to workload balancing within a multitenant
architecture, monitoring resources, predicting combined workload and performing the
tenant consolidation. There are three possible solutions that we explore in this section for
efficient resource allocation and workload management.
First, the authors of Relational Cloud: A Database-as-a-Service for the Cloud
propose placing tenants and associated workload onto a set of nodes (or machines) that
are dedicated only to that workload. During this phase, they will monitor the resources
that are consumed and generate a time dependent resource profile that will allow for them
to predict how the workload will eventually interact with other tenant workloads that are
currently running within the system. The authors propose monitoring, predicting and
consolidating workloads through an engine called Kairos. [7] Kairos monitors CPU,
RAM and disk I/O, analyzes the resource consumption for each database over time so
that is may produce an assignment of databases to physical machines, finally, it performs
the actual consolidation of the databases. [28]
Resource monitoring by Kairos involves querying the OS and DBMS running on
each machine in order to generate statistics about CPU, RAM and disk I/O, buffer pool
utilization and log flushes. CPU usage for the consolidated workload is simply the sum
of the CPU loads of every members workload. Unfortunately, RAM is not so easy to
measure. The statistics that are provided by the OS overestimate the actual resources that
are required since they only report the total memory allocated to the database and not the
memory that was actually in use. Therefore, in order to estimate the actual amount of
RAM that is used, the authors propose gauging the buffer pool. In order for a DBMS to
44


operate efficiently, the working set should remain in main memory. As a result,
techniques that estimate the working set of a database so that it can be determined
whether or not two databases are consolidated together must be devised. The authors
state that the initial step is to determine if the system is over provisioned. This can be
done by collecting information pertaining to OS disk reads and DBMS buffer pool miss
ratios. If the miss ratio in the buffer pool is close to zero this tells us that the working set
fits within the buffer pool. If the miss ratio of the buffer pool is high but there are few
physical disk reads then the working set does not fit in the buffer pull however, it does fit
in the OS file cache. Finally, if there exists high buffer pool miss ratios and a lot of
physical disk reads, the working set size exceed both the memory available in the buffer
pool and the OS file cache, causing it to read from disk continuously. This last scenario
indicates that memory is definitely not over provisioned and that the total RAM available
to the DBMS is actively utilized. But, for the other scenarios, its vital that we are able to
measure the amount of memory that is being utilized either in the OS file cache or in the
buffer pool. In order to do this, they authors issue SQL queries to a DBMS that is
unmodified. First, they generate an empty probe table and grow it slowly. While
growing the table, they force the DBMS to keep pages in the buffer pool by running
queries several times for every insert. They then monitor disk reads by the DBMS. By
gingerly stealing buffer pool cache space as well as observing how many pages the
DBMS reads back from disk, they are able to detect when they start to push useful pages
out of the buffer cache. One additional important detail is how often to probe the table.
This requires very careful balancing so that the table is probed often enough for the
buffer manager to keep data in RAM but not so often that CPU overhead is added.
Therefore, the authors propose querying the probe table once every 1-10 seconds to that
the DBMS keeps the probe data in RAM and CPU overhead down. [28] On the simpler
side, in order to understand disk I/O usage, OS tools such as iostat give an easy way to
estimate the disk I/O.
Next the authors address how to estimate combined workloads. When it comes to
estimating resource requirements for combined databases, CPU and RAM is not
complicated, we would simply sum the CPU and RAM for each individual workload that
45


could possibly co-located. But, for determining combined load estimations for disk is
much more complicated.
The issue is the database utilizes unused disk bandwidth to proactively work
through other tasks like flushing dirty pages from the buffer pool, I/O throughput grows
sub-linearly with the workload size which is dictated by the user, it is hard to predict
exactly how sequential or random a combined set of workloads will be and finally, there
are numerous hardware and software configuration parameters that influence the I/O
throughput a system can ultimately achieve. Therefore, measuring the actual amount of
disk I/O can be difficult with the workloads are combined. The authors suggest that
regardless of the number of databases a DBMS hosts, it must coordinate I/O between the
databases by combining log writes from the different workloads into a single sequential
stream of log writes allowing for group commits to be leveraged. It must also delay
write-back operations of dirty pages for all of the different databases and perform them in
sorted order to minimize disk seeks. The authors attempt to address the fact that the
complex behavior of the disk subsystem makes modeling the I/O requirements difficult
by treating the system as a black box and experimentally deriving its transfer function.
[28] Thus, they developed a tool that automates the process of collecting experimental
data from the live system and then builds an empirical model that captures disk
behavior. The tool records row updates per second, the working set size in bytes and the
complete disk throughput in bytes per second. The outcome is a map of the system
response to different degrees of load and working set sizes. This map can then predict
how multiple workloads will behave once combined. [28]
Now that they developed a technique to determine combined disk estimations,
they must now assign workloads to different physical servers to find an assignment that
minimizes the number of machines as well as balances the load across those machines.
Therefore, the created a function:
46


minimize X Ct'n-ri)) signum(^xtJ)); ij X
subject to Vi ^2, = j
Vj maxt (y~] CPUtx xtJ) < MaxCPUj; t
Vj maxtiT^ MEMh xlJ) < MaxMEMj;
Vj diskModel(DISKlt,xtj) < MaxDISKj',
additional placement constraints
Vi,jxtJ e Ar;0 < xX} < 1
Equation VI. 1 Consolidation Precition Function [28]
In the above figure, x,:/ =1 when workload i is assigned to server j and 0
otherwise, and R, is the number of replicas desired for workload i. MaxCPUj, MaxMEMj,
MaxDISKj are the maximum amount of CPU, RAM, and disk I/O available at server /,
and Cti is the time series describing the utilization of resource C (CPU, RAM, disk) for
workload i at time t. [28] The authors state that their function accomplishes minimizing
the number of servers that are required for consolidation by using signum functions that
are equal to 1 when input is greater than 0 and 0 when its input is 0. This model provides
that any solution using k-1 servers will have a lower objective function value than any k
server solution. The authors state that when there is at least one workload assigned to a
server, they can evaluate the servers contribution by evaluating its resource utilization
over time Cti, causing for unbalanced solutions to be penalized. There are also
constraints that guarantee the feasibility of any solution. The CPU, RAM and disk
constraints allow for the combined load imposed on each server to never exceed the
available resources at any given moment, which therefore avoids saturation and over
commitment of a server.
Finally, the model that they established allows for them to handle replication and
workload placement issues. The replication variable controls how many replicas of each
workload need to be placed. Thus, they are able to achieve high consolidation factors
47


and balance loads across servers without deteriorating the throughput of the consolidation
workloads. [28]
Scalability/Elasticity
Live migration enables elastic load balancing and scalability with no downtime
and minimal disruption of multitenant databases, which reside in a cloud computing
environment. There are many ways in which live migration can be implemented. This
section will review three of those techniques.
One method to accomplish live migration is based on the concept of virtualization
in the database layer. In this method, the goal is to decouple the logical representation of
a cell (a cell is a self-contained granule of application data, meta data, and state
representing a tenant in the database) from the node hosting it. The authors of Live
Database Migration for Elasticity in a Multitenant Database for Cloud Platforms utilize
what is known as an iterative copy technique, which attempts to transfer the main
memory state of the cell in order for the cell to restart warm at the destination node. The
main memory state of the cell is comprised of the cached database state and the
transaction execution state. In general, the database state consists of the cached database
pages or buffer pool or some variant of this. The transaction state includes the active
transaction and possibly a subset of committed transactions, which are needed to validate
the active transactions. The live migration presented here has two main phases.
48


Owning
DBMS Node
Source DBMS Node (>!)
Destination DBMS Node (N^*)
f Pre Migration Phase Toi,T t \
0. Normal Database Operation | 1. Migration Phase | 1. Normal Database Operation
Time
lb. Synchronize
and Catch-up 1
I
la. Begin Migration
Snapshot state at NK
Initialize at
lc. Atomic Handover Phase
Stop serving at
Synchronize remaining state
2. Post Migration Phase
Start serving at N*
Resume normal operation
Figure VI. 1 Database Migration Timeline. [29]
Phase 0 can be thought of the database operating in normal mode, executing
transactions. Phase 1 is known as the migration phase. This phase notifies the source
node and the destination node to start migration. There are multiple sub-phases to phase
1. Phase la begins the migration by taking a snapshot of the database state at the source
node. The snapshot is then migrated over to the destination node and the migration of the
specific cell is initialized. Note that the source node must continue to process
transactions while the migration is in progress. Phase lb is the actual iterative copy
phase. Due to the fact that the source node continues to server the cell that is migrating
while the snapshot is being moved to the destination node, the state of the migration cell
at the destination node will be behind the actual state at the source node. The iterative
copy attempts to catch-up and synchronize the states between the destination node and
the source node. Phase lc is the actual atomic handover of ownership of the migrated
cell to the destination node. The source node stops serving the cell and copies the final
un-synchronized state to the destination node, flushes all changes from committed
transactions to the persistent storage. Finally, phase 2 is the post migration and marks the
restarting of operations. This iterative copy migration allows for minimal service
49


disruption as opposed to other techniques such as stop and copy or on demand migration.
In stop and copy, the service to a specific cell is stopped, the data is copied and migrated,
and then service is started once again. In On demand migration, minimal information is
transferred during what is known as a quick stop and copy migration. Thus, it is easy to
see why this option is much more appealing than other proposed solutions. [29]
Another method that has been introduced as an option for performing live data
migration is a technique, which takes advantage of on-demand pull and asynchronous
pushes of data. The authors of Zephyr: Live Migration in Shared Nothing Databases for
Elastic Cloud Platforms utilize this synchronous dual mode in order to allow for both the
source and the destination nodes to execute transactions. First, the tenants metadata is
migrated to the destination node. At which point in time, the destination node can begin
serving new transactions while the source node is completing any transactions that were
active when the migration began. Here, read and write access or rather ownership of the
database pages are partitioned between the source and destination nodes where the source
node initially owns all the pages and the destination node only acquires pages ownership
on-demand as transactions at the destination node access the pages. Its also important to
note that index structures are replicated from the source to the destination during the
migration. Synchronization between the source and destination is necessary during the
short dual mode. Zephyr does not rely on the database layer, which allows for it to
provide better flexibility in choosing the destination for migration, which may or may not
have the tenants replica. [27]
The authors of Relational Cloud: A Database Service for the Cloud present the
third live migration and elastic scalability technique. They believed that the solution in
elastic scalability could be accomplished through database partitioning. The partitioning
strategy that the authors propose is focused around OLTP and Web workloads, which
means that they are well suited for short-lived transactions. Consequently, they must
partition the data in such a way that they can minimize the number of multi-node
transactions. When the number of nodes is not minimized, then there is an increase in the
time spent holding locks. Therefore, they analyze execution traces so that they can
identify sets of tuples that are accessed together within individual transactions. These are
represented as a graph where each node is a tuple and an edge is drawn between two
50


nodes whose tuples are touched with a single transaction. The weight on the edge will
represent how many times the tuple is accessed in the workload. The authors then use
graph partitioning to find / balanced logical partitions, while trying to minimize the total
weight of the cut edges. The goal is to hopefully find a partitioning of the database tuples
that minimizes the number of distributed transactions. The relational cloud must now
find a very concise representation of the partitions so that SQL statements can be
appropriately routed; this is done by defining a set of predicates on the tuple attributes.
Therefore, given a set of tuples, and a partition label for each tuple, the system can
extract a set of candidate attributes from the predicates used in the trace. Once this is
complete, the attributes are given to the decision tree algorithm along with the
partitioning labels. If the decision tree can successfully generalize the partitioning with
just a few predicates, what is considered a good explanation for the graph partition is
found. Otherwise, the system must use lookup tables to represent the partitioning
scheme. [7]
This approach allows for independence from the schema layout as well as the
foreign key information. The authors state that this allows for intrinsic correlations
hidden in data. [7] But, this also means that the approach is only effective when it comes
to partitioning databases containing multiple many-to-many relationships. The technique
furthermore encounters difficulties since it cold lead to a graph with N nodes and N2
edges for an N-tuple database. [7]
Database Schema Issues
As previously alluded to, it is common practice for customers that are migrating
to a multi-tenant cloud environment to need to map a single tenant schema to the
multitenant schema in the database. This can be extremely challenging to a service
provider to create a base schema, which allows for the tenants to be easily map. It also
introduces an issue of shared tables being too sparse as well as the inability to effectively
utilize indexing. All of these issues cause for the unnecessary usage of resources. First,
we will look at a way to map schemas to maximize efficiency within the database. Then,
we will evaluate a technique that limits the number of null fields and provides indexing
for multitenant architectures that are shared table
51


The authors of Multi-Tenant Databases for Software as a Service: Schema-
Mapping Techniques suggest that specific tables must be shared among tenants and
others must be mapped to fixed generic structures. The basis of this new schema is to
help implement multi-tenancy on top of a standard (existing) relational database. Thus,
they introduce a new schema-mapping technique called Chunk Folding, where logical
tables are vertically partitioned into chunks that are folded together into different physical
multi-tenant tables and joined as needed. [8] The authors also take the meta-data and
divide it between application specific tables and a large fixed set of generic tables called
Chunk Tables. An example of this would be as follows:
Figure VL2 Chunk Folding Example. [8]
The initial chunk is a row is stored in a table that is associated with the entity
Account. The second chunk is also stored in a conventional table associated with an
extension for health care. All remaining chunks are stored in different chunk tables.
The best performance is obtained by mapping the most heavily utilized parts of
the logical schema into the conventional tables and the rest into Chunk Tables, which
match their structure as close as possible. Through experimentations, the authors are able
to find that narrow Chunk Tables encounter a large overhead for reconstructing the rows
whereas wider Chunk Tables are more competitive in their performance to a conventional
table. [8]
Chunk folding is not the only technique for schema mapping. But, chunk folding
is the only technique, which tries to account for the logical schemas of tenants, the
52


distribution of data within those schemas and the application queries that go along with
them. First there is a basic layout technique. This technique is extremely easy to
implement, by adding a tenant ID column to each table and share the tables among the
different tenants. This approach allows for good consolidation but no extending
capabilities. Next we look at extension table layout, extensions are split into separate
tables, where tenants may share extensions. This implies that the extension tables as well
as the base tables must have a tenant column. Here, a row column must be created so that
the logical source tables can be reconstructed.
AccountExt
Tenant Row Aid Name
17 1 Acme
17 1 2 Gump
35 0 1 Ball
42 0 1 Big
HealthcareArrn..n.
Tenant Row Hospital Beds
17 0 St. Mary 135
17 1 State 1042
AutomotiveAccount |
Tenant Row Dealers
1 421 0| 651
Figure VI.3 Extension Table Layout. [8]
Thus, at runtime in an extension table layout, the reconstruction of the logical
source tables carries a large overhead due to the additional joins and I/O if the row
fragments are not clustered together. A draw back to this approach is that the number of
tables will grow in proportion to the number of tenants. Other schema mapping
techniques include universal table layout and pivot table layout. The solution that we are
more concerned with is the chunk table layout structure and the actual chunk folding.
Tenant Table Chunk Row Inti Strl
17 0 0 0 1 Acme
17 0 1 0 135 St. Mary
17 0 0 1 2 Gump
17 0 1 1 1042 State
35 1 0 0 1 Ball
42 2 0 0 1 Big
42 2 1 0 65
Figure VI.4 Chunk Table. [8]
53


The chunk table layout is effective when data can be partitioned into dense
subsets. The chunk table has a set of data columns of different types, with and without
indexes. There is also a chunk column where each logical source table is partitioned into
groups of columns each with a chunk id. This reduces the amount of stored meta-data
and the overhead for reconstructing the logical source tables. This approach also allows
for a precise way of adding indexes and splitting overly wide columns. But, it generates
more complicated query transformations. Now, chunk folding comes into play where
logical source tables are vertically partitioned into chunks, which can be folded together
into different physical multi-tenant tables and joined as required.
AccountRow
Tenant Row Aid Name
17 0 1 Acme
17 1 2 Gump
35 0 1 Ball
42 0 1 Big
Chunky
Tenant TaBleXhun
17
17
42
0
0
2
li
ow Inti
0
0
135
1042
65
St. Mary |
State
Figure VL5 Chunk Folding. [8]
The above example shows where Accounts are placed into a conventional table
and extensions are placed in a single chunk table. The databases metadata is divided
between application-specific conventional tables and large fixed sets of chunk tables. [8]
Next, we look at a possible solution for limiting the sparsity of tables as well as
how indexing on multitenant shared tables can be accomplished. The authors of
Supporting Database Applications as a Service introduce M-Store, which provides
storage and indexing services for multitenant databases. To account for the additional
problems that arise they introduce Bitmap Interpreted Tuple (BIT) and Multi-Separated
Index (MSI). M-Store utilizes shared tables to achieve optimal scalability in a
multitenant cloud. In this environment, when using shared tables, tenants store their
tuples to the shared tables by appending each with a TenantID, which signifies which
tenant the tuple belongs to and setting unused attributes to NULL. Consequently, this
54


creates the issue of shared tables being too spared. In order to make the base schema
general, the service provider must cover each possible attribute that the tenant may use,
thus leading to creating the base schema as a huge number of attributes. On the other
hand, the tenant more than likely only utilizes a small handful of the attributes, allowing
for a substantial amount of NULLs to be stored in the shared table. Using BIT, only
values from configured attributes are stored in the shared table. Thus, NULL values from
unused attributes are not stored. To achieve this, a bitmap string is constructed for each
tenant that resolves which attributes belong to that tenant and which do not. Next, tuples
are stored and retrieved based off the bitmap string created for each tenant. Further detail
gives evidence that the length of the bitmap string is directly proportional to the number
of attributes in the base schema. Each position in the string corresponds to whether or
not an attribute is used by setting the value to 1 or 0 respectively. Therefore, when a
tenant performs a tuple insertion, NULLs in attributes where their position corresponds to
a 0 in the bitmap string are removed. The bitmap string can also be utilized to retrieve
specific attributes. The second piece of M-store, MSI, accounts for the fact that since the
amount of data is large in a shared table, there must be an efficient indexing technique
utilized to retrieve tuples. Instead of building an index for all tenants, they build an index
for each specific tenant. Though the number of indexes grows linearly with the number
of tenants, given a particular attribute, only a small portion of tenants will build an index
on that attribute. This makes index scans more efficient due to the fact that each tenant
need only scan their own index files and tuples. [24]
55


CHAPTER
VII. CONCLUSION
Overview
With the increasing number of applications that are being deployed onto cloud
platforms, the need for being able to efficiently manage resources for a multitenant
database is real and increasing. Multitenant databases in a cloud must have the ability to
perform live migration for effective load balancing and elasticity as well as have the
ability to properly monitor, predict and consolidate database workloads accurately in
order to achieve efficient resource management.
Best Architecture
DBMS architecture
Defining a very specific database system architecture is critical for obtaining the
optimal results when trying to perform live migration or workload consolidation. We
propose that a parallel database is utilized with a shared disk memory architecture. This
will allow for all processors to access disks with roughly the same performance, but they
will be unable to access each others RAM. A parallel database will improve
performance of loading of data, index building and evaluation of queries. Parallel
databases are specifically instrumental when dealing with large databases that process a
large number of transactions. It will increase throughput, improve response time, has the
ability to process a large numbers of transactions without issues, provides substantial
performance improvements, increases the availability of the system and server a large
number of users. [26] Furthermore, shared disk architecture is ideal for cloud computing.
It allows for clusters of low-cost servers to be used as a single collection of data and can
easily be served by a storage area network (SAN) or a network attached storage (NAS).
Shared disk also supports elastic scaling since one can easily add another server to
increase throughput. Shared disk also lowers administrative costs since servers can be
56


upgraded individually without taking the entire cluster offline. Not only that, but shared
disk provides high availability which is a necessity in cloud computing. Finally, shared
disk will allow for a multitude of data partitioning options, which can help with overall
performance of the system [25]
Now that the overall database model has been provided, the focus is turned to an
overall system setup. Shared process is the most feasible multitenant architecture that is
available to and for the majority of tenants. Though, it has not gone unnoticed that
SalesForce has had tremendous success with shared table, shared process fits in better
with my concepts of efficient resource management of multitenant databases in a cloud
environment. Therefore, the authors of Live Database Migration for Elasticity in a
Multitenant Database for Cloud Platforms were on the right path with some of their
multitenant database system architecture decisions. One of the most important concepts
is that the logical representation of a tenant should be decoupled from the physical server
that is hosting it. Below is the representation of the multitenant database model the
authors of the article designed. We will further expand on this design.
Tenant Applications
Controller
>
DBMS
Nodes
Tenant Transactions
Query Router
DBMS Node
n Tenant Cell
r U Cached DB State
V 1
_ t tenant Cell (TM + DM) Transaction State
Loa Manaeer
- Data Flow
-----> Control Flow
Figure VII.1 Database Architecture Model [29]
57


First, the architecture must decouple the ownership by using network attached
storage (NAS). This will allow for the actual DBMS data to be stored persistently. This
will also provide scaling of the storage layer for additional capacity as well as
throughput. This will also allow for the transfer of ownership from one DBMS node to
another when live migration is performed and prevent the need to migrate any actual
data. This will make the live migration must quicker. Next, a tenants transactions
should be isolated to a single node. If we can anticipate that a tenant is small enough to
be consistently serviced by a single node, this will remove the need for distributed
synchronization among all the nodes for transactions. During migration, we can be
guaranteed that the transactions processed by a tenant are only interacting with one node.
The third design in the architecture is that there must exist some type of abstraction,
which conceals the dynamics within the DBMS from the tenants. Is should be
unnecessary for the tenant to realize which physical machine hosts their data. Therefore,
when users issue queries, there must be some type of query router that hides how the
queries are routed to the correct DBMS node hosting the cell. This way, when live
migration is performed, it will be seamless in the tenants eyes. They will not need to
understand how to redirect their queries. Later, the query router will play an intricate role
in the system as overall. The next item in the multitenant cloud environment model,
ideally, would allow for each DBMS node (pictured above) to run a single DBMS
instance and host multiple tenants. This means that each tenant that is hosted by a node
would share the buffer pool and logging infrastructure for maintaining transaction logs.
By sharing the logs among the different cells, this prevents multiple independent and
competing disk writes, which could come about by having the different tenants logging at
different times and therefore improve overall performance. [29] It would be anticipated
that each DBMS node has a large shared buffer pool in its own memory that has the
ability to dynamically adjust the size based on system needs and available resources. It is
also important to enforce how the data is laid out across the different disks it has
available. Since sequential access is much quicker than random access, the DBMS must
place blocks onto the disk so that queries have the ability to access the data sequentially.
The DBMS clearly understands its workload access patterns far better than any
underlying OS, thus the DBMS must have full control over spatial positioning of the
58


database blocks on disk. Therefore, there should exist a file system on each disk (or
logical volume) within the DBMS to allow for the DBMS to allocate a single large file in
each of the file systems and control the placement of data within that file. It is possible to
recommend that the DBMS stores data directly to the raw storage device, this would
make the portability of the DBMS more difficult. As a result, the DBMS should control
where the data should be placed on disk, we also need for the DBMS to dictate when the
data is physically written to disk. The main reasons for this have been previously
discussed in section 2.6.2, but it is important to recall that his will directly impact the
transactional databases ACID compliance as well as improve overall system
performance. [1]
Database normalization.
Database normalization is the process of minimizing redundancy and dependency
related to fields and tables of a relational database. The objective of normalization is to
isolate data so that additions, deletions and modifications of fields are made in only one
table and then propagated throughout the rest of the database through defined
relationships. [31]
There are many benefits to a database from normalization. It provides better
overall database organization, reduces the amount of redundant data, provides data
consistency within the database, gives a more flexible database design and finally it
presents a better handle on overall security. It is also easy to see that this methodology
conserves disk space by minimizing duplicate data and the potential of inconsistent data
is reduced since the data has been broken into smaller tables, finally, the database is more
flexible as far as modifying existing structures. Since redundant data does not exist, it is
easier to grant limited table access. [32]
The major disadvantage of normalization is that it reduces database performance.
Upon a user querying the database, there are factors such as CPU usage, memory usage
and I/O usage that must be taken into consideration. A normalized database requires
much more CPU, memory and I/O in order to process a transaction and queries. The
59


normalized database must first locate the requested tables and then join the data from all
the tables together in order for the request to be processed.
There are multiple Normal forms. They are numbered from the lowest form of
normalization, first normal form, through the fifth normal form. Fifth normal form is
rarely seen or utilized. First normal form (INF) eliminates duplicate columns from the
same table and creates separate tables for each group of related data. Each row also has a
unique column or a multiple columns as the primary key. Second normal form (2NF)
follows all the requirements of first normal form but also removes subsets of data that
apply to multiple rows of a table by placing them into a separate table. It also creates a
relationship between the new tables and predecessors via foreign keys. Third normal
form (3NF) must meet all the rules for second (and thus first) normal forms as well as it
removes columns that are not dependent upon the primary key. Boyce-Codd normal
form (BCNF) must meet all the requirements of third normal form and also every
determinant must be a candidate key. Fourth normal form (4NF) must meet all the
requirements of third normal form but also have no multi-valued dependencies. [30]
There is also a denormalization process that a database can undergo. This process
involves modifying table structures to allow for a controlled redundancy in order to
increase database performance. A denormalized database and a database that has not
been normalized are different things. [30]
Ideally, the database normalization for our system should not go beyond second
normal form. This way, we could maintain all of the concepts that are important with
relational, transactional databases but at the same time we can anticipate there will not be
an increasing number of join statements for queries to work properly. Therefore, there
will be no overall performance degradation due to the additional overhead of SQL
statements.
Resource Allocation & Load Balancing
Monitoring resources.
The authors of Workload-Aware Database Monitoring and Consolidation
provided us with some information pertaining to how they would monitor CPU, RAM
60


and disk I/O, buffer pool and log flushes. Their ideas are good for gauging RAM in a
database, but can be tuned to be more accurate. In order to guage the working set size of
the specific tenant, it would be much more accurate to use queries which pertain to the
application than just determining the working set size based on queries that are not even
relevant to the tenants database. If we were to initially hold a database in a staging area
prior to integrating it with other tenant databases, (This concept is also utilized in the
indexing and partitioning section of the paper, 7.5.) this would allow for the collection of
common queries and accurate statistics on resources since the database is on designated
hardware as this point. Then these queries that are issued could easily be simulated for
performance testing. If we begin to witness a miss ratio of the buffer pool that is close to
zero, then we should decrease the size of the buffer pool, simulate the queries again and
evaluate the miss ratio. Eventually, this process will allow for us to identify the smallest
amount of RAM that is required for the database to function correctly. If on the other
hand, we are experiencing high buffer pool miss ratios but hardly any physical disk reads
or high buffer pool miss ratios and high physical disk reads, we can increase the size of
the buffer pool until we are able to come close to a zero miss ratio of the buffer pool.
This would help to make a determination on the minimum size our buffer pool
should be as well as the minimum amount of RAM that is required for the database to
function correctly.
Predicting combined workload
When evaluating combined CPU usage, it is true, as stated by the authors of
Workload-Aware Database Monitoring and Consolidation that the CPU usage found
above, in the monitoring section, can simply be added together to obtain a total CPU
usage of the combined workload. For RAM, it was previously established the minimum
size that a buffer pool needs to be in order to hold the working set of a specific database,
therefore, the sum of the amounts could be calculated between the databases that are to be
considered for consolidation. Finally, predicting the combined workload for disk I/O can
be estimated to be the sum of all disk EO across the combined systems.
61


Another factor that should be taken into consideration when predicting a
combined workload and which databases should be consolidated together is each
databases peak hours. This is the timeframe that the database is utilized the most
heavily. Many databases sit idle for long periods of time with quick peaks of utilization.
Depending on where the majority of customers or users reside, the hours in which the
database/application is utilized could be extremely different. Two databases with
opposite workloads could potentially be combined onto the same server since peak times
will not conflict with each other. Ultimately, this would be a statistic that is easily
collected when collecting information related to resource usage.
Workload consolidation.
When consolidating workloads, there is one additional step that should be taken in
order to maximize efficiency, the top queries that have been identified for each databases
working set, should be pinned in the buffer pool. It is possible that since the database
that is to be migrated into the multitenant environment will be held in a staging area first
where statistics and information pertaining to the database and workload can be gathered,
then we should be able to assume that during this point in time, majority of the queries
against the database have been accounted for. We should be able to see which of those
queries are continuously being called and which tables are being utilized. Since in
DBMS there is a concept of pinning items within the buffer pool. We could pin tables in
memory so that access times to heavily used tables can be improved. [1]
Live Migration
Additional ideas should be included when performing live migration. The main
concept of live migration, which has already been presented (see section 6.2), can be
utilized but other concepts can and should be taken into consideration to further optimize
the process.
The first proposed change would be in the determination of when to perform live
migration. If again the concept of a query router is created, which was initially presented
by the authors of Relational Cloud: A Database-as-a-Service for the Cloud, as well as
62


the authors of Live Database Migration for Elasticity in a Multitenant Database for
Cloud Platforms, we could ultimately utilized the query router to not only route
transactions/requests to the appropriate DBMS node [29] that is hosting the tenant, but
we could also use it to monitor SQL statements, estimate the cost of queries and finally
provide a degree of performance isolation by controlling the rate in which queries are
dispatched. [7]
The first concept of the query router directly correlates with our multitenant
database model to mask the physical location of a tenants data from the tenant. The
query router first and foremost will be responsible for routing the query to the proper
node. [29] Next, the query router should also review queries that are being executed to
identify their access patterns. Once we have information pertaining to their access
patterns we can better make decisions surrounding database partitioning and indexing
(which will be discussed in more detail below). This could also lead to us potentially
modifying the query optimizer to better execute certain queries that can be seen
repeatedly running against different database. This will allow for us to identify a
working set on the different DBMS nodes. The option to modify the query optimizer
must be made available.
Furthermore, the query router could ultimately estimate the cost of a query or a
set of queries based on the available resources of the system. In order to accomplish this,
the query router would need to keep track of which DBMS node a query is being routed
to along with the potential cost of the query, which is provided by the query optimizer
(discussed in section 2.4), the arrival time of the SQL request and finally, the service
level agreement (SLA) requirements for performance/time restrictions. Ultimately, the
query router would make a decision on which SQL requests should run concurrently and
whether or not the requests exceed the resources readily available on the machine and
would potentially violate SLA. The system would need to continuously recalculate
available resources and costs as query results are returned to make sure SLA standards
are being satisfied. Now, the query router is functioning to control the rate at which
tenant requests are being made to specific nodes within the system. We also now have a
way to recognize that the required resources to meet SLA are not available and live
migration must take place.
63


Partitioning and Indexing
One of the key factors for deciding to use a shared process multitenant
architecture within the cloud is to allow for the ability to add indexes to increase database
performance as well as partition data based on a specific tenant.
For each separate tenant, the query router should monitor how many times it has
seen the same or similar query as well as how long the query takes to return results (as
previously mentioned). Keeping track of which fields are being referenced in the query
and the amount of time a query is running for will allow for us to know which fields
should be indexed and in what orders. If the same queries are repeatedly called over and
over, then we want to optimize the system to handle those queries. We want to maintain
non-clustered indexes where three or less indexes exist on any given table. One of the
indexes will be for the primary key of the table. Since we are dealing with a relational
database, we know that there will exist a primary key on every table. Then also allow for
one or two additional indexes on a given table based on the frequency of a query or a
query taking an extended amount of time. It would be ideal if the query router would
continuously monitor which fields of a table are constantly being accessed and if it
changes over time, then we would be allowed to drop and recreate the indexes based on
the new evidence. Though, in all actuality, it is unlikely for applications to have
changing queries over time.
What this has ultimately done is tried to optimize the fields that are being used
and not just create indexes on data that are not even utilized. That is a waste of space and
resources. Now, logic should be introduced to the system so that is would be smart
enough to possibly re-arrange how a query is structured so that the indexes can be
guaranteed to always be utilized every possible query.
Finally, by having the query router keep track of which queries are being
executed, allows for gathering of information pertaining to how data should be
partitioned within the database. Not only that, due to the structure of the system, this has
now allowed for the data to be partitioned based specifically on a tenant and their
activities. The data should be both horizontally and vertically partitioned. The vertical
partitioning should be based on the columns that are accessed on a consistent basis by
64


queries. The horizontal partitioning should be related to breaking up tables with a large
number of rows. Again it is possible for the query router to identify which areas of a
table are being utilized. This would determine where to divide the database. Once we
have identified which columns are vertically partitioned, that data should be placed on
hardware that has better I/O performance. This will allow for the most active areas (hot
spots) within the database to be faster than if the data only existed on traditional disks.
In order to account for all of these different factors for data access, the database
could initially be migrated to a staging area where it is on dedicated hardware. Then
upon migrating the system into the multitenant environment, the recommended indexes
and partitions would be applied. From there, they would continue to be monitored by the
query router.
65


REFERENCES
1. Joseph M. Hellerstein Michael Stonebraker, James Hamilton, Architecture of a
Database System, Foundations and Trends in Databases, v.l n.2, p.141-259,
February 2007
2. Wikipedia, (2011, May 2). Cloud Computing, [Online], Available:
http://en.wikipedia.org/wiki/MSI_protocol
3. Unknown. (2009, August 13). Advantages of Cloud Computing, [Online],
Available: http://contactdubai.com/webhosting/advantages-of-cloud-computing
4. Introduction to Cloud Computing Architecture, 1st ed., Sun Microsystems, Santa
Clara, CA, 2009
5. Randy Bias, (2009, Sept 29). Cloud Standards are Misunderstood, [Online],
Available: http://cloudscaling.com/blog/cloud-computing/cloud-standards-are-
mi sunder stood
6. Wikipedia, (2011, May 07). Software as a Service, [Online], Available:
http://en.wikipedia.org/wiki/Software_as_a_service
7. Curino, Carlo et al. "Relational Cloud: A Database-as-a-Service for the Cloud."
5th Biennial Conference on Innovative Data Systems Research, CIDR 2011,
January 9-12, 2011 Asilomar,California
8. Stefan Aulbach; Torsten Grust; Dean Jacobs; Alfons Kemper; Jan Rittinger;,
Multi-Tenant Databases for Software as a Service: Schema-Mapping
Techniques, In Proceedings of the ACM SIGMOD International Conference on
Management of Data, SIGMOD 2008, Vancouver, BC, Canada, June 10-12,
2008, pages 1195-1206. ACM, 2008
9. Amazon, (2011), Amazon Elastic Compute Cloud, [Online], Available:
http://aws.amazon.com/ec2/
10. Mateljan, V.; Cisic, D.; Ogrizovic, D., "Cloud Database-as-a-Service (DaaS) -
ROI," MIPRO, 2010 Proceedings of the 33rd International Convention, vol., no.,
pp. 1185-1188, 24-28 May 2010
11. Amazon, (2011). Amazon RDS running Oracle Database, [Online], Available:
http://aws. amazon. com/rds/oracle/?utm_source=OraclePR&utm_medium=RDSL
andingPage&utm_campaign=Oracle
12. Frederick Chong, Gianpaolo Carraro, Roger Wolter, (2006, June), Midti-Tenant
Data Architecture, [Online], Available: http://msdn.microsoft.com/en-
us/library/aa479086.aspx
13. Dean Jacobs and Stefan Aulbach. (2007). Ruminations on Midti-Tenant
Databases [Online], Available: http://cloud.pubs.dbs.uni-
leipzig.de/sites/cloud.pubs.dbs.uni-
leipzig.de/files/Jacobs2007RuminationsonMultiTenantDatabases.pdf
14. A. Elmore, S. Das, D. Agrawal, A. El Abbadi. Whos Driving this Cloud?
Towards Efficient Migration for Elastic and Autonomic Multitenant Databases.
Technical Report 2010-05,CS,UCSB, 2010.
66


15. Daniel J. Abadi, Data Management in the Cloud: Limitations and Opportunities,
IEEE Data Eng. Bull., vol. 32, no. 1, pp. 3-12, 2009
16. Google, (2011). Uploading and Downloading Data Google App Engine,
[Online], Available:
http://code.google.com/appengine/docs/pvthon/tools/uploadingdata.html
17. Amzaon, (20 l l). A WS Import Export, [Online], Available:
http://aws.amazon.com/importexportv/
18. Lubor, (2010, Jul 30). Loading data to SQL Azure the fast way, [Online],
Available: http://blogs.msdn.com/b/sqlcat/archive/2010/07/30/loading-data-to-
sql -azure-the-fast-wav. aspx
19. Ani Thakar and Alex Szalay. 2010. Migrating a (large) science database to the
cloud. In Proceedings of the 19th ACM International Symposium on High
Performance Distributed Computing (HPDC '10). ACM, New York, NY, USA,
430-434
20. Ian Murphy, (2010, June 10). Why Databases Must Follow the Application to the
Cloud, [Online], Available: http://www.computerweeklv.com/blogs/database-
notes/2010/06/whv-databases-must-follow-the-applications-to-the-cloud.html
21. Eric Knorr, (2010, Dec 7). What Salesforces Database.com really means,
[Online], Available: http://www.infoworld.com/t/cloud-computing/what-
salesforces-databasecom-reallv-means-759
22. John Considine, (2010, Mar 04). Cloud Latency issues, [Online], Available:
http://www.cloudswitch.com/blog/tag/cloud%201atencv%20issues
23. Sean Porter (2010, Mar). Fix 10 bottleneck by throwing disks at it! EC2 Style,
[Online], Available: http://portertech.ca/fix-vour-io-bottleneck-bv-throwing-
disks-at-i
24. Mei Hui; Dawei Jiang; Guoliang Li; Yuan Zhou;, "Supporting Database
Applications as a Service," Data Engineering, 2009. ICDE '09. IEEE 25th
International Conference on vol., no., pp.832-843, March 29 2009-April 2 2009
25. Mike Hogan. (2008, November 14). Cloud Computing & Databases How
Databases can meet the demands of cloud computing [Online], Available:
https://docs.google. com/viewer?a=v&q=cache:sS9SAVRVePoJ: www.scaledb.co
m/pdfs/CloudComputingDaaS.pdf+&hl=en&gl=us&pid=bl&srcid=ADGEEShL3
muPWNagHHC HNJcq_Dp41ZDc04pk68rkeW 13aG9r87NbDd43 lP7IwTYJLt9
qU ohW QXKOPPGWK S eNSF iugDg YyuUHPy OKD 5 a J Cy rXmfm4EdoXF mObXr
4Z8SbawOMOT3-Pr2&sig=AHIEtbRVkbGoiy71L5eOjbvwxAyBoWx81Q
26. S.K. Singh, Parallel Database Systems, in Database Systems: Concepts, Design
and Applications, 1st ed. Prentice Hal, 2009, ch. 17, pp 527-537.
27. Aaron Elmore et al. Zephyr: Live Migration in Shared Nothing Databases for
Elastic Cloud Platforms. SIGMODll, June 12-16, 2011 Athens, Greece
28. Carlo Curino; Evan Jones; Samuel Madden; Hari Balakrishnan; Workload-
Aware Database Monitoring and Consolidation, SIGMOD ll. June 12-16,
Athens, Greece, 2011
29. S. Das, S. Nishimura, D. Agrawal, and A. El Abbadi. Albatross: Lightweight
Elasticity in Shared Storage Databases for the Cloud using Live Data Migration.
PVLDB, 4(8): 494-505, May 2011.
67


30. Wikipedia. (2012, March 19). Database Normalization [Online], Available at:
http://en.wikipedia.org/wiki/Database_normalization
31. Mike Chappie. (2012). Database Normalization Basics [Online], Available at:
http://databases.about.eom/od/specificproducts/a/normalization.htm
32. Ronald Plew and Ryan Stephens. (2003, January 24). The Database
Normalization Process [Online], Available at:
http://www.informit.com/articles/article.aspx?p=30646
33. Wikipedia. (2012, March 5). Partition (Databases) [Online], Available at:
http://en.wikipedia.org/wiki/Partition_%28database%29
34. Wikipedia. (2012, March 22). Database Index [Online], Available at:
http://en.wikipedia.org/wiki/Database_index
68


Full Text

PAGE 1

STUDY OF RESOURCE MANAGEMENT FOR MULTITENANT DATABASE SYSTEMS IN CLOUD COMPUTING B y Christine G. Martinez B.S., University of Colorado, Denver, 2004 A thesis submitted to the Faculty of the Graduate School of the University of Colorado in partial fulfillment of the requirements for the degree of Master's of Science Computer Science and Engineering 2012

PAGE 2

ii This thesis for the Master 's of Science degree by Christine G. Martinez has been approved for the Computer Science and Engineering by Ilkyeun Ra, A dvisor Gita Alaghband, C hair Tom Altman Date ___ 4/10/2012 ____ _________ ___

PAGE 3

iii Martinez, Christine, G. (M.S ., Computer Science and Engineering ) Study Of Resource Management for Multitenant Database Systems in Cloud Computing Thesis directed by Professor Ilkyeun Ra. ABSTRACT Cloud computing can offer the business community higher availability, guaranteed throughput and service rate, higher reliability, security, and cost effect ive maintenance. These very attractive benefits create the growing popularity of cloud computing, and make many companies eager to migrate their existing database applications to the cloud. In the cloud, most of these applications share processors, memory disk spaces, and databases with other companies' applications. The cloud service providers run multiple tenants' databases in the cloud and therefore needs an effective resource sharing management method in order to allow users to keep lower overall c osts without loss or degrading quality of their services. Thus, developing an efficient resource management for multi tenant database system in cloud is essential for both business community and cloud providers. To build an efficient resource management, two key technical components that must be addressed. First, is how to create a workload aware system, this means being able to monitor resource consumption, predict a combined workload of multitenant databases and finally identify which workloads can be co located on a database server to achieve the best consolidation and performance that is possible. The second component is having the capability to scale out. Elastic scalability allows for the support of multiple databases and workloads,

PAGE 4

iv which range in size. When processing exceeds the capabilities of one node, we must be able to spread the workload across multiple nodes in order to achieve higher throughput. This thesis attempts to provide a comprehensive look at current technical issues surrounding e fficient resource management of multitenant databases in cloud computing so that we are able to answer the above two questions. To achieve our goal, we will explore how a database management system operates and performs work. This will enable a better sen se of the atmosphere where the multitenant databases will reside and why clouds are becoming so popular. Finally, we will present our study result of multi tenant database, including possible architectures, current resource management issues, and proposed solutions and lastly, new ideas on how to solve these problems. Approved: Ilkyeun Ra

PAGE 5

v DEDICATION I dedicate this work t o my husband, Andres Martinez

PAGE 6

vi TABLE OF CONTENTS CHAPTER I. INTRODUCTION ................................ ................................ ................................ ....... 1 What is being researched and investigated ................................ ....................... 1 Thesis Layout ................................ ................................ ................................ .... 1 II. DATABASE MANAGEMENT SYSTEM ARCHITECTURE ................................ .. 4 Introduction to database management systems ................................ ................. 4 Processing m odels. ................................ ................................ ............................ 5 Buffers ................................ ................................ ................................ ............... 8 Memory architectures ................................ ................................ ..................... 10 Shared memory. ................................ ................................ .................. 10 Share Nothing. ................................ ................................ .................... 11 Shared disk. ................................ ................................ ......................... 12 Query Processor ................................ ................................ .............................. 13 Parsing. ................................ ................................ ................................ 13 Rewrite. ................................ ................................ ............................... 13 Optimizer. ................................ ................................ ........................... 14 Executor. ................................ ................................ ............................. 15 Indexing and Partitioning ................................ ................................ ................ 15 Indexing. ................................ ................................ ............................. 16 Partitioning. ................................ ................................ ......................... 17 Storage Management ................................ ................................ ...................... 17 Location. ................................ ................................ ............................. 17 Buffering. ................................ ................................ ............................ 18 Transactions ................................ ................................ ................................ .... 19

PAGE 7

vii Understanding Shared DBMS Components ................................ ................... 19 Catalog manager. ................................ ................................ ................ 19 Memory allocator. ................................ ................................ ............... 20 III. CLOUD COMPUTING ................................ ................................ ............................. 21 What is cloud computing ................................ ................................ ................ 21 Benefits and Motivation of Cloud Computing ................................ ................ 25 Basic Trends in Cloud Computing ................................ ................................ .. 25 Rise of Multitenancy ................................ ................................ ....................... 27 IV. MULTITENANT DATABASE S IN CLOUD COMPUTING ................................ 28 Benefits of multitenant databases in cloud computing ................................ ... 28 Shared Machine Multitenancy Database Architecture ................................ ... 28 Shared Process Multitenant Database Architecture ................................ ........ 29 Shared Table Multitenant Database Architectures ................................ ......... 30 Multitenant Architectures and Cloud Service ................................ ................. 31 V. CURRENT CHALLENGES IN MULTITENANT DATABASES IN CLOUD COMPUTING ................................ ................................ ................................ ................... 33 Overview of database type challenges ................................ ............................ 33 Overview of Multitenant Architectural Challenges ................................ ........ 33 Shared machine/hardware architecture challenges ............................. 33 Shared process architecture challenges ................................ ............... 34 Shared table architecture challenges ................................ ................... 35 Resource Allocation and Workload Balancing ................................ ............... 35 Monitoring resources. ................................ ................................ ......... 36 Predicting combined workload. ................................ .......................... 36 Workload consolidation. ................................ ................................ ..... 37 Scaling/Elasticity ................................ ................................ ............................ 37

PAGE 8

viii Database Schema Design Issues ................................ ................................ ..... 38 Challenges Recognized But Not Resolved In This Paper ............................... 38 Transactional d atabases. ................................ ................................ ..... 38 Security. ................................ ................................ .............................. 39 Network latency. ................................ ................................ ................. 39 Administrative issues. ................................ ................................ ......... 41 Data warehouses. ................................ ................................ ................ 41 VI. CURRENT SOLUTIONS TO CHALLENGES ................................ ........................ 44 Resource allocation and workload balancing ................................ ................. 44 Scalability/Elasticity ................................ ................................ ....................... 48 Database Schema Issues ................................ ................................ ................. 51 VII. CONCLUSION ................................ ................................ ................................ .......... 56 Overview ................................ ................................ ................................ ......... 56 Best Architecture ................................ ................................ ............................ 56 DBMS architecture ................................ ................................ ............. 56 Database normalization. ................................ ................................ ...... 59 Resource Allocation & Load Balancing ................................ ......................... 60 Monitoring resources. ................................ ................................ ......... 60 Predicting combined workload. ................................ .......................... 61 Workload consolidation. ................................ ................................ ..... 62 Live Migration ................................ ................................ ................................ 62 Partitioning and Indexing ................................ ................................ ................ 64 REFERENCES ................................ ................................ ................................ ................. 66

PAGE 9

ix LIST OF FIGURES Figure II.1 Main Components of a Database Management System. [1] ................................ ....... 4 II.2 Process Per DBMS Worker.[1] ................................ ................................ ................... 6 II.3 Thread Per DBMS Worker.[1] ................................ ................................ .................... 7 II.4 Process Pool.[1] ................................ ................................ ................................ ........... 8 II.5 Shared Memory Architecture.[1] ................................ ................................ .............. 10 II.6 Shared Nothing Architecture.[1] ................................ ................................ ............... 11 II.7 Shared Disk Architecture.[1] ................................ ................................ ..................... 12 II.8 Query Plan.[1] ................................ ................................ ................................ ........... 15 III.1 Cloud Diagram. [3] ................................ ................................ ................................ .. 21 III.2 C loud Stack. [5] ................................ ................................ ................................ ....... 23 IV.1 Shared Memory Architecture [12] ................................ ................................ ........... 28 IV.2 Shared Process Architecture [12] ................................ ................................ ............ 30 IV.3 Shared Table Architecture [12] ................................ ................................ ............... 31 IV.4 Multitenant Database Architecture and Cloud Services. [14] ................................ 32 VI.1 Database Migration Timeline. [29] ................................ ................................ .......... 49 VI.2 Chunk Folding Example. [8] ................................ ................................ ................... 52 VI.3 Extension Tabl e Layout. [8] ................................ ................................ .................... 53 VI.4 Chunk Table. [8] ................................ ................................ ................................ ...... 53 VI.5 Chunk Folding. [8] ................................ ................................ ................................ ... 54

PAGE 10

x VII.1 Database Architecture Model [29] ................................ ................................ ......... 57

PAGE 11

xi LIST OF EQUATIONS Equation VI.1 Consolidation Precition Function [28] ................................ ................................ ..... 47

PAGE 12

xii LIST OF ABBREVIATIONS 1. ACID Atomicity, Consistency, Isolation, and Durability 2. AMI Amazon Machine Image 3. CPU Central Processing Unit 4. DaaS Database as a Service 5. DBA Database Administrator 6. DBMS Database Manag ement System 7. EBS Elastic Block Store 8. EC2 Amazon Elastic Compute Cloud 9. FIFO First In First Out 10. GB Gigabyte 11. I/O Input/Output 12. IaaS Infrastructure as a Service 13. KB Kilobyte 14. MB Megabyte 15. NAS Network Area Storage 16. NF Normal Form 17. NIST National Institute of Standards and Technology 18. OS Operating System 19. PaaS Platform as a Service 20. RAM Random Access Memory 21. RDS Amazon Relational Database Service 22. SaaS Software as a Service 23. SAN Service Area Network 24. SDSS Sloan Digital Sky Survey 25. SLA Service Level Agreement 26. SQL Structured Query Language 27. VM Virtual Machine 28. WAN Wide Area Network

PAGE 13

1 CHAPTER I. INTRODUCTION What is being researched and investigated Cloud computing has become increasingly popular and relational databases are essential to almost every computing environment today. Making the two closely intertwined. Cloud computing is an attractive concept due to the fact that it moves the burden of provisioning, configuring, scaling, backing up and access control away from the company (or tenant) to the service provider. This allows for lower overall costs for the users. Therefore, companies are able to deploy large numbers of web applications to t he cloud effortlessly. These web applications have different database schemas as well as erratic load patterns. In order for the service provider to lower the costs, they must co locate multiple tenants' databases onto a single server for effective reso urce sharing. The two key resource management features that must be addressed in a multitenant database, which resides in a cloud are efficient multitenancy and elastic scalability. There are also key database architectural details that can be implement ed in order to help efficiently utilize resources such as data normalization, partitioning and indexing. Thus the concept of a query router, which monitors the database management system, is introduced. Efficient Multitenancy evaluates a set of databases and workloads making the determination as to what is the best possible way to service them. The cloud provider wants to find the minimum number of nodes that can service the databases while still maintaining service level agreements on query performance. There are three critical pieces to efficient multitenancy, monitoring resource consumption of individual databases, predicting combined workloads and the method of combining the databases. Monitoring resources involves evaluating a combination of databas e management system and operating system resources. The resources that need to be monitored are CPU, RAM, and disk I/O. Monitoring RAM in a DBMS is difficult due to the fact that most operating systems over provision the memory that is allocated to the d atabase. Thus, a methodology must be put into place to evaluate the amount of RAM a database requires.

PAGE 14

2 This is done be evaluating the working set of the application. When predicting the combined workload for multiple databases, determining I/O is burden some since the DBMS exploits unused bandwidth. Different solutions for each of these three pieces are presented as well as specific enhancements, which would further help in maintaining efficient multitenancy. Elastic scalability specifically deals with supporting multiple databases with varying workloads. The approach taken for elastic scalability is live migration. The system must be workload aware and quickly make the determination that a given workload has exceeded the capacity of a single node. On ce this has been identified, the system needs a method to scale out and process against multiple nodes such that higher throughput can be achieved. Scaling out must also go undetected by the users and happen as quickly as possible thus as transactions com e into the system, they must execute against a source node until a destination node has been warmed up and made ready to accept transactions. The method that can be utilized to achieve this will be evaluated as well as improvements that can be made to fur ther maximize the efficiency of resource management. Finally, this paper will introduce the concept of a query router and monitor. This abstraction has the ability to mask how queries from different tenants are routed to the correct database node hosting their data so that tenants need not know where their data resides. It also monitors SQL statements so that it can identify their access patterns. This information allows for more precise data partitioning, indexing and potential query optimizations. The query router also estimates the cost of queries based on available resources and compare them to service level agreements. This allows for the query monitor to provide a degree of performance isolation by controlling the rate at which queries are dispatc hed to nodes. As well as it allows for easy identification of situations where the workload has exceeded current capacities. All of these details provide a foundation for comprising a tenant specific architecture that is workload aware and scalable. The aspiration of this paper is to propose a comprehensive multitenant database architecture that can reside in a cloud environment, which is elastic, workload aware and specifically supports the resource issues that are encountered with multitenant database.

PAGE 15

3 Thesis Layout The rest of this paper is laid out into the following sections, 2, database management system architecture. In order to be able to make knowledgeable suggestions for how to handle resource allocation within a database, there first must be an understand ing of how a database management system functions and utilizes memory. Section 3 will provide an overview of cloud computing with some preliminary information pertaining to cloud computing and infrastructure in order to understand the environ ment where the problem resides. Section 4 is dedicated to understanding the different multitenant database architectures. Understanding these is key to understanding resource implications. Section 5 examines the current challenges with multitenant databa ses in cloud computing. Section 6 will provide possible solutions to resource issues and finally section 7 are my evaluations, conclusions and possible solutions.

PAGE 16

4 CHAPTER II. DATABASE MANAGEMENT SYSTEM ARCHITECTURE Introduction to database management systems Database management systems (DBMS) are complex. There are five main components of a relational DBMS, the process manager, client communication manager, relational query processor, transactional storage manager and the shared components and utilitie s. Figure II 1 Main Components of a Database Management System. [1] This section will serve as an overview of some of these components.

PAGE 17

5 Processing models Many times, when evaluating a database management system, there is an execution of concurrent user requests, which must be mapped to operating system processes or threads. In order to understand how the different processing models work, we must understand some basic components within the datab ase system as well as the operating system. The operating system process is a single unit of program execution that is scheduled by the operating system kernel. It is essentially combining an operating system execution unit with an address space private t o the process. The operating system thread is scheduled by the operating system kernel and is an operating system execution unit that does not contain the additional private operating system address space. The lightweight thread package is scheduled at the application level in the user space without the kernel's involvement. The user space scheduler as well as its lightweight threads all run within a single operating system process as a single thread of execution. A drawback of lightweight threads is that any blocking operation will block all threads in the process, preventing any threads from making progress. The DBMS client implements the API that is used by application programs in order to communicate with the DBMS The DBMS Worker is a thread that resides within the DBMS, which does work for the DBMS client. There must be a one to one correspondence between a DBMS worker and a DBMS client. The worker takes care of all SQL requests from one DBMS client by sending the request to the DBMS server and returns the results to the client. There are three process models that are utilized by DBMS, process per DBMS worker, thread per DBMS worker and process pool. The process per DBMS worker is an implementation where the DBMS workers are map ped directly onto OS processes. Here, the OS scheduler must manage the timesharing of DBMS workers. What complicates

PAGE 18

6 this process model is the fact that the in memory data structures are shared across the DBMS connections; this includes the lock table an d the buffer pool. [1] Figure II 2 Process Per DBMS Worker .[1] It's important to note this model requires substantial use of shared memory and it also diminishes the advantages of address space separatio n. This process model also does not scale very well when there are large numbers of concurrent connections this is due to the fact that a process has more state than a thread and consequently consumes more memory. The next process model is thread per DB MS worker. In this model, a single multi threaded process hosts all of the DBMS worker activity. This model relies on a dispatcher thread to listen for new DBMS connections; each connection is thus allocated to a new thread. SQL requests, which are subm itted by clients, are executed entirely by the corresponding thread running a DBMS worker.

PAGE 19

7 Figure II 3 Thread Per DBMS Worker.[1] The thread runs inside the DBMS process, returns the results to the client and waits for the next request from that same client. There are many multithreading challenges with this specific process model; the OS does not protect the threads from each other 's memory overruns and stray pointers; debugging is difficult due to race conditions; there is also a difficulty when it comes to porting across OS due specifically to the differences in the threading interfaces. The last process model is the process po ol. This model is the most complex and difficult to implement. In this model, rather than allocating an entire process per DBMS worker, they are hosted by a pool of processes.

PAGE 20

8 Figure II 4 Process Poo l.[1] Now, the central process supports all DBMS client connections. Hence, as SQL requests are made, they are allocated to one of the processes within the process pool. The statement is executed, the results are returned to the client and the process i s returned to the pool so that it can once again be allocated to another request as needed. There are many advantages to this process model, there are a smaller number of processes that are required and is much more efficient. [1] Buffers T he objective of these different models is to execute as many concurrent requests as possible while being as independent as possible. But, full isolation is not possible since they are operating on the same database and thus, shared memory is used to share data structures and states. In all of the processing models, data is migrated from the DBMS to the requesting client, this implies that requests are moved to the server processes, results are returned to clients and then must be moved back out. All of t his is done utilizing buffers, disk I/O buffers and client connection buffers. Buffers are an

PAGE 21

9 important concept in DBMS. Disk I/O buffers read and write to shared data stores. There are two different scenarios when evaluating disk I/O buffers, there are either database I/O requests or log I/O requests. Database I/O requests, also known as the buffer pool, is where all persistent database data is staged. In thread per DBMS worker, the buffer pool is a heap data structure that is available for all thread s to utilize. Whereas in the other two models, the buffer pool is allocated within shared memory and available to all processes. Ultimately, the buffer pool is a data structure, which is available to all database threads and processes. The way that the buffer pool works is that when a thread requires that a page be read from the database, it creates an I/O request that specifies the disk address as well as a handle to a free memory location, or rather frame in the buffer pool for where the result can be placed. To flush a buffer pool page to disk, then a thread must generate an I/O call that indicates the page's current frame in the buffer pool as well as its destination address on disk. Log I/O requests, commonly called the log tail, is an in memory q ueue that is flushed to the log disk in FIFO order. The queue consists of an array of entries, which are generated during transaction processing. Thus, one type of flushing is the commit transaction flush. A transaction is not successful until a commit log record is flushed to the log device. Again, if we evaluate the different processing models, we can see that for the thread per DBMS worker, the log tail is a heap data structure. In the other two models, there are two different options, a separate pr ocess manages the log or the log tail is allocated in shared memory like the buffer pool. It's important to note that understanding these different process models as well as the different buffers and requests that can be made will allow for the correspon dence between multitenant systems and workload. As the workload increases, throughput will increase to a maximum point and beyond that point, the throughput will decrease. This is a direct correlation with the memory pressures that exist in database mana gement. In these scenarios, the DBMS cannot maintain the working set of database pages in the buffer pool and begins to waste all of its time replacing pages. We will see that these issues become more prevalent with query processing, which tends to consu me a large amount of main memory. Thrashing in these instances can be directly related to contention for locks, where transactions continuously deadlock.[1]

PAGE 22

10 Memory architectures Shared m emory I n a parallel system, shared memory means that all processors can access the same RAM as well as disk with the same performance. The process model for shared memory, the OS supports the transparent assignment of processes or threads across the processors. Figure II 5 Shared Memory Architecture.[1] All three of the different process models run efficiently on this type of a system, but the main challenge is to alter the query execution layer such that it c an take full advantage of the ability to parallelize a single query across multiple CPUs. Failure of a processor in this type of architecture results in the shutdown of the machine and ultimately the entire DBMS. [1]

PAGE 23

11 Share Nothing. In a shared nothing p arallel system, there exist a cluster of independent machines, which communicate via a high speed network. Figure II 6 Shared Nothing Architecture.[1] In this type of a system, there is not a way to directly access the memory or disk of another system. In shared nothing memory architectures, the coordination of the various machines is left up to the DBMS. Generally, the DBMS runs one of the standard pr ocess models on each machine. Thus, each machine has the capability to accept SQL requests from clients. But each machine only stores a portion of the data locally. This means that once a query request is received, the request is sent to additional mach ines such that they all execute the query in parallel against the data they are locally storing. In essence, the underlying data structure is dictating that the data is partitioned between each machine such that each processor has the ability to execute i ndependently of the others. There are different options to partitioning data, which will be discussed later. Thus, it is easy to see that this memory architecture allows unsurpassable scalability.

PAGE 24

12 Finally, it's important to note that a failure of a mac hine in this system will typically does not result in the entire DBMS being shut down. But, does result in lose of access to some data. [1] Shared disk The shared disk memory architecture in a parallel system allows for all processors to access disks wit h roughly the same performance, but they are unable to access each other's RAM. We can see this type of memory architecture in Oracle DBMS as well as some DB2 DBMS. Figure II 7 Shared Disk Architecture. [1] This architecture allows for lower cost of administration since partitioning of data does not have to necessarily be a consideration when setting up this model. Here, failure of a single DBMS processing node does not affect the other nodes' ability t o still access the entire database. But, shared disk is still susceptible to a single point of failure. If data is corrupted before reaching storage or while in storage, then all nodes have access to only this corrupt page. Since data is copied into RA M and modified on multiple machines, each machine must have its own local memory for locks and buffer pool pages and thus data is shared across machines, explicit coordination is required. There must be distributed locks and cache coherency to manage the different buffer pools. [1]

PAGE 25

13 Query P rocessor Ultimately, a query processor takes the SQL statement, validates it, optimizes it into an execution plan, and finally executes it. The client program, which issued the query, then pulls the result tuple. Unders tanding how a query is actually processed within a DBMS will directly correspond to how resources are utilized when a SQL statement is issued and how we might eventually be able to achieve higher throughput and allocate work to additional nodes when necess ary. Parsing For every SQL statement that is submitted, the parser must verify that the query is correctly defined, resolve names and references, convert the query into the internal format, which is utilized by the optimizer and finally verify that the user has security to execute the query. The parser first must consider every table that is referenced in the FROM clause of the SQL statement and verify that the name is accurate and valid. After doing this, the parser invokes the catalog manager in ord er to verify that the table is in the system catalog. The, utilizing the catalog, it establishes that every attribute that is referenced is accurate. If the query is parsed successfully, to this point, there is an authorization check to make sure that th e user has the necessary permissions on the tables to perform the query. Once the user passes security and the parser is thus successful, the query is handed off to the query rewriter for processing. [1] Rewrite The query rewriter simplifies and normali zes the query without changing semantics. It does this by only relying on the query and metadata in the catalog and not by actually accessing any data within the tables. The rewriter generates an internal representation of the query in the same internal format it accepted at its input. In more detail, the rewriter's responsibilities are to handle view expansion by rewriting the query to replace the view with tables and predicates referenced by the view. It then substitutes all references to the view wit h column references to tables within the view. This is done until there are no references to any views within the SQL statement. It also functions to

PAGE 26

14 perform constant arithmetic evaluations in order to simplify the expressions. The list continues on wit h what the rewriter is tasked with, logical rewriting of predicates, semantic optimization, and subquery flattening. [1] Optimizer Once the internal representation of the query has been created, the optimizer takes it and develops an efficient query pla n for the execution of the query. In many instances, the query plan can be thought of as a dataflow diagram. Queries are divided into SELECT FROM WHERE blocks where the optimization of each block takes place.

PAGE 27

15 Figure II 8 Query Plan.[1] "Only the main physical operators are shown." [1] The query plan can be generated in different ways, it can be compiled into machine code or interpretable. Currently, the query plan is compiled into some type of interpre table data structure so that it can be more portable between different platforms. Some of the main components of the query plan are plan space, selectivity estimation, search algorithms, parallelism and auto tuning. [1] Executor The query executor is a runtime interpreter of the query plan. Ultimately, the query executor takes in the dataflow graph and recursively invokes actions for the operators. Therefore, most executors utilized an itorator. Every iterator has an input, wh ich defines an edge in the dataflow graph, as well as operators, which are the nodes of the dataflow graph. The operators are executed within a subclass of the iterator. The iterator must deal with memory allocation for in flight data. Normally, the it erator is pre allocated a fixed number of tuple descriptors. It never allocates memory dynamically. A tuple descriptor is an array of column references. Every column reference is a reference to a tuple in memory as well as a column offset for that tuple There are two possible locations where the actual tuple that is referenced is stored in memory. The first possible location is within the pages in the buffer pool and the second possibility is that the iterator allocated space for the tuple on the memo ry heap. In the first instance, where tuples reside in the buffer pool, these are called BP tuples. The iterator creates a tuple descriptor which references a BP tuple, it increments the count of active references to the tuple on that page and decrements the count when the tuple descriptor is cleared. In the second option, the tuple is an M tuple. In order to construct an M tuple, the iterator copies columns from the buffer pool. [1] Indexing and Partitioning The response time of a transactional database is substantially affected by the rate that data can be retrieved from disk. Therefore, having indexing and partitioning in place

PAGE 28

16 will help to speed up the retrieval of data substantially and ultimately lead to a better performing system that requ ires less resources to execute. Indexing Database indexes are utilized to improve the speed of data retrieval but cause for slower writes and increased storage requirements. Generally, indexes enable sub linear lookup time. If we compare a non indexe d database to an indexed database, we would see the following; a non indexed database, which contains N data objects where there it is desired to retrieve only one of the objects, would examine each object until a match was found. This would cause for on average the retrieval of half the objects before the desired one is found and a lookup of all the objects for an unsuccessful lookup attempt, making the worst case linear time. But, an indexed data structure improves the performance of the lookup. It can be thought of the same way as an index page in a book, where there would no longer be a need to scan the entire book to find what you are looking for but instead just quickly find what you want and go directly to that page. There are two main index archi tectures, clustered and non clustered. Clustered indexes change the data block into a very specific order to match the index. Which therefore results in the row data being stored in that order. This means that only one clustered index can be created on a table. The main feature of clustered index is the ordering of the physical data rows in compliance with the index blocks that point to them. Ultimately, this allows for the next row item in the sequence to be immediately before or after the last one, a nd so fewer data block reads are needed. Non clustered indexes allow for the data to be presented in an arbitrary order but the logical ordering is specified by the index. The index tree has the index keys in sorted order where the leaf level of the inde x has the pointer to the record. Non clustered indexes also allow for more than one index to be on any given table. With indexes, it is very important to note that the order in which columns are listed in the index definition is crucial. It is possible t o retrieve a set of row identifiers using only the first indexed column, but it is not possible to retrieve the set of row identifiers using only the second or greater indexed column. [34]

PAGE 29

17 Partitioning Partitioning is a division of logical databases in to distinct independent parts. The partitions may be laid out over multiple nodes. There are two types of partitioning, horizontal or vertical. Horizontal partitioning means that different rows from within a table are divided up among the different node s. A good example of this would be partitioning customers by zip code. If their zip code is less than 50000 they are stored on node 1 and customers with a zip code greater than 50000 are stored on node 2. Vertical partitioning is dividing the data by co lumns instead of rows. In many cases, different sets of hardware are utilized to store the separate columns; storing infrequently used or wide columns on slower devices and columns that are continuously accessed on faster devices. Generally, the method u tilized to understand how to split the data is to divide up the dynamic data from the static data, where dynamic data is not used as often as static data. There are many different partitioning criteria: range, list, hash, or composite. [33] Storage Mana gement Deciphering what implications there are when dealing with the locality of data is critical in the process of formulating the best possible solution for resource management. Clearly all these factors play a role in efficient resource management. Lo cation The location of the actual data is important to consider when evaluating performance of a database. Since sequential access is much faster than random access, the DBMS needs to control where and how the data is laid out across disks. The best wa y for it to control spatial locality is to store the data directly to raw disk devices, alleviating the additional requirements of a file system all together. Part of the reason that this works well is due to location proximity. The raw devices' addresse s generally correspond to physical proximity of the storage location. Using raw disk devices does have pitfalls, the DBA must allocate an entire disk partition to the DBMS and access interfaces are OS specific which can cause for the database to be less p ortable. Another

PAGE 30

18 possible way fro the DBMS to control spatial locality of its data is to create a large file in the OS file system and manage the positioning of the data as offsets in that file. Inherently, the file is a linear array of disk resident pag es. [1] Buffering W hen or rather the frequency at which data is physically written to the disk must be taken into consideration Many OS have come with I/O buffering mechanisms to make the determination as to when to do reads and writes of the file blocks. The issue with the OS doing this is that is could ultimately postpone or reorder writes which will cause for the DBMS to become discombobulated. Since we are primarily concerned with relational databases, we must evaluate the correctness of the database. It can now no longer guarantee recovery after a failure unless the DBMS is controlling the timing and ordering of writes. The next issue with the OS controlling the buffering mechanism has to do with performance. The OS has support for read ah ead and write behind mechanisms which do not work well with DBMS access patterns. The last issue is what is known as double buffering and the large CPU overhead of memory copies. Since the DBMS must do its own buffering, any buffering by the OS is redund ant. This not only wastes system memory, it also wastes time and processing resources since on reads it copies the data from disk to the OS buffer and then again to the DBMS buffer pool and on writes both of the copies are required in reverse. This can c reate a major bottleneck because essentially it is contributing to latency, consuming CPU cycles and flooding the CPU data cache. Thus, it is very important that the DBMS controls the page replacement techniques as well as double buffering is avoided and writes are sent to disk based on the requests of the DBMS. One of the main components of a DBMS is the buffer pool. It can have a profound affect on the overall DBMS. Every DBMS has a large shared buffer pool in its own memory space with a dynamically ad justable size depending on the system needs and available resources. The buffer pool is simply an array of frames in which each frame is an area of memory that is the size of a database disk block. Blocks are copied to the buffer pool from disk, with no format changes. It is then manipulated within memory

PAGE 31

19 and later written back. There also exists a hash table that works with the array of buffer pool frames. The hash table maps page numbers currently in memory to their location in the frame table, the l ocation of the page on backing disk storage, and metadata about the page. The metadata generally includes a dirty bit so that it can be determined whether or not the page has changed since it was last read from disk as well as additional information for p age replacement policies so that the page can be evicted when the buffer pool is full. [1] Transactions This will be a brief discussion on transactions since the topic is extremely complex and having an overview will provide enough information to understan d the remaining componenets The largest section of a DBMS is the transactional storage manager. There are generally four components within the transactional storage manager, a lock manager for concurrency control, a log manager for recovery, a buffer poo l for database I/O and access methods for organizing data on disk. First, it is important to understand the notion ACID, Atomicity, Consistency, Isolation, and Durability. Isolation within a DBMS is done via a locking protocol, while durability is throu gh logging and recovery. Atomicity is accomplished by a combination of locking and logging. Finally, consistency is completed by runtime checks in the query executor. [1] Understanding Shared DBMS Components There are many different shared components wit hin a DBMS, but the two that are of most interest for this thesis are described below. Catalog m anager The catalog manager actually holds information pertaining to the data as well as the overall system in the form of metadata. Essentially, the catalog manager keeps track of the names of entities within the database, such as users, schemas, tables, columns,

PAGE 32

20 indexes, etc. and their relationships. It is in and of itself stored as a set of tables within the database. High traffic areas of the catalog are generally materialized within main memory as needed. In addition to that, the catalog data is cached in query plans at parsing time, often in a denormalized form. [1] Mem ory a llocator Database management systems memory management should not be completel y focused on the buffer pool. Database systems also allocate large amounts of memory to other tasks. Things such as query joins and sorts require a significant amount of memory at runtime. As a rule, most DBMS use a context based memory allocator. A me mory context is an in memory structure, which maintains a list of regions of contiguous virtual memory or rather memory pools. [1] Every region can have a header that contains a context label or a pointer to the context header structure. The basic API for memory contexts include calls to create a context with a given name or type, allocate a chunk of memory within a context, delete a chunk of memory within a context, delete a context, or reset a context, clearly providing software engineering advantages. But, memory contexts also provide performance advantages where the overhead for malloc() and free() are high. This is due to the fact that memory contexts have the ability to use semantic knowledge on how memory will be allocated and deallocated and thus can accordingly call malloc() and free() to minimize OS overhead. Another advantage to memory allocators is that it can call malloc() to allocate large regions. This will eliminate the issue of needing to call free() for many small objects, incurring a high expense. [1]

PAGE 33

21 CHAPTER III. CLOUD COMPUTING What is cloud computing There are thousands of different definitions and explanations as to what cloud computing is and that many opinion s to go along with the subject matter. A most infantile definition of cloud computing would be that it is Internet based computing. It allows users to access technology enabled services over the Internet. The National Institute of Standards and Technology (NIST) gives a mo re precise definition of cloud computing as, "Cloud computing is a model for enabling convenient, on demand access to a shared pool of configurable computing resources (e.g., networks, servers, storage, applications, and services) that can be rapidly prov isioned and released with minimal management effort or service provider interaction." [2] Figure III 1 Cloud Diagram. [3]

PAGE 34

22 Cloud computing provides computational software, data access as well as storage s ervices to end users. It typically involves providing dynamically scalable and more often than not, virtualized resources. Generally, the cloud architecture contains multiple components, which must communicate with each other over different application p rogramming interfaces. The two most significant components of a cloud computing architecture are the front end and the back end. The front end is the piece that the normal end user will see and the back end is the cloud itself. [2] Typically the goals an d characteristics of a cloud are to be highly scalable, available, reliable, secure, flexible, serviceable, and efficient. A cloud must be scalable or also known as elastic. This may be the most important characteristic of a cloud. This means that it wo uld be anticipated that applications within a cloud environment would scale to meet the demands of the workload automatically. This way, performance as well as service levels are not compromised. It's important to note that the cloud should not just scal e up, but also down in times where the demands are lower. Availability is another critical characteristic of a cloud. A n application deployed in a cloud is up and running 24/7/365, basically every minute of every day. The next characteristic is reliabil ity A cloud must always be reliable. Applications cannot fail or lose data when they are in the cloud. Upon a server crashing, the users should not notice any degradation in service. The next characteristic is security. Security within a cloud is an e xtremely controversial topic with many complex issues surrounding it. H ere it simply means that an application inside the cloud must be resilient to unauthorized access. Users must be able to feel confident that their data is secure. Flexiblility in a c loud dictates that the cloud must be compatible with the most efficient means to deploy an application. Another important aspect of a cloud is that it must be serviceable. Serviceable implies that in the event it is necessary to modify any of the underly ing cloud architecture, the application is not disrupted during this time period. Finally, the last common goal and characteristic of cloud computing is to be efficient. Users must have the ability to quickly deploy applications in the cloud. This allo ws for users to reduce operational costs and provide its customers with greater transparency through technology. [4]

PAGE 35

23 Figure III 2 Cloud Stack. [5] As depicted above, the cloud architecture is made up of multiple layers, the client, application, platform infrastructure and server. It is possible to share services within any of the layers and often times, service providers offer services that are either at the software, platform or infrastructure layer. T he client layer consists of computer hardware and software that is dependent on the cloud for application delivery. Cloud application services, also known as software as a service (SaaS), sometimes referred to as on demand software, has the ability to del iver software to users over the Internet. This eliminates the necessity to install and run applications on a customer's computer. This also helps to simplify the maintenance and support of the application. The vast majority of SaaS solutions are based n multitenant architectures where there is one version of the application, which is used for all customers (rather tenants). Many times in SaaS, the applications do not support customization but instead promote configuration. This means that the tenants have the ability to set options that affect functionality and the look and feel of the application. SaaS also promotes accelerated feature delivery where

PAGE 36

24 applications are updated more frequently than traditional software, open integration protocols and co llaborative functionality. [6] Cloud platform services, platform as a service (PaaS) allow for users to have a computing platform and solution stack as a service. This helps in the deployment of application due to the fact that users do not have to purcha se the required underlying hardware to support the application. Many also feel that PaaS helps to facilitate application design, development, testing, deployment, and hosting. Cloud infrastructure as a service (IaaS) provides the computer infrastructure, which is more often than not a platform virtualization. It supplies users with basic storage and computational capabilities. Finally, servers layer consists of the products, which are necessary to deliver the cloud to the end user. There is one final layer that is up and coming and will be covered more in the trends section of the document, which is database as a service. Database as a service (DaaS) attempts to move the op erational burden of provisioning, configuration, scaling, performance tuning, backup, privacy, and access control away from database users to the service provider. DaaS is so appealing because it promises to offer scalability as well as being an economica l solution. It will allow for users to take advantage of the lack of correlation between workloads of different applications, the service can also be run using fewer machines than if each workload was individually provisioned for its peak. [7] The final p iece in understanding cloud computing is the different infrastructure models, which consist of public, private, and hybrid clouds. Generally, third party vendors develop public clouds. In the majority of public clouds, applications from multiple differen t customers are mingled together on the cloud's servers, storage system and networks. One of the benefits of a public cloud is that it can be much larger than a private cloud could aspire to be. It has the ability thus to offer scaling up or down on dema nd. Private clouds are built for one specific company, which allows for better data control and security. The company therefore owns the infrastructure and maintains complete control of the cloud. Lastly is the hybrid cloud. This cloud infrastructure m odel combines both the public and the private clouds in order to provide on demand, externally provisioned scalability. This type of cloud model has additional complexities such as determining how to distribute applications across both a public and privat e cloud.

PAGE 37

25 Thus, the relationship between the data and the application must be understood for best performance in this type of cloud. [4] Benefits and Motivation of Cloud Computing Many companies want to utilize clouds because they are cheaper, scalable, p rovide easy remote access, faster provisioning of applications, the list goes on and on. Getting up and running within a cloud is quick and easy. When you consider that you do not need to invest in any type of infrastructure, hardware, technical support, and all users need in order to access information and data is the Internet. There is also no need to worry about storage in a cloud since storage is virtually limitless. Clouds additionally provide the scalability that many companies need with just the click of a button. Basic Trends in Cloud Computing The different service cloud layers and ultimately the available services within those layers are driving many of the trends in cloud computing. The first trend is the utilization of virtual machines in clouds. Virtual machines are the standard deployment model now for cloud computing. Especially when running a relational database in the cloud. Many IaaS as well as PaaS utilized virtual machines to accommodate for demand. This is eviden t when look ing at Amazon Elastic Compute Cloud (EC2). EC2 allows fo r its customers to basically rent virtual computers to run their applications on. EC2 utilizes Xen virtualization where each virtual machine, or rather instance, functions as a virtual private server. SaaS is driving the trend of multitenancy in the clo ud. With multitenancy in the database, this allows for effective resource sharing for customer applications that have small but varying resource requirements. Multitenancy thus obliterates the need for separate systems for each tenant. This means lower s ubscription fees for individual tenants and higher hardware/system utilization for the service provider. Looking at a real world example of multitenancy, Salesforce.com is probably the most familiar service provider that utilizes multitenancy in both the application and the database. [8] C loud computing has started the trend of everything must be on demand and users want to pay as they go. The very essence of cloud computing refers to the provisioning

PAGE 38

26 of computational resources on demand. Again, the prim ary influence in this area is Amazon EC2. They specifically state that they have on demand instances that let you pay for compute capacity by the hour with no long term commitments. They promote that this allows for the users to alleviate the costs and c omplexities of planning, purchasing, as well as maintaining hardware, which are incredibly expensive. [9] The reason that this trend is important is that it has given rise to the need for elas tic scalability/load balancing. U sers expect for a vendor to ha ve the ability to automatically distribute incoming traffic across multiple instances. Now, users want their applications to scale up when necessary and down when the demand is not warranted. Thus, only paying for what they absolutely need. Finally, a trend that is taking place by many of the large vendors is offering DaaS. DaaS hosts databases in the cloud environment and also provides database features like data definition, storage and retrieval. Such vendors as Amazon, Microsoft, and Google have begun offering this service. Amazon Relational Database Services (RDS) is available to users for when an application requires a relational database and users want to reduce the time spent on data management. Amazon also offers Amazon EC2, with a relation al database Amazon Machine Image (AMI) for when applications require a particular relational database and the customer would like to maintain complete control over the database. The instance runs the database and the data is actually stored within an Amaz on Elastic Block Store (EBS) volume. As previously mentioned, Microsoft also offers a similar feature, SQL Azure. This is their cloud based relational database service, which is built on SQL Server technologies. It is highly available, scalable, multi t enant database service that is hosted in the cloud. It is beneficial to users because it helps to ease provisioning and development of multiple databases. Finally, Google AppEngine Datastore offers DaaS. It was built on BigTable (which is non relational ) and has the ability to store richer data types including lists, which contain collections within a single item. [10] As a follow up on the previous trend, Amazon will be making Oracle 11g available via Amazon RDS in the near future. This will be the fi rst time that Oracle is available in a public cloud. This is a huge accomplishment since Oracle is the king of

PAGE 39

27 relational databases management systems it brings us one step closer to having a full relational database in the cloud. [11] Rise of Multitenanc y Multitenant database architecture is where many users, typically unrelated when placed into the context of a cloud, make use of shared resources. In a cloud, this allows for multiple customer applications to be consolidated, removing the need for separ a te systems for each tenant. Multitenant database architectures can reduce the total cost of ownership because multiple businesses are consolidating onto the same operational system. Sharing resources at different levels of abstraction and distinct isolat ion levels allows for various mutitenancy models. These levels are shared machine, shared process and shared table.

PAGE 40

28 CHAPTER IV. MULTITENANT DATABASES IN CLOUD COMPUTING Benefits of multitenant databases in cloud computing Multitenant databases in a cloud can handle high traffic volumes at low cost. It can reduce the total cost of ownership by aggregating customers together and leveraging economy of scale. This includes money for hardware, software, operational expenditures for bandwidth and personn el. Multitenancy allows for pooling of resources. This improves the utilization by eliminating need to provision each customer for maximum load. The goal of a multitenant database in a cloud is to minimize the number of machines required while still main taining query and application performance goals. Ultimately, multitenant data platforms must minimize operating cost by efficient resource sharing. [7] Shared Machine Multitenancy Database Architecture In this multitenant architecture, each customer receives their own database process but multiple customers can share the same machine. This means that each tenant has their own set of data that is logically isolated from data, which belongs to other tenan ts. Figure IV 1 Shared Memory Architecture [12]

PAGE 41

29 This approach does not require that the implementation of the database be modified. It also does not does not reduce customer isolation. A draw back of this is that executing administrative operations in bulk is not possible each database can and will execute queries on its own. In this multitenant architecture, the primary limitation is that it does not pool memory, each database requires is own connec tion pool for every application server thus, sockets cannot be shared among customers. Here though, customer migration is more straightforward due to the fact that each customer receives his or her own database process. This can also mean that if the ven dor pre allocates a specific amount of space for the database, there could end up being a large amount of wasted space when the database is smaller. [13] Shared Process Multitenant Database Architecture Shared process architecture gives each customer their own tables but multiple customers share the same database process. This method still offers a logical degree of isolation for each tenant. In general, it does not matter whether or not customers receive their own schema but it is useful for them to recei ve their own physical table space. This enables the customer to easily migrate their data by simply moving a file from one server to another. This approach is better at pooling memory than the previous architecture. Since only one database exists in the shared process architecture, customers can easily share connection pools. It also opens the door to the fact that one customer could possibly access another customer's data or prevent the other customer from getting a reasonable amount of resources. [13 ]

PAGE 42

30 Figure IV 2 Shared Process Architecture [12] This method can support a larger number of tenants per database server. This method makes restoring a tenant's data in the event of a failure much more dif ficult. Since each tenant only has their own schema, restoring the entire database could mean overwriting the data of every other tenant on the same database. [12] Shared Table Multitenant Database Architectures The final multitenant architecture, shared table allows for data from different customers to be stored in the same table. Here, a column is added to every table so that the owner of each row can be identified. This means that every query must specify a value to reflect which tenant should be eval uated. In order for customers to be able to extend the database schema, every table contains a fixed number of generic columns.

PAGE 43

31 Figure IV 3 Shared Table Architecture [12] The shared table architecture is the best at pooling resources and has the ability to scale up as needed, due to the fact that it is only limited to the number of rows that the database can hold. Another benefit to this architecture is that since there is only one table, administrative tasks can be executed in bulk by simply executing the queries that range over a specific tenant's rows. On the other hand, a downside to this approach is that migrating a users data to the table can be difficult and require executing data manipulation lan guage against the production table. The intermingling of different customer's data can also cause for performance issues since one customer's data can be spread out across many different pages. One of the significant drawbacks to this architecture is tha t queries intended for a single customer must contend with data from all the customers, ultimately compromising any query optimization. Continuing to evaluate the fact that there is only one shared table, it must be understood that if one customer wants t o place an index on their specific column(s) then all customers must have that index. [13] Multitenant Architectures and Cloud Service I n these different models, the tenant's data can be stored in different forms. The following table makes the connection between the database multitenancy architecture and the cloud computing service.

PAGE 44

32 Figure IV 4 Multitenant Database Architecture and Cloud Services. [14] While exploring the suitability of the architecture with the various scenarios, IaaS provides the lowest level of abstraction such as raw computation, storage and networking. Supporting multitenancy in the IaaS layer is much more flexible and allows for different schemas for sharing. PaaS providers give a higher level of abstraction to its tenants. For PaaS providers that have a single data store API, a shared table or instance can meet data needs for the platform. But, PaaS providers, which have the ability to support a variety of data stores, have the potential to leverage any multitenant database model. Finally, SaaS, which has the highest level of abstraction, the shared table architecture is the most optimal. [14]

PAGE 45

33 CHAPTER V. CURRENT CHALLENGES IN MULTITENANT DATABASES IN CLOUD COMPUTING Overview of database type challenges There are many issues surrounding multitenant databases in cloud computing as well as databases in general existing in cloud computing. One of the biggest issues is that multitenancy introduces contention for shared resources, such as CPU, RAM and I/O. This also makes it more difficult to support scalability due to the fact that the resources are shared. Other issues surrounding databases and cloud computing include, database schema consolidation, partitioning, indexing, quer y optimization, security, network latency, whether or not a transactional database should even exist in a cloud and more. Overview of Multitenant Architectural Challenges In evaluating the three previously mentioned multitenant architectures, shared machine, shared process, shared table, there are faults or specific implications with resource sharing which pertain to each of them. Shared machine/hardware architecture challenges The shared machine architecture, where each customer receives their ow n database process and multiple customers share the same machine, is very popular due to the fact that it does not require any modifications to an existing database and provides great tenant isolation. [13] Unfortunately, s calability is poor since running independent database instances not only wastes memory but also CPU cycles. It is obvious to see that the number of instances grows linearly with the number of tenants. Thus, this model cannot scale beyond tens of customers per server. We can start to ge t a vivid

PAGE 46

34 understanding of the sheer numbers required to simply startup independent databases instances if we evaluate MySQL DBMS. MySQL consumes 30 MB of memory on startup alone. We can also see that there is a large amount of disk space that is wasted since each database instance must be allocated a finite amount of disk space to even run. [24] Since this architecture requires sharing resources at the machine level, this could potentially mean using multiple virtual machines or sharing virtual machines by using different user accounts or different database installations. Here, there is no database resource sharing only sharing of machine resources. Each database instance and VM is sharing a common pool of physical computing resources. Utilizing the ma chine in such a way requires 2 to 3 times more machines to consolidate the same number of workloads, which ultimately offers 6 to 12 times less performance. [7 ] One of the major implications to this architecture is that there is a substantial cost incur red due to redundant components and lack of coordination using limited machine resources in an unoptimized way. Each VM must contain a separate copy of the operating system and database. The database therefore has its own buffer pool and each database mu st have its own logs to disk, etc. Therefore, a way and method to dictate how the shared resources will be dived up to the different instances must be established. It's obvious from this potential architecture that shared hardware is not the most efficie nt way to share and utilize resources. [13] Shared process architecture challenges In the shared process architecture, customers get their own tables within the database instance. [13] Thus, multiple customers share the same database processes. We can cl early see with this architecture the number of private tables grows linearly with the number of tenants. Therefore, we are limited by the number of tables a database can store/handle and the amount of available memory. As an example, IBM DB2 allocates 4K B of memory for each table; so 100,000 tables consume 400MB of memory right off the bat. [8 ] Since memory buffers are allocated in per table manner, buffer space

PAGE 47

35 contention occurs among the tables for the remaining cache. I/O can be balanced by distributi ng customers across different disks. Similar to the previous architecture, the shared process architecture can involve sharing database processes at various isolation levels. This could imply sharing only the installation binary, or sharing database res ources such as logging, buffer pools to sharing the same schema and tables. An example of shared processes would be RelationalCloud, SQLAzure or ElasTranS. [14] Shared table architecture challenges The shared table architecture data from a tenant is not o nly in the same database schema, but data from many customers is stored in same table. Generally, this architecture is achieved by appending a tenant id attribute to tuples in order for them to be recognized as belonging to a specific tenant. This provid es the best pooling of resources and has the ability to scale up is only limited by the number of rows a database can handle. Which itself is dependent on the amount of available memory. [24] But, this architecture also allows for tables to be extremely sparse due to the fact that there are a large number of attributes that not all tenants utilize. Hence leaving a large number of null vales in any given table. This leads to wasted disk space and poor performance since it is difficult to index any of the data due to the fact that it is unlikely tenants are using the same columns. [24] There is a large hit with shared table when it comes to the basic necessary functionality of a database. Ther e must be query optimization, table scans, explain plans and statistics are very costly in this architecture. There is a large contention for cache pools, but cache pools do not work as effectively since queries from multiple tenants could potentially be hitting the database at any given time. An e xample of shared table would be Salesforce.com. [14] Resource Allocation and Workload Balancing The goal of efficient multitenancy is to minimize the number of machines required, while still meeting performance goals. Given a group of databases and their

PAGE 48

36 associated workloads, what is the best way to serve them from a designated set of machines? Therefore, the system must understand the resource requirements of each separate workload. [7] Resource allocation wi thin a multitenant database, means multiple things, verifying that each tenant has enough resources to properly function as well as load balancing and scaling to meet the needs of each tenant. The multitenant architecture must be able to handle ill behave d tenants. When a tenant begins to consume an excessive amount of resources, there must be a way to validate that other tenants do not experience slow down, blocking or throttling. Monitoring resources. There is a combination of DBMS and OS resources th at must be evaluated. The resources that ultimately need to be monitored are CPU, RAM and disk I/O including buffer pool utilization and log flushes. It's crutial to decipher how an individual database is consuming each resource so that it is readily apparent how the database will behave once it is combined with other databases and what databases are good candidates to be consolidated onto the same machines. One of the issues with resource monitoring and DBMS is gauging how much RAM is truly being used. RAM is a resource that is difficult to monitor within a DBMS. When the DBMS is the primary service on a machine, the OS tends to overestimate the actual resources, which are required and reports back the total memory that is allocated to the database process. The database will fill the buffer pool even if the working set is smaller than the buffer pool. This means that unless the application is actively accessing the entire b uffer pool at maximum throughput, the DBMS can operate identically with less RAM. Thus, a way to verify the actual usage of RAM for a DBMS is required. [28] Predicting combined workload Combining the workloads of multiple databases means that there must be a way to predict the combined resource requirements when multiple workloads are consolidated onto a single server. Unfortunately, it is very difficult to determine the combined workload for disk I/O.

PAGE 49

37 There are multiple reasons as to why predicting d isk performance of a set of database workloads is difficult First, a DBMS tends to exploit unused disk bandwidth to flush dirty buffer pool pages back to disk when it notices that the disk is underutilized. This makes it difficult to estimate minimum I/ O requirements. Secondly, disk I/O grows sub linearly with workload size. Next, complex interaction between the DBMS, OS and disk controller makes it strenuous to predict how sequential or random the combined set of workloads will be. Finally, there are many hardware and software configurations, which impact the I/O throughput a system can achieve. [28] Workload consolidation After monitoring the resources and predicting combined workload, the final task left to do is the actual combining of the differ ent databases. This could mean that we are given hundreds of databases that should be combined and now it is up to us to decide which hardware they should all be placed on. T his activity is strenuous since we are trying to minimize the number of machines required to support a specific workload combination as well as balance the entire load across machines while not exceeding their capacities. We have to take into account each workload's disk, memory, and CPU necessities while looking at a given machine's available resources. [28] Scaling/Elasticity Elastic scalability refers to the ability to accommodate for databases of different size and workload requirements. When the workload of the database exceeds the capacity of a single machine, then it must support scaling out. [7] A multitenant database in a cloud system must be able to support scale out. This is an important concept for resource allocation and keeping operational costs negligible. Elasticity allows for the query processing to be partition ed amongst multiple nodes so that the maximum throughput can be achieved. The system must therefore be able to determine when to migrate, which cells or databases should migrate and where they should relocate. The scaling/migration must also be done effi ciently so that there is very minimal disruption and no impact in service. [29]

PAGE 50

38 Database Schema Design Issues It is common practice for a cloud service provider to map multiple single tenant logical schemas to one multitenant physical schema in the databa se. This can be very difficult and fundamentally there are limitations as to the number of tables that a database can handle. In order to achieve acceptable consolidation, certain tables must be shared among tenants and certain tables must be mapped into fixed generic structures. Determining which should be shared and which should not be is not a trivial task. [8] In the cloud, multitenant data management must also be able to account for an increasing number of tenants without performance degradation. Th us, the system must be scalable. This gives rise to additional issues, tables are too sparse and indexing on shared tables is not effective. When data is stored in large shared tables, this produces an extensive number of NULL values in each row. NULL v alues waste disk bandwidth and undermine the efficiency of query processing. Secondly, since the amount of data is quite large in a multitenant architecture, it is especially important to develop an efficient indexing technique to efficiently retrieve dat a from a shared table. If the index were to be created where they encompass the entire table, performing an index scan would be incredibly inefficient and degradable to performance. [24] Challenges Recognized But Not Resolved In This Paper T here were many different aspect and challenges of cloud computing and databases that were recognized and investigated. All of which are legitimate concerns within the area, but for this thesis, their possible solutions were not investigated. Below the challenges are l aid out. Transactional databases There has been must debate as to whether or not a transactional database belongs in the cloud. For good reasoning, the authors of Data Management in the Cloud: Limitations and Opportunities make the conclusion that th ey should not reside in the cloud. As the authors look at the main characteristics of a cloud, which in essence are

PAGE 51

39 the previously discussed benefits of cloud computing, it is possible that transactional databases may not have the ability to take advanta ge of many of those benefits. First, a cloud is meant to have elastic computing power. This means that when there are changes in the environment, additional computational resources can be allocated on the fly to handle the new demands. These resources are generally in the way of additional server instances. A transactional database is typically not a share nothing architecture, which means that it might not be able to take advantage of the additional server resources to handle the load. Thus, scalabi lity might be extremely difficult. Second, data in a cloud is stored at an untrusted site. Though this paper is not looking into the security of cloud computing, this is still an important concept especially when it comes to transactional databases. This means that there is an increase in potential security risks, making the need to encrypt the data in the database a must. The majority of data in a transactional database is mission critical business data. This data needs to be protected and secure which is much more difficult in the cloud. Third, a cloud is able to provide high availability and durability, which is done by replicating the data across large geographic distances. In a transactional database, this would make maintaining ACID (Atomicity, Co nsistency, Isolation and Durability guarantees that a database's transactions are processed reliably) impossible. [15] Maintaining ACID compliancy is most notably the largest issue that transactional databases have with existing in a cloud. ACID complicat es elastic load balancing, scalability, live migration and performance of the database as noted above. Security The multitenant architecture must be able to isolate one tenant's database from another's. This includes verifying that a tenant only has acc ess to their specific data and that the database itself is secure from outside access. As the number of tenants grows, securing the database can become more and more complicated. Network latency

PAGE 52

40 Though we understand that network latency is an issue that plagues all types of databases whether transactional or a data warehouse (or even multitenant which we will get to in a minute) that reside in a cloud, we will not be resear ching a solution for this issue There are multiple reasons for latency. One rea sons for latency in a cloud database is the physical proximity of the user, database and application to each other. When evaluating the location of the database and the application, it is found that latency in the cloud is proportional to how far apart th e application and the database are to each other. As the application and the database get further and further apart, latency increases. Thus, it is important to try and migrate not only the database to the cloud but also the application. [20] An example of this issue can be seen with Salesforce.com. Salesforce.com began to offer its users a new relational database as a service (DaaS), Database.com. This database only serves as a backend for applications that are running on say, Amazon, Google or elsewhe re. This means that the database and the application are not close in proximity to each other and thus, users have found issues with latency when running their applications. In order to best utilize Database.com, users must have their applications runnin g on Force.com. [21] This appears to be a spectacularly orchestrated business move by Salesforce.com. Latency can also play a factor when we look at the physical location of the customer relative to the cloud, which houses their applications and/or database. Customers should always try to use a cloud that is closes to their physical location. The more routers and distance between the customer and the cloud, the higher the latency will be. Finally, customers should strive to take advantage of WAN ( Wide Area Network) optimizations. This can help to minimize the impact of bandwidth restrictions and work to give users the best possible link between themselves and their data and application. Understanding this type of information better helps us to be tter understand what we must do in order to optimize our applications and databases in the cloud. [22] The above latency issues deal strictly with locality and infrastructure, but there are other reasons for latency in the cloud. The number of concurrent users can directly impact the number of transactions that can occur per second. It's important to correctly configure a database to only allow for a maximum number of concurrent users as to not

PAGE 53

41 degrade performance. Latency can also be attributed to I/O bottlenecks. These bottlenecks can be directly related to high disk latency as the service provider. [23] Administrative issues As previously mentioned, depending on the multitenant architecture, administrative functions can be difficult. When the arch itecture is shared machine, the isolation between customers causes executing administrative operations in bulk impractical. It is necessary to execute the administrative queries on each database individually. In the shared process architecture, executing administrative operations in bulk is doable. But, operations such as adding customers, removing customer and extending the base schema entail executing DDL statements. This is problematic for databases, which behave poorly when their schemas are modified Finally, shared table, administrative operations can be executed in bulk but queries must include the correct range over the necessary tenant columns. Data warehouses A data warehouse can be thought of as a database that is mainly utilized for reporti ng. It is a snapshot of a production database at some point in time. These types of databases do not generally have transactions and can be integrated with different business intelligence tools in order to more easily extract data. One of the largest is sues surrounding placing a data warehouse into a cloud is the size/amount of the data that resides in the database. There are limitations on how much data a specific cloud service provider will allot any one customer as well as there are issues with actua lly migrating the data into the cloud. When dealing with a small amount of data, let's say under 100GB, there are more options available to customers than dealing with larger data sets that can be in the terabytes of data range. With 100GB or less, users can make decisions to have their data warehouse as consistent with production data as desired. When users have multiple terabytes of data, then there is less flexibility in what can be easily accomplished as far as consistency is concerned. There is als o a need here to evaluate the different options that service providers have in order to migrate the data into the cloud.

PAGE 54

42 Amazon AWS offers an import/export tool, which allows for 60TB or more to be loaded in less than 1 days time but the data must be sent to Amazon, via snail mail for them to actually load it. If a user has less than 5 TB of data and an Internet connection that was 100Mbps, then it would take them 1 to 2 days to load the data into the cloud at any given moment themselves. [17] These same types of issues surround Google App Engine as well as Microsoft's Azure. Google App Engine simply suggests utilizing test or .csv files to migrate data into the cloud. But, does not offer any type of assistance to migrate large amounts of data. This cou ld cause tremendous time delays and make any type of consistency of data between production data and the data warehouse difficult. [16] Microsoft's Azure has a 50GB maximum database size limit at this point in time. Azure suggests that data is divided int o smaller sizes so that it can more easily be loaded. It is speculated that Azure has a 50GB limit so that performance is always maintained. Keeping the data size small makes backups and recovery easier. [18] These limitations proved to be too much for J ohn Hopkins University as they attempted to put an existing scientific (astronomical) database known as the Sloan Digital Sky Survey (SDSS) in the cloud. They attempted this with two separate cloud providers, Amazon (EC2) and Microsoft (SQL Azure). When the users attempted to migrate the data to EC2, they utilized a 100GB subset of the database (which is approximately 1/35 th size of the actual data). They were also unsuccessful in actually getting queries on the data to run faster than on a single server The users had even less luck when they tried to migrate the data to Azure. They were unable to load all the data and the migrating tools that were provided by Microsoft automatically stripped out several features that rendered the data unusable such as functions and stored procedures. [19] This simply proves the validity of the data set size limitation. Other issues which plague data warehouses in clouds are fault tolerance and the ability to run in a heterogeneous environment. Due to the fact that man y times in data warehouses, there is a large amount of data and/or queries against the data, which are extracting a large data set, it's important that the DBMS/ architecture surrounding the data warehouse is fault tolerant. Fault tolerance for a data war ehouse means that a query does not have to be restarted if one of the nodes involved in the query process fails. When we evaluate how often a node in a cloud environment fails and the fact that

PAGE 55

43 extremely complex queries on large amounts of data could util ize hundreds (or even thousands) of server instances for hours, the likelihood for failure is extremely high. If the cloud and data warehouse cannot handle these faults, it will be extremely difficult to complete any query or analysis. [15] Finally, the d ata warehouse must be ability to run in a heterogeneous environment. The performance of the nodes in a cloud may not be consistent, which means that some nodes will out perform other nodes by an order of magnitude. Ideally, work that needs to be executed in a query will be equally divided across all nodes. Upon one node degrading in performance, the cloud should have the ability to take the appropriate measures to offload the work of the failing node to a different node(s). This ability would also help to improve the total query latency. This is not an easy feat for many service providers. But, is a necessity for customers contemplating placing their data warehouse into the cloud. [15]

PAGE 56

44 CHAPTER VI. CURRENT SOLUTIONS TO CHALLENGES Resource allocation and workload balancing One of the first challenges that cloud providers are faced with is making the determination of where to place the different databases/tenants within the system in order to minimize the number of machines required, while still meeting pe rformance goals. There are consequently three keys to workload balancing within a multitenant architecture, monitoring resources, predicting combined workload and performing the tenant consolidation. There are three possible solutions that we explore in this section for efficient resource allocation and workload management. First, the authors of Relational Cloud: A Database as a Service for the Cloud propose placing tenants and associated workload onto a set of nodes (or machines) that are dedicated only to that workload. During this phase, they will monitor the resources that are consumed and generate a time dependent resource profile that will allo w for them to predict how the workload will eventually interact with other tenant workloads' that are currently running within the system. The authors propose monitoring, predicting and consolidating workloads through an engine called Kairos. [7] Kairos m onitors CPU, RAM and disk I/O, analyzes the resource consumption for each database over time so that is may produce an assignment of databases to physical machines, finally, it performs the actual consolidation of the databases. [28] Resource monitoring by Kairos involves querying the OS and DBMS running on each machine in order to generate statistics about CPU, RAM and disk I/O, buffer pool utilization and log flushes. CPU usage for the consolidated workload is simply the sum of the CPU loads of every m ember's workload. Unfortunately, RAM is not so easy to measure. The statistics that are provided by the OS overestimate the actual resources that are required since they only report the total memory allocated to the database and not the memory that was a ctually in use. Therefore in order to estimate the actual amount of RAM that is used, the authors propose gauging the buffer pool. In order for a DBMS to

PAGE 57

45 operate efficiently, the working set should remain in main memory. As a result, techniques that es timate the working set of a database so that it can be determined whether or not two databases are consolidated together must be devised. The authors state that the initial step is to determine if the system is over provisioned. This can be done by colle cting information pertaining to OS disk reads and DBMS buffer pool miss ratios. If the miss ratio in the buffer pool is close to zero this tells us that the working set fits within the buffer pool. If the miss ratio of the buffer pool is high but there a re few physical disk reads then the working set does not fit in the buffer pull however, it does fit in the OS file cache. Finally, if there exists high buffer pool miss ratios and a lot of physical disk reads, the working set size exceed both the memory available in the buffer pool and the OS file cache, causing it to read from disk continuously. This last scenario indicates that memory is definitely not over provisioned and that the total RAM available to the DBMS is actively utilized. But, for the oth er scenarios, it's vital that we are able to measure the amount of memory that is being utilized either in the OS file cache or in the buffer pool. In order to do this, they authors issue SQL queries to a DBMS that is unmodified. First, they generate an empty probe table and grow it slowly. While growing the table, they force the DBMS to keep pages in the buffer pool by running queries several times for every insert. They then monitor disk reads by the DBMS. By gingerly "stealing" buffer pool cache spa ce as well as observing how many pages the DBMS reads back from disk, they are able to detect when they start to push useful pages out of the buffer cache. One additional important detail is how often to probe the table. This requires very careful balanc ing so that the table is probed often enough for the buffer manager to keep data in RAM but not so often that CPU overhead is added. Therefore, the authors propose querying the probe table once every 1 10 seconds to that the DBMS keeps the probe data in R AM and CPU overhead down. [28] On the simpler side, in order to understand disk I/O usage, OS tools such as iostat give an easy way to estimate the disk I/O. N ext the authors address how to estimate combined workloads. When it comes to estimating resour ce requirements for combined databases, CPU and RAM is not complicated, we would simply sum the CPU and RAM for each individual workload that

PAGE 58

46 could possibly co located. But, for determining combined load estimations for disk is much more complicated. The issue is the database utilizes unused disk bandwidth to proactively work through other tasks like flushing dirty pages from the buffer pool, I/O throughput grows sub linearly with the workload size which is dictated by the user, it is hard to predict exact ly how sequential or random a combined set of workloads will be and finally, there are numerous hardware and software configuration parameters that influence the I/O throughput a system can ultimately achieve. Therefore, measuring the actual amount of dis k I/O can be difficult with the workloads are combined. The authors suggest that regardless of the number of databases a DBMS hosts, it must coordinate I/O between the databases by combining log writes from the different workloads into a single sequential stream of log writes allowing for group commits to be leveraged. It must also delay write back operations of dirty pages for all of the different databases and perform them in sorted order to minimize disk seeks. The authors attempt to address the fact that the complex behavior of the disk subsystem makes modeling the I/O requirements difficult by treating the system as a black box and experimentally deriving its transfer function. [28] Thus, they developed a tool that automates the process of collectin g experimental data from the live system and then builds an empirical model' that captures disk behavior. The tool records row updates per second, the working set size in bytes and the complete disk throughput in bytes per second. The outcome is a map o f the system response to different degrees of load and working set sizes. This map can then predict how multiple workloads will behave once combined. [28] Now that they developed a technique to determine combined disk estimations, they must now assign wo rkloads to different physical servers to find an assignment that minimizes the number of machines as well as balances the load across those machines. Therefore, the created a function:

PAGE 59

47 Equation VI 1 Consolidation Precition Function [28] In the above figure, x ij =1 when workload i is assigned to server j and 0 otherwise, and R i is the number of replicas desired for workload i MaxCPU j MaxMEM j MaxDISK j are the maximum amount of CPU, RAM, and disk I/O available at server j and C ti is the time series describing the utilization of resource C (CPU, RAM, disk) for workload i at time t." [28] The authors state that their function accomplishes minimizing the number of servers that are required for conso lidation by using signum functions that are equal to 1 when input is greater than 0 and 0 when its input is 0. This model provides that any solution using k 1 servers will have a lower objective function value than any k server solution. The authors stat e that when there is at least one workload assigned to a server, they can evaluate the server's contribution by evaluating its resource utilization over time C ti causing for unbalanced solutions to be penalized. There are also constraints that guarantee the feasibility of any solution. The CPU, RAM and disk constraints allow for the combined load imposed on each server to never exceed the available resources at any given moment, which therefore avoids saturation and over commitment of a server. Finall y, the model that they established allows for them to handle replication and workload placement issues. The replication variable controls how many replicas of each workload need to be placed. Thus, they are able to achieve high consolidation factors

PAGE 60

48 and balance loads across servers without deteriorating the throughput of the consolidation workloads. [28] Scalability/Elasticity Live migration enables elastic load balancing and scalability with no downtime and minimal disruption of multitenant databases, which reside in a cloud computing environment. There are many ways in which live migration can be implemented. This section wil l review three of those techniques. One method to accomplish live migration is based on the concept of virtualization in the database layer. In this method, the goal is to decouple the logical representation of a cell (a cell is a self contained granule of application data, meta data, and state representing a tenant in the database) from the node hosting it. The authors of Live Database Migration for Elasticity in a Multitenant Database for Cloud Platforms utilize what is known as an iterative copy tech nique, which attempts to transfer the main memory state of the cell in order for the cell to restart warm at the destination node. T he main memory state of the cell is comprised of the cached database state and the transaction execution state. In general, the database state consists of the cached database pages or buffer pool or some variant of this. The transaction state includes the active transaction and possibly a subset of committed transactions, which are needed to validate the active transactions. The live migration presented here has two main phases.

PAGE 61

49 Figure VI 1 Database Migration Timeline. [29] Phase 0 can be thought of the database operating in normal mode, executing transactions. Phase 1 is known as the migration phase. This phase notifies the source node and the destination node to start migration. There are multiple sub phases to phase 1. Phase 1a begins the migration by taking a snapshot of the database state at the source node. The s napshot is then migrated over to the destination node and the migration of the specific cell is initialized. Note that the source node must continue to process transactions while the migration is in progress. Phase 1b is the actual iterative copy phase. Due to the fact that the source node continues to server the cell that is migrating while the snapshot is being moved to the destination node, the state of the migration cell at the destination node will be behind the actual state at the source node. The iterative copy attempts to catch up and synchronize the states between the destination node and the source node. Phase 1c is the actual atomic handover of ownership of the migrated cell to the destination node. The source node stops serving the cell and copies the final un synchronized state to the destination node, flushes all changes from committed transactions to the persistent storage. Finally, phase 2 is the post migration and marks the restarting of operations. This iterative copy migration allow s for minimal service

PAGE 62

50 disruption as opposed to other techniques such as stop and copy or on demand migration. In stop and copy, the service to a specific cell is stopped, the data is copied and migrated, and then service is started once again. In On dema nd migration, minimal information is transferred during what is known as a quick stop and copy migration. Thus, it is easy to see why this option is much more appealing than other proposed solutions. [29] Another method that has been introduced as an opt ion for performing live data migration is a technique, which takes advantage of on demand pull and asynchronous pushes of data. The authors of Zephyr: Live Migration in Shared Nothing Databases for Elastic Cloud Platforms utilize this synchronous dual mo de in order to allow for both the source and the destination nodes to execute transactions. First, the tenant's metadata is migrated to the destination node. At which point in time, the destination node can begin serving new transactions while the source node is completing any transactions that were active when the migration began. Here, read and write access or rather ownership of the database pages are partitioned between the source and destination nodes where the source node initially owns all the pag es and the destination node only acquires pages ownership on demand as transactions at the destination node access the pages. It's also important to note that index structures are replicated from the source to the destination during the migration. Synchr onization between the source and destination is necessary during the short dual mode. Zephyr does not rely on the database layer, which allows for it to provide better flexibility in choosing the destination for migration, which may or may not have the te nant's replica. [27] The authors of Relational Cloud: A Database Service for the Cloud present the third live migration and elastic scalability technique They believed that the solution in elastic scalability could be accomplished through database part itioning. The partitioning strategy that the authors propose is focused around OLTP and Web workloads, which means that they are well suited for short lived transactions. Consequently, they must partition the data in such a way that they can minimize the number of multi node transactions. When the number of nodes is not minimized, then there is an increase in the time spent holding locks. Therefore, they analyze execution traces so that they can identify sets of tuples that are accessed together within i ndividual transactions. These are represented as a graph where each node is a tuple and an edge is drawn between two

PAGE 63

51 nodes whose tuples are touched with a single transaction. The weight on the edge will represent how many times the tup le is accessed in t he workload. The authors then use graph partitioning to find l balanced logical partitions, while trying to minimize the total weight of the cut edges. The goal is to hopefully find a partitioning of the database tuples that minimizes the number of distr ibuted transactions. The relational cloud must now find a very concise representation of the partitions so that SQL statements can be appropriately routed; this is done by defining a set of predicates on the tuple attributes. Therefore, given a set of tu ples, and a partition label for each tuple, the system can extract a set of candidate attributes from the predicates used in the trace. Once this is complete, the attributes are given to the decision tree algorithm along with the partitioning labels. If the decision tree can successfully generalize the partitioning with just a few predicates, what is considered a good explanation for the graph partition is found. Otherwise, the system must use lookup tables to represent the partitioning scheme. [7] This approach allows for independence from the schema layout as well as the foreign key information. The authors state that this allows for "intrinsic correlations hidden in data". [7] But, this also means that the approach is only effective when it comes to partitioning databases containing multiple many to many relationships. The technique furthermore encounters difficulties since it cold lead to a graph with N nodes and N 2 edges for an N tuple database. [7] Database Schema Issues As previously alluded to, it is common practice for customers that are migrating to a multi tenant cloud environment to need to map a single tenant schema to the multitenant schema in the database. This can be extremely challenging to a service provider to create a base schema, wh ich allows for the tenants to be easily map. It also introduces an issue of shared tables being too sparse as well as the inability to effectively utilize indexing. All of these issues cause for the unnecessary usage of resources. First, we will look at a way to map schemas to maximize efficiency within the database. Then, we will evaluate a technique that limits the number of null fields and provides indexing for multitenant architectures that are shared table

PAGE 64

52 The authors of Multi Tenant Databases for Software as a Service: Schema Mapping Techniques suggest that specific tables must be shared among tenants and others must be mapped to fixed generic structures. The basis of this new schema is to help implement multi tenancy on top of a standard (exist ing) relational database. Thus, they introduce a new schema mapping technique called "Chunk Folding, where logical tables are vertically partitioned into chunks that are folded together into different physical multi tenant tables and joined as needed." [8 ] The authors also take the meta data and divide it between application specific tables and a large fixed set of generic tables called Chunk Tables. An example of this would be as follows: Figure VI 2 Chunk Folding Example. [8] The initial chunk is a row is stored in a table that is associated with the entity Account. The second chunk is also stored in a conventional table associated with an extension for health care. All remaining chunks are store d in different chunk tables. The best performance is obtained by mapping the most heavily utilized parts of the logical schema into the conventional tables and the rest into Chunk Tables, which match their structure as close as possible. Through experim entations, the authors are able to find that narrow Chunk Tables encounter a large overhead for reconstructing the rows whereas wider Chunk Tables are more competitive in their performance to a conventional table. [8] Chunk folding is not the only techniqu e for schema mapping. But, chunk folding is the only technique, which tries to account for the logical schemas of tenants, the

PAGE 65

53 distribution of data within those schemas and the application q ueries that go along with them. First there is a basic layout te chnique. This technique is extremely easy to implement, by adding a tenant ID column to each table and share the tables among the different tenants. This approach allows for good consolidation but no extending capabilities. Next we look at extension tab le layout, extensions are split into separate tables, where tenants may share extensions. This implies that the extension tables as well as the base tables must have a tenant column. Here, a row column must be created so that the logical source tables ca n be reconstructed. Figure VI 3 Extension Table Layout. [8] Thus, at runtime in an extension table layout, the reconstruction of the logical source tables carries a large overhead due to the additional jo ins and I/O if the row fragments are not clustered together. A draw back to this approach is that the number of tables will grow in proportion to the number of tenants. Other schema mapping techniques include universal table layout and pivot table layout The solution that we are more concerned with is the chunk table layout structure and the actual chunk folding. Figure VI 4 Chunk Table. [8]

PAGE 66

54 The chunk table layout is effective when data can be partit ioned into dense subsets. The chunk table has a set of data columns of different types, with and without indexes. There is also a chunk column where each logical source table is partitioned into groups of columns each with a chunk id. This reduces the a mount of stored meta data and the overhead for reconstructing the logical source tables. This approach also allows for a precise way of adding indexes and splitting overly wide columns. But, it generates more complicated query transformations. Now, chun k folding comes into play where logical source tables are vertically partitioned into chunks, which can be folded together into different physical multi tenant tables and joined as required. Figure VI 5 Chunk Folding. [8] The above example shows where Accounts are placed into a conventional table and extensions are placed in a single chunk table. The database's metadata is divided between application specific conventional tables and large fixed sets o f chunk tables. [8] Next, we look at a possible solution for limiting the sparsity of tables as well as how indexing on multitenant shared tables can be accomplished. The authors of Supporting Database Applications as a Service introduce M Store, which provides storage and indexing services for multitenant databases. To account for the additional problems that arise they introduce Bitmap Interpreted Tuple (BIT) and Multi Separated Index (MSI). M Store utilizes shared tables to achieve optimal scalability in a multitenant cloud. In this environment, when using shared tables, tenants store their tuples to the shared tables by appending each with a TenantID, which signifies which tenant the tuple belongs to and setting unused att ributes to NULL. Consequently, this

PAGE 67

55 creates the issue of shared tables being too spared. In order to make the base schema general, the service provider must cover each possible attribute that the tenant may use, thus leading to creating the base schema a s a huge number of attributes. On the other hand, the tenant more than likely only utilizes a small handful of the attributes, allowing for a substantial amount of NULLs to be stored in the shared table. Using BIT, only values from configured attributes are stored in the shared table. Thus, NULL values from unused attributes are not stored. To achieve this, a bitmap string is constructed for each tenant that resolves which attributes belong to that tenant and which do not. Next, tuples are stored and r etrieved based off the bitmap string created for each tenant. Further detail gives evidence that the length of the bitmap string is directly proportional to the number of attributes in the base schema. Each position in the string corresponds to whether o r not an attribute is used by setting the value to 1 or 0 respectively. Therefore, when a tenant performs a tuple insertion, NULLs in attributes where their position corresponds to a 0 in the bitmap string are removed. The bitmap string can also be utili zed to retrieve specific attributes. The second piece of M store, MSI, accounts for the fact that since the amount of data is large in a shared table, there must be an efficient indexing technique utilized to retrieve tuples. Instead of building an index for all tenants, they build an index for each specific tenant. Though the number of indexes grows linearly with the number of tenants, given a particular attribute, only a small portion of tenants will build an index on that attribute. This makes index s cans more efficient due to the fact that each tenant need only scan their own index files and tuples. [24]

PAGE 68

56 CHAPTER VII. CONCLUSION Overview With the increasing number of applications that are being deployed onto cloud platforms, the need for being able to e fficiently manage resources for a multitenant database is real and increasing. M ultitenant database s in a cloud must have the ability to perform live migration for effective load balancing and elasticity as well as have the ability to properly monitor, pre dict and consolidate database workloads accurately in order to achieve efficient resource management. Best Architecture DBMS architecture Defining a very specific database system architecture is critical for obtaining the optimal results when trying to pe rform live migrati on or workload consolidation. We propose that a parallel database is utilized with a shared disk memory architecture. This will allow for all processors to access disks with roughly the same performance, but they will be unable to acces s each other's RAM. A parallel database will improve performance of loading of data, index building and evaluation of queries. Parallel databases are specifically instrumental when dealing with large databases that process a large number of transactions. It will increase throughput, improve response time, has the ability to process a large numbers of transactions without issues, provides substantial performance improvements, increases the availability of the system and server a large number of users. [26 ] Furthermore, shared disk architecture is ideal for cloud computing. It allows for clusters of low cost servers to be used as a single collection of data and can easily be served by a storage area network (SAN) or a network attached storage (NAS). Share d disk also supports elastic scaling since one can easily add another server to increase throughput. Shared disk also lowers administrative costs since servers can be

PAGE 69

57 upgraded individually without taking the entire cluster offline. Not only that, but sha red disk provides high availability which is a necessity in cloud computing. Finally, shared disk will allow for a multitude of data partitioning options, which can help with overall performance of the system [25] Now that the overall database model has b een provided, the focus is turned to an overall system setup. S hared process is the most feasible multitenant architecture that is available to and for the majority of tenants. Though, it has not gone unnoticed that SalesForce has had tremendous success with shared table, shared process fits in better with my concepts of efficient resource management of multitenant databases in a cloud environment. Therefore, the authors of Live Database Migration for Elasticity in a Multitenant Database for Cloud Platfo rms were on the right path with some of their multitenant database system architecture decisions. One of the most important concepts is that the logical representation of a tenant should be decoupled from the physical server that is hosting it. Below is the representation of the multitenant database model the authors of the article designed. We will further expand on this design. Figure VII 1 Database Architecture Model [29]

PAGE 70

58 First, the architecture must decouple the ownership by using network attached storage (NAS). This will allow for the actual DBMS data to be stored persistently. This will also provide scaling of the storage layer for additional capacity as well as throug hput. This will also allow for the transfer of ownership from one DBMS node to another when live migration is performed and prevent the need to migrate any actual data. This will make the live migration must quicker. Next, a tenant's transactions should be isolated to a single node. If we can anticipate that a tenant is small enough to be consistently serviced by a single node, this will remove the need for distributed synchronization among all the nodes for transactions. During migration, we can be gu aranteed that the transactions processed by a tenant are only interacting with one node. The third design in the architecture is that there must exist some type of abstraction, which conceals the dynamics within the DBMS from the tenants. Is should be un necessary for the tenant to realize which physical machine hosts their data. Therefore, when users issue queries, there must be some type of query router that hides how the queries are routed to the correct DBMS node hosting the cell. This way, when live migration is performed, it will be seamless in the tenant's eyes. They will not need to understand how to redirect their queries. Later, the query router will play an intricate role in the system as overall. The next item in the multitenant cloud envir onment model, ideally, would allow for each DBMS node (pictured above) to run a single DBMS instance and host multiple tenants. This means that each tenant that is hosted by a node would share the buffer pool and logging infrastructure for maintaining tra nsaction logs. By sharing the logs among the different cells, this prevents multiple independent and competing disk writes, which could come about by having the different tenants logging at different times and therefore improve overall performance. [29] I t would be anticipated that each DBMS node has a large shared buffer pool in its own memory that has the ability to dynamically adjust the size based on system needs and available resources. It is also important to enforce how the data is laid out across the different disks it has available. Since sequential access is much quicker than random access, the DBMS must place blocks onto the disk so that queries have the ability to access the data sequentially. The DBMS clearly understands its workload access p atterns fa r better than any underlying OS, thus the DBMS must have full control over spatial positioning of the

PAGE 71

59 database blocks on disk. Therefore, there should exist a file system on each disk (or logical volume) within the DBMS to allow for the DBMS to allocate a single large file in each of the file systems and control the placement of data within that file. It is possible to recommend that the DBMS stores data directly to the raw storage device, this would make the portability of the DBMS more difficu lt. As a result, the DBMS should control where the data should be placed on disk, we also need for the DBMS to dictate when the data is physically written to disk. The main reasons for this have been previously discussed in section 2.6.2, but it is import ant to recall that his will directly impact the transactional database's ACID compliance as well as improve overall system performance. [1] Database n ormalization Database normalization is the process of minimizing redundancy and dependency related to fi elds and tables of a relational database. The objective of normalization is to isolate data so that additions, deletions and modifications of fields are made in only one table and then propagated throughout the rest of the database through defined relation ships. [31] There are many benefits to a database from normalization. It provides better overall database organization, reduces the amount of redundant data, provides data consistency within the database, gives a more flexible database design and finally it presents a better handle on overall security. It is also easy to see that this methodology conserves disk space by minimizing duplicate data and the potential of inconsistent data is reduced since the data has been broken into smaller tables, finally, the database is more flexible as far as modifying existing structures. Since redundant data does not exist, it is easier to grant limited table access. [32] The major disadvantage of normalization is that it reduces database performance. Upon a user que rying the database, there are factors such as CPU usage, memory usage and I/O usage that must be taken into consideration. A normalized database requires much more CPU, memory and I/O in order to process a transaction and queries. The

PAGE 72

60 normalized database must first locate the requested tables and then join the data from all the tables together in order for the request to be processed. There are multiple Normal forms. They are numbered from the lowest form of normalization, first normal form, through the fifth normal form. Fifth normal form is rarely seen or utilized. First normal form (1NF) eliminates duplicate columns from the same table and creates separate tables for each group of related data. Each row also has a unique column or a multiple columns as the primary key. Second normal form (2NF) follows all the requirements of first normal form but also removes subsets of data that apply to multiple rows of a table by placing them into a separate table. It also creates a relationship between the new tables and predecessors via foreign keys. Third normal form (3NF) must meet all the rules for second (and thus first) normal forms as well as it removes columns that are not dependent upon the primary key. Boyce Codd normal form (BCNF) must meet all the requirements of third normal form and also every determinant must be a candidate key. Fourth normal form (4NF) must meet all the requirements of third normal form but also have no multi valued dependencies. [30] There is also a denormalization process tha t a database can undergo. This process involves modifying table structures to allow for a controlled redundancy in order to increase database performance. A denormalized database and a database that has not been normalized are different things. [30] Ide ally, the database normalization for our system should not go beyond second normal form. This way, we could maintain all of the concepts that are important with relational, transactional databases but at the same time we can anticipate there will not be a n increasing number of join statements for queries to work properly. Therefore, there will be no overall performance degradation due to the additional overhead of SQL statements. Resource Allocation & Load Balancing Monitoring resources The authors of Workload Aware Database Monitoring and Consolidation provided us with some information pertaining to how they would monitor CPU, RAM

PAGE 73

61 and disk I/O, buffer pool and log flushes. Their ideas are good for gauging RAM in a database, but can be tuned to be more accurate. In order to guage the working set size of the specific tenant, it would be much more accurate to use queries which pertain to the application than just determining the working set size based on queries that are not even relevant to the tenant s database. If we were to initially hold a database in a staging area prior to integrating it with other tenant databases, (This concept is also utilized in the indexing and partitionin g section of the paper, 7.5.) t his would allow for the collection of co mmon queries and accurate statistics on resources since the database is on designated hardware as this point. Then these queries that are issued could easily be simulated for performance testing. If we begin to witness a miss ratio of the buffer pool tha t is close to zero, then we should decrease the size of the buffer pool, simulate the queries again and evaluate the miss ratio. Eventually, this process will allow for us to identify the smallest amount of RAM that is required for the database to functio n correctly. If on the other hand, we are experiencing high buffer pool miss ratios but hardly any physical disk reads or high buffer pool miss ratios and high physical disk reads, we can increase the size of the buffer pool until we are able to come clos e to a zero miss ratio of the buffer pool. This would help to make a determination on the minimum size our buffer pool should be as well as the minimum amount of RAM that is required for the database to function correctly. Predicting combined workload When evaluating combined CPU usage, it is true, as stated by the authors of Workload Aware Database Monitoring and Consolidation that the CPU usage found above, in the monitoring section, can simply be added together to obtain a total CPU usage of the comb ined workload. For RAM, it was previously established the minimum size that a buffer pool needs to be in order to hold the working set of a specific database, therefore, the sum of the amounts could be calculated between the databases that are to be consi der ed for consolidati on Finally, predicting the combined workload for disk I/O can be estimated to be the sum of all disk I/O across the combined systems.

PAGE 74

62 Another factor that should be taken into consideration when predicting a combined workload and which databases should be consolidated together is each database's peak hours. This is the timeframe that the database is utilized the most heavily. Many databases sit idle for long periods of t ime with quick peaks of utilization. Depending on where the majority of customers or users reside, the hours in which the database/application is utilized could be extremely different. Two databases with opposite workloads could potentially be combined o nto the same server since peak times will not conflict with each other. Ultimately, this would be a statistic that is easily collected when collecting information related to resource usage. Workload consolidation When consolidating workloads, there is one additional step that should be take n in order to maximize efficiency, the top queries that have been identified for each databases' working set, should be pinned in the buffer pool. It is possible that since the database that is to be migrated into th e multitenant environment will be held in a staging area first where statistics and information pertaining to the database and workload can be gathered, then we should be able to assume that during this point in time, majority of the queries against the da tabase have been accounted for. We should be able to see which of those queries are continuously being called and which tables are being utilized. Since in DBMS there is a concept of pinning items within the buffer pool. We could pin tables in memory so that access times to heavily used tables can be improved. [1] Live Migration Additional ideas should be included when performing live migration. The main concept of live migration, which has already been presented (see section 6.2), can be utilized but ot her concepts can and should be taken into consideration to further optimize the process. The first proposed change would be in the determination of when to perform live migration. If again the concept of a query router is created which was initially pres ented by the authors of Relational Cloud: A Database as a Service for the Cloud as well as

PAGE 75

63 the authors of Live Database Migration for Elasticity in a Multitenant Database for Cloud Platforms we could ultimately utilized the query router to not only rout e transactions/requests to the appropriate DBMS node [29] that is hosting the tenant, but we could also use it to monitor SQL statements, estimate the cost of queries and finally provide a degree of performance isolation by controlling the rate in which qu eries are dispatched. [7] The first concept of the query router directly correlates with our multitenant database model to mask the physical location of a tenant's data from the tenant. The query router first and foremost will be responsible for routing the query to the proper node. [29] Next, the query router should also review queries that are being executed to identify their access patterns. Once we have information pertaining to their access patterns we can better make decisions surrounding databas e partitioning and indexing (which will be discussed in more detail below). This could also lead to us potentially modifying the query optimizer to better execute certain queries that can be seen repeatedly running against different database. This will a llow for us to identify a working set on the different DBMS nodes. The option to modify the query optimizer must be made available. Furthermore, the query router could ultimately estimate the cost of a query or a set of queries based on the available res ources of the system. In order to accomplish this, the query router would need to keep track of which DBMS node a query is being routed to along with the potential cost of the query, which is provided by the query optimizer (discussed in section 2.4), the arrival time of the SQL request and finally, the service level agreement (SLA) requirements for performance/time restrictions. Ultimately, the query router w ould make a decision on which SQL requests should run concurrently and whether or not the request s exceed the resources readily available on the machine and would potentially violate SLA. The system would need to continuously recalculate available resources and costs as query results are returned to make sure SLA standards are being satisfied. Now, t he query router is functioning to control the rate at which tenant requests are being made to specific nodes within the system. We also now have a way to recognize that the required resources to meet SLA are not available and live migration must take plac e.

PAGE 76

64 Partitioning and Indexing One of the key factors for deciding to use a shared process multitenant architecture within the cloud is to allow for the ability to add indexes to increase database performance as well as partition data based on a specific ten ant. F or each separate tenant, the query router should monitor how many times it has seen the same or similar query as well as how long the query takes to return results (as previously mentioned) Keeping track of which fields are being referenced in the query and the amount of time a query is running for will allow for us to know which fields should be indexed and in what orders. If the same queries are repeatedly call ed over and over, then we want to optimize the system to handle those queries. We wan t to maintain non clustered indexes where three or less indexes exist on any given table. One of the indexes will be for the primary key of the table. Since we are dealing with a relational database, we know that there will exist a primary key on every t able. Then also allow for one or two additional indexes on a given table based on the frequency of a query or a query taking an extended amount of time. It would be ideal if the query router would continuously monitor which fields of a table are constant ly being accessed and if it changes over time, then we would be allowed to drop and recreate the indexes based on the new evidence. Though, in all actuality, it is unlikely for applications to have changing queries over time. What this has ultimately done is tried to optimize the fields that are being used and not just create indexes on data that are not even utilized. That is a waste of space and resources. Now, logic should be i ntroduce d to the system so that is would be smart enough to possibly re arr ange how a query is structured so that the indexes can be guaranteed to always be utilized every possible query. Finally, by having the query router keep track of which queries are being executed, allows for gather ing of information pertaining to how data should be partitioned within the database. Not only that, due to the structure of the system, this has now allowed for the data to be partitioned based specifically on a tenant and their activities. The data should be both horizontally and vertically par titioned. The vertical partitioning should be based on the columns that are accessed on a consistent basis by

PAGE 77

65 queries. The horizontal partitioning should be related to breaking up tables with a large number of rows. Again it is possible for the query ro uter to identify which areas of a table are being utilized. This would determine where to divide the database. Once we have identified which columns are vertically partitioned, that data should be placed on hardware that has better I/O performance. This will allow for the most active areas (hot spots) within the database to be faster than if the data only existed on traditional disks. In order to account for all of these different factors for data access, the database could initially be migrated to a staging area where it is on dedicated hardware. Then upon migrating the system into the multitenant environment, the recommended indexes and partitions would be applied. From there, they would continue to be monitored by the query router.

PAGE 78

66 REFERENCES 1. Joseph M. Hellerstein Michael Stonebraker James Hamilton, Architecture of a Database System, Foundations and Trends in Databases, v.1 n.2, p.141 259, February 2007 2. Wikipedia, (2011, May 2). Cloud Computing [Online]. Available: http://en.wikipedia.org /wiki/MSI_protocol 3. Unknown. (2009, August 13). Advantages of Cloud Computing, [Online]. Available: http://contactdubai.com/webhosting/advantages of cloud computing 4. Introduction to Cloud Computing Architecture 1 st ed., Sun Microsystems, Santa Clara, CA, 2009 5. Randy Bias, (2009, Sept 29). Cloud Standards are Misunderstood, [Online]. Available: http://cloudscaling.com/blog/cloud computing/cloud standards are misunderstood 6. Wikipedia, (2011, May 07). S oftware as a S ervice, [Online]. Available: http://en.wikipedia.org/wiki/Softwar e_as_a_service 7. Curino, Carlo et al. "Relational Cloud: A Database as a Service for the Cloud." 5th Biennial Conference on Innovative Data Systems Research, CIDR 2011, January 9 12, 2011 Asilomar,California 8. Stefan Aulbach; Torsten Grust; Dean Jacobs; Alfons Kemper; Jan Rittinger; "Multi Tenant Databases for Software as a Service: Schema Mapping Techniques In Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2008, Vancou ver, BC, Canada, June 10 12, 2008, pages 1195 1206. ACM, 2008 9. Amazon, (2011), Amazon Elastic Compute Cloud, [Online]. Available: http://aws.amazon.com/ec2/ 10. Mateljan, V.; Cisic, D.; Ogrizovic, D., "Cloud Database as a Service (DaaS) ROI," MIPRO, 2010 Proceedings of the 33rd International Convention vol., no., pp.1185 1188, 24 28 May 2010 11. Amazon, (2011). Amazon RDS running Oracle Database, [Online]. Available: http://aws.amazon.com/rds/oracle/?utm_source=OraclePR&utm_medium=RDSL andingPage&utm_campaign=Oracle 12. Frederick Chong, Gianpaolo Carraro, Roger Wolter, (2006, June), Multi Tenant Data Architecture [Online]. Available: http://msdn.microsoft.com/en us/library/aa479086.aspx 13. Dean Jacobs and Stefan Aulbach (2007). Ruminations on Multi Tenant Databases [Online]. Available: http://cloud.pubs.dbs.uni leipzig.de/sites/cloud.pubs.dbs.uni leipzig.de/files/Jacobs2007RuminationsonMultiTenantDatabases.pdf 14. A. Elmore, S. Das, D. Agrawal, A. El Abbadi. Who's Driving this Clo ud? Towards Efficient Migration for Elastic and Autonomic Multitenant Databases. Technical Report 2010 05,CS,UCSB, 2010.

PAGE 79

67 15. Daniel J. Abadi, "Data Management in the Cloud: Limitations and Opportunities, IEEE Data Eng. Bull. vol. 32, no. 1, pp. 3 12, 200 9 16. Google, (2011). Uploading and Downloading Data Google App Engine, [Online]. Available: http://code.google.com/appengine/docs/python/tools/uploadingdata.html 17. Amzaon, (20 11). AWS Import/Export [Online]. Available: http://aws.amazon.com/importexportv/ 18. Lubor, (2010, Jul 30). Loading data to SQL Azure the fast way [Online]. Available: http://blogs.msdn.com/b/sqlcat/archive/2010/07/30/loading data to sql azure the fast way.aspx 19. Ani Thakar and Alex Szalay. 2010. Migrating a (large) sc ience database to the cloud. In Proceedings of the 19th ACM International Symposium on High Performance Distributed Computing (HPDC '10). ACM, New York, NY, USA, 430 434 20. Ian Murphy, (2010, June 10). Why Databases Must Follow the Application to the Cloud, [ Online]. Available: http://www.computerweekly.com/blogs/database notes/2010/06/why databases must follow the applications to the cloud.html 21. Eric Knorr, (2010, Dec 7). What Salesforce's Database.com really means [Online]. Available: http://www.infoworld.com/t/cloud computin g/what salesforces databasecom really means 759 22. John Considine, (2010, Mar 04). Cloud Latency issues [Online]. Available: http://www.cloudswitch.com/blog/tag/cloud%20latency%20issues 23. Sean Porter (2010, Mar). Fix IO bottleneck by throwing disks at it! EC2 Style, [Online]. Available: http://porter tech.ca/fix your io bottleneck by throwing disks at i 24. Mei Hui; Dawei Jiang; Guoliang Li; Yuan Zhou; "Supporting Database Applications as a Service," Data Engineering, 2009. ICDE '09. IEEE 25th International Conference on vol., no., pp.832 843, March 29 2009 April 2 2009 25. Mike Hogan. (2008, November 14). Cloud Computing & Databases How Databases can meet the demands of cloud computing [Online]. Available: https://docs.google.com/viewer?a=v&q=cache:sS9SAVRVePoJ:www.scaledb.co m/pdfs/CloudComputingDaaS.pdf +&hl=en&gl=us&pid=bl&srcid=ADGEEShL3 muPWNagHHC1INJcq_Dp4lZDc04pk68rkeW1_3aG9r87NbDd431P7IwTYJLt9 qUohWQXKOPPGWKSeNSFiugDgYyuUHPy0KD5aJCyrXmfm4EdoXFm0bXr 4Z8Sbaw0M0T3 Pr2&sig=AHIEtbRVkbGoiy71L5eOjbvwxAyBoWx8lQ 26. S.K. Singh, "Parallel Database Systems", in Datab ase Systems: Concepts, Design and Applications, 1st ed. Prentice Hal, 2009, ch. 17, pp 527 537. 27. Aaron Elmore et al. "Zephyr: Live Migration in Shared Nothing Databases for Elastic Cloud Platforms." SIGMOD'11, June 12 16, 2011 Athens, Greece 28. Carlo Curin o; Evan Jones; Samuel Madden; Hari Balakrishnan; "Workload Aware Database Monitoring and Consolidation," SIGMOD'11. June 12 16, Athens, Greece 2011 29. S. Das, S. Nishimura, D. Agrawal, and A. El Abbadi. Albatross: Lightweight Elasticity in Shared Storage Databases for the Cloud using Live Data Migration. PVLDB, 4(8): 494 505, May 2011.

PAGE 80

68 30. Wikipedia. (2012, March 19). Database Normalization [Online]. Available at: http://en.wikipedia.org/wik i/Database_normalization 31. Mike Chapple. (2012). Database Normalization Basics [Online]. Available at: http://databases.about.com/od/specificproducts/a/normalization.htm 32. Ronald Plew and Ryan Stephens. (2003, January 24). The Database Normalization Process [Online]. Available at: http://www.informit.com/articles/article.aspx?p=30646 33. Wikipedia. (2012, March 5). Partition (Databases) [Online]. Available at: http://en.wikipedia.org/wiki/Partition_%28database%29 34. Wikipedia. (2012, March 22). Database Index [Online]. Available at: http://en.wikipedia.org/wiki/Database_index