Ignacio Castro| Cloud Computing
1
ECS781(A,P) CLOUD COMPUTING
Cloud Data Management
Dr. Ignacio Castro
School of Electronic Engineering and Computer Science
Security (quick recap)
▪ Attack types
▪ Hashing: what it is, how to use it
▪ Encryption:
▪ Symmetric vs asymmetric
▪ Public vs private key encryption
Ignacio Castro| Cloud Computing
3
The Cloud is someone else computer
Ignacio Castro| Cloud Computing
4
https://xkcd.com/908/
And sh** happens: OVH/Strasbourg burned (10/03/2021)
Ignacio Castro| Cloud Computing
5
Contents
▪ Data at Cloud Scale
▪ Dealing with partitioning
▪ Dealing with replication
▪ Cloud Data Management Systems
Ignacio Castro| Cloud Computing
6
Traditional Data Management Systems
▪ Table model for data, based on relational algebra
▪ Very powerful query language (SQL)
▪ Requires expertise, careful design of table structure, indices and queries
▪ Data consistency and reliability are guaranteed by ACID properties
▪ Atomicity, Consistency, Isolation, and Durability
▪ Single, powerful machines (vertical scalability)
Ignacio Castro| Cloud Computing
7
PID
DESCRIPTION
PRICE
1
Intel i7
£400
2
Surface Pro
£899
3
32Gb Ram
£200
4
Raspberry PI+
£30
5
Geforce 1080
£4000
OID
CID
ODATE
SDATE
1
1
29/4/2018
NULL
2
2
20/1/2018
24/1/2008
CID
NAME
COMPANY
ADDRESS
1
Theresa
GOVUK
Downing st
2
Colin
QMUL
Mile End Rd
OID
PID
AMOUNT
1
1
2
1
5
2
2
2
1
SQL Tables
orders
products
clients
order_details
Ignacio Castro| Cloud Computing
8
Sample SQL Queries
▪ INSERT INTO orders VALUES (1000, 1, ‘2018-04-29’, ‘2018-05-01’);
▪ UPDATE products SET PRICE=8000, DESCRIPTION=‘Geforce 1080’ WHERE PID = ‘1’;
▪ DELETE FROM orders WHERE ODATE < ‘2012-12-31’ and SDATE IS NOT NULL;
▪SELECT DESCRIPTION, PRICE FROM products; ▪SELECT * FROM products;
▪SELECT * FROM products WHERE PRICE < 300; ▪SELECT * FROM products WHERE PID = ‘1’;
Ignacio Castro| Cloud Computing
9
ACID Database Properties
▪ Atomicity
▪ All or nothing: transactions must act as a whole, or not at all
▪ No changes within a transaction can persist if any change within the transaction fails
▪ Consistency
▪ Must transform database from one valid state to another: changes made by a transaction respect all database integrity constraints and the database remains in a consistent state at the end of a transaction
▪ Isolation
▪ Transactions cannot see changes made by other concurrent transactions
▪ Concurrent transactions leave the database in the same state as if the transactions were executed serially
▪ Durability
▪ Database data are persistent,
▪ Changes made by a transaction that completed successfully are stored permanently
Ignacio Castro| Cloud Computing
10
How much data is generated in the cloud?
Ignacio Castro| Cloud Computing
11
Evolution of Cloud applications
Ignacio Castro| Cloud Computing
12
Concerns of cloud application developers
▪ Reliability: the system should continue to work correctly in the face of adversity
▪ Scalability: as the system growths, there should be reasonable ways of dealing with that growth
▪ Maintainability: over time, it should be productive to not only maintain the current behaviour of the system, but also adapt it to new use cases
Ignacio Castro| Cloud Computing
13
Requirements for Cloud Data management
▪ Reliability: preventing data loss, making database services highly available
▪ Preventing single points of failure
▪ Scalability: more data to store, more users requesting data
▪ Latency: Internet users from all locations ▪ Maintainability
▪ As services/applications change, so might the data model
Ignacio Castro| Cloud Computing
14
NoSQL databases
▪ NoSQL (Not only SQL) systems
▪ Started in the 2000s, exploded in 2010s
▪ Motivation: ▪ scalability
▪ simpler data models ▪ programmer friendly
Ignacio Castro| Cloud Computing
15
ACID vs BASE
▪NoSQL sacrifices ACID for performance/scalability
▪Updates eventually propagated, but limited guarantees on the consistency of reads
▪“BASE” instead of “ACID”:
▪BASE = Basically Available, Soft state,
Ignacio Castro| Cloud Computing
16
Eventually consistent
▪ACID = Atomicity, Consistency, Isolation, Durability
NoSQL database types and examples
▪ Key/value Databases
▪ Simple value or row, indexed by a key ▪ e.g. Voldemort, Vertica, memcached
▪ Big table Databases
▪ “a sparse, distributed, persistent multidimensional sorted map”
▪ e.g. Google BigTable, Azure Table Storage, Amazon SimpleDB, Apache Cassandra
▪ Document Databases
▪ Multi-field documents (or objects) with JSON access ▪ e.g. MongoDB, RavenDB (.NET specific), CouchDB
▪ Graph Databases
▪ Manage nodes, edges, and properties ▪ e.g. Neo4j, TitanDB
Ignacio Castro| Cloud Computing
17
NoSQL databases landscape
Support for various interfaces for data access
Logically model data using loosely typed extensible data schema
Horizontal scaling through data distribution model across multiple nodes
Data persists either in disk or memory or both; sometimes in pluggable custom stores
Ignacio Castro| Cloud Computing
18
Taking advantage of cloud elasticity
▪ Vertical scaling
▪ Use more powerful VMs... up to a point
▪ Horizontal scaling
▪ Data is partitioned into multiple cloud instances ▪ Need mapping from data to partition
▪ Replication
▪ Achieve reliability
▪ Replica management (updates)
Ignacio Castro| Cloud Computing
19
Contents
▪ Data at Cloud Scale
▪ Dealing with partitioning
▪ Dealing with replication
▪ Cloud Data Management Systems
Ignacio Castro| Cloud Computing
20
How to scale: Partition
▪ Partition: division of a logical database or its constituent elements into distinct independent parts
▪ Critical for scalability
▪ Two main types of partitioning: ▪ Horizontal
▪ vertical
Ignacio Castro| Cloud Computing
21
Partition
Division of a logical database or its elements into distinct independent parts
▪ Critical for scalability
▪ Two main types of partitioning: ▪ Horizontal
▪ vertical
Ignacio Castro| Cloud Computing
22
Types of data partitioning
▪ Horizontal partitioning: different rows into different tables ▪ Vertical partitioning: different columns into different tables
Ignacio Castro| Cloud Computing
https://docs.microsoft.com/en-us/azure/architecture/best-practices/data-partitioning
23
Horizontal partitioning Vertical partitioning
Horizontal partitioning
▪ Horizontally scaling data storage
▪ Known as sharding in the database world
▪ Data partitions are served from different machines ▪ Improves scalability → queries can be parallelised ▪ Clients need to know how to locate the data
Ignacio Castro| Cloud Computing
24
Finding the data: request routing
▪ Clients need to know where the data is located ▪ Multiple approaches
Ignacio Castro| Cloud Computing
[Klepperman, Designing Data Intensive Applications, pg 215]
25
Common partitioning strategies
▪ Range partitioning: split the space of keys into ranges, and allocate ranges to partitions
https://docs.oracle.com/cd/B10500_01/server.920/a96524/c12parti.htm
Ignacio Castro| Cloud Computing
26
Common partitioning strategies
▪ Range partitioning: split the space of keys into ranges, and allocate ranges to partitions
Ben Dami Zico Ignacio Felix Joseph
A-H
I-P
Q-Z
Ignacio Castro| Cloud Computing
https://docs.oracle.com/cd/B10500_01/server.920/a96524/c12parti.htm
27
Common partitioning strategies
▪ Range partitioning: split the space of keys into ranges, and allocate ranges to partitions
▪ Hash partitioning: hash each key (essentially obtaining a random number), and allocate these numbers to partitions (using the modulo operation)
Ignacio Castro| Cloud Computing
https://docs.oracle.com/cd/B10500_01/server.920/a96524/c12parti.htm
28
Common partitioning strategies
▪ Hash partitioning: hash each key (essentially obtaining a random number), and allocate these numbers to partitions using the modulo operation
Mod 3 0
0
1
2 2 1
Hash(x) Ben 18
Dami 06 Zico 22 Ignacio 20 Felix 95 Joseph 19
1
2
3
Ignacio Castro| Cloud Computing
https://docs.oracle.com/cd/B10500_01/server.920/a96524/c12parti.htm
29
Common partitioning strategies
▪ Hash partitioning: hash each key (essentially obtaining a random number), and allocate these numbers to partitions using the modulo operation
Hash(x) Mod 3
1
2
3
Ben 18 0 Dami 06 0
Zico 22 1
Ignacio 20 2 Felix 95 2
Joseph 19 1
Ignacio Castro| Cloud Computing
https://docs.oracle.com/cd/B10500_01/server.920/a96524/c12parti.htm
30
Partition challenges
▪ Scalability:
▪ dealing with data growth
▪ Partition rebalancing: ▪ mapping data to nodes
▪ Querying across partitions: ▪ finding the right data
Ignacio Castro| Cloud Computing
31
Scalability challenges: skew
▪ Data skew: some partitions might be holding more data than others
▪ Some partition schemes don’t guarantee equal number of elements ▪ Some keys might hold more values than others
▪ Load skew: Partitions might not receive the same amount of requests
Ignacio Castro| Cloud Computing
32
Popularity Skew
Ignacio Castro| Cloud Computing
H. Kwak et al, Characteristics of User-Generated Video Content, 2014
33
Scalability challenges: rebalancing partitions
▪ Changing the number of nodes might require remapping between nodes and partitions
▪ Worst case scenario: hash mod N
▪ Adding a new node to a hash partitioned element would change the
location of every item
▪ Good strategy for most schemes:
▪ Fixed number of virtual partitions
▪ Nodes have tokens, these tokens can be handed over gracefully as elements are added to the system
Ignacio Castro| Cloud Computing
34
Challenges in Rebalancing Partitions
Adding a new node to a hash partitioned element would change the location of every item!
Hash(x) Mod 3 Mod 4
1
2
3
4
2 2 2
0
31
3
Ben 18 0 Dami 06 0
Zico 22 1
Ignacio 20 2 Felix 95 2
Joseph 19 1
https://docs.oracle.com/cd/B10500_01/server.920/a96524/c12parti.htm
Ignacio Castro| Cloud Computing
35
Common partitioning strategies
▪ Hash + range partitioning Hash(x)
Range
0-10
11-20
21-30
76-100
Ben 18
Dami 06
Zico 22
Ignacio 20
Felix 95
Joseph 19
Ignacio Castro| Cloud Computing
36
Solution: Consistent Hashing
▪Special type of partitioning strategy that reduces the impact of nodes entering and leaving the system
▪Each database object is mapped to a point on a circumference (‘hash ring’) by hashing its key value (as in hash partitioning)
▪Each available machine (node) is mapped to a point on the edge of the same circle
▪To find the node to store an object:
▪ Hashes the object’s key to a point on the edge of the circle,
▪ Walks clockwise around the circle until it encounters the first node
Ignacio Castro| Cloud Computing
37
Consistent Hashing
o1
A
Objects o1 and o4 are o2 stored on the node A
B
Object o2 is stored on the node B
Object o3 is stored on the node C
o4
o3 C
Ignacio Castro| Cloud Computing
38
Consistent Hashing: node changes
▪ A node leaves the network: the node in the clockwise direction stores all new objects that would belong to the failed node
▪ The data objects of the failed node have to be redistributed to remaining nodes
▪ Nodes added to the network:
▪ Mapped to a point in the hash ring
▪ All objects that map between the point of the new node and the first counter clock wise neighbour, map to the new node
Ignacio Castro| Cloud Computing
39
Consistent Hashing: node changes
o1
A
o2 B
o4
o3 C
Ignacio Castro| Cloud Computing
40
Consistent Hashing: node changes
o1
D
o4
o2 B
A
The node C has left and the node D has entered the network
o3 C
Ignacio Castro| Cloud Computing
41
Consistent Hashing: node changes
o1
D
o4
A
The node C has left and the node D has entered the network
Object o1 is stored on the node A
Object o2 is stored on the node B
o3
o2 B
Ignacio Castro| Cloud Computing
42
Objects o3 and o4 are stored on the node D
Query challenges: Range queries across partitions
PPaartritiotino1n-1
Partition-2
62
Query Server-1
Query Server-2
Select count (*) from Emp where age > 50 AND
sal > 90,000’;
. . .
Emp Table
440
. . .
Query Coordinator
Ans=62+440+…+1,123=99,000
Ignacio Castro| Cloud Computing
44
Partition-k
1,123
Server-k
Query
Secondary indexes help find matching rows
Ignacio Castro| Cloud Computing
45
You MUST now know
Don’t say I didn’t
▪ ACID vs BASE
▪ Partitioning: say!
Ignacio Castro| Cloud Computing
46
▪ Types:
▪ Horizontal
▪ Vertical ▪ Strategies ▪ Range
▪ Hash
▪ Hash+range
▪ Consistent-hashing
Contents
▪ Data at Cloud Scale
▪ Dealing with partitioning
▪ Dealing with replication
▪ Cloud Data Management Systems
Ignacio Castro| Cloud Computing
47
Data replication
▪Horizontally scaling data storage
▪Multiple nodes are responsible to store the same
data
▪All replicas must be synchronised
▪Multiple variant techniques that use replication: ▪ Memory caches
▪ Leader-based replication ▪ Clustering
Ignacio Castro| Cloud Computing
48
Memory Caches
▪ Transient, partitioned and replicated in-memory databases
▪ Replicate most frequently requested data
▪ Benefits:
▪ Fast response to clients
▪ Off-loading database servers
Ignacio Castro| Cloud Computing
49
Memcached
▪ High performance distributed in-memory caching service that manages key-value pairs
▪ Very similar to a Hashtable, dictionary ▪ Key-value API: get and set methods
▪ Goal: attend majority of requests for read-heavy workloads ▪ Popular: used in Facebook, LinkedIn, Flickr…
Ignacio Castro| Cloud Computing
50
Memcached use with standard DB
Web App
Memcache d Client
get(key)
get_from_db(key)
DB
Memcached Node
Ignacio Castro| Cloud Computing
51
foo = memcached.get(fooId) if foo is None:
foo = get_from_db(fooId)
memcached.set(fooId, foo)
Scaling Horizontally Memcached
Example: hash(key) = 2
get(key)
get_from_db(key)
Memcached
DB
Ignacio Castro| Cloud Computing
52
Web App
Memcached Node #1
Memcache d Client
. . .
Node #2
▪ Multiple Memcached nodes, oblivious that they are part of a cluster
▪ Client hashes keys, partitioning them between Memcached nodes
Memcached Node #N
Leader based replication
▪One server is dedicated to writes (leader)
▪A number of replica servers are dedicated to satisfy
reads (followers)
▪The leader propagates data updates to followers
▪ If the leader crashes before completing replication to at least one follower, the write operation is lost
▪ Otherwise the most up to date follower undertakes the role of the leader
Ignacio Castro| Cloud Computing
53
Clustering
▪ Cluster: Group of redundant computers that provide a continued service and can sustain high user workloads
▪High-Availability (HA) clusters provide continued service in the event of failures to any element of the infrastructure.
▪ Redundancy eliminates Single Points Of Failures
▪ When a HA cluster detects a hardware/software fault, it immediately restarts the application on another system without requiring administrative intervention, a process known as failover
Ignacio Castro| Cloud Computing
54
Synchronous vs Asynchronous replication
▪ Synchronous: the Leader waits for confirmation that the write was received, then report success to the user and makes the write visible
▪ Asynchronous: the leader sends the message but does not wait for the follower’s response
[Klepperman, Designing Data Intensive Applications, pg 154]
Ignacio Castro| Cloud Computing
55
The problem with synchronous updates
▪Safe, but negatively impact latency
▪Some update strategies help (e.g. chain replication)
▪High availability of a service is often characterized by small latency
▪ Amazon: 0.1 secs more response time will cost them 1% in sales
▪ Akamai: 0.1 secs more response time causes 7% drop in traffic,
▪ Google: 0.5 secs in latency caused traffic to drop by 20%
▪ Asynchronous updates improve latency, at the cost of potential
side effects
Ignacio Castro| Cloud Computing
56
Risk 1: Non-monotonic reads
▪ User can see things “moving backward in time”
▪ Can happen if a user makes several reads from different replicas
Follower 1 has little lag and reflects changes
Follower 2 has larger lag and it is not up to date
User makes the same query twice
Ignacio Castro| Cloud Computing
[Klepperman, Designing Data Intensive Applications]
57
Risk 2: Violation of causality
▪ If some partitions are replicated slower than others, an observer may see the answer before they see the question
Information does not propagate homogeneously across partitions!
Observer sees the answer before the question
Ignacio Castro| Cloud Computing
58
Goal: linearisability
Intuition: the system should appear as if there was only one copy of the data
▪ Usual expectation from developers
▪ Equivalent to atomic consistency in ACID databases
▪As soon as a write operation is complete, all reads will view the updated value
▪If one client reads one updated value, all future reads will also see that updated value (or any further update)
▪Requires constraints in replica update rules Ignacio Castro| Cloud Computing
59
Impact of network failures (partitions)
▪ A network interruption forces a choice between linearizability and availability
Ignacio Castro| Cloud Computing
60
Contents
▪ Data at Cloud Scale
▪ Dealing with partitioning
▪ Dealing with replication
▪ Cloud Data Management Systems
Ignacio Castro| Cloud Computing
62
Brewer’s CAP Theorem
▪Brewer’s Conjecture (2000)
▪Symposium on Principles of Distributed Computing ▪Formally proven in 2002 (Gilbert and Lynch, MIT)
▪A distributed system cannot guarantee at the same time all three of:
▪Consistency (Linearisability)
▪ Availability
▪Network Partitioning tolerance
Ignacio Castro| Cloud Computing
63
Brewer’s CAP Theorem
NA
João Ricardo Lourenço et al. “Choosing the right NoSQL database for the job: a quality attribute evaluation.” Journal of Big Data 2.1 (2015): 18. Ignacio Castro| Cloud Computing
64
CAP Theorem properties
▪ Network Partition tolerance – the service operates normally in the presence of network partitions
A network partition occurs if two or more “islands” of network nodes cannot connect to each other, messages are highly delayed or lost.
▪ Strong Consistency – Linearisability. Reads either obtain the latest updated value, or an error
▪ Availability – The system is available to server requests
Ignacio Castro| Cloud Computing
65
Consistent systems
If application requires consistency (linearizability) and some replicas are disconnected (e.g. network problem)
some replicas cannot process requests while disconnected ➔ unavailability
▪ wait until the network problem is fixed, or ▪ return an error
Ignacio Castro| Cloud Computing
66
Eventually Consistent systems
▪ Asynchronous updates:
“replicas update in the background” ▪ The system converges eventually
▪ Not a single model:
▪ active research area,
▪ many consistency models: between linearizability and pure asynchronous updates
Ignacio Castro| Cloud Computing
67
Diversity of database features
Ignacio Castro| Cloud Computing
72
NA
▪ No choice: network partitions will happen (whether you like it or not)
▪ Thus, a better way of phrasing CAP would be: either Consistent or Available when Partitioned
Ignacio Castro| Cloud Computing
73
Critique of CAP
▪ No choice: network partitions will happen (whether you like it or not)
▪ A better way of phrasing CAP would be: either Consistent or Available when Partitioned
Ignacio Castro| Cloud Computing
74
Cassandra
▪A free and open-source, distributed, wide column store, NoSQL database management system designed to handle large amounts of data across many commodity servers
▪Initially developed at Facebook to power the Facebook inbox search feature
▪Facebook released Cassandra as an open-source project on Google code in July 2008.
Ignacio Castro| Cloud Computing
77
Apache Cassandra
▪ Open Source Distributed Database
▪ Based on two influential NoSQL systems: ▪ Amazon Dynamo and Google BigTable
▪ Released in 2008, used by Facebook, eBay, etc.
▪ Great example of partition AND replication features
Ignacio Castro| Cloud Computing
78
Cassandra features
1. Elastic: read and write throughput increases linearly as new machines are added
▪ High performance for write operations
2. Supports content replication, per node and
3. Decentralised:faulttolerantwithnosinglepointof failure; no “master” node
4. Data model: Column based, multi dimensional hashtable, no join capabilities
5. Tunable consistency, per operation
Ignacio Castro| Cloud Computing
datacenter
79
Cassandra partitioning
▪ Consistent hashing: multiple Cassandra nodes form a ring
▪ Rings can span multiple datacentres (Cassandra is aware of topology)
▪ Virtual nodes (vnodes): every physical node is split into many virtual nodes (256 default) for easier partition rebalancing
Ignacio Castro| Cloud Computing
[Hewitt and Carpenter, Cassandra the Definitive Guide, 2nd Ed]
80
Cassandra Data Replication
▪ Keys have associated a replication factor (number of replicas over the network)
▪ The nodes in charge of storing replicas are the ones immediately to the right (i.e., clockwise) of the node that has to store the key copy based on the consistent hash function
Ignacio Castro| Cloud Computing
81
Cassandra: Access to Data Replicas
#1
#6 #2
HASH VALUE
ReplicationFactor = 3
Coordinator
Client
#5
#3
Ignacio Castro| Cloud Computing
82
#4
Remember: update propagation across replicas
reply reply reply
Which option is best?
Ignacio Castro| Cloud Computing
85
Tunable Consistency: Write / Read Operations
▪How many replicas need to reply for the operation to become a success?
tem
Level
Description
All replicas
https://docs.datastax.com/en/archived/cassandra/2.0/cassandra/dml/dml_config_consistency_c.html
Consistent system:
no response if one replica is
not accessible!
Ignacio Castro| Cloud Computing
86
ANY
QUORUM
LOCAL_QUORUM
EACH_QUORUM
ALL
One node
Eventually consistent sys
N/2 + 1 replicas
N/2 + 1 replicas in local data centre
N/2 + 1 replicas in each data centre
Tunable consistency : Write / Read Operations
▪Level of consistency depends on: ▪ N = replication factor
▪ W = number of write nodes ▪ R = number of read nodes
▪Consistency is an spectrum!
▪“Golden rule” (i.e., rule of thumb) ▪ R + W <= N : eventual consistency
▪ R + W > N “Strong consistency
Ignacio Castro| Cloud Computing
87
Still not a strong as linearizability!
Data model of Cassandra
▪ Based on Bigtable (Google): ▪ 1 single table
▪ Chang, Fay, et al. “Bigtable: A distributed storage system for structured data.” ACM Transactions on Computer Systems (TOCS) 26.2 (2008): 1-26.
▪ Similarities with SQL databases (tables, columns…) ▪ Less powerful
▪ Similar query language
Ignacio Castro| Cloud Computing
88
eBay Cassandra Deployment
Ignacio Castro| Cloud Computing https://www.slideshare.net/jaykumarpatel/cassandra-at-ebay-13920376
89
eBay Cassandra Deployment
High availability / minimise latency
2 copies in each DC
Ignacio Castro| Cloud Computing
90
Only 1 node needs to reply
Recommended bibliography
▪M. Kleppmann, Designing Data-Intensive Applications. ▪ Part II: Distributed Data
▪ Chapters 5, 6, 9
▪ De Candia et al, “Dynamo: Amazon’s highly available
key-value store”, SOSP 2007
▪W. Vogels, “Eventually Consistent”, CACM 2009
Ignacio Castro| Cloud Computing
92
Ignacio Castro| Cloud Computing
94