WIXLIB

11/13/18Reading MaterialNOSQL: “Scalable SQL and NoSQL Data Stores”Rick Cattell, SIGMOD Record, December 2010 (Vol. 39, No. 4) see webpage http://cattell.net/datastores/ for updates and more pointers MongoDB manual: https://docs.mongodb.com/manual/CompSci 516Database SystemsColumn Store: D. Abadi, P. Boncz, S. Harizopoulos, S. Idreos and S. Madden. The Design and Implementation ofModern Column-Oriented Database Systems. Foundations and Trends in Databases, vol. 5, no.3, pp. 197–280, 2012. See VLDB 2009 tutorial: http://nms.csail.mit.edu/ stavros/pubs/tutorial2009column stores.pdfLecture 20NoSQLandColumn StoreOptional: “Dynamo: Amazon’s Highly Available Key-value Store” By Giuseppe DeCandia et. al. SOSP2007Instructor: Sudeepa Roy Duke CS, Fall 2018CompSci 516: Database Systems“Bigtable: A Distributed Storage System for Structured Data” Fay Chang et. al. OSDI 20061Duke CS, Fall 2018CompSci 516: Database Systems23Duke CS, Fall 2018CompSci 516: Database Systems4NoSQLSee the optional/additional slides on MongoDBon the course websiteMay be useful for HW3Duke CS, Fall 2018CompSci 516: Database SystemsSo far -- RDBMSToday NoSQL: ”new” database systems Relational Data Model Relational Database Systems (RDBMS) RDBMSs have– not typically RDBMS– relax on some requirements, gain efficiency andscalability New systems choose to use/not use severalconcepts we learnt so far– a complete pre-defined fixed schema– a SQL interface– e.g. “System ---” does not use locks but uses multiversion CC (MVCC) or,– “System ---” uses asynchronous replication– and ACID transactions therefore, it is important to understand the basics(Lectures 1-18) even if they are not used in somenew systems!Duke CS, Fall 2018CompSci 516: Database Systems5Duke CS, Fall 2018CompSci 516: Database Systems61

11/13/18Warnings!OLAP vs. OLTP Material from Cattell’s paper (2010-11) –some info will be outdated OLTP (OnLine Transaction Processing)–––––– see webpage http://cattell.net/datastores/ forupdates and more pointers We will focus on the basic ideas of NoSQLsystems Optional reading slides at the end onMongoDB OLAP (OnLine Analytical Processing)– Many aggregate/group-by queries – multidimensional data– Data mostly static– Will study OLAP Cube soon– may be useful for HW3– there are also comparison tables in the Cattell’spaper if you are interestedDuke CS, Fall 2018CompSci 516: Database SystemsRecall transactions!Multiple concurrent read-write requestsCommercial applications (banking, online shopping)Data changes frequentlyACID properties, concurrency control, recovery7Duke CS, Fall 2018New Systems When you study a new system, compare it withRDBMS-s on its– to do updates as well as reads– in contrast to traditional DBMSs and data warehouses– to provide good horizontal scalability (?) for simpleread/write database operations distributed over manyservers Originally motivated by Web 2.0 applications––––––data modelconsistency mechanismsstorage mechanismsdurability guaranteesavailabilityquery support These systems typically sacrifice some of thesedimensions– e.g. database-wide transaction consistency, in order toachieve others, e.g. higher availability and scalability– these systems are designed to scale to thousands ormillions of usersCompSci 516: Database Systems9Duke CS, Fall 2018NoSQL101. the ability to horizontally scale “simple operations”throughput over many servers2. the ability to replicate and to distribute (partition) data overmany servers3. a simple call level interface or protocol (in contrast to SQLbinding)4. a weaker concurrency model than the ACID transactions ofmost relational (SQL) database systems5. efficient use of distributed indexes and RAM for data storage6. the ability to dynamically add new attributes to data records NoSQL stands for “Not Only SQL” or “NotRelational”– not entirely agreed upon Next: six key features of NoSQL systemsCompSci 516: Database SystemsCompSci 516: Database SystemsNoSQL: Six Key Features Many of the new systems are referred to as“NoSQL” data storesDuke CS, Fall 20188New Systems vs. RDMS We will examine a number of SQL and so- called“NoSQL” systems or “data stores” Designed to scale simple OLTP-style applicationloadsDuke CS, Fall 2018CompSci 516: Database Systems11Duke CS, Fall 2018CompSci 516: Database Systems122

11/13/181. Memcached: main featuresImportant Examples of New Systems Three systems provided a “proof of concept” andinspired many other data stores popular open source cache supports distributed hashing (later)1. Memcached2. Amazon’s Dynamo3. Google’s BigTableDuke CS, Fall 2018 demonstrated that in-memory indexes can behighly scalable, distributing and replicatingobjects over multiple nodesCompSci 516: Database Systems132. Dynamo : main features data fetched are not guaranteed to be up-todate but updates are guaranteed to be propagatedto all nodes eventuallyCompSci 516: Database Systems15 https://cloud.google.com/bigtable/ h.google.com/en//archive/bigtable-osdi06.pdfDuke CS, Fall 2018CompSci 516: Database Systems16ACID vs. BASE The idea is that by giving up ACID constraints, onecan achieve much higher performance and scalability Recall ACID for RDBMS desired properties oftransactions:– Atomicity, Consistency, Isolation, and Durability The systems differ in how much they give up– e.g. most of the systems call themselves “eventuallyconsistent”, meaning that updates are eventuallypropagated to all nodes– but many of them provide mechanisms for some degree ofconsistency, such as multi-version concurrency control(MVCC) NOSQL systems typically do not provide ACID Basically Available Soft state Eventually consistentCompSci 516: Database Systems14 demonstrated that persistent record storagecould be scaled to thousands of nodes “column families”BASE (not ACID J)Duke CS, Fall 2018CompSci 516: Database Systems3. BigTable : main features pioneered the idea of eventual consistency as away to achieve higher availability and scalabilityDuke CS, Fall 2018Duke CS, Fall 201817Duke CS, Fall 2018CompSci 516: Database Systems183

