Agenda Scalability Availability CAP Theorem Scalability Availability Consistency BASE Transaction

Transcription

1 Cloud --- Scalability Availability ---

2 Agenda Scalability Availability CAP Theorem Scalability Availability Consistency BASE Transaction

3 Scale-out Scale-out Availability

4 Scalabilty Availability Scalability Availability

5 Availability Replica Replica Eventually Consistency TransactionACID BASE

6 Scale-up Scale-out

7 $10,0 00 machi ne $10,0 00 machi ne $1000 machi ne $1000 machi ne Scale-up Scale-out $500 machi ne $500 machi ne # Machines Scale Up $500 machi ne $500 machi ne $500 machi ne $500 machi ne $500 machi ne $500 machi ne $500 machi ne $500 machi ne Scale Out

8 Scale-up

9 Scale-out

10 Google PC? 33PC

11 Scalability Scale-out Scalability

12 Application GFS Client Google File System (file name,chunk index) (chunk handle, chunk location) GFS Master File NameSpace /foo/bar Chunk 2ef0 Instruction to chunkserver (chunk handle,byte range) chunk data Chunkserver state GFS chunkserver GFS chunkserver Linux File System Linux File System Scalable

13 Master Google MapReduce Worker Partition0 Partition1 Split 0 Split 1 Split 2 Split 3 Scalable Worker Partition0 Partition1 Scalable Worker Worker Output file0 Output file1 Split 4 Worker Partition0 Partition1 Input File and its Split Map Phase Intermediate File on Local Disk Reduce Phase Final Output

14 Bigtable Client Google BigTable Bigtable Client Library Open Bigtable Bigtable Tablet Server Bigtable Master Scalable Bigtable Tablet Server Bigtable Tablet Server Cluster Sheduling System Google File System Chubby Lock Service

15 Amazon Dynamo Consistent Hashing Scalable B,C,D K A,B]

16 Microsoft Azure SDS f(g) = 4601 G Service Instance 1 Service Instance Service Instance Service Instance 5501 Service Instance 5000 G Service Instance Partition Data Overlay Service Request Logical Partitions A, B C, D E, F G, H I, J K, L 28 Service Instances Scalable

17 Microsoft Azure SDS Front-end Node REST/SOAP ACE Logic Data Access Library Front-end Node REST/SOAP ACE Logic Data Access Library Front-end Node REST/SOAP ACE Logic Data Access Library SDS frontend Master Cluster Provisionin g Service Management Deployme nt Health Monitori ng Master Node Partition Manager Data Node Components Master Node Partition Manager Data Node Components Scalable Data Cluster Data Node Data Node Data Node Data Node Data Node SQL Server Fabric Mgmt. Servic es SQL Server Fabric Mgmt. Servic es SQL Server Fabric Mgmt. Servic es SQL Server Fabric Mgmt. Servic es SQL Server Fabric Mgmt. Servic es Fabri c Replicatio n Fetch Partition Map SQL Client

18 Scalability

19 Scalable Scalable On Premise

20 Scalability Scalability Virtualization Scalability Scalability Virtualization

21 Scalability Scalability Scalablity Scalability Scalable Scalability

22 Availability

23 Scale-out 3-year MTBF, 1000 Google 2000

24

25 Google? Ben Jai, Google Platforms Architect Google

26 Cloud Cloud = Scalability + Availability

27 Availability Fail-Over

28 Google File System Availability Google File System Availability Chunk Server

29 4 Client Master 7 Secondary Replica A Primary Replica 3 5 Secondary Replica B 6

30 Windows Azure Availability Windows Azure File System Data Storage Replica Fail-over

31 MS Azure Primary Secondary (quorum) Ack S Ack Ack Read Value Write P Write Write Ack S Ack S Write Write S

32 MS Azure Primary Secondary replica Secondary P B S SP S! S

33 Glassfish Fail-Over Consistency

34 Cluster Cache 4cluster

35 Cache Cachereplica

36 Cache

37 Cache

38 Cache

39 Cluster

40 Cluster

41 Cluster

42 CAP Theorem

43 CAP C,A,P Consistency Partition Availability

44 CAP C A Consistency + Availability P

45 CAP C A Consistency + Partition database / P

46 CAP C A Availability + Partition / DNS P

47 Cloud Cloud C P A C P A? C C P P A A C P A?

48 Availability Consistency e-

49 e- Availability

50 Availability Consistency

51 Read-OnlyPrimary-Key

52 ? Google

53 e- AvailabilityConsistency

54 Scalability Availability Consistency CAPScalability Availability Consistency Cloud

55 CAP Cloud C A P C P A C P A C P A

56 Consistency Scalable Available Consistency Availability Consistent

57 Azure Ack Value Read Write Ack Ack P Ack Ack S Write Write S S Write Write S

58 Azure Consistency

59 Azure Consistent? Primary

60 Eventually Consistency

61 Eventually Consistency Consistent Consistent Eventually Consistency DNS Eventually Consistent

62 Consistency Consistency Eventually ConsistencyCAP Scalable Available Eventually Consistent

63 BASE Consistency ACID Atomic,Consistent,Isolation, Durable

64 OS OS OS OS? OS

