Unit 1: Virtualization and Distributed Computing

1. Evolution and Foundations of Distributed Computing

Distributed computing represents the paradigm wherein a collection of autonomous, networked computers coordinates their actions by exchanging messages, presenting themselves to end users as a unified, coherent computational facility. The emergence of modern cloud infrastructure is the direct culmination of decades of evolution across distinct distributed system models.

CODECopy Code
+-----------------------------------------------------------------------------+
|                   EVOLUTION TOWARD CLOUD COMPUTING                          |
+-----------------------------------------------------------------------------+
| Mainframes (1960s)    : Centralized compute, dumb terminals, time-sharing.  |
|          |                                                                  |
| Client-Server (1980s) : Two-tier/three-tier distributed RPC and sockets.    |
|          |                                                                  |
| Cluster Computing     : Homogeneous commodity PCs linked via high-speed LAN |
|          |              (e.g., Beowulf clusters for parallel MPI jobs).     |
|          v                                                                  |
| Grid Computing (1990s): Heterogeneous, geographically dispersed systems     |
|          |              sharing federated virtual organization resources.   |
|          v                                                                  |
| Utility Computing     : Packaging computing resources as metered services   |
|          |              analogous to traditional water/electricity grids.   |
|          v                                                                  |
| Cloud Computing (2000s): Dynamically scalable, virtualized, multi-tenant    |
|                         on-demand computing delivered over the Internet.    |
+-----------------------------------------------------------------------------+

1.1 Core Characteristics of Distributed Systems

1. Resource Sharing: Hardware (CPU, storage, peripherals) and software (databases, files, services) are shared collaboratively across networked nodes.
2. Openness & Scalability:
   • Systems are constructed using standard open protocols (e.g., POSIX, TCP/IP, REST, gRPC).
   • Horizontal Scalability (Scale-Out): Adding more independent worker nodes to a distributed cluster.
   • Vertical Scalability (Scale-Up): Adding more CPU cores, RAM, or NVMe disks to a single physical machine.
3. Concurrency: Multiple autonomous processes execute simultaneously on disparate physical processors, handling concurrent requests.
4. Fault Tolerance: A partial failure in one hardware component or network switch does not halt the entire system. Resilience is maintained via replication, heartbeat monitoring, and consensus protocols (Paxos, Raft).
5. Transparency Dimensions:
   • Access Transparency: Identical operations access local and remote resources.
   • Location Transparency: Users access resources without knowing their physical geography.
   • Migration Transparency: Resources move without changing their addresses.
   • Replication Transparency: Multiple duplicate copies operate invisibly to users.
   • Concurrency Transparency: Concurrent processes operate without interference.
   • Failure Transparency: Masking node faults so applications run uninterrupted.

2. Virtualization Foundations & Theory

Virtualization is the creation of a virtual (rather than actual) version of a computational resource, including computer hardware platforms, storage devices, and computer network resources. It acts as an abstraction layer that completely decouples physical hardware from operating systems and running applications.

CODECopy Code
+-----------------------------------------------------------------------------+
|                      POPEK-GOLDBERG VIRTUALIZATION MODEL                    |
+-----------------------------------------------------------------------------+
|                                                                             |
|   Three Core Virtual Machine Monitor (VMM) Properties (1974):               |
|                                                                             |
|   1. EQUIVALENCE (Fidelity):                                                |
|      Any program running under the VMM must exhibit behavior essentially   |
|      identical to that demonstrated when running on bare hardware.          |
|                                                                             |
|   2. RESOURCE CONTROL (Safety):                                             |
|      The VMM must retain absolute control of virtualized hardware resources.|
|      Guest software must not be able to compromise hypervisor authority.    |
|                                                                             |
|   3. EFFICIENCY (Performance):                                              |
|      A statistically dominant majority of machine instructions must be      |
|      executed directly on the raw physical processor without VMM mediation. |
|                                                                             |
+-----------------------------------------------------------------------------+

2.1 The Popek-Goldberg Virtualization Theorem

