WIXLIB

Data sharding and replicationGenoveva Vargas SolarFrench Council of scientific research, LIG-LAFMIA, ar.com

NoSql Stores: availability andperformancenReplicationn Copy data across multiple servers(each bit of data can be found inmultiple servers)n Increase data availabilityn Faster query evaluationnShardingn Distribute different data acrossmultiple serversn Each server acts as the single sourceof a data subsetnOrthogonal techniques2

Replication: pros & consnData is more availablennFailure of a site containing Edoes not result in unavailabilityof E if replicas existnnnPerformancenParallelism: queries processedin parallel on several nodesnReduce data transfer for localdataIncreased updates costSynchronisation: each replicamust be updatedIncreased complexity ofconcurrency controlnConcurrent updates to distinctreplicas may lead toinconsistent data unlessspecial concurrency controlmechanisms are implemented3

Sharding: why is it useful?nnnnScaling applications by reducingdata sets in any single databasesSegregating dataSharing application dataSecuring sensitive data byisolating itnImprove read and write performancenSmaller amount of data in each user group implies fasterqueryingnIsolating data into smaller shards accessed data is morelikely to stay on cachenMore write bandwidth: writing can be done in parallelnSmaller data sets are easier to backup, restore ely work donenParallel work: scale out across more nodesnParallel backend: handling higher user loadsnShare nothing: very few QL%Resume%database%Master%Site%database%Decrease resilience improve availabilitynIf a box goes down others still operatenBut: Part of the data missing4

Sharding and replicationnSharding with no replication: unique copy, distributed data setsnnnnReplication of shardsnnn( ) Better concurrency levels (shards are accessed independently)(-) Cost of checking constraints, rebuilding aggregatesEnsure that queries and updates are distributed across shards( ) Query performance (availability)(-) Cost of updating, of checking constraints, complexity of concurrency controlPartial replication (most of the times)nOnly some shards are duplicated5

Contact:Genoveva Vargas-Solar, CNRS, -solar.com/teaching/6

ReferencesnEric A., Brewer "Towards robust distributed systems." PODC. 2000nRick, Cattell "Scalable SQL and NoSQL data stores." ACM SIGMOD Record 39.4 (2011): 12-27nJuan Castrejon, Genoveva Vargas-Solar, Christine Collet, and Rafael Lozano, ExSchema:Discovering and Maintaining Schemas from Polyglot Persistence Applications, In Proceedings ofthe International Conference on Software Maintenance, Demo Paper, IEEE, 2013nM. Fowler and P. Sadalage. NoSQL Distilled: A Brief Guide to the Emerging World of PolyglotPersistence. Pearson Education, Limited, con20137

8NOSQL STORES: AVAILABILITY ANDPERFORMANCE

Replication master - an'be'done'from'master'or'slaves'nHelps with read scalability but does not help withwrite scalabilitynRead resilience: should the master fail, slaves canstill handle read requestsnMaster failure eliminates the ability to handle writesuntil either the master is restored or a new master isappointednBiggest complication is kes one node the authoritative copy/replica thathandles writes while replica synchronize with the masterand may handle reedsnAll replicas have the same weightnnReplicas can all accept writesThe lose of one of them does not prevent access tothe data storennnPossible write – write conflictAttempt to update the same record at the sametime from to different placesMaster is a bottle-neck and a point of failure9

Master-slave replication managementnnMasters can be appointednManually when configuring the nodes clusternAutomatically: when configuring a nodes cluster one of them elected as master. The master can appoint a new masterwhen the master fails reducing downtimeRead resiliencennnRead and write paths have to be managed separately to handle failure in the write path and still reads can occurReads and writes are put in different database connections if the database library accepts itReplication comes inevitably with a dark side: inconsistencynDifferent clients reading different slaves will see different values if changes have not been propagated to all slavesnIn the worst case a client cannot read a write it just madeEven if master-slave is used for hot backups, if the master fails any updates on to the backup are lostn10

Replication: ata'nodes'communicate'their'writes'nnAllows writes to any node; the nodes coordinate tosynchronize their copiesThe replicas have equal weightDeals with inconsistenciesnReplicas coordinate to avoidconflictnNetwork traffic cost forcoordinating writesnUnnecessary to make all replicasagree to write, only the majoritynSurvival to the loss of the minorityof replicas nodesnPolicy to merge inconsistent writesFull performance on writing to anyreplican11

a%nnnnAbility to distribute both data andload of simple operations over manyservers, with no RAM or disk sharedamong serversA way to horizontally scale writesImprove read performanceApplication/data store supportnPuts different data on separate nodesnEach user only talks to one servicerso she gets rapid responsesnThe load should be balanced outnicely between serversEnsure thatn data that is accessed together isclumped together on the samenoden that clumps are arranged on thenodes to provide best data access

13ShardingDatabase lawsnSmall databases are fastnBig databases are slownKeep databases smallPrinciplenStart with a big monolithicdatabasenBreak into smaller databasesnAcross many clustersnUsing a key valueInstead of having one million customers informationon a single big machine .100 000 customers on smaller and different machines