65 BASE Basically Available Soft-State Eventually Consistent ACID BASE BASEACID

66 Soft-State Partial Failure

67 ACID Transaction ID Begin Transaction insert ( update set =+100 where update set +100 where = End Transaction

68 ID

69 ID

70 ACID ACID ID Transaction Manager

71 ACID Consistent ACID ID

72 Soft-State Eventually Consistent ACID ACID Soft-State Eventually Consistent

73 Soft-State Eventually Consistent ACID Transaction Manager ID ACID

74 Soft-State Eventually Consistent ACID ACID Transaction Manager BASE Transaction ID

75 Soft- State Eventually Consistent Consistency Soft-State Eventually Consistency Eventually Consistency Consistency Consistency

76 Basically Availability Cloud Basically Availability Optimistic Concurrent Controll

77 Thread A Thread B Share dcoun t Count++ Count++ GetCount() Count++ GetCount() 12 Count++ GetCount() GetCount() ? 13?

78 Thread A Thread B Share dcoun t [Begin Tx] GetCount() GetCount() Count Count++ [Commit Tx] 14 Availability

79 Basically Available Thread A Thread B Share dcoun t Worker Queue GetCount() 12 GetCount() 12 Q.PutMsg( add ) Q.PutMsg( add ) 12 Q.GetMsg() GetCount() GetCount() Count++ Q.GetMsg() Count++

80 Internet Windows Azure m Web Role n Worker Role Queue Windows Azure Datacenter L B Web Site Web Web (ASPX, Site Site ASMX, (ASPX, ASMX, (ASPX, WCF) ASMX, Web Role WCF) WCF) Queue Worker Service Role Tables Storage Blobs

81 Queue Queue Producers Consumers P C 1 1. Dequeue(Q, 30 sec) msg1 Queue msg1 P 1 C 2 2. Dequeue(Q, 30 sec) msg2 Queue

82 Producers Consumers P 2 P C 1 C 2 2. Dequeue(Q, 30 sec) msg2 3. C2 msg2 4. Delete(Q, msg2) 7. Dequeue(Q, 30 sec) msg1 1. Dequeue(Q, 30 sec) msg 1 5. C 1! msg1 Deueue 30Queue

83 Basically Availability Optimistic Lock

84 Entity Client A Version Rating Client B 5 : Ch9, Jan-1, 3 1 : Ch9, Jan-2, 2 9 : Ch9, Jan-3, 6 version Etag

85 Entity Client Client A B 1 : Ch9, Jan-2, Version Rating 1 : Ch9, Jan-2, 2: 2 Ch9, Jan-2, 5 2 2: Ch9, Jan-2, 4 5 : Ch9, Jan-1, 3 1 : Ch9, Jan-2, 2 9 : Ch9, Jan-3, 6

86 Version Client A 1: Ch9, Jan-2, 5 Version Rating Client B 1: Ch9, Jan-2, 4 If-Match: 1 Ch9, Jan-2, 5 5 : Ch9, Jan-1, 3 1 : Ch9, Jan-2, 2 9 : Ch9, Jan-3, 6

87 Version Client A 1: 2: Ch9, Jan-2, 5 Version Rating Client B 1: Ch9, Jan-2, 4 If-Match: 1 Ch9, Jan-2, 5 5 : Ch9, Jan-1, : Ch9, Jan-2, : Ch9, Jan-3, 6 Version Client-A

88 Version Client A Client B Error: Version Rating 1: 412 2: Ch9, Jan-2, 5 1: Ch9, Jan-2, 4 If-Match: 1 1: Ch9, Jan-2, 4 5 : Ch9, Jan-1, : Ch9, Jan-2, : Ch9, Jan-3, 6 Precondition failed (412)

89 Persistency Scalability Availability Consistency Scale-out

90 1,000 PC Scale-out 2G 500G PC PC TByte 0.5Peta Byte Scale-out Scalability

91 365 Availability volatile persistent Coherence

92 Index Indexing Key/Value Hash Indexing

93 P2P/DHT Scalability Availability P2P/DHT

94 P2P/DHT(1) P2P Overlay Scale-out Availability

95 P2P/DHT(2) P2P P2P DHT Distributed Hash Table DHT Hash Table

96

97 Scale-out Scalability Cloud Scale-out Scalability Cloud Availability Cloud Scalability Availability Consistency

98 Eventually Consistent Soft State Basically Available ACID Transaction Eventually Consistent Soft State

99 Basically Availability Optimistic Concurrent Controll P2P/DHT Scalable Available Cloud Cloud

100

101 A Note on Distributed Computing Jim Waldo et al. i_tr pdf

102 (partial failure)

103

104 Formulated in 10 Years Ago Network is Homegenous added by Gosling

105 --- Complexity Quanta and Platform Definition Summary of Jim Waldo s Keynote at the 10th Jini Community Meeting eo/complexity_quanta_and_platform_defin ition.mov esentations/waldo_keynote.pdf

106 (SEQ) (MT) MT (MP) MT (MM) (MMU) Web

107

108 Lamport: microsoft.com/users/lamport/pubs/pubs.html OS

109 Seq to MT : MT to MP : ( ) MP to MM : ( ) MM to MMU : (web ).