Gerald J. Popek and Robert P. Goldberg classified CPU instruction sets into three categories:

• Privileged Instructions: Instructions that trap if executed in user mode and do not trap in supervisor/kernel mode (e.g., CLI, STI, halting the CPU).
• Sensitive Instructions: Instructions that behave differently depending on the execution mode (control-sensitive) or that examine/modify hardware configurations, page tables, or segment registers (behavior-sensitive).
• Innocuous Instructions: All remaining standard instructions (arithmetic, branch, data movement).

The Popek-Goldberg Theorem:
A computer architecture is strictly classically virtualizable if and only if all sensitive instructions are a strict subset of privileged instructions:
$\text{Sensitive Instructions} \subseteq \text{Privileged Instructions}$

2.2 The Historic x86 Virtualization Gap

In the classical Intel IA-32 (x86) architecture, the Popek-Goldberg theorem was violated.

• The x86 architecture features four hierarchical privilege levels (Rings 0, 1, 2, 3). Operating system kernels traditionally reside in Ring 0, while user applications execute in Ring 3.
• When running a guest operating system inside a virtual machine, the guest OS is demoted to Ring 1 (or Ring 3) so the hypervisor can occupy Ring 0.
• The Gap: Seventeen sensitive x86 instructions (e.g., POPF, PUSHF, SGDT, SIDT, SLDT, SMSW, LAR, LSL) were sensitive but unprivileged:
  • When executed in user mode (Ring 1/3), they did not trap to Ring 0! Instead, they failed silently or returned the host hardware's real register values, breaking virtual machine isolation and fidelity.

CODECopy Code
+-----------------------------------------------------------------------------+
|                    THE CLASSICAL x86 PRIVILEGE RING MODEL                   |
+-----------------------------------------------------------------------------+
|                                                                             |
|                     [ Ring 3: User Applications ]                           |
|                                 |                                           |
|                     [ Ring 2: OS Services / Unused ]                        |
|                                 |                                           |
|                     [ Ring 1: Device Drivers / Paravirtualized Guest ]       |
|                                 |                                           |
|                     [ Ring 0: Host OS Kernel / Bare-Metal Hypervisor ]      |
|                                                                             |
| Problem: Ring 1 guest executing `POPF` fails silently without trapping to 0!|
+-----------------------------------------------------------------------------+

3. Hypervisor Architectures: Type-1 vs Type-2

A Hypervisor (or Virtual Machine Monitor - VMM) is the software, firmware, or hardware layer that creates, runs, and orchestrates Virtual Machines (VMs).

CODECopy Code
+-----------------------------------------------------------------------------+
|                      TYPE-1 VS TYPE-2 HYPERVISOR TAXONOMY                   |
+-----------------------------------------------------------------------------+
|                                                                             |
|     TYPE-1 (BARE-METAL / NATIVE)               TYPE-2 (HOSTED)              |
|                                                                             |
|  +-----------------------------+     +-----------------------------+        |
|  | Guest VM 1  |  Guest VM 2   |     | Guest VM 1  |  Guest VM 2   |        |
|  | (OS + Apps) |  (OS + Apps)  |     | (OS + Apps) |  (OS + Apps)  |        |
|  +-------------+---------------+     +-------------+---------------+        |
|  |     TYPE-1 HYPERVISOR       |     |     TYPE-2 HYPERVISOR       |        |
|  | (VMware ESXi, Hyper-V, Xen) |     |  (VirtualBox, Workstation)  |        |
|  +-----------------------------+     +-----------------------------+        |
|  |      RAW PHYSICAL           |     |     HOST OPERATING SYSTEM   |        |
|  |   BARE-METAL HARDWARE       |     |        (Linux, Windows)     |        |
|  |    (CPU, RAM, NIC, SAN)     |     +-----------------------------+        |
|  |                             |     |      PHYSICAL HARDWARE      |        |
|  +-----------------------------+     +-----------------------------+        |
+-----------------------------------------------------------------------------+