Sharding criterianPartitioningnnnRelational: handled by the DBMS (homogeneous DBMS)NoSQL: based on ranging of the k-valueFederationnnRelationaln Combine tables stored in different physical databasesn Easier with denormalized dataNoSQL:n Store together data that are accessed togethern Aggregates unit of distribution14

15ShardingArchitecturennProcessEach application server (AS) isrunning DBS/clientnPick a dimension that helps sharding easily(customers, countries, addresses)nPick strategies that will last a long time asrepartition/re-sharding of data is operationallydifficultnThis is done according to two different principlesEach shard server is runningna database servernreplication agents and queryagents for supporting parallelquery functionalitynPartitioning: a partition is a structure thatdivides a space into tow partsnFederation: a set of things that togethercompose a centralized unit but each individuallymaintains some aspect of autonomyCustomers data is partitioned by ID in shards using analgorithm d to determine which shard a customer ID belongs to

Replication: aspects to nFaulttoleranceAvailabilityImportant elements to considernData to duplicatenCopies locationnDuplication model (master –slave / P2P)nConsistency model (global –copies)à Find a compromise !16

17PARTITIONINGA PARTITION IS A STRUCTURE THAT DIVIDES A SPACE INTO TOW PARTS

Background: distributed relationaldatabasesnExternal schemas (views) are often subsetsof relations (contacts in Europe andAmerica)nAccess defined on subsets of relations:80% of the queries issued in a region haveto do with contacts of that regionnRelations partitionn Better concurrency leveln Fragments accessed independentlynImplicationsn Check integrity constraintsn Rebuild relations18

19FragmentationnHorizontalnnnnGroups of tuples of the same relationBudget 300 000 or 150 000Not disjoint are more difficult to manageVerticalnGroups attributes of the same relationnSeparate budget from loc and pname ofthe relation projectnHybrid

20Fragmentation: rulesVerticalnnClusteringnGrouping elementary fragmentsnBudget and location information in tworelationsHorizontalnTuples of the same fragment must be statistically homogeneousnnKeep important conditionsnSplittingnDecomposing a relation according toaffinity relationships among attributesIf t1 and t2 are tuples of the same fragment then t1 and t2 havethe same probability of being selected by a querynCompletenEvery tuple (attribute) belongs to a fragment (withoutinformation loss)nIf tuples where budget 150 000 are more likely to beselected then it is a good candidateMinimumnIf no application distinguishes between budget 150 000and budget 150 000 then these conditions are unnecessary

21Sharding: horizontal partitioningnnnThe entities of a database are split into two ormore sets (by row)Load%balancer%In relational: same schema several physicalbases/serversnPartition contacts in Europe and America shardswhere they zip code indicates where the will be foundnEfficient if there exists some robust and implicit way toidentify in which partition to find a particular entityLast resort shardnNeeds to find a sharding function: modulo, roundrobin, hash – partition, range - ave%2%Odd%IDs%MySQL%Slave%n%

22FEDERATIONA FEDERATION IS A SET OF THINGS THAT TOGETHER COMPOSE A CENTRALIZED UNIT BUT EACHINDIVIDUALLY MAINTAINS SOME ASPECT OF AUTONOMY

FEDERATION: vertical SHARDINGnPrinciplen Partition data according to their logicalaffiliationn Put together data that are commonly accessed23Load%balancer%Cache%1%Web%3%Web%2%nnnThe search load for the large partitioned entity canbe split across multiple servers (logical andphysical) and not only according to multiple indexesin the same logical serverCache%2%Web%1%MySQL%Master%Different schemas, systems, and physicalbases/serversShards the components of a site and not only nal%user%Resume%database%

24NOSQL STORES: PERSISTENCY MANAGEMENT

«memcached»n«memcached» is a memory management protocol based on a cache:n Uses the key-value notionn Information is completly stored in RAMn«memcached» protocol for:n Creating, retrieving, updating, and deleting information from thedatabasen Applications with their own «memcached» manager (Google,Facebook, YouTube, FarmVille, Twitter, Wikipedia)25

Storage on disc (1)nØFor efficiency reasons, information is stored using the RAM:nWork information is in RAM in order to answer to low latency requestsnYet, this is not always possible and desirableThe process of moving data from RAM to disc is called "eviction”; thisprocess is configured automatically for every bucket26

Storage on disc (2)nNoSQL servers support the storage of key-value pairs on disc:nPersistency–can be executed by loading data, closing andreinitializing it without having to load data from another sourcenHot backups– loaded data are sotred on disc so that it can bereinitialized in case of failuresnStorage on disc– the disc is used when the quantity of data ishigher thant the physical size of the RAM, frequently usedinformation is maintained in RAM and the rest es stored on disc27

Storage on disc (3)nStrategies for ensuring:nnØEach node maintains in RAM information on the key-value pairs it stores.Keys:nmay not be found, ornthey can be stored in memory or on discThe process of moving information from RAM to disc is asynchronous:nThe server can continue processing new requestsnA queue manages requests to discIn periods with a lot of writing requests, clients can be notified that theserver is termporaly out of memory until information is evicted28

29NOSQL STORES: CONCURRENCY CONTROL