WIXLIB

11/5/17Data Store CategoriesExample NOSQL systems The data stores are grouped according to their data model Key-value Stores:– store values and an index to find them– based on a programmer- defined key– Project Voldemort, Riak, Redis, Scalaris, TokyoCabinet, Memcached/Membrain/Membase Document Stores: Document Stores:– store documents– The documents are indexed and a simple query mechanism isprovided– Amazon SimpleDB, CouchDB, MongoDB, Terrastore Extensible Record Stores: Extensible Record Stores:– Hbase, HyperTable, Cassandra, Yahoo’s PNUTS– store extensible records that can be partitioned vertically andhorizontally across nodes– Some papers call these “wide column stores” Relational Databases:– MySQL Cluster, VoltDB, Clustrix, ScaleDB, ScaleBase,NimbusDB, Google Megastore (a layer on BigTable) Relational Databases:– store (and index and query) tuples– e.g. the new RDBMSs that provide horizontal scalingDuke CS, Fall 2017CompSci 516: Database Systems37Use Case : Key-value store where you need to look up objects based onmultiple fields– e.g., a driver’s name, license number, ownedvehicle, or birth date39Duke CS, Fall 2017CompSci 516: Database Systems40Use case: Scalable RDBMS uses cases similar to those for document stores: If your application requires many tables withdifferent types of data– multiple kinds of objects, with lookups based on any field. However, aimed at higher throughput, and may providestronger concurrency guarantees,– a relational schema centralizes and simplifies datadefinition and SQL simplifies operations– or for projects with many programmers– at the cost of slightly more complexity than the document stores Suppose storing customer information for an eBay-styleapplication, and you want to partition your data bothhorizontally and vertically:– cluster customers by country, so that you can efficiently search all ofthe customers in one country– separate the rarely-changed “core” customer information such ascustomer addresses and email addresses in one place, and– put certain frequently-updated customer information (such as currentbids in progress) in a different place, to improve performanceCompSci 516: Database Systems38– e.g. in a Department of Motor Vehiclesapplication, with vehicles and driversUse case: Extensible Record StoreDuke CS, Fall 2017CompSci 516: Database Systems application with multiple different kinds ofobjects– that does many RDBMS queries to create a tailoredpage when a user logs in– Suppose it takes several seconds to execute thosequeries, and the user’s data is rarely changed– you might want to store the user’s tailored page as asingle object in a key-value storeCompSci 516: Database SystemsDuke CS, Fall 2017Use case: Document Store if you have a simple application with only onekind of object, and you only need to look upobjects up based on one attribute Suppose you have a web applicationDuke CS, Fall 2017 Key-value Stores:41 However, more useful if the application does notrequire– updates or joins that span many nodes– transaction coordination– or, data movementDuke CS, Fall 2017CompSci 516: Database Systems427

