Soma-notes - User contributions [en]

DistOS 2015W Session 12

2015-04-20T14:23:41Z

Jasons: /* Comet */

* [http://static.usenix.org/legacy/events/osdi10/tech/full_papers/Beaver.pdf Beaver et al., "Finding a needle in Haystack: Facebook’s photo storage" (OSDI 2010)]
* [https://www.usenix.org/conference/osdi12/technical-sessions/presentation/gordon Gordon et al., "COMET: Code Offload by Migrating Execution Transparently" (OSDI 2012)]
* [https://www.usenix.org/conference/osdi14/technical-sessions/presentation/muralidhar Muralidhar et al., "f4: Facebook's Warm BLOB Storage System" (OSDI 2014)]
* [https://www.usenix.org/conference/osdi14/technical-sessions/presentation/zhang Zhang et al., "Customizable and Extensible Deployment for Mobile/Cloud Applications" (OSDI 2014)]

Session 12 had two separate themes running through their papers.

The first was the storage of large volumes of data that would never be modified, rarely be deleted, and read with varying frequency distributions. This was a specific sub problem of the more general challenge of high performance scalable & reliable distributed storage, and once more leads the solvers at hand (Facebook) to design specialized systems to the exploit the specifics of the sub problem for superior performance.

The second was a return to code offloading mechanisms that could turn programs distributed, in a new modern context. COMET works by taking existing smartphone applications and splicing the user interaction and computation between the phone and an external server. Sapphire provides a whole cluster of deployment modules that one can mix & match and apply to conformant programs to turn them into distributed applications.

=Haystack=
* Facebook's Photo Application Storage System.
* Previous Fb photo storage based on NFS design. The reason why NFS didn't work is that it took 3 file-system accesses per logical photo read. Haystack only needs one access.
*Main goals of Haystack:
** High throughput with low latency. It uses one disk operation to provide these.
**Fault tolerance
**Cost effective
**Simple
*Facebook stored all images in haystack with a CDN in front to cache hot data. Haystack still needs to be fast since accessing non-cached data is still common.
*Haystack reduces the memory used for ''filesystem metadata''
*It has 2 types of metadata:
**''Application metadata''
**''File System metadata''
* The architecture consists of 3 components:
**Haystack Store
**Haystack Directory
**Haystack Cache
*Pitchfork and bulk sync were used to tolerate faults. theTfault tolerance works in a very profound way to make haystack feasible and reliable

=Comet=
*Introduced the concept of distributed shared memory (DSM). In a DSM, RAMs from multiple servers would appear as if they are all belonging to one server, allowing better scalability for caching.
*DSM provides advatage over RPC(Remote Procedure Call) including multi threading suuport, thread migration during execution.
*client and server model maintain consistency using DSM
*Comet model works by offloading the computation intensive process from the mobile to only one server.
*The offloading process works by passing the computation intensive process to the server and hold it on the mobile device. Once the process on the server completes, it returns the results and the handle back to the mobile device. In other words, the process does not get physically offloaded to the server but instead it runs on the server and stopped on the mobile device.
*In Java Memory Model, memory reads and writes are partially ordered by a transitive "happens-before" relationship.
**Java Virtual Machine can keep track of data flow which DSM use to keep the heap, stacks, and locking states consistent across endpoints.

=F4=
* Warm Blob Storage System.
** Warm Blob is a store for large quantities of immutable data that isn't frequently accessed, but must still be available.
** Built to reduce the overhead of haystack for old data that doesn't need to be quite as available. Generally data that is a few months old is moved from Haystack to Warm Blob.
** F4 reduce the space usage of Haystack from a replication factor of 3.6 to 2.8 or 2.1 using Reed Solomon coding and XOR coding respectively but still provides consistency.
** Less robust to data center failures as a result.
*Reed Solomon coding basically use(10,4) which means 10 data and 4 parity blocks in a stripe, and can thus tolerate losing up to 4 blocks which means it can tolerate 4 rack failure and use 1.4 expansion factor.Two copies of this would be 2* 1.4= 2.8 effective replication factor.
*XOR coding use(2,1) across three data center and use 1.5 expansion factor which gives 1.5*1.4= 2.1 effective replication factor.
*The caching mechanism provides the reduction in load on storage system and it makes BLOB scaleable.

=Sapphire=
*Represents a building block towards building this global distributed systems. The main critique to it is that it didn’t present a specific use case upon which their design is built upon.
*Sapphire does not show their scalability boundaries. There is no such distributed system model that can be “one size fits all”, most probably it will break in some large scale distributed application.
*Reaching this global distributed system that address all the distributed OS use cases will be a cumulative work of many big bodies and building it block by block and then this system will evolve by putting all these different building blocks together. In other words, reaching a global distributed system will come from a “bottom up not top down approach” [Somayaji, 2015].
*The concept of separate application logic from deployment logic helps programmers in making a flexible system. The other important part that makes it as a scalable system was that it is object based and could be integrated with any object oriented language.

DistOS 2015W Session 10

2015-04-20T14:13:20Z

Jasons:

* [http://en.wikipedia.org/wiki/Distributed_hash_table Wikipedia's article on Distributed Hash Tables]
* [http://en.wikipedia.org/wiki/Kademlia Wikipedia's article on Kademlia]
* [http://pdos.csail.mit.edu/~petar/papers/maymounkov-kademlia-lncs.pdf Maymounkov and Mazieres, "Kademlia: A Peer-to-peer information system based on the XOR Metric" (2002)]
* [http://en.wikipedia.org/wiki/Tapestry_%28DHT%29 Wikipedia's article on Tapestry]
* [http://pdos.csail.mit.edu/~strib/docs/tapestry/tapestry_jsac03.pdf Zhao et al, "Tapestry: A Resilient Global-Scale Overlay for Service Deployment" (JSAC 2003)]
* [https://www.usenix.org/legacy/event/osdi10/tech/full_papers/Geambasu.pdf Geambasu et al., "Comet: An active distributed key-value store" (OSDI 2010)]

Session 10 is about Distributed Hash Tables. How they work, various algorithmic options (keyspace partitioning being a major example) and some of the earliest implementations.

(Feel free to tweak the questions!)

==Kademlia==
Members: Kirill, Deep, Jason, Hassan

* '''Why are DHTs relevant to distributed OSs?'''
** Using many system, having repetition
** DHT to distributed content over multiple nodes
** Decentralized therefore peer-to-peer

* '''How is content divided?'''
** File hashes
** Node ID to locate the value
** 160 bit key space, binary tree for partition and searching down the tree

* '''How is the network traversed?'''
** Highest prefix and increase the number of digit it used to get close to the target nodes

* '''What trust assumptions does the system make?'''
** DHT by itself is insecure
** The academic and practitioner communities have realized that all current DHT designs suffer from a security weakness, known as the Sybil attack
** K-buckets
*** Binary tree with each node having k-buckets as leaf
*** Any given k-node is very unlikely to fail within an hour of each other
*** New nodes are only inserted when there is room in the bucket or the oldest node doesn't respond
** Uses UDP therefore packets are often lost

* '''Performance constraints?'''
** Binary tree traversing, therefore traversing is maximum O(log n)

* '''What non-DHT internet infrastructure would you replace with a DHT? How suitable is Kademlia for this purpose?'''
** DNS
** Any kind of meta-data service

==Comet==
Members: Mohamed Ahmed, Apoorv Sangal, Ambalica Sharma

* Why are DHTs relevant to distributed OSs?
DHT is an infrastructure than enables many clients to share information, and scale to handle node arrival, departure and failure. DHT's serve many of the design goals of disbtributed operating systems. The paper states that "DHTs are increasingly used to support a variety of distributed applications, such as file-sharing, distributed resource tracking, end-system multicast, publish-subscribe systems, distributed search engines"

* How is content divided?
One of the three main components of the comet system is a routing substrate which
implements the value/node mapping. This allows a client to find the node htat stores
a specific data item. Since Comet uses a DHT implementation, routing occurs by applying
a hash function to the key to compute node ID's that store the associated value.

* How is the network traversed?

* What trust assumptions does the system make?
Assumes clients re untrusted autonomous nodes.

A client node running Comet should be protected from the execution of handlers
e.g. an executing handler cannot corrupt the node or use unlimited resources.
Handlers should not be able to mount messaging attacks on other nodes.

Users downloading Comet must trust it and have guarantees about its behavior. For this reason, Comet enforces four important restrictions:
1. Limited knowledge: an ASO is not aware of other objects
or resources stored on the same node and has no
direct way to learn about them.
2. Limited access: an object handler can manipulate only its own value and cannot modify the values of other objects on its storage node.
3. Limited communication: an active storage object cannot
send arbitrary messages over the network.
4. Limited resource consumption: an ASO’s resource usage is strictly bounded, e.g., the system limits the amount of computation and memory it can consume.

* Performance constraints?

* What non-DHT internet infrastructure would you replace with a DHT? How suitable is Comet for this purpose?

==Tapestry==
Members: Ashley, Dany, Alexis, Khaled

* Why are DHTs relevant to distributed OSs?

Because they provide a way to distribute information over large networks (distributed key/value store).

* How is content divided?

Uses consistent hashing (SHA-1), upon node creation (join) creates optimal routing table.

* How is the network traversed?

You look at your neighbours, you see which neighbour is closest to your destination, and recurse.

* What trust assumptions does the system make?

It assumes the system is entirely trustworthy from adversaries. While network failures may happen and nodes may go down, no node will explicitly try to mess with the network.

* Performance constraints?

O(log n) access times to any given node. Best effort publishing/unpublishing via decentralized object location routing.

* What non-DHT internet infrastructure would you replace with a DHT? How suitable is Tapestry for this purpose?

== DHT Discussion ==
* DHT is weak against mutation
* performance - high variance
** hop vs direct connection
*DHT as DNS server
**DHT have no ownership/authority
*DHT as web hosting server
** ok for static content but not good for dynamic content which might have private data

== Other Resources ==
*[http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1610546&tag=1 A survey and comparison of peer-to-peer overlay network schemes]
*[http://link.springer.com/article/10.1007/s12083-012-0157-3 Collaborative Applications over Peer-to-Peer Systems – Challenges and Solutions]

DistOS 2015W Session 8

2015-04-20T10:24:56Z

Jasons: /* WEB */

* The link to Vannevar Bush’s article, “As we may think” http://www.theatlantic.com/magazine/archive/1945/07/as-we-may-think/303881/

* How both the article and the video relates to the course?
The creation of the Web is basically what drove the need to have a way of connecting thousands of machines and develop a mechanism between these machines to share files and data in an efficient way. In other words, the Science of Distributed Operating Systems has evolved as a result of the creation of the Web and it’s exponential growth.

*OS is made to run program
**example:
**Mac OS - GUI
**UNIX - text processing, shell pipe

== WEB ==

*Web is not tied to fixed interface
**interface is flexible
**different type of content, text, image, video, file, dynamic, static, are presented different way
**website have one to many viewers.

*stateless
**allows scalability
**server does not keep state of client
**the disadvantage of stateful server is the cost of coordination between servers for state of clients

DistOS 2015W Session 8

2015-04-20T10:19:49Z

Jasons:

* The link to Vannevar Bush’s article, “As we may think” http://www.theatlantic.com/magazine/archive/1945/07/as-we-may-think/303881/

* How both the article and the video relates to the course?
The creation of the Web is basically what drove the need to have a way of connecting thousands of machines and develop a mechanism between these machines to share files and data in an efficient way. In other words, the Science of Distributed Operating Systems has evolved as a result of the creation of the Web and it’s exponential growth.

*OS is made to run program
**example:
**Mac OS - GUI
**UNIX - text processing, shell pipe

== WEB ==

*Web is not tied to fixed interface
**interface is flexible
**website have 1 to many viewers.

*stateless
**allows scalability
**server does not keep state of client
**the disadvantage of stateful server is the cost of coordination between servers for state of clients

DistOS 2015W Session 7

2015-04-20T10:12:24Z

Jasons: /* Key Features */

= Ceph =
Unlike GFS that was talked about previously, this is a general purpose distributed file system (for various file size, from small to large). It follows the same general model of distribution as GFS and Amoeba.

HOW IT WORKS
Ceph file system runs on top of the same object storage system that provides object storage and block device interfaces. The Ceph metadata server cluster provides a service that maps the directories and filenames of the file system to objects stored within RADOS clusters. The metadata server cluster can expand or contract, and it can rebalance the file system dynamically to distribute data evenly among cluster hosts. This ensures high performance and prevents heavy loads on specific hosts within the cluster.

BENEFITS
The Ceph file system provides numerous benefits:
It provides stronger data safety for mission-critical applications.
It provides virtually unlimited storage to file systems.
Applications that use file systems can use Ceph FS with POSIX semantics. No integration or customization required!
Ceph automatically balances the file system to deliver maximum performance.

== Advantages of using File systems ==
* It supports heterogeneous operating systems including all flavors of the unix operating system as well as Linux and windows
* Multiple client machines can access a single resource simultaneously.
enables sharing common application binaries and read only information instead of putting them on each single machine. This results in reduced overall disk storage cost and administration overhead.
*Gives access to uniform data to groups of users.
*Useful when many users exists on many systems with each user's home directory located on every single machine. Network file systems allows you to all users home directories on a single machine under /home

== Main Components ==
* Client

* Cluster of Object Storage Devices (OSD)
** It basically stores data and metadata and clients communicate directly with it to perform IO operations
** Data is stored in objects (variable size chunks)

* Meta-data Server (MDS)
** It is used to manage the file and directories. Clients interact with it to perform metadata operations like open, rename. It manages the capabilities of a client.
** Clients '''do not''' need to access MDSs to find where data is stored, improving scalability (more on that below)

== Key Features ==
* Decoupled data and metadata
** good for scalability of various file size, from small to large

* Dynamic Distributed Metadata Management

** It distributes the metadata among multiple metadata servers using dynamic sub-tree partitioning, meaning folders that get used more often get their meta-data replicated to more servers, spreading the load. This happens completely automatically

* Object based storage
** Uses cluster of OSDs to form a Reliable Autonomic Distributed Object-Store (RADOS) for Ceph failure detection and recovery

* CRUSH (Controlled, Replicated, Under Scalable, Hashing)
** The hashing algorithm used to calculate the location of object instead of looking for them
** This significantly reduces the load on the MDSs because each client has enough information to independently determine where things should be located.
** Responsible for automatically moving data when ODSs are added or removed (can be simplified as ''location = CRUSH(filename) % num_servers'')
** The CRUSH paper on Ceph’s website can be [http://ceph.com/papers/weil-crush-sc06.pdf viewed here]

* RADOS (Reliable Autonomic Distributed Object-Store) is the object store for Ceph

= Chubby =
It is a coarse grained lock service, made and used internally by Google, that serves multiple clients with small number of servers (chubby cell).

Chubby was designed to be a lock service, a distributed system that clients could connect to and share access to small files. The servers providing the system are partitioned into a variety of cells and access for a particular file is managed through one elected master node in one cell. This master makes all decisions and informs the rest of the cell nodes of that decision. If the master fails, the other nodes elect a new master. The problem of asynchronous consensus is solved through the use of timeouts as a failure detector. To avoid the scaling problem of a single bottleneck, the number of cells can be increased with the cost of making some cells smaller.

== System Components ==
* Chubby Cell
** Handles the actual locks
** Mainly consists of 5 servers known as replicas
** Consensus protocol ([https://en.wikipedia.org/wiki/Paxos_(computer_science) Paxos]) is used to elect the master from replicas

* Client
** Used by programs to request and use locks

== Main Features ==
* Implemented as a semi POSIX-compliant file-system with a 256KB file limit
** Permissions are for files only, not folders, thus breaking some compatibility
** Trivial to use by programs; just use the standard ''fopen()'' family of calls

* Uses consensus algorithm (paxos) among a set of servers to agree on who is the master that is in charge of the metadata

* Meant for locks that last hours or days, not seconds (thus, "coarse grained")

* A master server can handle tens of thousands of simultaneous connections
** This can be further improved by using caching servers as most of the traffic are keep-alive messages

* Used by GFS for electing master server

* Also used by Google as a nameserver

== Issues ==
* Due to the use of Paxos (the only algorithm for this problem), the chubby cell is limited to only 5 servers. While this limits fault-tolerance, in practice this is more than enough.
* Since it has a file-system client interface, many programmers tend to abuse the system and need education (even inside Google)
* Clients need to constantly ping Chubby to verify that they still exist. This is to ensure that a server disappearing while holding a lock does not indefinitely hold that lock.
* Clients must also consequently re-verify that they hold a lock that they think they hold because Chubby may have timed them out.

DistOS 2015W Session 7

2015-04-20T10:07:40Z

Jasons: /* Ceph */

= Ceph =
Unlike GFS that was talked about previously, this is a general purpose distributed file system (for various file size, from small to large). It follows the same general model of distribution as GFS and Amoeba.

HOW IT WORKS
Ceph file system runs on top of the same object storage system that provides object storage and block device interfaces. The Ceph metadata server cluster provides a service that maps the directories and filenames of the file system to objects stored within RADOS clusters. The metadata server cluster can expand or contract, and it can rebalance the file system dynamically to distribute data evenly among cluster hosts. This ensures high performance and prevents heavy loads on specific hosts within the cluster.

BENEFITS
The Ceph file system provides numerous benefits:
It provides stronger data safety for mission-critical applications.
It provides virtually unlimited storage to file systems.
Applications that use file systems can use Ceph FS with POSIX semantics. No integration or customization required!
Ceph automatically balances the file system to deliver maximum performance.

== Advantages of using File systems ==
* It supports heterogeneous operating systems including all flavors of the unix operating system as well as Linux and windows
* Multiple client machines can access a single resource simultaneously.
enables sharing common application binaries and read only information instead of putting them on each single machine. This results in reduced overall disk storage cost and administration overhead.
*Gives access to uniform data to groups of users.
*Useful when many users exists on many systems with each user's home directory located on every single machine. Network file systems allows you to all users home directories on a single machine under /home

== Main Components ==
* Client

* Cluster of Object Storage Devices (OSD)
** It basically stores data and metadata and clients communicate directly with it to perform IO operations
** Data is stored in objects (variable size chunks)

* Meta-data Server (MDS)
** It is used to manage the file and directories. Clients interact with it to perform metadata operations like open, rename. It manages the capabilities of a client.
** Clients '''do not''' need to access MDSs to find where data is stored, improving scalability (more on that below)

== Key Features ==
* Decoupled data and metadata

* Dynamic Distributed Metadata Management

** It distributes the metadata among multiple metadata servers using dynamic sub-tree partitioning, meaning folders that get used more often get their meta-data replicated to more servers, spreading the load. This happens completely automatically

* Object based storage
** Uses cluster of OSDs to form a Reliable Autonomic Distributed Object-Store (RADOS) for Ceph failure detection and recovery

* CRUSH (Controlled, Replicated, Under Scalable, Hashing)
** The hashing algorithm used to calculate the location of object instead of looking for them
** This significantly reduces the load on the MDSs because each client has enough information to independently determine where things should be located.
** Responsible for automatically moving data when ODSs are added or removed (can be simplified as ''location = CRUSH(filename) % num_servers'')
** The CRUSH paper on Ceph’s website can be [http://ceph.com/papers/weil-crush-sc06.pdf viewed here]

* RADOS (Reliable Autonomic Distributed Object-Store) is the object store for Ceph

= Chubby =
It is a coarse grained lock service, made and used internally by Google, that serves multiple clients with small number of servers (chubby cell).

Chubby was designed to be a lock service, a distributed system that clients could connect to and share access to small files. The servers providing the system are partitioned into a variety of cells and access for a particular file is managed through one elected master node in one cell. This master makes all decisions and informs the rest of the cell nodes of that decision. If the master fails, the other nodes elect a new master. The problem of asynchronous consensus is solved through the use of timeouts as a failure detector. To avoid the scaling problem of a single bottleneck, the number of cells can be increased with the cost of making some cells smaller.

== System Components ==
* Chubby Cell
** Handles the actual locks
** Mainly consists of 5 servers known as replicas
** Consensus protocol ([https://en.wikipedia.org/wiki/Paxos_(computer_science) Paxos]) is used to elect the master from replicas

* Client
** Used by programs to request and use locks

== Main Features ==
* Implemented as a semi POSIX-compliant file-system with a 256KB file limit
** Permissions are for files only, not folders, thus breaking some compatibility
** Trivial to use by programs; just use the standard ''fopen()'' family of calls

* Uses consensus algorithm (paxos) among a set of servers to agree on who is the master that is in charge of the metadata

* Meant for locks that last hours or days, not seconds (thus, "coarse grained")

* A master server can handle tens of thousands of simultaneous connections
** This can be further improved by using caching servers as most of the traffic are keep-alive messages

* Used by GFS for electing master server

* Also used by Google as a nameserver

== Issues ==
* Due to the use of Paxos (the only algorithm for this problem), the chubby cell is limited to only 5 servers. While this limits fault-tolerance, in practice this is more than enough.
* Since it has a file-system client interface, many programmers tend to abuse the system and need education (even inside Google)
* Clients need to constantly ping Chubby to verify that they still exist. This is to ensure that a server disappearing while holding a lock does not indefinitely hold that lock.
* Clients must also consequently re-verify that they hold a lock that they think they hold because Chubby may have timed them out.

DistOS 2015W Session 5

2015-04-20T10:03:57Z

Jasons: /* Google File System */

= The Clouds Distributed Operating System =
It is a distributed OS running on a set of computers that are interconnected by a group of network. It basically unifies different computers into a single component.

The OS is based on 2 patterns:
* Message Based OS
* Object Based OS

== Object Thread Model ==

The structure of this is based on object thread model. It has set of objects which are defined by the class. Objects respond to messages. Sending message to object causes object to execute the method and then reply back.

The system has '''active objects''' and '''passive objects'''.

# Active objects are the objects which have one or more processes associated with them and further they can communicate with the external environment.
# Passive objects are those that currently do not have an active thread executing in them.

The content of the Clouds data is long lived. Since the memory is implemented as a single-level store, the data exists forever and can survive system crashes and shut downs.

== Threads ==

The threads are the logical path of execution that traverse objects and executes code in them. The Clouds thread is not bound to a single address space. Several threads can enter an object simultaneously and execute concurrently. The nature of the Clouds object prohibits a thread from accessing any data outside the current address space in which it is executing.

== Interaction Between Objects and Threads ==

# Inter object interfaces are procedural
# Invocations work across machine boundaries
# Objects in clouds unify concept of persistent storage and memory to create address space, thus making the programming simpler.
# Control flow achieved by threads invoking objects.

== Clouds Environment ==

# Integrates set of homogeneous machines into one seamless environment
# There are three logical categories of machines- Compute Server, User Workstation and Data server.

= Plan 9 =

Plan 9 is a general purpose, multi-user and mobile computing environment physically distributed across machines. Development of the system began in the late 1980s. The system was built at Bell Labs - the birth place of Unix. The original Unix OS had no support for networking, and there were many attempts over the years by others to create distributed systems with Unix compatibility. Plan 9, however, is distributed systems done following the original Unix philosophy.

The goals of this system were:
# To build a distributed system that can be centrally administered.
# To be cost effective using cheap, modern microcomputers.

The distribution itself is transparent to most programs. This is made possible by two properties:
# A per process group namespace.
# Uniform access to most resources by representing them as a file.

== Unix Compatibility ==

The commands, libraries and system calls are similar to that of Unix and therefore a casual user cannot distinguish between these two. The problems in UNIX were too deep to fix but still the various ideas were brought along. The problems addressed badly by UNIX were improved. Old tools were dropped and others were polished and reused.

== Similaritieis with the UNIX ==
<ul>
<li>shell</li>
<li>Various C compilers</li>
</ul>

== Unique Features ==

What actually distinguishes Plan 9 is its '''organization'''. Plan 9 is divided along the lines of service function.
* CPU services and terminals use same kernel.
* Users may choose to run programs locally or remotely on CPU servers.
* It lets the user choose whether they want a distributed or centralized system.

The design of Plan 9 is based on 3 principles:
# Resources are named and accessed like files in hierarchical file system.
# Standard protocol 9P.
# Disjoint hierarchical provided by different services are joined together into single private hierarchical file name space.

=== Virtual Namespaces ===

In a virtual namespace, a user boots a terminal or connects to a CPU server and then a new process group is created. Processes in group can either add to or rearrange their name space using two system calls - mount and bind.

* '''Mount''' is used to attach new file system to a point in name space.
* '''Bind''' is used to attach a kernel resident (existing, mounted) file system to name space and also arrange pieces of name space.
* There is also '''unbind''' which undoes the effects of the other two calls.

Namespaces in Plan 9 are on a per-process basis. While everything had a way reference resources with a unique name, using mount and bind every process could build a custom namespace as they saw fit.

Since most resources are in the form of files (and folders), the term ''namespace'' really only refers to the filesystem layout.

=== Parallel Programming ===
Parallel programming was supported in two ways:
* Kernel provides simple process model and carefully designed system calls for synchronization.
* Programming language supports concurrent programming.

== Legacy ==

Even though Plan 9 is no longer developed, the good ideas from the system still exist today. For example, the ''/proc'' virtual filesystem which displays current process information in the form of files exists in modern Linux kernels.

= Google File System =

It is scalable, distributed file system for large, data intensive applications. It is crafted to Google's unique needs as a search engine company.

Unlike most filesystems, GFS must be implemented by individual applications and is not part of the kernel. While this introduces some technical overhead, it gives the system more freedom to implement or not implement certain non-standard features.

Link to an explanation on how GFS works
[http://computer.howstuffworks.com/internet/basics/google-file-system1.htm]

== Architecture ==

The architecture of the Google file system consists of a single master, multiple chunk-servers and multiple clients. Chunk servers are used to store the data in uniformly sized chunks. Each chunk is identified by globally unique 64 bit handle assigned by master at the time of creation. The chunks are split into 64KB blocks, each with its own hashsum for data integrity checks. The chunks are replicated between servers, 3 by default. The master maintains all the file system metadata which includes the namespace and chunk location.

Each of the chunks is 64 MB large (contrast this to the typical filesystem sectors of 512 or 4096 bytes) as the system is meant to hold enormous amount of data - namely the internet. The large chunk size is also important for the scalability of the system - the larger the chunk size, the less metadata the master server has to store for any given amount of data. With the current size, the master server is able to store the entirety of the metadata in memory, increasing performance by a significant margin.

== Operation ==

Master and Chunk server communication consists of
# checking whether there any chunk-server is down
# checking if any file is corrupted
# deleting stale chunks

When a client wants to do some operations on the chunks
# it first asks the master server for the list of servers that store the parts of a file it wants to access
# it receives a list of chunk servers, with multiple servers for each chunk
# it finally communicates with the the chunk servers to perform the operation

The system is geared towards appends and sequential reads. This is why the master server responds with multiple server addresses for each chunk - the client can then request a small piece from each server, increasing the data throughput linearly with the number of servers. Writes, in general, are in the form of a special ''append'' system call. When appending, there is no chance that two clients will want to write to the same location at the same time. This helps avoid any potential synchronization issues. If there are multiple appends to the same file at the same time, the chunk servers are free to order them as they wish (chunks on each server are not guaranteed to be byte-for-byte identical). Changes may also be applied multiple times. These issues are left for the application using GFS to resolve themselves. While a problem in the general sense, this is good enough for Google's needs.

== Redundancy ==

GFS is built with failure in mind. The system expects that at any time, there is some server or disk that is malfunctioning. The system deals with the failures as follows.

=== Chunk Servers ===

By default, chunks are replicated to three servers. This exact number depends on the application in question doing the write. When a chunk server finds that some of its data is corrupt, it grabs the data from other servers to repair itself{{Citation needed}}.

=== Master Server ===

For efficiency, there is only a single live master server at a time. While not making the system completely distributed, it avoid many synchronization problems and suits Google's needs. At any point in time, there are multiple read-only master servers that copy metadata from the currently live master. Should it go down, they will serve any read operations from the clients, until one of the hot spares is promoted to being the new live master server.

=== Server:Stateless ===
*the servers does not store states about clients
*no caching at client either
**since most program only cares about the output
**if client wants up-to-date result, rerun the program
*use heartbeat messages to monitor servers
**good for system with assumption that changes (or failures) are often

DistOS 2015W Session 4

2015-04-20T09:51:01Z

Jasons: /* Andrew File System */

= Andrew File System =
AFS (Andrew File System) was set up as a direct response to NFS. Essentially universities found issues when they tried to scale NFS in a way that would allow them to share files amongst their staff effectively. AFS was more scalable than NFS because read-write operations happened locally before they were committed to the server (data store).

Since AFS copies files locally when they were opened and only sends the data back when they are closed, all operations between opening and closing the file are very fast and do not need to access the network. NFS works with files remotely, so there is no data to transfer when opening/closing the file, making those operations instant.

There are several problems with this design, however:
* The local system must have enough space to temporarily store the file.
* Opening and closing the files requires a lot of bandwidth for large files. To read even a single byte, the entire file must be retrieved (later versions remedied this).
* If the close operation fails, the system will not have the updated version of the file. Many programs are designed around local filesystems, and therefore don't even check the return value of the close operation (as this is unlikely to fail on a local FS), giving users the false impression that everything went well.

Given all this, AFS was suitable for working with small files, not large ones, limiting its usefulness. It is also notoriously annoying to set up as it is geared towards university-sized networks, further limiting its success.

*Kerberos protocol
**authentication protocol using time based ticket
**single sign on system to authenticate and use other services
**AFS uses Kerberos for authentication, and implements access control lists on directories for users and groups.

= Amoeba Operating System =

=== Capablities: ===
* Pointer to the object
* Capability assigning right to perform to some operation to the object ticket
* Communicate wide area network
* a kind of ticket or key that allows the holder of the capa- bility to perform some (not neces- sarily all)
* Each user process owns some collection of capabilities, which together define the set of objects it may access and the types of operations that my ne performed on each
* After the server has performed the operation, it sends back a reply message that unblocks the client
* Sending messages, blocking and accepting forms the remote procedure call that can be encapsulate using to make entire remote operation look like local procedure
* Second field: used by the sever to identify which of its objects is being addressed server port and object number identify object which operation to performed
* Generates 48-bit random number
* The third field is the right field which contains a bit map telling which operation the holder of the capability may performed
* X11 Window management

=== Thread Management: ===
* Same process have multiple thread and each process has its own registered counter and stack
* Behave like process
* It can synchronized using mutex semaphore
* File: Multiple thread,
* Blocked when there's multiple threads
* Buttlet thread the mutex
* The careful reader may have noticed that user process can pull 813kbytes/sec

= Unique features =

== Pool processors ==
Pool processors are group of CPUs that are dynamically allocated as user needs. When a program is executed, any of the available processor run.

== Supported architectures ==
Many different processor architectures are supported including:
* i80386 (Pentium)
* 68K
* SPARC

= The V Distributed System =

* First tent in V design: High Performance communication is the most critical facility for distributed systems.
* Second; The protocols, not the software, define the system.
* Third; a relatively small operating system kernel can implement the basic protocols and services providing a simple network-transparent process, address space & communication model.

=== Ideas that significantly affected the design ===
* Shared Memory.
* Dealing with group of entities same as they deal w/individual entities.
* Efficient file caching mechanism using the virtual memory caching mechanism.

=== Design Decisions ===
* Designed for a cluster of workstations with high speed network access ( only really supports LAN ).
* Abstract the physical architecture of the participating workstations, by defining common protocols providing well-defined interfaces.

V was run on LAN, and its developers developed a really fast IPC protocol which allowed for it to be a fasted distributed operating system in a small geographic area. Aside from the IPC protocols, V also implemented RPC calls in the background.

V uses the strong consistency model. This model can cause issues with concurrency because in V files are a memory space. Thus two different users accessing the same file and in fact accessing the same memory location. This could result in issues unless there is an effective implementation to deal with multiple versions, etc.

VMTP protocol was used for communication. It supports request-respond behavior. Besides, it provides transparency, group communication facility and flow control. It is pretty much like TCP.

DistOS 2015W Session 3

2015-04-20T09:43:44Z

Jasons: /* Locus */

= Multics =

'''Team:''' Sameer, Shivjot, Ambalica, Veena

It came into being in the 1960s and it completely vanished in 2000s. It was started by Bell, General Electric and MIT but Bell backed out of the project in 1969.
Multics is a time sharing OS which provides multitasking and multiprogramming. It is not a distributed OS but it a centralized system which was written in machine-specific assembly.

It provides the following features:
# Utility Computing
# Access Control Lists
# Single level storage
# Dynamic linking
#* Sharded libraries or files can be loaded and linked to Random Access Memory at run time
# Hot swapping
# Multiprocessing System
# Ring oriented Security
#* It provides number of levels of authorization within the computer system
#* Still present in some form today, inside both processors (like x86) and operating systems

= Unix =

Unix in its original conception is a small, minimal API system designed by two guys from Bell Labs. It was essentially an OS that was optimized for the needs of programmers but not much beyond that. The UNIX OS ran on one computer, and terminals ran from that one computer. Thus it is not a distributed operating system as it is centralized and implements time sharing. In fact, it didn't even have support for networking in the first version.

The C language was created specifically for Unix, as the creators wanted to create a machine-agnostic language for the operating system.

Most features from Unix are still available in present day Unix-based systems. For example, the shell, with its piping capabilities, is still used today in its original form.

= NFS =

NFS is a protocol for working with distributed file systems transparently using RPC. These connections are not secure. Sun wanted to encrypt these RPC connections but encryption would result in government regulations that Sun wanted to avoid in order to sell NFS over seas.

<blockquote>
Sun wanted to secure their NFS with encryption, but at the time encryption was regulated like munitions in the United States. Exporting any product that had encryption was impossible, but Sun needed those sales abroad. To avoid these regulations, Sun decided to sell the insecure NFS version of the system.
</blockquote>

'''Team''': Mert

*Sun used "open protocol" approach to develop NFS
** Simply specified the exact message formats that clients and servers would use to communicate.
** Different groups could develop their own NFS servers and thus compete in an NFS marketplace.
** ex. Sun, NetApp, EMC, IBM, etc.

*NFSv2, simple and fast server crash recovery
**Any minute that the server is down (or unavailable) makes all the clients unproductive.
**The protocol is designed to deliver in each protocol request all the information that is needed in order to complete the request.
**stateless approach: the server does not track anything about what clients are doing
**no fancy crash recovery is needed, the server just starts running again, and a client, at worst, might have to retry a request.

= Locus =

# Not scalable
#* The synchronization algorithms were so slow, they only managed to run it on five computers
#* Every computer stores a copy of every file
#* Also used CAS to manage files
# Not efficient with abstractions
#* Trying to distribute files and processes
#Allowed for process migration
#Transparency
#* It provided network transparency to “disguise” its distributed context.
#Dynamic reconfiguration. (It adapts topology changes.)

Locus has lots of similarities with the today's systems. It uses replication and partitioning which are employed in cloud and distributed systems.

'''Team''': Eric

*LOCUS was capable of distribute file and processes among the nodes but not the computing power.

= Sprite =

''' Team''': Jamie, Hassan, Khaled

Sprite had the following Design Features:
# Network Transparency
# Process Migration, file transfer between computers
#* User could initiate a process migration to an idle machine, and if the machine was no longer idle; due to it being used by another user, the system would take care of the process migration to another machine
# Handling Cache Consistency
#* Sequential file sharing ==> By using a version number for each file
#* Concurrent write sharing ==> Disable cache to clients, enable write-blocking and other methods
# Implemented a caching system that sped up performance
# Implemented a log structured file system
#* They realized that with increasing amounts of RAM in computers which can be used for caching, writes to the disk were the main bottleneck, not reads.
#* Log structured file-systems are optimized for writes, as changes to previous data are appended at the current position.
#* This allows for very fast, sequential writes.
#* Example: SSD (Solid-state disks)

The main features to take away from the Sprite system is that it implemented a log structured file system, and implemented caching to increase performance.

DistOS 2015W Session 3

2015-04-20T09:39:51Z

Jasons: /* NFS */

= Multics =

'''Team:''' Sameer, Shivjot, Ambalica, Veena

It came into being in the 1960s and it completely vanished in 2000s. It was started by Bell, General Electric and MIT but Bell backed out of the project in 1969.
Multics is a time sharing OS which provides multitasking and multiprogramming. It is not a distributed OS but it a centralized system which was written in machine-specific assembly.

It provides the following features:
# Utility Computing
# Access Control Lists
# Single level storage
# Dynamic linking
#* Sharded libraries or files can be loaded and linked to Random Access Memory at run time
# Hot swapping
# Multiprocessing System
# Ring oriented Security
#* It provides number of levels of authorization within the computer system
#* Still present in some form today, inside both processors (like x86) and operating systems

= Unix =

Unix in its original conception is a small, minimal API system designed by two guys from Bell Labs. It was essentially an OS that was optimized for the needs of programmers but not much beyond that. The UNIX OS ran on one computer, and terminals ran from that one computer. Thus it is not a distributed operating system as it is centralized and implements time sharing. In fact, it didn't even have support for networking in the first version.

The C language was created specifically for Unix, as the creators wanted to create a machine-agnostic language for the operating system.

Most features from Unix are still available in present day Unix-based systems. For example, the shell, with its piping capabilities, is still used today in its original form.

= NFS =

NFS is a protocol for working with distributed file systems transparently using RPC. These connections are not secure. Sun wanted to encrypt these RPC connections but encryption would result in government regulations that Sun wanted to avoid in order to sell NFS over seas.

<blockquote>
Sun wanted to secure their NFS with encryption, but at the time encryption was regulated like munitions in the United States. Exporting any product that had encryption was impossible, but Sun needed those sales abroad. To avoid these regulations, Sun decided to sell the insecure NFS version of the system.
</blockquote>

'''Team''': Mert

*Sun used "open protocol" approach to develop NFS
** Simply specified the exact message formats that clients and servers would use to communicate.
** Different groups could develop their own NFS servers and thus compete in an NFS marketplace.
** ex. Sun, NetApp, EMC, IBM, etc.

*NFSv2, simple and fast server crash recovery
**Any minute that the server is down (or unavailable) makes all the clients unproductive.
**The protocol is designed to deliver in each protocol request all the information that is needed in order to complete the request.
**stateless approach: the server does not track anything about what clients are doing
**no fancy crash recovery is needed, the server just starts running again, and a client, at worst, might have to retry a request.

= Locus =

# Not scalable
#* The synchronization algorithms were so slow, they only managed to run it on five computers
#* Every computer stores a copy of every file
#* Also used CAS to manage files
# Not efficient with abstractions
#* Trying to distribute files and processes
#Allowed for process migration
#Transparency
#* It provided network transparency to “disguise” its distributed context.
#Dynamic reconfiguration. (It adapts topology changes.)

Locus has lots of similarities with the today's systems. It uses replication and partitioning which are employed in cloud and distributed systems.

'''Team''': Eric

= Sprite =

''' Team''': Jamie, Hassan, Khaled

Sprite had the following Design Features:
# Network Transparency
# Process Migration, file transfer between computers
#* User could initiate a process migration to an idle machine, and if the machine was no longer idle; due to it being used by another user, the system would take care of the process migration to another machine
# Handling Cache Consistency
#* Sequential file sharing ==> By using a version number for each file
#* Concurrent write sharing ==> Disable cache to clients, enable write-blocking and other methods
# Implemented a caching system that sped up performance
# Implemented a log structured file system
#* They realized that with increasing amounts of RAM in computers which can be used for caching, writes to the disk were the main bottleneck, not reads.
#* Log structured file-systems are optimized for writes, as changes to previous data are appended at the current position.
#* This allows for very fast, sequential writes.
#* Example: SSD (Solid-state disks)

The main features to take away from the Sprite system is that it implemented a log structured file system, and implemented caching to increase performance.

DistOS 2015W Session 3

2015-04-20T09:18:17Z

Jasons: /* NFS */

= Multics =

'''Team:''' Sameer, Shivjot, Ambalica, Veena

It came into being in the 1960s and it completely vanished in 2000s. It was started by Bell, General Electric and MIT but Bell backed out of the project in 1969.
Multics is a time sharing OS which provides multitasking and multiprogramming. It is not a distributed OS but it a centralized system which was written in machine-specific assembly.

It provides the following features:
# Utility Computing
# Access Control Lists
# Single level storage
# Dynamic linking
#* Sharded libraries or files can be loaded and linked to Random Access Memory at run time
# Hot swapping
# Multiprocessing System
# Ring oriented Security
#* It provides number of levels of authorization within the computer system
#* Still present in some form today, inside both processors (like x86) and operating systems

= Unix =

Unix in its original conception is a small, minimal API system designed by two guys from Bell Labs. It was essentially an OS that was optimized for the needs of programmers but not much beyond that. The UNIX OS ran on one computer, and terminals ran from that one computer. Thus it is not a distributed operating system as it is centralized and implements time sharing. In fact, it didn't even have support for networking in the first version.

The C language was created specifically for Unix, as the creators wanted to create a machine-agnostic language for the operating system.

Most features from Unix are still available in present day Unix-based systems. For example, the shell, with its piping capabilities, is still used today in its original form.

= NFS =

NFS is a protocol for working with distributed file systems transparently using RPC. These connections are not secure. Sun wanted to encrypt these RPC connections but encryption would result in government regulations that Sun wanted to avoid in order to sell NFS over seas.

<blockquote>
Sun wanted to secure their NFS with encryption, but at the time encryption was regulated like munitions in the United States. Exporting any product that had encryption was impossible, but Sun needed those sales abroad. To avoid these regulations, Sun decided to sell the insecure NFS version of the system.
</blockquote>

'''Team''': Mert

*Sun used "open protocol" approach to develop NFS
** Simply specified the exact message formats that clients and servers would use to communicate.
** Different groups could develop their own NFS servers and thus compete in an NFS marketplace.
** ex. Sun, NetApp, EMC, IBM, etc.

= Locus =

# Not scalable
#* The synchronization algorithms were so slow, they only managed to run it on five computers
#* Every computer stores a copy of every file
#* Also used CAS to manage files
# Not efficient with abstractions
#* Trying to distribute files and processes
#Allowed for process migration
#Transparency
#* It provided network transparency to “disguise” its distributed context.
#Dynamic reconfiguration. (It adapts topology changes.)

Locus has lots of similarities with the today's systems. It uses replication and partitioning which are employed in cloud and distributed systems.

'''Team''': Eric

= Sprite =

''' Team''': Jamie, Hassan, Khaled

Sprite had the following Design Features:
# Network Transparency
# Process Migration, file transfer between computers
#* User could initiate a process migration to an idle machine, and if the machine was no longer idle; due to it being used by another user, the system would take care of the process migration to another machine
# Handling Cache Consistency
#* Sequential file sharing ==> By using a version number for each file
#* Concurrent write sharing ==> Disable cache to clients, enable write-blocking and other methods
# Implemented a caching system that sped up performance
# Implemented a log structured file system
#* They realized that with increasing amounts of RAM in computers which can be used for caching, writes to the disk were the main bottleneck, not reads.
#* Log structured file-systems are optimized for writes, as changes to previous data are appended at the current position.
#* This allows for very fast, sequential writes.
#* Example: SSD (Solid-state disks)

The main features to take away from the Sprite system is that it implemented a log structured file system, and implemented caching to increase performance.

DistOS 2015W Session 2

2015-04-20T09:07:56Z

Jasons: /* Reading Response Discussion */

= Reading Response Discussion =
*In computing, time-sharing, is the sharing of a computing resource among many users by means of multiprogramming and multi-tasking.
**In the old days, computers were expensive and physically large, so one computer was shared among many users using terminals.

== Mother of All Demos: ==

'''Team:''' Jason, Kirill, Sravan, Agustin, Hassan Ambalica, Apoorv, Khaled

* 1968, lead by Doug Inglebard
* Initial public display of many modern technologies
* One computer with multiple remote terminals
* Video conferencing
* Computer mouse (and coined the term)
* Word processing, rudimentary copy and paste
* Dynamic file linking (hypertext)
* Revision control/version control/source control
* Collaborative real-time editor
** User privilege control in that user can provide read-only access, read-write privilege to file
* Corded keyboard
** Marco keyboard that allows messages quickly, while using mouse at same time
* Not really a distributed operating system, but great start because multiple users at different terminals could share same resources

== Early Internet ==

== Alto ==

'''Team:''' Tory, Veena, Sameer, Mert, Deep, Nameet, Moe

* Initially developed around 1973 by Xerox, upgraded over next few years
* High speed network connectivity (3 Mbps @ 1km distance)
* Connected up to 256 machines
* Protocol similar to cross between UDP/TCP, before TCP invented
* Allowed sharing of printers
* Also allowed distribution of files across computers (redundancy/reliability)
* Sort of early cloud
* Allowed for remote debugging, store error logs
* Allowed machines to use processing power of others
* Much of the time it would be idling, which is amazing at a time when computers cost a fortune

= Professor lead discussion 1 =

A true distributed operating system does not actually exist, its more of a dream.

You'll find in the history of trying to achieve this dream of a distributed operating system there has always been a road block as a result of a technical issue. People would come up with a solution to this technical issue but then they would find that some other technical issue would crop up. For example 'The Mother of All Demos' tried to build a distributed operating system but they had no networking. They had to point a television camera at the computer monitor to be able to demo their concept. The early internet came along and dealt with the issue of no networking. However the early internet itself had other technical issues.

A common buzz word during the early days of development was '''time sharing''', which is an old term for multiple processes running simultaneously. However, at the time it referred to multiple users sharing the CPU cycles on a single computer. Today, a single user's many processes using a single CPU is much more common.

= Discussion: Easy on one computer, hard on multiple computers =

{| class="wikitable" width="100%"
|+ '''Instant Messaging'''
|-
! Why is it easy?
! Why is it hard?
|-
| Can't be out sync
| Synchronization issues
* Server-client modal
** If two or more servers they get requests same time, they have to figure out how to synchronize the data
* Peer-to-Peer
** Each peer has to figure out how to sync each message
|-
| Only one data store/source
|-
|}

{| class="wikitable" width="100%"
|+ '''Mortal Kombat/Twitch Gaming'''
|-
! Why is it easy?
|
* Full control of all software
* All possible users are physically co-located
* Latency minimized
! Why is it hard?
|
* Games are fundamentally low-latency. Networking is fundamental high-latency.
* Input prediction doesn't work well on twitchy games.
* Have to handle lying or faulty clients.
* Have to handle users finding each other.
|-
|}

{| class="wikitable" width="100%"
|+ '''Photo Album'''
|-
! Why is it easy?
! Why is it hard?
|-
|}

=== Commonalities ===
* Synchronization
* Bandwidth
* Reliability/Fault Tolerance
* Interoperability
* Discovery
* Routing
** In modern system this issue has been mostly abstracted away
** Classic example would be Wireless Ad-hoc networking

The above list is not hard on a single system because all the cores have equal access to all the resources. Also as a result of excellent engineering modern single systems can very effective deal with any errors that may result.