11/13/18“CAP” TheoremTwo foci for NoSQL systems Often Eric Brewer’s CAP theorem cited for NoSQL A system can have only two out of three of the following properties:1. “Simple” operations Consistency– do all clients see the same data? Availability2. Horizontal Scalability– is the system always on? Partition-tolerance– even if communication is unreliable, does the systemfunction? The NoSQL systems generally give up consistency– However, the trade-offs are complexDuke CS, Fall 2018CompSci 516: Database Systems19Duke CS, Fall 20181. “Simple” Operations Shared-Nothing Horizontal Scaling– e.g. key lookups– reads and writes of one record or a small number of records The ability to distribute both the data and the load ofthese simple operations over many servers This is in contrast to complex queries, joins, or read-mostlyaccess– with no RAM or disk shared among the servers Not “vertical” scaling– where a database system utilizes many cores and/or CPUsthat share RAM and disks Inspired by web, where millions of users may both read andwrite data in simple operations– e.g. search and update multi-server databases of electronicmail, personal profiles, web postings, wikis, customer records,online dating records, classified ads, and many other kinds ofdataCompSci 516: Database Systems202. Horizontal Scalability Reading or writing a small number of related records ineach operationDuke CS, Fall 2018CompSci 516: Database Systems Some of the systems we describe provide both verticaland horizontal scalability21Duke CS, Fall 2018CompSci 516: Database Systems222. Horizontal vs. Vertical ScalingWhat is different in NOSQL systems Effective use of multiple cores (vertical scaling) isimportant When you study a new NOSQL system, noticehow it differs from RDBMS in terms of– but the number of cores that can share memory islimited horizontal scaling generally is less expensive– can use commodity servers Note: horizontal and vertical partitioning are not relatedto horizontal and vertical scaling (Lecture 18)– except that they are both useful for horizontal scalingDuke CS, Fall 2018CompSci 516: Database Systems231.2.3.4.Concurrency ControlData Storage MediumReplicationTransactionsDuke CS, Fall 2018CompSci 516: Database Systems244

11/13/18Choices in NOSQL systems:1. Concurrency ControlChoices in NOSQL systems:2. Data Storage Mediuma) Locks––some systems provide one-user-at-a-time read or update locksMongoDB provides locking at a field levelb) MVCC– snapshots or replication to disk– poor performance when overflows RAMc) None–––a) Storage in RAMdo not provide atomicitymultiple users can edit in parallelno guarantee which version you will readb) Disk storage– caching in RAMd) ACID––pre-analyze transactions to avoid conflictsno deadlocks and no waits on locksDuke CS, Fall 2018CompSci 516: Database Systems25Duke CS, Fall 2018Choices in NOSQL systems:3. Replicationa) supportb) do not supportc) in between– faster, but updates may be lost in a crashc) Both– support local transactions only within a singleobject or “shard”– shard a horizontal partition of data in adatabase– local copies synchronously, remote copiesasynchronouslyCompSci 516: Database Systems26Choices in NOSQL systems:4. Transaction Mechanisms whether mirror copies are always in synca) Synchronousb) AsynchronousDuke CS, Fall 2018CompSci 516: Database Systems27Duke CS, Fall 2018CompSci 516: Database Systems28Data Model Terminology for NoSQLComparison from Cattell’s paper (2011) Unlike SQL/RDBMS, the terminology for NoSQLis often inconsistent– we are following notations in Cattell’s paper All systems provide a way to store scalar values– e.g. numbers and strings Some of them also provide a way to store morecomplex nested or reference valuesDuke CS, Fall 2018CompSci 516: Database Systems29Duke CS, Fall 2018CompSci 516: Database Systems305

11/13/18Data Model Terminology for NoSQL Same as before A “tuple” is a row in a relational table The systems all store sets of attribute-value pairs– but use four different data structures1.2.3.4.– attribute names are pre-defined in a schema– the values must be scalar– the values are referenced by attribute name– in contrast to an array or list, where they arereferenced by ordinal positionTupleDocumentExtensible RecordObjectDuke CS, Fall 2018CompSci 516: Database Systems1. Tuple31Duke CS, Fall 20182. DocumentCompSci 516: Database Systems323. Extensible Record Allows values to be nested documents or lists aswell as scalar values A hybrid between a tuple and a document families of attributes are defined in a schema but new attributes can be added (within anattribute family) on a per-record basis Attributes may be list-valued– think about XML or JSON The attribute names are dynamically defined foreach document at runtime A document differs from a tuple in that theattributes are not defined in a global schema– and a wider range of values are permittedDuke CS, Fall 2018CompSci 516: Database Systems33Duke CS, Fall 20184. ObjectCompSci 516: Database Systems34Example NOSQL systems Key-value Stores: Analogous to an object in programminglanguages– Project Voldemort, Riak, Redis, Scalaris, TokyoCabinet, Memcached/Membrain/Membase– but without the procedural methods Document Stores:– Amazon SimpleDB, CouchDB, MongoDB, Terrastore Values may be references or nested objects Extensible Record Stores:– Hbase, HyperTable, Cassandra, Yahoo’s PNUTS Relational Databases:– MySQL Cluster, VoltDB, Clustrix, ScaleDB, ScaleBase,NimbusDB, Google Megastore (a layer on BigTable)Duke CS, Fall 2018CompSci 516: Database Systems35Duke CS, Fall 2018CompSci 516: Database Systems366