11/5/17Consistent Hashing (CH) Recall dynamic hashing schemes If the #of slots (directory size) changes, then almostall keys had to be remapped In consistent hashing (CH), with #keys K and #slots N, only K/N keys need to be remapped on average Applies to the design of Distributed Hash Table(DHTs) for Uniform Load DistributionConsistent Hashingin DynamoDB– partition a keyspace among a set of sites/nodes– additionally provide an overlay network that connectsnodes such that the nodes responsible for any key can beefficiently locatedDuke CS, Fall 2017CompSci 516: Database Systems43Duke CS, Fall 2017DynamoDB : CH 1/2 Data item identified by a key Assign to a node by hashing the key to yield its positionon the ring Walk the ring clockwise to find the first node with aposition larger than the item’s position Each node is responsible for the region in the ringbetween it and its predecessor node on the ring– represents the “position” on the ring Note: departure or arrival of a node onlyaffects its immediate neighbor The other nodes remain unaffected K/N on average! Data item identified by a key Assign to a node by hashingthe key toCompSci 516: Database Systems45Duke CS, Fall 2017DynamoDB: Replication46 Proposed by CS theoreticians from MIT:– Karger-Lehman-Leighton-Panigrahy-Levine-Lewin– “Consistent Hashing and Random Trees: Distributed Caching Protocolsfor Relieving Hot Spots on the World Wide Web” – STOC 1997– coordinator handles all keys in its range– Coordinator replicates each key it is in charge of Consistent hashing gave birth to Akamai Technologies– Founded by Danny Lewin and Tom Leighton in 1998– Akamai’s content delivery network is one of the largest distributedcomputing platforms– Now market cap 12B and 6200 employees– Managing web-presence of many major companies by storing it locally replicating it at the N-1 clockwise succesor nodes in the ring Each node is in charge of region of the ring between it and itsN-th predecessor 2001: The concept of Distributed Hash Table (DHT) isproposed (how to look for a file) and CH was re-purposed Now used in Dynamo, Couchbase, Cassandra, Voldemort,Riak, .Node B replicates key K at nodes C and DNode D will store keys in the range (A, B], (B, C], (C, D]Note: there may be N “physical” nodes, uses “virtualnodes”CompSci 516: Database SystemsCompSci 516: Database SystemsCH History Dynamo replicates its data on multiple (N) hosts for highavailability and durability Each key k is assigned to a coordinator which is in charge ofreplicationDuke CS, Fall 201744DynamoDB : CH 2/2 [ref. the DynamoDB paper, sec 4.3] Must scale incrementally Consistent hashing is used to dynamically distributedata around a “ring” of nodes ( sites) The output of a hash function is treated as a circularring Each node is assigned a random value in this spaceDuke CS, Fall 2017CompSci 516: Database Systems47Duke CS, Fall 2017CompSci 516: Database Systems488

11/5/17Why choose RDBMS over NoSQL : 1/31. If new relational systems can do everythingthat a NoSQL system can, with analogousperformance and scalability (?), and with theconvenience of transactions and SQL, NoSQLis not neededSQL vs. NOSQLArguments for both sidesstill a controversial topic2. Relational DBMSs have taken and retainedmajority market share over othercompetitors in the past 30 years– (network, object, and XML DBMSs)Duke CS, Fall 2017CompSci 516: Database Systems49Why choose RDBMS over NoSQL : 2/33. Successful relational DBMSs have been builtto handle other specific application loads inthe past:–––––CompSci 516: Database Systems51Why choose NoSQL over RDBMS : 1/31. We haven’t yet seen good benchmarks showingthat RDBMSs can achieve scaling comparable withNoSQL systems like Google’s BigTable– then a key-value store is adequate and probably easier to understandthan a relational DBMS– Likewise for a document store on a simple application: you only paythe learning curve for the level of complexity you requireCompSci 516: Database Systems50Why choose RDBMS over NoSQL : 3/3Duke CS, Fall 2017CompSci 516: Database Systems52Why choose NoSQL over RDBMS : 2/33. Some applications require a flexible schema2. If you only require a lookup of objects based on asingle keyDuke CS, Fall 2017CompSci 516: Database Systems4. While no “one size fits all” in the SQLproducts themselves, there is a commoninterface with SQL, transactions, andrelational schema that give advantages intraining, continuity, and data interchangeread-only or read-mostly data warehousingOLTP on multi-core multi-disk CPUsin-memory databasesdistributed databases, andnow horizontally scaled databasesDuke CS, Fall 2017Duke CS, Fall 201753– allowing each object in a collection to have differentattributes– While some RDBMSs allow efficient “packing” of tupleswith missing attributes, and some allow adding newattributes at runtime, this is uncommonDuke CS, Fall 2017CompSci 516: Database Systems549

