1、1,The Kangaroo approach to Data movement on the Grid,Rajesh Rajamani (rajcs.wisc.edu) June 03, 2002,2,Condor and the Grid,What is the Grid?,Grid applications tend to have demanding I/O needs. Process/produce large amounts of data Need for an efficient mechanism to transfer data,3,Motivation,Suppose
2、you want to transfer 10 large (10s of GB) and 100 small files (in KB) from UW to Vietnam - Would you use FTP, if you know that - Network connection to Vietnam is minimal at the best of times ? Would you be satisfied with the reliability and performance of FTP?,4,Motivation,Shortcomings of FTP - 1. P
3、erformance suffers in case of transient errors,D,R,R,R,App,slow link,R,D,Router,Destination,Data,Fast, but unreliable link,5,Motivation,TCP checksum can fail to detect errors for large xfers TCP uses 16-bit checksum, which is ones complement of the ones complement sum of the TCP segment (RFC1071)011
4、0011001100110 0101010101010101 0000111100001111 - 1100101011001010 0011010100110101,6,TCP checksum,All burst errors of 16 or fewer bytes will be detected except when 0x0000 is replaced by 0xFFFF and vice versa Other errors are detected only probabilistically 1110011001100110 0101010101010101 Origina
5、l checksum = 1000111100001111 0011010100110101 - 1100101011001011 (ones complement sum) 0011010100110100 (checksum),7,Checksum errors,0110011001100110 0011010101010101 Original checksum = 0010111100001111 0011010100110101 - 1100101011001010(ones complement sum) 0011010100110101 (checksum) Error goes
6、 undetected!,8,Motivation (contd.),3. Doesnt support persistent queues4. Opens a connection for every transfer (which in most cases is a single file),9,Motivation (contd.),No support to efficiently broadcast/multicast files,10,The Vision,K,K,K,K,K,K,K,Data Movement System,App,K,=Kangaroo server,11,O
7、utline,Motivation Architecture Replication Conclusions,12,Architecture,Message based architecture Layers Application Adaptation Consistency Transport,13,Architecture,Kangaroo Transport,Consistency,Adaptation,get, put, push, commit,Application,Kangaroo Transport,Kangaroo Transport,Consistency,ack,ack
8、,open, read, write, close, fsync,open, read, write, close, fsync,TCP/IP,TCP/IP,TCP/IP,get, put, commit, route,get, put, push,commit,14,Adaptation layer,Consistency,Adaptation,get, put, push, commit,Application,open, read, write, close, fsync,15,Interposition agents,Std Library,Kernel,Application,Std
9、 Library,Kernel,Agent,Application,16,Bypass and PFS,Bypass - General-purpose tool for trapping and redirecting standard library procedures. PFS Pluggable File System PFS traps all I/O operations. It converts file-related operations to Kangaroo operations. Can be applied at run-time to any dynamicall
10、y-linked program: setenv LD_PRELOAD ./pfs_agent.so vi /kangaroo/antipholus.cs.wisc.edu/u/r/a/raj/.cshrc gcc /http/www.cs.wisc.edu/raj/example.c -o /kangaroo/antipholus.cs.wisc.edu/u/r/a/raj/temp/example,17,Bypass Mechanism,A static call is bound to a function definition when the library is linked. D
11、ynamic calls are bound at run time by the loader. The preload/bypass mechanism is a hook only into the dynamic loader,18,Multiple Bypass,Interposition agent,Standard Library,Application,open _open _open read write,Entrypoints,Switch,printf scanf open _open _open read write,Global DS,layer,opendir re
12、addir socket accept connect,19,printf() calls write(),Interposition agent,Standard Library,Application,write open _open _open read,Entrypoints,Switch,printf scanf open _open _open read write,Global DS,layer,opendir readdir socket accept connect,20,Architecture,Kangaroo Transport,Consistency,Adaptati
13、on,get, put, push, commit,Application,Kangaroo Transport,Kangaroo Transport,Consistency,ack,ack,open, read, write, close, fsync,open, read, write, close, fsync,TCP/IP,TCP/IP,TCP/IP,get, put, commit, route,get, put, push,commit,21,Consistency layer,Kangaroo Transport,Consistency,Kangaroo Transport,Co
14、nsistency,ack,ack,open, read, write, close, fsync,get, put, commit, route,get, put, push,commit,Adaptation,get, put, push, commit,22,Kangaroo message format,Source IP,Destination IP,File name,Operation put, get, push,Data/Offset,23,Consistency layer,Interface Get block, put block, commit blocks, pus
15、h blocksSemantics Ordering - Order preserving Reliability - Detects success Duplication - Delivers at most once,24,Ordering and Duplication,For most applications, order of writes doesnt matter. E.g. - writes to different offsets Only renames and writes that overlap are non-idempotent. Majority of th
16、e operations are idempotent Consistency layer deals with non-idempotent operations by using kangaroo_push,25,Architecture,Kangaroo Transport,Consistency,Adaptation,get, put, push, commit,Application,Kangaroo Transport,Kangaroo Transport,Consistency,ack,ack,open, read, write, close, fsync,open, read,
17、 write, close, fsync,TCP/IP,TCP/IP,TCP/IP,get, put, commit, route,get, put, push,commit,26,Transport layer,Kangaroo Transport,Consistency,Kangaroo Transport,Kangaroo Transport,ack,ack,TCP/IP,TCP/IP,TCP/IP,get, put, commit, route,get, put, push,commit,Consistency,27,Transport layer,Interface Send mes
18、sage, query route, query status Semantics Ordering - None (or worse!) Reliability - Likely, but not guaranteed. Duplication - Unlikely, but possible. Performance Uses all available resources (net, memory, disk) to maximize throughput Replication necessary to provide reliability Must cache blocks unt
19、il delivery is acknowledged Replication may introduce inconsistencies,28,Cedar Bandwidth regulator,Standard socket abstraction. Enforces limits on how much bandwidth can be consumed across multiple times scales. Also measures congestion and reports to locally-determined manager. Example: If conditio
20、ns are good, do not exceed 10Mb/s. If there is competition for the link, fall back to no more than 1Mb/s.,29,Replication,Endpoints keep copies of data blocks until they are acknowledged. Receiver sends cumulative acks and commits unbroken sequences. Replication can be costly Choices - Replicate send
21、er Pass the buck - Change end-point,30,Pass the Buck,Delete the local copy after a one-hop ack. Requires atomic accept and sync. (Similar to email),S,K,K,K,K,D,S,D,sender,Data,ACK,31,Conclusions,Large scale file transfer is not a solved problem. Many interesting research issues Kangaroo provides an
22、efficient mechanism to transfer large datasets over the WAN. It does so by using all available resources (net, memory, disk) to maximize throughput Kangaroo is a data movement system, an overlay network, a distributed buffer system,32,Kangaroo,Uses three basic techniques to address some issues Uses
23、a virtual circuit to transfer data Buffering on intermediate nodes improves performance Retries till it succeeds (when it encounters an error).,33,As side effects,Kangaroo Allows applications to hide latency by overlapping I/O and CPU Maximizes use of resources However, No support for inter-process
24、consistency Does NOT provide low-latency single file transfers Does not use checksums, but will do so in the near future No support for multicasting to multiple clients AS YET,34,Future - Multiroute and Multicast,K,K,K,K,K,K,K,App,35,References,D. Thain, J. Basney, S.-C. Son, and M. Livny, “The Kang
25、aroo Approach to Data Movement on the Grid“, Tenth IEEE Symposium on High Performance Distributed Computing (HPDC10), San Francisco, California, August 7-9, 2001 J.Stone and Craig Partridge, “When The CRC and TCP Checksum Disagree, SIGCOMM 2000Gemmell, Jim, Schooler, Eve, and Gray, Jim, Fcast Multicast File Distribution, IEEE Network, Vol. 14, No. 1, Jan 2001,
