Forem: MinhQuan805

History of NoSQL: The Data Management Revolution

MinhQuan805 — Fri, 05 Sep 2025 11:23:10 +0000

🌐 To dive deeper into the details of NoSQL, visit: Quan Note

NoSQL is a group of database management systems (DBMS) designed to overcome the limitations of traditional relational databases. Unlike systems based on fixed-schema tables, NoSQL offers:

Flexible data models: Stores and retrieves data in non-tabular relational formats, such as documents, key-value, wide-column, or graphs.
High scalability: Supports handling large data volumes and high access loads in distributed environments.
Elasticity: Enables rapid changes and efficient data replication.

The history of NoSQL is closely tied to the internet boom, the rise of Web 2.0 applications, and the need to process unstructured data in large-scale systems.

NoSQL has become a critical solution for tech giants like Google, Amazon, and Netflix, meeting demands for performance, reliability, and scalability.

I. 1960s–2000: The Origins of Non-Relational Databases

a. Early Concepts:

Before NoSQL emerged, non-relational database models already existed, serving large-scale enterprise systems:

Hierarchical databases: For example, IMS (Information Management System) by IBM, widely used in banking and aviation systems since the 1960s.
Network databases: For example, CODASYL, enabling complex data modeling through network relationships. These systems did not use the relational (table-based) model proposed by Edgar F. Codd, which became the standard in the 1970s with databases like Oracle and MySQL.

b. Technological Context:

The rise of the internet in the late 1990s transformed how data was generated and used. Web applications like social media, e-commerce, and search engines required:

Handling unstructured data (e.g., posts, images, videos).
Supporting high read/write loads from millions of concurrent users.
Distributed architectures to ensure availability and fault tolerance.
Traditional relational databases, with fixed schemas and strict consistency requirements, struggled to meet these demands, particularly in horizontal scaling.

Impact: These limitations laid the groundwork for the development of non-relational storage systems, leading to the birth of NoSQL.

II. 2000s: The Birth of the NoSQL Term

a. Origin of the Term:

In 1998, Carlo Strozzi coined the term NoSQL to describe his lightweight, open-source, non-relational database designed for simplified data storage. However, the concept did not gain widespread traction at the time.

b. Scalability Challenges:

In the mid-2000s, major tech companies like Google and Amazon faced unprecedented data management challenges:

Google developed Bigtable (2006): A distributed storage system designed to handle structured data across thousands of servers. Bigtable powered services like Google Search and Google Maps.
Amazon created Dynamo (2007): A distributed key-value store optimized for high performance and fault tolerance, supporting services like Amazon’s e-commerce platform.

These systems laid the foundation for modern NoSQL databases, emphasizing scalability and availability.

c. Significance:

The solutions from Google and Amazon inspired the open-source community, leading to the development of systems like HBase (based on Bigtable) and DynamoDB (a commercialized version of Dynamo).

III. 2009: The Modern NoSQL Movement

a. Key Milestone:

In 2009, Johan Oskarsson, an engineer at Last.fm, reused the term NoSQL while organizing an event in San Francisco to discuss non-relational, distributed, and open-source databases.
The term quickly became a symbol of the movement for non-relational data stores, including open-source implementations of Bigtable (Google) and DynamoDB (Amazon).

b. Rise of MongoDB and Redis:

Also in 2009, two prominent NoSQL databases emerged and gained widespread adoption:

MongoDB: A document-based database that allows storage of semi-structured data in JSON or BSON formats. MongoDB is used in applications like e-commerce (eBay) and content management (Forbes).
Redis: A key-value store renowned for its high speed and caching capabilities. Redis is used by Twitter and Stack Overflow for real-time data processing.

The success of MongoDB and Redis solidified NoSQL as a leading choice for large-scale applications.

IV. 2010s: The NoSQL Ecosystem Flourishes

a. NoSQL Explosion:

The NoSQL ecosystem expanded rapidly with the introduction of specialized databases:

Neo4j: A graph database ideal for applications like social networks and network analysis (e.g., LinkedIn uses Neo4j to analyze user relationships).
Elasticsearch: A search engine and analytics database used by Wikipedia and eBay for full-text search.
HBase: A distributed database modeled after Bigtable, used by Facebook for messaging data processing.

Major companies like Netflix, LinkedIn, and Twitter adopted NoSQL to meet demands for performance and real-time data processing from millions of users.

b. CAP Theorem:

Defined by Eric Brewer in 2000 and widely popularized in the 2010s, the CAP theorem became a guiding principle for non-relational database design.

A distributed data store can only guarantee two out of three of the following:

Consistency: Data remains consistent after every operation (e.g., all users see the same data after an update).
Availability: The system is always operational with no downtime.
Partition Tolerance: The system continues to function even if servers are partitioned and cannot communicate.

Real-world examples:

MongoDB prioritizes consistency and availability in non-partitioned systems.
Cassandra prioritizes availability and partition tolerance, ideal for globally distributed applications.

V. 2020s: Blurring the Lines Between SQL and NoSQL

a. Convergence of Paradigms:

Relational databases began incorporating NoSQL features:

Support for JSON documents (e.g., PostgreSQL, MySQL).
Horizontal scaling through technologies like sharding and replication.

NoSQL databases adopted traditional features:

ACID transactions (Atomicity, Consistency, Isolation, Durability) to ensure data integrity.
SQL-like query languages (e.g., Cassandra’s CQL).
For example, MongoDB introduced multi-document transactions in 2018, blurring the line with SQL.

b. Multi-Model Databases:

Systems like ArangoDB, OrientDB, and Azure Cosmos DB support multiple data models (document, graph, key-value) within a single system.

This trend reflects the need for flexible storage solutions suited for complex applications like artificial intelligence (AI) and big data analytics.

📝 Contact Me

✍️ Blog: Quan Notes

💼 LinkedIn: Võ Minh Quân

How does CPU scheduling ensure that every real-time task meets its deadline?

MinhQuan805 — Mon, 25 Aug 2025 13:54:46 +0000

For a deeper understanding of operating systems and related concepts, feel free to explore more resources on my website: Quan Notes

Scheduling is the strategy of selecting the most suitable process to execute in order to achieve the highest efficiency.

Real-time systems are designed to perform real-time tasks, which need to be executed immediately with a certain degree of urgency.

CPU scheduling for real-time systems poses many challenges due to the real-time requirements.

There are two types of real-time systems:

Soft real-time systems: Critical tasks are given the highest priority, but no other guarantees are provided.
Hard real-time systems: Tasks must be completed before their deadlines. If a task misses its deadline, it is considered a failure, and execution after the deadline has no value or may be canceled by the system.

In this article, we will explore some issues related to process scheduling in both soft and hard real-time systems.

I. Minimizing Latency

Real-time systems operate on an event-driven model, waiting for events from software (e.g., a timer expiring) or hardware (e.g., a remote-controlled device detecting an obstacle). When an event occurs, the system must respond and process it quickly.
Event latency is the time from when an event occurs to when it is serviced.

Events in real-time systems have varying latency requirements. For example, an anti-lock braking system requires a latency of 3–5 milliseconds to respond when a wheel slips, otherwise the car may lose control. In contrast, a radar system on an aircraft may tolerate a latency of a few seconds.
There are two decision-making modes in scheduling:

Non-preemptive: Once in the running state, a process will execute until it completes or is interrupted due to an I/O request.
Preemptive: A running process can be interrupted mid-execution and moved back to the ready state.

The performance of real-time systems is affected by two types of latency:

Interrupt Latency: The time from when an interrupt reaches the CPU to when the interrupt service routine (ISR) begins.

The operating system must complete the current instruction, identify the type of interrupt, save the current process state, and then handle the interrupt.
Minimizing and bounding interrupt latency is critical, especially in hard real-time systems, and interrupts can only be disabled for very short periods to update kernel data structures.

Dispatch Latency: The time it takes for the scheduler to stop one process and start another. The most effective technique for keeping dispatch latency low is to provide a preemptive kernel, which includes:

Conflict Phase: Pausing kernel tasks and releasing resources from lower-priority processes.
Dispatch Phase: Scheduling a higher-priority process onto the CPU.

Real-time systems need to minimize both interrupt latency and dispatch latency to ensure immediate responses for real-time tasks.

II. Priority-Based Scheduling

The core feature of a real-time operating system is the ability to respond immediately to real-time processes when they request CPU time. Therefore, the scheduler must support priority-based scheduling with preemption.

These algorithms assign priorities to processes based on their importance; more critical tasks are given higher priority.
If preemption is supported, a running process will be paused when a higher-priority process becomes ready.

Examples:

Operating systems like Windows, Linux, and Solaris assign the highest priority to real-time processes.
Windows has 32 priority levels, with levels 16–31 reserved for real-time processes. Linux and Solaris have similar mechanisms.

Limitations:

Priority-based scheduling with preemption only guarantees functionality for soft real-time systems.
Hard real-time systems further ensure that tasks are serviced by their deadlines, requiring additional scheduling features.

III. Task Models in Real-Time Systems

1. Periodic Tasks

These are real-time tasks that repeat after a fixed time interval, known as the period.

These tasks are triggered by clock interrupts. For example, collecting data from a sensor every 5 seconds.

a. Rate Monotonic Scheduling (RMS)

Priority is assigned based on the inverse of the period: shorter periods receive higher priority, and longer periods receive lower priority.
A set of processes can be scheduled if it satisfies the formula:

Where:

To understand Rate Monotonic scheduling, consider the following example table:

Calculating Utilization (U):

The RMS threshold for n = 3:

Result: U=0.75 ≤ 0.7797, so this set of processes is schedulable with RMS.

Based on periods:

• P1(T1 = 20): Lowest priority.

• P2(T2 = 5): Highest priority.

• P3(T3 = 10): Second-highest priority.

Priority order: P2 > P3 > P1.

b. Earliest Deadline First (EDF)

This is an optimal dynamic priority scheduling algorithm for real-time systems, applicable to both static and dynamic scheduling.
Priority Principle: The process with the earliest deadline is assigned the highest priority, while processes with later deadlines receive lower priority.
High Efficiency: Can achieve 100% CPU utilization while ensuring all processes meet their deadlines, as long as the schedule is feasible.
Priority Adjustment: When a new process becomes ready, it announces its deadline to the system, and the priorities of existing processes are dynamically adjusted based on the new deadline.

2. Aperiodic Tasks

These are real-time tasks that occur at random times, without a fixed period.

The time between two occurrences can be very short (even zero) or very long.
These tasks are typically soft real-time and involve random interactions, e.g., pressing a key on a keyboard for input.
Scheduling algorithms for periodic tasks, such as Total Bandwidth Server and Enhanced Virtual Release Advancing, can be explored further.

References

Silberschatz, A., Gagne, G., & Galvin, P. B. (n.d.). Operating System Concepts. [Edition number if known, e.g., 10th ed.]. Wiley.

For more insights, visit my website: Quan Notes.