XMBSMDSJ

2026

< Back to index

Revision

History of Cloud Computing

Parallelization (L3)

Computation Scaling Up

Amdahl’s Law

$T(1) = \sigma + \pi$

$T(N) = \sigma + \frac{\pi}{N}$

$S = \frac{T(1)}{T(N)} \approx \frac{1}{\alpha}$

This over simplifies the problem, because the overhead replicates in parallelization

Gustafson-Barsis’s Law

$T(1) = \sigma + N\pi$ $T(N) = \sigma + \pi$

where $\pi$ is fixed parallel time per process and $\alpha$ is fraction of running time sequential program spends on parallel part $\frac{\pi}{\sigma} = \frac{1-\alpha}{\alpha}$

$S(N) = \alpha + N(1-\alpha) = N - \alpha(N-1)$

Computer Architectures

Types of parallelisms

Implicit parallelism means parallel languages and parallelizing compilers that take care of identifying parallelism, the scheduling of calculations and placement of data. This is quite hard to do though.

Explicit parallelism requires the programmer to take effort of parallelization, like mapping tasks to processors and inter-process communications. This approach assumes user is the best judge of how parallism can be exploited for a particular application.

Hardware parallelism level

In hardware threading CPU, extra control units are added to allow more instructions to be processed per cycle. They usually share arithmetic units, so heavy use of one type of computation can tie up the available units of the CPU preventing other threads from using them.

Multi-core CPU can perform computational tasks in parallel in principle. The Control units have indenpendant arithmatic units but share cache.

Symmetric Multiprocessing means two or more identical processors connected to a single shared main memory, with full access to all I/O devices, controlled by a single OS that treats all processors equally. It’s more complex to program since need to program both CPUs and inter-processor communications.

Non-Uniform Memory Access provides speed up by allowing a processor to access its local memory faster than non-local memory. As long as data are localized, performance is improved.

Software Parallelism Approaches

Most languages support parallelization features like Threads, Pools, Lock, Semaphores. There are some key issues that need to be tackled. Deadlock (Process constantly wait for each other), Livelock (Processes involved in livelock constantly change with regard to one another, but none are progressing)

Message passing interface (MPI) is widely adoped approach for message passing in parallel system. Key MPI functions include MPI_Init, MPI_Finalize, MPI_COMM_SIZE, MPI_COMM_RANK, MPI_SEND, MPI_RECV, … It supports both point to point and broadcast communications.

(HT)Condor It is a specialized workload management system for compute-intensive jobs. It offers job queueing mechanisms, scheduling policies, priority schemes, resource monitoring/management. Users submit jobs to Condor and it chooses when and where to run the job, monitors their progress and informs the user upon completion. There no need for shared file system across machines, data can be staged to machines as needed.

Facts about Distributed Systems

How to design a parallel system?

In master-slave model, master decomposes the problem into small tasks and distributes to workers and gather partial results to produce final result.

Shared memory parallelism (MP)

Multi-threading is one type of shared memory parallelism. A master forks a number of sub threads and diveide tasks between them. One implementation is OpenMP, which is limited to single instance.

Distributed memory parallelism (MPI)

Programs are parallelized by sending messages between processes. Some functions in MPI are:

Parallism Patterns

Cluster Computing (L4)

Concepts

Supercomputer is a single computer system that has exceptiona; processing power for its time. One metric is the number of floating-point operation per second (FLOPS).

High-performance computing (HPC) is any computer system whose architecture allows for above average performance.

Clustered computing is when two or more computers servce a single resource (improved performance and redundancy). A collection of smaller computers strapped together with a high-speed local network.

Research computing is the software application used by research comminity to aod research. THis skill gap is a major problem and must be addresed because as datasets grow, the researchers will need to able to process the data.

HPC

The HPC cluster architecture is like this Queueing system and scheduler are placed at management node whiel user access are via logon node.

Supercomputers use Linux because:

Cloud (L5)

Definition

Cloud computing is a model for enabling ubiqutous convenient, on demand network access to a pool of configurable computing resources that can be repidly provisioned and released with minimal management effort and provider interaction. Cloud computing has following characteristics:

How to attach a volume

Public cloud

Pros:

Cons

Private cloud

Pros:

Cons:

Hybrid Cloud

Pros:

Cons:

Automation

Web Service (L6)

SOA (Service-Oriented Architecture)

Design principles:

SOAP vs ReST

SOAP ReST
Built upon RPC About resources and the way they can be manipulated remotely
Stack of protocols that covers every aspect of using a remote service A style of using HTTP

WSDL (Web service description language)

ReST design best practice

ReST principles

Uniform interface

HATEOAS (Hyper Media As the Engine of App)

ReST 2.0

Safe/Idempotent methods

A method is safe if does not change anything. (N calls == 0 call). A method is idempotent if (N calls = 0 call)

Method Safety
GET, OPTION, HEAD Safe
PUT, DELETE Idempotent
POST Neither

Virtualization vs Containerization

Virtualization has advantages like containment and horizontal scalability, but requires more resources. Guest OS and binaries might be duplicated, wasting resources.

Containerization allows virtual instances to share a single host OS, binaries, drivers and libraries to reduce waste.

Paraleter VM Container
Guest OS Has their own kernel Share same kernel
Comm Eth Pipes, sockets
Security Depends on Hypervisor Requires close scrutiny
Performance Small overhead when translating instructions Near native
Isolation FS and lib not shared Shared lib, fs can be shared
Startup Slow Fast
Storage Large Small

