Massive Data StorageStorage on the "Cloud" and the Google File Systempaper by: Sanjay Ghemawat,Howard Gobioff, and Shun-Tak Leungpresentation by: Joshua MichalczakCOP 4810 - Topics in Computer ScienceDr. Marinescu, Spring 2011, UCFOutlineA history of data storageDefining "Massive" data storageDefining the properties of a good storage systemGoogle's storage - the Google File System (GFS)Cloud storage and you: present and futureA history of storage - 1970sInternal 4K ROM expandable to 12KUsed Cassette Tapes for external I/OCapacity based on read/write speedRoughly 200K of storageA history of storage - 1980sFirst introduced in 1971More expensive thancassettesEquivalent storagecapacityNot many computers yet offered diskette drivesPopularity rose in early 1980sMany competing manufacturers (cheaper)Larger capacities (> 1MB)Most machines offered diskette peripherals (Commodore 64), or used it exclusively (Apple II, Macintosh)A history of storage - 1990s to presentHard drives first introduced in 1957Reserved for "macrocomputers"Very expensive; $3,200 / monthCost and drive size limit adoptionin households1973 - IBM - first "sealed" hard drive 1980 - Seagate - first hard drive formicrocomputers; 5 MB for $4501980 - IBM - first 1GB hard drive;size of a refridgerator for $40,000Drops in size (3-1/2 inch, 1988), cost, andthe introduction of interface standards(SCSI, 1986; IDE, 1986) led to largerhousehold adoption.Defining "Massive" data storageThings to consider:File type (text documents, pictures, movies, programs, etc)Cloud capacity vs. Local capacityTransfer rate (internet speed)A typical individual is unlikely to generate a "massive" amount of storageAt $100 / 1TB, why not just buy another drive?Consider then services with large clienteleInternet index & search: Google, Bing, Yahoo, etcData storage & sharing: Flickr, YouTube, Google Docs, Facebook, DropBox, etcGoogle's storage needs:2006: Reported that crawler alone uses 800TBMost (~97%) of files < 1GBWhat makes a good storage system?Let's ask Jim Grayreceived Turing Award in 1988"for seminal contributions to database andtransaction processing research andtechnical leadership in systemimplementation"Defined "ACID" (atomicity, consistency,isolation, and durability)properties that guarantee the reliability ofdatabase transactionsalthough originally designed for databases, these terms can apply to all forms of data storage, include our "on-the-cloud" modelAtomicity"all or nothing"If any portion of a transaction fails, the entire transaction failsFailed transactions should leave the data unchanged; only complete transactions change the system's stateThe reason for failure should not matter (Hardware failure, system failure, connection loss, etc)Atomic transactions can't be subdivided Why is it important?Prevents data errors from transaction failure ("roll-back")Consistency"database integrity"The database remains "truthful" to it's intentTransactions move the database from one consistent state to anotherOnly "valid" data is written; "invalid" data is handled as per the implementation requirementsvalidity is determined by a set of data constraints Why is it important?When we access data, the data present matches our expectationsIsolation"incomplete modifications are invisible"Other operations cannot access data being modified by a transaction which has not yet completedConcurrent transactions should be unaware of each other (beyond possibly having to wait for access) Does this mean we can't have concurrency?No. It just means that if we do have concurrency, that we take extra precautions to prevent data contaminationIt may make implementing concurrency "harder" (the naive solution will likely not work)Why bother?Prevents the database from going into inconsistent states because of transaction interleavingDurability"ability to recover from failure"When a transaction reports back as complete and successful, any modifications it made should be impervious to system failureThis means that the system should never have to roll-back completed transactionspartially completed transactions at the time of failure won't affect the system (atomic)the state of the database should be valid (consistent)Why is it importantAll systems eventually failIt is best to consider failure at design time rather than as an after-thought."ACIDS" - Scalability"Capacity growth"The data capacity of the system should be expandableadding additional storage should be possible, if not easyData access / commits run at an acceptable rate, even during high system usage "acceptable" will be applicationspecificHow dare you?!I know! I'm sorry :(Why would you suggest such a thing?To comply with our "massive" requirements: large amounts of data being sent and received by many users simultaneously.GFS - System RequirementsUses commodity hardware; often failsMillions of files, typically > 100MB, some > 1GBWorkload consists mostly of reads (large, sequential reads and small, random reads)Workload may also contain large, sequential writes to append data; files seldom modified after writtenHigh concurrency required; often 100+ clients appending simultaneously; atomic with minimal synchronization overheadHigh bandwidth required before high latency; most applications will be processing data in bulk in a non-time-sensitive manner.GFS - FilesGFS - System OverviewGFS - Atomicity & ConcurrencyGFS implements a special file opperation: record appendClient sends an append command, specifying only the data to be written (no offset as is typical)The file system executes these command atomicly, which prevents fragmentation from concurrent interleavingThe file offset is returned to the client once the data is committed (for the client's future reference)GFS - Consistency & DurabilityGFS implements several Fault Tolerance measures, including:Data redundancy; minimum of 3 copies per chunckMachine redundancy; 3 master nodes which are hot-swappable should one fail Chunk checksum to detect data corruption; notifies master; new clean copy received from replicaFast recoveryMaster reboot: file hierarchy persistent; chunk location metadata rebuilt by probing networkChunkserver reboot: "thin", master controls metadata; once probed by master, available to networkChunkservers which report frequent errors (data errors, network errors, etc) are reported to humans for diagnosisMaster servers are more heavily monitored (key point of failure)GFS - Relaxing Isolation requirementsGFS improves concurrency performance by
View Full Document
Unlocking...