Flashcards
211 - cont
Cards in this deck (33)
- 1explain the map function in MapReduce?Map: processes a key/value pair to generate a set of intermediate key/value pairs (extract something important)
- takes a series of tuples
- processes each tuple
- output 0 or more tuples - 2explain the reduce function in mapreduce?merges intermediary values (aggregate, summaries, filter, transform)
- called once for each unique
- iterates through each value
- outputs 0 or more results as - 3give an example of MapReduceGoal: count all book in the library that mention 'Antarctica'
- divide the library into sections
- one 'worker' per section reads all books and records mentions
- all worker meet when done
- collate findings - 4what is GFS?Google File System
- 5what is the GFS?The Google File System is a propriety distributed file system developed by Google to provide efficient reliable access to data using large clusters of commodity hardware
- 6what is chubby?provides simple file system API for small files
supports coarse grained synchronisation in loosely coupled (asynchronous) and large scale distributed systems - 7what is chubby used for?as a small scale filing system for, e.g. meta-data
as a name server
- using chubby files to maintain name to address mappings
to achieve distributed consensus/ locking/ election
- use of lamports paxos algo - 8What are the steps of the Paxos algorithm?1) elect a coordinator
2) seek consensus
3) reaching consensus - 9explain the first step in paxos?1) electing a coordinator
to identify the right coordinator, an ordering is given to coordinators through the attachment of a sequence number. Each replica maintains the highest sequence number seen so far and, if bidding to be a coordinator, will pick a higher number(which is unique) and broadcasts this to all replicas in a propose message (bidding to be a coordinator). If other replicas have not seen a higher bidder, they reply with a promise message - indicating that they will not deal with other (older) coordinators with lower seq numbers. If a majority of promise messages are received, this replica can act as a coordinator - 10explain step 2 in the paxos algorithmseeking consensus
an elected coordinator may submit a value and then subsequently broadcast an accept message to all replicas. Other replicas either ACK this message if they accept this as the agreed value, or reject it. The coordinator waits, possibly indefinitely in the algorithm, for a majority of replicas to ACK the accept message - 11explain the last step in the paxos algorithmreaching consensus
if a majority of replicas do ack, then a consensus has effectively been achieved. The coordinator then broadcasts a commit message to notify replicas of this agreement - 12what is BigTable?a very large scale distributed table indexed by row, column and timestamp (built on top of GFS and Chubby)
supports semi-structured and structured data on top of GFS (but without full relational operations, e.g. join) - 13how does BigTable work?table split up into fixed sized tablets optimised for GFS
- 14What does GFS provide to networks and connected nodes?fault tolerance,
reliability,
scalability,
availability, - 15what is the output commit problem?committing to an output (sending client back result) when backups haven't been updates
- 16exactly once solution to the output commit problem?discard duplicate requests due to crash
- attach a running request ID to requests and log the replies
- request ID specific to client (several clients may be active)
- old replies can be replayed - 17what is a transaction?Synchronisation mechanisms to access (and modify) shared data concurrently
- between a client and a data repository (e.g. database) - 18what operations does a transaction engine need?Begin_transaction
End_transaction: end transaction + try to commit
Abort: kill transaction & forget everything about it - 19what is a distributed transaction?A transaction where operations involve multiple servers
(e.g airline + hotel) - 20issues with distributed transactions?need distributed algorithms for concurrency control and recovery schemes
must deal with added difficulty of distributed deadlock
crucial issue of atomic commit protocols - 21protocols for transaction commitment?One-phase atomic commit protocol
Two-phase commit protocol - 22what is the one-phase atomic commit protocol?The coordinator keeps requesting all participants to commit until they return an ACK
no chance of a participant to initiate an abort - 23what is the two-phase atomic commit protocol?phase 1: calls for participants vote
phase 2: complete a commit or an abort according to output of vote - 24what is P2P computing?P2P computing is the sharing of computer resources and services by direct exchange between systems (peers)
- 25how does Gnutella discover peers?1) join the network
2) determining who is on the network
- ping/pong
3) search - flood based search
- flood neighbours with search query
4) download
- peers respond with a QueryHit (contains contact info) - 26issues with Gnutella search?wastes bandwidth
- many redundant messages - 27what are the two types of free riding?downloading but not sharing any data
not sharing any interesting data - 28how does BitTorrent client find data?find torrent file on a well known webserver
- 29how do clients download data through torrent files?the torrent file has address of tracker for file
the tracker, which runs on a webserver, keeps track of all peers downloading file - 30What is a BitTorrent Swarm?The BitTorrent clients form a swarm: a self-organised network
Seeder - peer having entire file
Leecher - peer downloading file - 31how are files downloaded from BitTorrent peers?files are broken into small chunks
client first asks 50 random peers from tracker
Random First Chunk:
- when peer starts to download, request random chunks
- when first complete chunk assembled, switch to rarest-first and participate in uploading
Rarest-first:
- look at all chunks at all peers, and request chunks that owned by fewest peers - 32what is the tit-for-tat strategy?Uses in P2P systems
encourages cooperation, discourages free-riding
- a peer serves peers that serve it - 33—
Information
- Description
- Flashcards on 211 - cont, created by Lewis Stones on 01/05/2018.
- Created by
- Lewis Stones
- Views
- 1
- Rating