11/5/17Why choose NoSQL over RDBMS : 3/34. A relational DBMS makes “expensive” (multi- nodemulti-table) operations “too easy”– NoSQL systems make them impossible or obviouslyexpensive for programmersColumn Store5. While RDBMSs have maintained majority marketshare over the years, other products haveestablished smaller but non-trivial markets in areaswhere there is a need for particular capabilities– e.g. indexed objects with products like BerkeleyDB, or graph-followingoperations with object-oriented DBMSsDuke CS, Fall 2017CompSci 516: Database Systems55Duke CS, Fall 2017CompSci 516: Database Systems57Duke CS, Fall 2017CompSci 516: Database SystemsDuke CS, Fall 2017CompSci 516: Database Systems56Row vs. Column Store Row store– store all attributes of a tuple together– storage like “row-major order” in a matrix Column store– store all rows for an attribute (column) together– storage like “column-major order” in a matrix e.g.– MonetDB, Vertica (earlier, C-store), SAP/Sybase IQ,Google Bigtable (with column groups)Ack: Slide from VLDB 2009 tutorial on Column storeDuke CS, Fall 2017CompSci 516: Database SystemsDuke CS, Fall 2017CompSci 516: Database SystemsAck: Slide from VLDB 2009 tutorial on Column store5958Ack: Slide from VLDB 2009 tutorial on Column store6010

11/5/17Ack: Slide from VLDB 2009 tutorial on Column storeAck: Slide from VLDB 2009 tutorial on Column storeDuke CS, Fall 2017CompSci 516: Database Systems61Duke CS, Fall 2017CompSci 516: Database SystemsMongoDB Additional and Optional Slides onMongoDBMongoDB is an open source document store written in C provides indexes on collectionslocklessprovides a document query mechanismsupports automatic shardingReplication is mostly used for failoverdoes not provide the global consistency of a traditional DBMS supports dynamic queries with automatic use of indices, likeRDBMSs also supports map-reduce – helps complex aggregations acrossdocs provides atomic operations on fieldsCompSci 516: Database Systems63Duke CS, Fall 2017Optional slide: Read yourself The update command supports “modifiers” that facilitate atomicchanges to individual valuesCompSci 516: Database Systems64Optional slide: Read yourselfMongoDB: Atomic Ops on Fields–––––Optional slide: Read yourself– but you can get local consistency on the up-to-date primary copy of adocument(May be useful for HW3)https://docs.mongodb.comDuke CS, Fall 201762MongoDB: Index MongoDB indices are explicitly defined usingan ensureIndex call set sets a value inc increments a value push appends a value to an array pushAll appends several values to an array pull removes a value from an array, and pullAll removes severalvalues from an array– any existing indices are automatically used forquery processing Since these updates normally occur “in place”, they avoid theoverhead of a return trip to the server There is an “update if current” convention for changing a documentonly if field values match a given previous value MongoDB supports a findAndModify command to perform anatomic update and immediately return the updated document To find all products released last year (2015)or later costing under 100 you could write: db.products.find({released: { gte: new Date(2015, 1, 1,)}, price{‘ lte’: 100},})Duke CS, Fall 2017Duke CS, Fall 2017– useful for implementing queues and other data structures requiringatomicityCompSci 516: Database Systems65CompSci 516: Database Systems6611

11/5/17Optional slide: Read yourselfOptional slide: Read yourselfMongoDB: Data MongoDB stores data in a binary JSON-likeformat called BSON MongoDB supports master-slave replicationwith automatic failover and recovery– BSON supports boolean, integer, float, date, stringand binary types– MongoDB can also support large binary objects,eg. images and videos– These are stored in chunks that can be streamedback to the client for efficient deliveryDuke CS, Fall 2017CompSci 516: Database SystemsMongoDB: Replication67– Replication (and recovery) is done at the level ofshards– Replication is asynchronous for higherperformance, so some updates may be lost on acrashDuke CS, Fall 2017CompSci 516: Database Systems6812

column_stores.pdf Optional: "Dynamo: Amazon's Highly Available Key-value Store" By Giuseppe DeCandiaet. al. SOSP 2007 "Bigtable: A Distributed Storage System for Structured Data" Fay Chang et. al. OSDI 2006 Duke CS, Fall 2017 CompSci 516: Database Systems 3 NoSQL Duke CS, Fall 2017 CompSci 516: Database Systems 4