3.1 Architectural Comparison

4. Virtualization Implementation Techniques

To bridge the x86 virtualization gap and achieve near-native performance, computer scientists developed four major implementation paradigms:

CODECopy Code
+-----------------------------------------------------------------------------+
|                    FOUR PILLARS OF CPU VIRTUALIZATION                       |
+-----------------------------------------------------------------------------+
| 1. Full Virtualization with Binary Translation:                             |
|    Dynamic on-the-fly rewriting of sensitive guest instructions into safe   |
|    code sequences. Unmodified guest OS. (VMware 1998).                       |
|                                                                             |
| 2. Paravirtualization:                                                      |
|    Guest OS source code is modified to replace sensitive instructions with  |
|    explicit Hypercalls to the hypervisor API. (Xen 2003).                   |
|                                                                             |
| 3. Hardware-Assisted Virtualization:                                        |
|    CPU silicon extensions introduce new privilege modes:                    |
|    Intel VT-x (VMX root/non-root) & AMD-V (SVM). Guest runs unmodified.     |
|                                                                             |
| 4. Operating System-Level Virtualization (Containers):                      |
|    Single shared host kernel leveraging Linux cgroups and namespaces        |
|    to provide isolated user-space environments. (Docker, LXC).               |
+-----------------------------------------------------------------------------+

4.1 Full Virtualization via Binary Translation

• Concept: Developed by VMware in 1998. The guest operating system is completely unmodified and unaware that it is virtualized.
• Mechanism:
  • User-level guest code executes directly on the physical CPU at native speed (Direct Execution).
  • Kernel-level guest code is intercepted by the VMM. The VMM parses binary instructions dynamically in memory chunks, identifies non-virtualizable sensitive instructions, and translates them on-the-fly into safe instruction sequences or traps to the VMM (Dynamic Binary Translation).
  • Translated code blocks are cached in a Translation Cache for instant future execution.

4.2 Paravirtualization

• Concept: Pioneered by the University of Cambridge (Xen Project).
• Mechanism:
  • The guest operating system kernel is explicitly modified (ported).
  • Non-virtualizable sensitive instructions are replaced with software traps called Hypercalls (analogous to system calls, but calling from guest kernel to hypervisor).
  • Advantage: High performance; eliminates binary translation overhead.
  • Limitation: Proprietary operating systems (e.g., legacy Windows) whose source code cannot be modified could not run in paravirtualized mode.

4.3 Hardware-Assisted Virtualization

Introduced by Intel (Intel VT-x in 2005) and AMD (AMD-V in 2006) to resolve the x86 architectural virtualization gap at the silicon hardware level.

Intel VT-x Architectural Mechanisms:

1. Two New Operating Modes:
   • VMX Root Operation: Fully privileged execution mode used by the hypervisor. Rings 0 to 3 are available.
   • VMX Non-Root Operation: Execution mode used by guest software. Privileged and sensitive operations are modified so they automatically trigger a hardware trap into VMX root mode (VM Exit).
2. VM Transitions:
   • VM Entry: Hypervisor executes VMLAUNCH or VMRESUME to switch CPU context into VMX non-root mode, starting/resuming the guest VM.
   • VM Exit: Sensitive operations (e.g., executing CPUID, accessing CR3, page faults, external interrupts) trigger hardware context switch from VMX non-root back to VMX root mode.
3. Virtual Machine Control Structure (VMCS):
   • A 4 KB physical memory data structure maintained per virtual CPU.
   • Contains: Guest-State Area, Host-State Area, VM-Execution Control Fields, VM-Exit Control Fields, VM-Entry Control Fields, and VM-Exit Information Fields.

Second-Level Address Translation (SLAT) / Hardware Memory Virtualization:

