Slide 1The Akamai PlatformMotivationAkamai Configuration Management System (ACMS)ProblemAssumptionsRequirementsApproachArchitectureQuorum-based ReplicationAcceptance AlgorithmAcceptance Algorithm ContinuedAcceptance Algorithm ContinuedAcceptance Algorithm ContinuedAcceptance Algorithm ContinuedRecoveryThe Index TreeData DeliveryEvaluationPropagation Time DistributionPropagation times for various size filesDiscussionSlide 23Scalable Distributed Storage Sys.Amazon Dynamo – Consistent HashingVirtual Node for Load BalancingReplication for High AvailabilityQuorum for ConsistencyVector Clock for Eventual ConsistencyLatency of 99.9 PercentileLoad BalancingGoogle’s BigtableTabletSystem OrganizationFinding a TabletEditing a TableTableScalabilityDiscussion PointsACMS: The Akamai Configuration Management SystemA. Sherman, P. H. Lisiecki, A. Berkheimer, and J. WeinPresented byParya MoinzadehThe Akamai Platform•Over 15,000 servers•Deployed in 1200+ different ISP networks•In 60+ countriesMotivation•Customers need to maintain close control over the manner in which their web content is served•Customers need to configure different options that determine how their content is served by the CDN•Need for frequent updates or “reconfigurations”Akamai Configuration Management System (ACMS)•Supports configuration propagation management▫Accepts and disseminates distributed submissions of configuration information•Availability•Reliability•Asynchrony•Consistency•Persistent storageProblem•The widely dispersed set of end clients•At any point in time some servers may be down or have connectivity problems•Configuration changes are generated from widely dispersed places•Strong consistency requirementsAssumptions•The configuration les will vary in size from a few hundred bytes up to 100MB•Most updates must be distributed to every Akamai node•There is no particular arrival pattern of submissions•The Akamai CDN will continue to grow•Submissions could originate from a number of distinct applications running at distinct locations on the Akamai CDN•Each submission of a configuration file foo completely overwrites the earlier submitted version of foo•For each configuration file there is either a single writer or multiple idempotent (non-competing) writersRequirements•High Fault-Tolerance and Availability•Efficiency and Scalability•Persistent Fault-Tolerant Storage•Correctness•Acceptance Guarantee•SecurityApproachSmall set of storage pointsThe entire Akamai CDNArchitectureEdge ServersStorage PointsSPSPSPSPSPSPSPSPSPSPPublishersAccepting SPQuorum-based Replication•A quorum is defined as a majority of the ACMS SPs•Any update submission should be replicated and agreed upon by the quorum•A majority of operational and connected SPs should be maintained•Every future majority overlaps with the earlier majority that agreed on a fileAcceptance AlgorithmAcceptance Algorithmthe Accepting SP copies the update to at least a quorum of the SPsVector exchange protocolAcceptance Algorithm ContinuedSPSPSPSPSPSPSPSPSPSPUID for a configuration file foo:“foo.A.1234”A publisher contacts an accepting SPThe Accepting SP first creates a temporary file with a unique filename (UID)The accepting SP sends this file to a number of SPsIf replication succeeds the accepting SP initiates an agreement algorithm called Vector ExchangeUpon success the accepting SP “accepts” and all SPs upload the new fileAgreement algorithm ???Acceptance Algorithm Continued•The VE vector is just a bit vector with a bit corresponding to each Storage Point•A 1-bit indicates that the corresponding Storage Point knows of a given update•When a majority of bits are set to 1, we say that an agreement occurs and it is safe for any SP to upload this latest updateAcceptance Algorithm ContinuedAcceptance Algorithm ContinuedSPSPSPSPSPSPSPSPSPSP“A” initiates and broadcasts a vector: A:1 B:0 C:0 D:0 E:0“C” sets its own bit and re-broadcasts:A:1 B:0 C:1 D:0 E:0“D” sets its bit and rebroadcastsA:1 B:0 C:1 D:1 E:0Any SP learns of the “agreement” when it sees a majority of bits set. ABCDERecovery•The recovery protocol is called Index Merging•SPs continuously run the background recovery protocol with one another•The downloadable configuration files are represented on the SPs in the form of an index tree•The SPs “merge” their index trees to pick up any missed updates from one another•The Download Points also need to sync up stateThe Index Tree•Snapshot is a hierarchical index structure that describes latest versions of all accepted files•Each SP updates its own snapshot when it learns of a quorum agreement•For full recovery each SP needs only to merge in a snapshot from majority-1 other SPs•Snapshots are also used by the edge servers to detect changesData Delivery•Processes on edge servers subscribe to specific configurations via their local Receiver process•A Receiver checks for updates to the subscription tree by making HTTP IMS requests recursively•If the updates match any subscriptions the Receivers download the filesEvaluation•Workload of the ACMS front-end over a 48 hour period in the middle of a work week•14,276 total file submissions on the system •Five operating Storage PointsSize range Avg file sz Distribution Avg time(s)0K-1K 290 40% 0.611K-10K 3K 26% 0.6310K-100K 22K 23% 0.72100K-1M 167K 7% 2.231M-10M 1.8M 1% 13.6310M-100M 51M 3% 199.87The period from the time an Accepting SP is first contacted by a publishing application, until it replies with “Accept”Propagation Time Distribution•A random sampling of 250 Akamai nodes•The average propagation time is approximately 55 secondsPropagation times for various size files•Mean and 95th-percentile delivery time for each submission•99.95% of updates arrived within three minutes•The remaining 0.05% were delayed due to temporary network connectivity issuesThe average time for each file to propagate to 95% of its recipientsThe average propagation timeDiscussion•Push-based vs. pull-based update•The effect of increasing the number of SP on the efficiency•The effect of having less number on nodes in the quorum•The effect of having a variable sized quorum•Consistency vs. availability trade-offs in quorum selection•How is a unique and synchronized ordering of all update versions of a given configuration file maintained? Can it be optimized?•Is VE expensive? Can
View Full Document
Unlocking...