Container Orchestration

Manage containers at scale

Features:

Goals

Docker

It uses resource isolation features of Linux Kernel to allow independent containers to run within a single Linux instance. Can also be installed on Macos and windows, integrated with Hypervisor in maxOS and Hyper-V in windows.

Data can be persisted when container is deleted using docker volumes or bind mounts. Docker volumes are managed by docker, in /var/lib/docker/volumes, while bindmount is managed by user.

Big Data (L7)

4 Vs

Why use document-oriented DBMS for big data?

Relational database model implied fine-grained data, which are less conductive to partition-tolerance than coarse-grained data.

MongoDB vs CouchDB

CouchDB cluster is simpler, more available. Accepts HTTP requests. All the nodes accept requests. If data unavailable, it fetch from other node and return to user.

CouchDB cluster uses MVCC, while MongoDB uses a mix of two-phase commit for consistency and Paxos-like algorithm for leader election.

When a CouchDB cluster is partitioned and two nodes receive two different updates of the same document, two different revisions are added. However, only one of these is returned as the current version.

CouchDB Architecture

When partitioning happens in MongoDB which separate a primary into a partition with a minority of nodes, when primary detects that it can only see a minority of nodes, it steps down and a members in majority oartition holds election to become the new primary

MongoDB clusters are more complex, more consistent and less available. The sharding is on the replicaset level. Routers must be embedded in application servers. Only master node accept queries (depending on configurations)

MongoDB Architecture

CouchDB Views

CAP theorem

Consistency and availability are at odds when a Partition happens. Traditional databasrs are not concerned with network partitions, since all data were supposed to be in a small co-located cluster of servers.

Consistency and Availability: Two-phase commit It enforces consistency by:

Commit request phase:

Commit phase: The commit is success if all participants agree to commit. It fails if any of them vote “No”.

Availability and Partition Tolerance: MVCC

Consistency and Partition Tolerance: Paxos

Paxos ensures no matter what if data is written, it eventually propagate to all nodes. There will never be different nodes that think that some index contains different value.

Some assumptions:

Building blocks

The alg orithm overview

Big data processing (L8)

Challenges of big data analysis:

Hadoop

Hadoop HDFS uses 128MB block for smaller metadata, higher network efficiency and reduce need for seek operation. It is quite efficient when most data of a block is processed.

Hadoop uses YARN (Yet Another Resource Negotiator). Resource Manger is located on master node while Node Managers are on slave nodes. Everytime a MR job is initiated, an Application Master is started to negotiate resource with Resource Manager and start containers on slave node.

YARN core components:

Spark

Why Spark?

Spark components

Spark RDD (Resilient Distributed Dataset). Resilient means Data is stored with redundancy. Failing node does not effect integrity. It has following properties

Some RDD Transformations:

Key-value Transormations

Actions (Evaluation happens)

Virtualization (L9)

VMM or Hypervisor is a piece of software that provide the abstraction of a virtual machine. When looking at the virtual environment provided by VMM, there are three properties of interest:

Popek and Goldberg describe characteristics that ISA (Instruction Set Architecture) of physical machine must possess to run VMM with 3 properties above. There is a classification of instructions of an ISO into 3 different groups:

Theorem

For any conventional third-gen computer, an effective VMM may be constructed if the set of sensitive instruction for that computer is a subset of the set of privileged instructions.

This indicates that in order to build a VMM it is sufficient that all instructions that could affect the correct functioning of the VMM always trap and pass control to the VMM. This guarantees the resource control property. None privileged instructions must instead be executed natively.

This theorem also provides a simple technique for implementing a VMM, called trap-and-emulate virtualization, more recently called classic virtualization: because all sensitive instructions behave nicely, all the VMM has to do is trap and emulate every one of them

Virtual machine extensions

x86 is not originally virtualizable. VT-x (Intel) and SVM (AMD) are introduced to satisfy popek-goldberg theorem permit entering/exiting virtual execution mode where guestOS perceives itself as running with full privilege, but host OS remains protected.

VMM should support following features:

Full virtualization vs Para-virtualization

Full virtualization allow na unmodified guest OS to run in isolation by simulating full hardware. Guest OS has no idea it is virtualized.

With Para-virtualization, VMM exposes special interfaces to guest OS for better performance. It requires a modified/hypervisor aware Guest OS (Xen). This can optimise systems to use this interface since not all instructions need to be trapped/dealt with

Software based virtualization vs Hardware assisted virtualization

In software based (CPU) virtualization, Guest application code runs directly on CPU. Privileged codes are translated to run on CPU. Translated codes are larger and slightly slower.

In hardware assisted virtualization, the processor provides hardware assistant for CPU virtualization. Guests can use a separated mode called Guest Mode (Both applications and privileged codes are running in guest mode). On certain events, the processor exit guest mode and enter root mode. Hypervisor executes in root mode, determing reason for exit and restart guest in guest mode. With hardware assist, system calls and trap intensive workloads run close to native performance. Tasks that lead to large number of exitting guest mode may affect the performance.

Openstack Services (L9.2)

Security (L12)

Motivations and challenges

Why Security? Otherwise

Challenges of security

Technical Challenges of Security

Single Sign-on

Certification Authority (CA) has following responsibilities:

To issue a certificate

Exam Questions

Erroneous assumptions made in designing large-scale distributed system

Cloud computing do not solve many key challenges of large scale distributed systems

transmissions from the membrane between flesh and silicon