• In pure software paging, hypervisors maintained complex Shadow Page Tables to map guest virtual addresses directly to host physical addresses, causing frequent page fault VM exits.
• SLAT moves two-dimensional page translation directly into MMU silicon:
  • Intel EPT (Extended Page Tables) & AMD NPT (Nested Page Tables).
  • Guest OS manages Guest Virtual to Guest Physical translation; hardware EPT automatically translates Guest Physical to Host Physical addresses in hardware without triggering VM Exits.

CODECopy Code
+-----------------------------------------------------------------------------+
|                       TWO-DIMENSIONAL EPT PAGING WALK                       |
+-----------------------------------------------------------------------------+
| Guest Virtual Address (GVA)                                                 |
|          |                                                                  |
|          v (Guest Page Table Walk)                                          |
| Guest Physical Address (GPA)                                                |
|          |                                                                  |
|          v (Hardware EPT Page Table Walk - In Silicon MMU)                  |
| Host Physical Address (HPA) ---> [ Physical RAM Frame Access ]              |
+-----------------------------------------------------------------------------+

5. Types of Virtualization

Virtualization abstractions extend across all computational tiers:

CODECopy Code
+-----------------------------------------------------------------------------+
|                         VIRTUALIZATION TAXONOMY                             |
+-----------------------------------------------------------------------------+
| 1. Server Virtualization  : Partitioning 1 physical server into multiple VMs|
| 2. Storage Virtualization : Aggregating physical disks into logical pools   |
| 3. Network Virtualization : Decoupling network services from underlying wire|
| 4. Desktop Virtualization : Hosting client desktops on centralized servers  |
| 5. App Virtualization     : Encapsulating applications from underlying OS   |
+-----------------------------------------------------------------------------+

5.1 Storage Virtualization

• Block-Level Virtualization: Operates between storage devices and hosts (e.g., Storage Area Networks - SAN). Multiple physical storage arrays are pooled into logical units (LUNs) presented to servers. Features include thin provisioning, volume mirroring, and dynamic resizing.
• File-Level Virtualization: Operates at the file system level (Network Attached Storage - NAS), abstracting file paths and CIFS/NFS shares across disparate storage appliances.
• Virtual SAN (vSAN): Software-defined storage clustering local server SSDs/HDDs into a shared enterprise datastore.

5.2 Network Virtualization & Software-Defined Networking (SDN)

• VLAN (Virtual Local Area Network): IEEE 802.1Q standard tagging packets with a 12-bit VLAN ID (supporting up to 4,094 logical isolated broadcast domains on shared physical switches).
• VXLAN (Virtual Extensible LAN): Overcomes VLAN scalability limits by encapsulating Layer 2 Ethernet frames inside Layer 4 UDP packets with a 24-bit Virtual Network Identifier (VNI), supporting up to 16 million isolated virtual networks across Layer 3 clouds.
• Software-Defined Networking (SDN):
  • Decouples the Control Plane (network routing decisions, policy enforcement) from the Data Plane (packet forwarding hardware).
  • OpenFlow protocol enables centralized controllers to dynamically inject forwarding flow rules into distributed virtual switches (e.g., Open vSwitch - OVS).

5.3 Desktop Virtualization (VDI)

• Virtual Desktop Infrastructure (VDI): User desktop environments are hosted as virtual machines on data center servers. Users access their desktops over local networks or the Internet via remote display protocols (RDP, PCoIP, Citrix HDX).
• Centralizes security, backups, patch management, and endpoint compliance.

6. Containers vs Virtual Machines

Operating System-Level Virtualization (Containerization) abstracts the user space rather than physical hardware.

