WEB Lecture 20 NoSQL Databases: Concepts and Types

NoSQL Overview

What is NoSQL?

NoSQL stands for "not only SQL" and refers to non-relational persistent storage systems. Key characteristics include:

  • Weaker semantics than ACID.
  • Different data representation compared to SQL databases.
  • Scalability.
  • Speed (when it works as intended).

Why NoSQL?

  • SQL is associated with ACID properties, which ensure safety but can be slow and difficult to scale.
  • NoSQL is suitable for big data where full ACID compliance is not always necessary.
  • Large datasets require distributed systems, making NoSQL a viable option.

Azure: Planetary Scale Computing

Microsoft Azure has:

  • 200 datacenters.
  • 4,000,000 servers (and growing).

Websites and Applications

Websites commonly use multiple applications, each potentially leveraging different data stores:

  • Product Images: Object Store
  • User Sessions: Key-Value Store
  • Shopping Cart: Key-Value Session Store
  • Financial Transactions: Relational Store
  • Product Catalog: Document Store
  • Analytics: Column Store
  • Personalized Recommendations: Graph Store

Application Development/Deployment (PaaS)

Applications are built on multiple layers:

  • Primary application at the top.
  • Middleware.
  • Data at the bottom.

Example layers include:

  • Development Services (Versioning, Messaging, Security/Identity)
  • Physical Infrastructure (Storage - Disk/Flash)
  • Runtime Data Services (Relational, Columnar, Document, Key-Value, Object, Batch, File/Block, Dedicated)
  • Unified Infrastructure Orchestration (Security, Provisioning, SLA Monitoring, Logging, VMWare)

BASE

BASE is an alternative to ACID, focusing on availability and eventual consistency:

  • Basically Available: Guarantees availability.
  • Soft State: The system's state can change over time, even without input, due to eventual consistency.
  • Eventual Consistency: The system will become consistent over time if it stops receiving input.

Types of NoSQL

NoSQL databases are characterized by simple relationships including:

  • Key/Value Stores.
  • Wide Column Stores (e.g., Google uses this to index the internet).
  • Document Stores.
  • Object Stores (similar to key-value stores).

Specific examples mentioned:

  • REDIS.

These systems are designed to scale out, utilizing all machines.

Distributed Systems

Handling millions/billions of users across N machines requires even distribution. We distribute the problem over machines using statistics.

Desideratum: uniformly distributed
Law of Large Numbers

Sharding

Divide the key space by the number of machines (N).

  • Each machine is responsible for a subset of the keys.
  • Example: N = 10 machines, keys between 0 and 1,000,000.
    • m0 owns [0-99,999], m1 owns [100,000-199,999], etc.
  • Send requests to the machine that owns the key!
  • Key: md5(key)→key%N→machinemd5(key) \rightarrow key \% N \rightarrow machine
  • Strings can be sharded lexically or using a hash function.
  • MD5(x)/SHA1 are uniformly distributed.

Lexical Sharding with Strings

Example:

  • A-D
  • E-I
  • J-P
  • P-U
  • V-Z

Requests are routed based on the string's starting letter (e.g., "Santry" goes to V-Z, "Khan" goes to E-I).

Sharding with Hashing (N = 100)

Example:

  • Request: md5("Santry")%N=0md5("Santry") \% N = 0
  • Request: md5("Khan")%N=imd5("Khan") \% N = i

The requests are distributed across machines M0 to M99, including Mi.

Sharding Clients

Clients maintain maps of the cluster to know where to send requests.

  • M0: www.server0.oz
  • M99: www.server99.oz

Key-Value Stores

Data is stored in ⟨key,value⟩\langle key, value \rangle pairs.

  • Simple form of storage.
  • Knowing the key allows retrieval of the value.
  • Supports sharding.

Example: Redis

  • REmote DIctionary Server.
  • In-memory data storage with regular disk syncing.
  • Partitioning can address RAM limits.
  • Speeds up read and write access.
  • Master-slave replication of databases.
  • Various data types for values, including basic types and collections like lists, sets, and hashsets.

Redis Operations

  • Transactions supported to some extent, but no rollback.

    • Rollback implies an overhead on transaction time.

  • Examples:

    • SET account 36 (key is account, value is 36)
    • GET account (returns the value for the key)

  • Atomic operations, such as adding values, appending strings.

    • INCR account (add one to the account)
    • someKeys = KEYS(id*) (returns keys starting with id)

Wide Column Stores

  • Like SQL, uses tables.

  • The first column of each table is a key.

  • Rows can have different columns.

  • Rows, columns, or elements are often time-stamped for temporal functionality.

  • Schema-free.

  • Poor join support.

  • Distributed, asynchronous replication.

    • No need to update all duplicates at once.

  • Original implementation was Google BigTable.

    • Used to support Google's search product (PageRank).

Object Stores

Examples include:

  • Ceph
  • Cassandra
  • Massive scale-out (sharding).
  • Stores data at a planetary scale.

Document Stores

  • Stores documents (hierarchical data in formats like JSON or XML).

    • Not MS Word documents!

  • Each record in a document can include any field.

  • Every document has a unique ID.

  • Schema-free.

  • No join support between documents.

  • Query language provides an API to access documents.

    • Examples: range queries, regular expression searches.

Summary

  • NoSQL is used for Internet-scale data problems at the cost of forsaking ACID.

  • NoSQL supports domain-specific solutions to real business problems.

  • The choice between SQL and NoSQL is dictated by the problem.

    • "Do not use a hammer to vacuum your carpet."