CODECopy Code
+-----------------------------------------------------------------------------+
|                  VIRTUAL MACHINES VS CONTAINER ARCHITECTURE                 |
+-----------------------------------------------------------------------------+
|                                                                             |
|          VIRTUAL MACHINES                           CONTAINERS              |
|  +-----------------------------+          +-----------------------------+   |
|  |   App A     |    App B      |          |   App A     |    App B      |   |
|  +-------------+---------------+          +-------------+---------------+   |
|  | Bins / Libs | Bins / Libs   |          | Bins / Libs | Bins / Libs   |   |
|  +-------------+---------------+          +-------------+---------------+   |
|  | Guest OS A  | Guest OS B    |          |      CONTAINER ENGINE       |   |
|  | (Full Linux)| (Full Windows)|          |    (Docker, containerd)     |   |
|  +-------------+---------------+          +-----------------------------+   |
|  |      HYPERVISOR             |          |     SHARED HOST KERNEL      |   |
|  | (ESXi, KVM, Hyper-V)        |          |  (cgroups, namespaces, etc.)|   |
|  +-----------------------------+          +-----------------------------+   |
|  |     PHYSICAL HARDWARE       |          |     PHYSICAL HARDWARE       |   |
|  +-----------------------------+          +-----------------------------+   |
+-----------------------------------------------------------------------------+

6.1 Architectural Comparison

6.2 Core Linux Kernel Technologies Powering Containers

1. Linux Namespaces (Isolation):
   • pid: Process IDs (Container sees its main process as PID 1).
   • net: Network interfaces, IP routing tables, port bindings.
   • mnt: Mount points and file system root isolation (pivot_root).
   • ipc: System V IPC and POSIX message queues.
   • uts: Hostname and NIS domain name isolation.
   • user: User and Group ID mappings (root inside container maps to unprivileged UID on host).
2. Control Groups (cgroups - Resource Governance):
   • Enforces hard limits, prioritization, and accounting on physical hardware consumption: CPU shares/bandwidth, memory limits, blkio (disk I/O throughput), and network traffic.

7. Virtual Machine Management & Live Migration

7.1 Virtual Machine Lifecycle

The lifecycle of a virtual machine spans: Provisioning -> Configuration -> Running -> Paused/Suspended -> Snapshotting -> Live Migration -> Decommissioning.

• VM Snapshot: Captures the exact point-in-time state of a VM, including virtual disk blocks (via copy-on-write delta files), RAM contents, and virtual device configuration.

7.2 Live Migration Techniques

Live Migration is the process of moving a running virtual machine from one physical host server to another without interrupting active network connections or end-user transactions.

CODECopy Code
+-----------------------------------------------------------------------------+
|                     PRE-COPY LIVE MIGRATION WORKFLOW                        |
+-----------------------------------------------------------------------------+
| Stage 1: Pre-Migration Setup (Target host verifies resources).              |
| Stage 2: Reservation (Target host allocates CPU, RAM, VM container).        |
| Stage 3: Iterative Pre-Copy:                                                |
|          - Round 0: Copy all physical memory pages from Source to Target.   |
|          - While memory is copying, Guest VM continues writing to RAM!      |
|          - Hypervisor tracks modified pages using a Dirty Bitmap.           |
|          - Round 1..n: Re-transmit only dirty pages. Stop when delta small.|
| Stage 4: Stop-and-Copy (Downtime phase - typically < 50 ms):               |
|          - Suspend VM on Source host.                                       |
|          - Transfer final residual dirty pages and CPU registers (VCPU).    |
| Stage 5: Resume on Target & Gratuitous ARP:                                 |
|          - Target resumes VM from exact register state.                     |
|          - Broadcasts Gratuitous ARP to switch so network switches re-route |
|            packets to target host's physical switch port immediately.       |
+-----------------------------------------------------------------------------+

7.3 Resource Overcommitment Mechanisms

Hypervisors allow the sum of configured VM resources to exceed physical hardware capacity:

1. CPU Oversubscription: Allocates more virtual CPUs (vCPUs) than physical cores, relying on CPU scheduling algorithms.
2. Memory Ballooning: A pseudo-device driver installed inside the guest OS. When the host runs low on memory, it inflates the balloon driver inside a guest; the guest OS pages out user applications to satisfy the balloon's demand, allowing the hypervisor to reclaim physical frames.
3. Transparent Page Sharing (TPS): Identifies identical physical memory pages (e.g., redundant Windows OS pages) across different VMs and coalesces them into a single read-only physical frame using copy-on-write.