CSE 60641: Operating Systems (FA08)

[OS-FA08]: Lampson92

2008-12-10T13:10:00.000-08:00

The paper was well written and provides a thorough overview of authentication. The paper attempts to define a logic based approach to authentication in distributed systems.

The logic used to describe the system may be useful for designing the system but we are concerned that it doesn't help explain the system. We are unsure what the contribution is because it appears that most of the work was preexisting. It was interesting that they implemented most of the mechanisms.

Lampson91

2008-12-10T13:07:00.000-08:00

SUMMARY
The paper “Authentication in Distributed Systems: Theory and Practice” by Lampson,et.al. describes the logic behind a computer security model for use in a distributed system. The authors also contend that they have implemented the logic in a real authentication system but offer little information about the implementation. The theory they present seems consistent with modern security implementations used currently in production systems.

They also present several conceptual trade-offs or pairings that are important in security system design. For example, a security system needs to distinguish between authentication and authorization, the first term representing the need to define who wants to access a particular resource while the second term defines whether the principal wanting to access the resource actually has the privilege of doing so. Another tradeoff they identify is balancing security and availability, especially if we extend the definition of availability to include ease-of-use. For example, a 25-character password that must be changed every 3 days is probably more secure than a 4-digit pin number that never changes; however, users would probably find the shorter, non-variable password easier to use. Finally, the authors distinguish between using encryption for secrecy versus integrity although encryption can be used for both.

The authors state that their theory has been implemented for a group of 50 researchers at DEC’s Systems Research Center in Palo Alto.

OBSERVATIONS
I think the major benefit of this paper is that it presents a framework for the various issues that a designer needs to consider in developing a security system. The authors also referenced several “state-of-the-art” security tools such as RSA, Kerberos and DES (3DES is actually the latest shared key encryption standard but it’s basically a multiple application of DES). It would be interesting to know if the authors used the work done in designing these tools as the basis for their theory. In other words, did they develop a theory to satisfy the application?

There were two security issues that seemed to be overlooked in the paper although that doesn’t imply that the theory doesn’t satisfy these needs. First, they don’t directly address the possibility of a person who lacks the authorization to access a given resource can still give that authorization to another user. This would be the equivalent of a user administrator adding a person to a group that allows its members to access a file without the administrator actually being a part of that group. While the administrator could theoretically add himself to the group as well, the administrator does not have any of that group’s privileges at the time he adds the user. Second, they didn’t discuss the use of roles as a set of privileges assigned by a third party to a user. Their focus was on roles as a construct assigned by a user to control his or her own privileges.

Another observation that I found important was the relative difference in speed between public and shared key encryption. On p. 13, the authors show the results of tests that indicate that shared key encryption is 1000-5000 times faster than public key encryption. While those tests utilized MD4 and DES which have subsequently been replaced by MD5 and 3DES, even these later technologies are probably several orders of magnitude faster than RSA.

ISSUES
There is still a tremendous need for the Lampson model to be implemented in a robust production system. There are many security subsystems which address a portion of their theory (e.g. IPSec) but I’m not aware of a single vendor that presents a comprehensive solution.

While I believe their model extends to biometric authentication means, it would have been interesting to have the authors consider methods of authentication that are independent of the workstation and server.

Finally, there might be an opportunity to develop corollaries to the Lampson theory that could reduce the steps involved in authentication/authorization or improve the integration between user names and public keys.

Jerry Kruczek

Lampson91

2008-12-10T12:14:00.000-08:00

The paper defines the notion of principals as sources for requests. These requests are performed on objects such as files, devices or processes. A reference monitor that examines each request and decides whether to grant it. The paper also introduces the concept of a Trusted Computing Base. Lampson defines the trusted computing base of a computer system as simply a small amount of software and hardware that security depends on and that we distinguish from a much larger amount that can misbehave without affecting security. The theory described in the paper explains how to reason about a principal’s authority by deducing the other principals that it can speak for. An authenticating a channel is one important application They use the theory to explain many existing and proposed mechanisms for security.

Lampson91

2008-12-10T12:02:00.000-08:00

The authors describe a language to help talk about the problems of authentication in distributed systems, and subsequently state some of those problems, their solutions, and some of their own work. Their work is based on the idea of objects, request, principals and monitors, where an object is something like a file or a device, a request is to use an object, a principal is the entity making the request, and the monitor is in charge of validating requests. They define a language for this using terms like "Channel C speaks for principal A", etc, and set up the logical framework for much of the previous work in this area.

I liked that they were able to define a standardized way to talk about these security problems, but because I don't have much background in security issues I found a lot of it very hard to follow.

[OS-FA08]: Lampson 91

2008-12-10T12:00:00.000-08:00

A theory of authentication and a system to implement that is discussed. Theory consists of principals and relation between principlas. Simple and compound principals,channels etc are defined. Also they've used this theory to explain many existing and proposed mechanisms of security. Theory deals with principals and statements. Principlas can say things and statements are the things they say. A "speaks for" relation exist between principals.The concept of encryption is also explained mainly that of shared and public key. Another important fact that has an impact on security is "trusted computing base" (TCB)-a small amount of software and hardware. One of the popular public encryption scheme, Rivest-Shamir-Adleman or RSA and other schemes like Needham-Schroeder and Kerbos are given in detail. Finally,they've described the system they built and its features like passing principals as arguements efficiently, handles public and shared key encryption etc.On the whole the paper was interesting.

[OS-FA08]: Lampson91

2008-12-10T11:45:00.000-08:00

This paper proposed a theory of authentication in distributed systems, and it started with basic concepts like channels, principals, etc. The most interesting part of this paper is its discussion in section 8, authenticating inter-process communication, which is still an important aspect of today's research especially in terms of network security, which has some kind of similarity with web service communications, but web services are usual at a large level. And more interestly, they have a system implemented based on the theory.

[OS-FA08]: Lampson92

2008-12-10T10:51:00.000-08:00

This paper explains the theory behind authentication in distributed systems.

The basic idea of the paper is to discuss the underlying theory behind the authentication protocols in the various distributed systems of the time, including Needham-Schroeder and Kerberos. It also described basic concepts that increase the security of the systems, such as refreshing keys and public/private key cryptography.

They then go onto explain how this theory fits into their new method of authentication. That is, treating almost everything about the machine as untrusted, and thus requiring more security via revoking certificates and requiring secure machine booting.

In all it was an interesting paper, that was perhaps too long winded and could have gotten away with being much more concise.

[OS-FA08]: Walker83

2008-12-08T13:26:00.000-08:00

LOCUS is a distributed system, which has network transparency, high reliability, failure recovery. Despite its difference, LOCUS is compatible with Unix, its filesystem tree naming mechanism is a superset of the Unix's. But the interesting part of LOCUS about its filesystem is that it supports file replication, which reminds of read only replication in replication, and both of them can improve performance by replicate copies, but the replications in LOCUS are not read only, therefore, it introduces some further complication than AFS in terms of data update and failure recovery, and also LOCUS filesystem has the concept of logical group to manage different copies of a file to share the same file descriptor or inode, which is different from AFS replications. From a user's perspective, the dynamic reconfiguration in LOCUS is also intriguing, especially for a distributed system.
Overall, this paper is good, but as stated in its conclusion: Nothing is free. Therefore, the tradeoff between performance and reliability remains difficult.

Walker83

2008-12-08T11:14:00.001-08:00

SUMMARY
The paper by Walker, et.al. describes the FOCUS distributed operating system which, in the authors’ words provides “a high performance, network transparent, distributed file system”. The paper does an excellent job of describing the challenges faced by any distributed file system and how FOCUS addresses each of the problems. It does not detail the exact programming constructs that implement all of its features but does describe the concepts behind them.

FOCUS (and other similar O/Ses) must address the following issues:
--File replication (assuming high availability is a goal)
--Remote process initiation
--Recovery when one or more servers is unavailable
--Dynamic reconfiguration of the server complex
A key concept behind FOCUS is separating file activity into three categories of devices—the using site (US), storage site (SS) and current synchronization site (CSS). The first acts as the initiator of the file activity (read, delete, modify) while the data is physically stored on one or more storage sites. The CSS acts as a “controller” receiving file requests from a US and sending the requests to an appropriate SS.

The paper concludes by citing the operation of FOCUS on UCLA’s campus as evidence of its effectiveness but the authors don’t provide any data regarding the number of files, volume of file operations, network traffic, etc.

OBSERVATIONS
My first observation is that this paper could act as a primer for anyone wanting to design a distributed file system or evaluate an existing design. It provides detailed information on the needed features as well as discusses what would happen if a problem occurred.

There were four issues that I would like the paper to have addressed in more detail.
It seems one US could start a file update after another US began reading that file and before the second US finished the read operation. How is the second US notified that the file it just finished reading is no longer current?
How many devices can serve as a CSS and how is consistency maintained among those devices?
When a file is replicated across several SSes, the CSS directs the US to “the most efficient one” (p.52). What algorithm does the CSS use to choose the most efficient one? Is it the least recently used replica, the least utilized SS, the SS with the shortest network path? How to choose the best device across a network is an ongoing controversy with many networks.
What effect does network latency have on FOCUS? The authors don’t provide any information on the state of the UCLA networks on which FOCUS was implemented so it’s impossible to determine what was running on the networks along with FOCUS.

ISSUES
One of the authors, Gerald Popek, is still on the faculty of UCLA. Under contract from DARPA, the UCLA CS department in the 90s developed a distributed file system call FICUS which seems to use FOCUS as its base. I would be interested in seeing what happened with this system over time.

The paper also addressed the need to support a heterogeneous network of computers, but it seemed that while the network was built on different platforms, they were all DEC devices. The same challenges would be there if they included Intel or Sun devices but the implementation difficulties might be much more challenging.

Finally, FOCUS’ behavior might be significantly different in our current environment involving the wide variety of networks currently on campuses. How would router latencies affect the transmission of packets? Would firewalls pose a block? Would the performance be the same if the US was running on a wireless network as opposed to a wired Ethernet configuration?

Jerry Kruczek

Walker 83

2008-12-08T09:08:00.000-08:00

They describe the LOCUS distributed operating system. LOCUS is set up such that files and processes can live an any machine in the network in a completely transparent way. When the user creates a file, it goes to the appropriate machine and runs without the user having to know which machine it is going to or understand how the decision is made. For processes, the program can be run locally or remotely without any changes to the software.

To accomplish this, each machine can play up to three roles, Using Site, Storage Site and Current Synchronization Site. This allows the system to easily figure out where files are stored, whether they are cached on the local machine, etc.

It is good that they were able to come up with a system where the distributed nature of it is mostly transparent to the user. They even have a fairly robust failure recovery mechanism. However, given the nature of computing today, I don't think it will be very useful. LOCUS was designed for a set of 17 VAX machines. Probably they were accessed via workstations. In this kind of environment, time and disk sharing is key, so having a system that accommodated this was vital.

Today, however, each person has their own fairly powerful machine with lots of space. The reason to distribute a system is not so much to share time and space (because we get enough of that on our personal machines) as it is to provide resources to do large-scale parallel algorithms (hence systems like Condor, that use a large amount of commodity machines) or to provide redundancy (hence distributed file systems like AFS and NFS). LOCUS just does not seem too relevant in today's computing environment.

Chase 94

2008-12-04T05:15:00.000-08:00

They describe the Opal operating system, which allows more flexible memory protection by providing a single virtual address space shared by all programs rather than creating a virtual address space for each.

The advantages of Opal are that it allows two processes to share a segment of their virtual memory. In situations where IPC is necessary, this can save a lot of time because data does not need to be copied via pipes or files. It also allows you to set up more complicated trust scenarios where data can be passed from parents to children, etc.

There are several disadvantages in this system described in Chapter 6. The most important is that you could not build a Unix compatibility layer on top of Opal, because it is not possible to copy data during a fork the same way it is accomplished in Unix. This puts Opal at a major disadvantage, because any software would need to be ported to it.

They don't discuss the performance in very objective way. Instead, in the performance section, they talk about software implementations that used the sharing and protection features of Opal, but there's no real apples to apples comparison of how it measures up with the same software running on Unix. This makes sense, however, because Opal was designed to work well with a specific class of software (environments with several different types of processes using the same data).

Our biggest complaint, which is ultimately less important to the quality of the paper, is that they claim that a 64-bit address space should be enough "for all time". While I certainly agree that 64 bits can address a LOT of memory, if you look at some of the historical papers we've read, any time someone says that a certain amount of storage or memory is "should always be enough", that amount seems ridiculously small 10 or 20 years down the line. Of course, we don't have anywhere near 16 exabytes of RAM to address yet, and if you consider that the factor has grown 1000 times in the last 20 years or so, and it would need to increase by a factor of 10 billion to get to the exabyte level, it still makes uncomfortable to say it will be enough for all time.

S.M. Niaz Arifin, Hoang Bui, Mike Olson

[OS-FA08] Chase 94

2008-12-03T13:24:00.000-08:00

The paper talks about Opal, a 64 bit operating system. While the 64 bit architecture makes it possible to have a larger address space, Opal uses only one globally shared virtual address space for each process. The immediate concern which comes to my mind is protection. However the paper describes a mechanism where threads are limited to their protection domains. There is no loss of protection as the protection domain decides who can access it. The advantage of this approach is obvious. This approach enables beneficial code- and data-sharing patterns that are currently prohibitive, due in part to the inherent restrictions of multiple address spaces.

Opal works well in integrated software environments. An “integrated environment” is a collection of software tools that work together to support users in complex tasks: CAD, CASE, image processing, physical modeling, etc. Integrated application systems may be large and evolving; protection is crucial because the “tools” are separately authored programs, possibly running on behalf of different users, and yet these tools must work together and share information efficiently.

One concern I have: is Opal of any use in software environments where "integrated environment " is not required?

Chase 94

2008-12-03T13:16:00.000-08:00

In this paper, the authors introduced a new operating system—the Opal system. Opal is a single-address-space operating system. A single address space operating system is a type of operating system with simple memory management which uses only one globally shared virtual address space. (definition from wiki) I think this is a very good idea, especially in a distributed system. SASOS supports cluster computing in a distributed system in ways that provide an improved program development environment and higher performance than available from conventional operating systems. It provides permanent unique names for all resources, threads that can migrate throughout a distributed system without changing the pointer context in which they run.[1] In particular, the authors discussed the memory sharing and protection support in Opal. Because addresses are independent, so sharing is simplified. Besides, because addressability and access are independent, so there is no loss of protection.

Reference:
[1]Using a Distributed Single Address Space Operating System to Support Modern Cluster Computing, Alan Skousen, Donald Miller, Proceeding of the 32nd Hawaii International Conference on System Sciences, 1999

[Chase 95] FA 08

2008-12-03T12:59:00.000-08:00

This paper discusses increased memory size and flat address space and how it influences IPC , memory protection and the TLB. While we see the benefits of eliminating the extra abstraction of virtual addresses, we are unsure of the contribution. We are also unsure of the importance of doing this alongside other systems.
We feel that some drawbacks to flat addressing exist, such as the inability to virtually remap memory if a memory chip fails.

[OS-FA08]: Chase94

2008-12-03T12:02:00.000-08:00

This paper discusses a novel system for memory management in systems with a 64-bit address space.

Whereas in traditional systems virtual memory is employed to create separate address spaces for each process in order to isolate process from one another, this paper discusses an alternate approach. Namely, to create a single global address space for every process, and use alternate techniques in order to maintain security.

I thought that this was a very interesting technique, especially for the integrated market that they seemed to be shooting for. The technique addresses the problems faced by applications which want to share data, but are unable to due to inefficiencies in the memory model. It would be interesting to see if any integrated environments still use this technique, and, if not, what caused them to switch away from it.

[OS-FA08]: Chase94

2008-12-03T11:17:00.000-08:00

This paper seems like going to the day one of operating system, which utilizes single address space for the whole system, is this something like the operating system before virtual memory was introduced? Sort of, but not exactly. The main purpose of Opal is to facilitate the sharing performance among various closely interactive processes, so that single-address space can beat private-address-space and gain finer grain of sharing. From a programmer's perspective, I think such sharing mechanism from single-address-space is not always a plus, I think not everyone likes the idea of totally exposing himself/herself, and in Opal, shared memory is the core, which means whatever process A does on the memory, process B can access as long as process B has the right permission, this can be good for sharing, but it's not that good for coding, especially for collaborations between different modules: suppose process A need to expand its working set, which will need more memory space and process A change its memory space addresses for certain variables, and such changes could force process B to change too, and so on so forth. Therefore, scalability is an issue, both in terms of memory spacing extension and process number increase (Shared memory has serious scalibility problem when processor number goes up)
However, if the problems listed above can be controlled in a reasonable range, I think the idea in this paper is still good

[O-Fa08]: Chase 94

2008-12-03T10:40:00.000-08:00

This paper discusses about Opal,a single address space Operating System and the memory sharing and protection support in it. Opal provides a global virtual address that is shared by all. The main idea of Opal design is that there is a unique interpretation for all addresses. The purpose of expermenting with Opal is to find out the strengths and weaknesses of the single -address-space approach.Threads are theexecution units in Opal. Threads are restricted to a specific set of segment at a time. Protection domain is an execution context for threads and each thread executes exactly in one protection domain.

As addresses are context independent,sharing is simplified.There is no loss of data as addressability and access are independent.The concept of distributing the single address space brings out the issue of coherency of shared segments.Authors state that solutions to such problem must be applied at the appplication level. Another problem of single address space is that programs are not free to allocate addresses for their segments.In the end,we can say that context addressing feature of Opal ensures that procedures and data can be shared any time without priori address space coordination. Also Opal can be implemented along with the modern wide address architectures,thereby permitting experimentation while using exit
sting tools.

Chase94

2008-12-02T23:16:00.000-08:00

SUMMARY
The paper by Chase, et.al. provides a detailed description of the Opal operating system, an O/S designed to separate memory protection functionality from the programs using the memory. Its specific target is wide-address (i.e. 64-bit) architectures that can address over 2 exabytes of memory. The authors plan to use the system to improve memory sharing for integrated software environments such as CAD.

At the core of Opal are two concepts—memory will be managed globally for all programs and the programs themselves will not exist as independent entities but act as “procedures residing in the shared address space” (p.275). Opal also separated program execution, resource ownership and resource naming from the protection domains.

Opal was implemented as a server process on top of a Mach 3.0 microkernel running initially on a DECstation 5000 but eventually on a DEC 3000 Alpha-based system. Their results seemed to confirm that they had developed an effective way of implementing a shared memory system by run a Boeing CAD software environment on the Opal/Mach combination.

OBSERVATIONS
I don’t believe the authors provided enough data to substantiate their claim that Opal worked as planned. They provided a minimum set of data in Section 5.3 but didn’t provide any data points to use as a norm for comparison purposes. I think they exhibited proof-of-concept performance but didn’t give enough information to conclude that their system was superior to running the CAD program on a different O/S environment.

I also couldn’t find information about the further development of the Opal O/S in a web search. While the authors may have proven the viability of their concept, it may have been difficult to implement Opal in a production system. The paper gave no information about the difficulty of integrating Opal into Mach or about any “bugs” that might have occurred during the execution of the CAD environment.

The paper included two statements that I found interesting. On p.276, the authors state that “operating system protection structures are not the right level to impose modularity”. The contention seems logical but I don’t know if modern systems actually use protection domains to create modularity. It seems these domains operate as the authors say they should—they “enforce” module boundaries.

On p.278, the authors state “burdening the operating system…with fine-grained protection is an error, particularly given the safety that can be guaranteed by strongly typed languages”. This almost seems a contradiction of their goal of separating protection domains from the processes. It seems the only way to accomplish this is to have the operating system play a major role in managing the protection domains.

ISSUES
This paper does a good job of stimulating discussion of how we should use the tremendous amounts of memory addressable with 64-bit architectures. Should we just treat the additional memory as more of the same resource and develop systems in the same way as 32-bit processors? The single address space might not be the best solution. Developers are presented the opportunity of using an almost unlimited memory space and using it effectively may take a totally different operating environment.

The paper also didn’t directly address whether Opal was designed for a single-user or multi-user environment. With huge amounts of memory, we may be returning to a “time-sharing” environment where multiple users are running on low power devices and using a single high-powered server. I couldn’t determine from the paper if Opal would work flawlessly if multiple users with different usage patterns and security capabilities were sharing its resources.

Jerry Kruczek

Lamport 78

2008-12-02T05:39:00.001-08:00

The Lamport paper discussed the ordering of events in a distributed system. Because a distributed system can be viewed as a collection of distinct processes which are spatially separated and which communicate with one another by exchanging messages, so it is important for us to know which event precedes another in a distributed system. In this paper, the authors suggested using logical clock. I think this is a far better approach than using physical clock. Because first of all, the physical clock may not be accurate enough, second, the physical clocks of different processors are in general not suitable for time stamping events, because these clocks are not synchronized. Synchronization of the physical clocks of all processors in a multiprocessor system requires additional hardware mechanisms. So a better alternative approach is to use partial ordering of events using logical clocks for timestamping events with virtual time. The concept of virtual time has been used successfully to derive clock conditions in distributed systems, in which message-passing is the only form of interaction.

Lamport78

2008-12-01T13:49:00.000-08:00

SUMMARY
The two papers, “Time, Clocks and the Ordering of Events in a Distributed System” and “The ABCD’s of Paxos” discuss algorithms needed for the correct functioning of distributed systems. The first paper’s algorithm focuses on ordering events occurring on two or more distributed processes in the absence of a single universal physical time clock. Since each process is reliant on its own clocking mechanism, there are two primary needs: (1) how to order events such that if a occurred before b as noted by a single observer, the two processes responsible for a and b respectively would agree that a happened before b and (2) how to synchronize physical clocks used by the two processes so the clocks will never differ by more than an agreed-upon interval. The algorithm presented in the paper relies on all processes following the same set of rules and exchanging time stamps along with message content such as resource requests. It also requires an administrator to define certain parameters such as the maximum difference between a “correct” clock and a clock used by a process.

The second paper describes a series of algorithms derived from the Paxos algorithm that can be used to maximize the fault tolerance of a set of machines. Besides the Abstract Paxos defined by Lamport, the paper describes three physical implementations of Paxos, Classic Paxos (CP), Disk Paxos (DP) and Byzantine Paxos (BP). All four algorithms aim at determining a fault-tolerant consensus; i.e. a “majority” decision about the results of applying the same process to the same set of inputs. If one or more of the processes fail or yield a minority response, the remaining members of the majority will be used to determine the “correct” response.

OBSERVATIONS
Since both papers were discussing algorithms rather than physical implementations, there were no test results to critique. There were mathematical proofs of some theorems as well as mathematical substantiation of both algorithms. The Lamport paper was somewhat easier to understand and relate to real-world examples than the Lampson paper. It may be significant that the Lampson treatise was supplied for an invited talk but never formally published. A stronger editing process might have made the Paxos paper easier to understand.

ISSUES
It was difficult for me to understand all of the ramifications of the Paxos paper. The concept of voting is crucial in minimizing bad results but I would have like more explanation about the relation between Paxos and commercial fault tolerant systems. On the other hand, the Lamport paper addresses issues which have significant real-world applications. While that paper used resource sharing as an example of its ordering algorithm, security logging is another area that requires stringent ordering. An important security initiative is Unified Security Management where a security device compiles events from a number of security logs including different devices such as servers and firewalls. While each of the devices has its own physical clock, these clocks usually do not use a single time source and even if they do, the actual time on these systems could differ enough to make it impossible to order all log entries associated with a single security event. Without a guaranteed order, forensics becomes difficult as it is impossible to prove that J preceded K which preceded L, etc. I think these algorithms have a definite application in Unified Security Management.

Jerry Kruczek

[OS-FA08]: Lamport78

2008-12-01T13:12:00.000-08:00

In this paper the idea of ordering processes based on their occurrence in time is discussed. This is a very serious problem, as if processes aren't ordered properly, then most systems will not function as anticipated by the users. This leads to errors which are hard to diagnose and fix.

Overall the paper was very interesting and well written. The idea of defining a partial ordering of events in the system was discussed and explained in a very intuitive fashion. The lack of need for physical clocks in this system was also explained very well.

The interesting thing about this paper I thought was the discussion on physical clocks. In general it is very hard to keep clocks synchronized together. This is due to the simple fact that if one has only one clock, then one cannot determine if skew exists. With two clocks, one can determine the skew between the two clocks, but still has no way of determining which clock is correct. Thus at least 3 clocks are necessary to keep time in any reasonable sense of the word. Thus the proof of correctness of the algorithm not necessarily depending on knowing a real time, but instead requiring that the skew between the clocks be below some value was very interesting, and a very good property for the system to have.

[OS FALL 08] Lamport 78

2008-12-01T13:07:00.000-08:00

The Lamport paper describes how logical clocks can be used to synchronize elements of a distributed system. The Lampson paper describes the design of a system using logical clocks. Logical clocks allow partial ordering without a physical clock. With synchronized physical clocks we can achieve total ordering. We thought the Lamport paper was well written and provided a nice overview of clocks in distributed systems. The Lampson paper provides an overview of fault tolerance using ideas presented in the Lamport paper.

[OS FALL 08] Lamport 78

2008-12-01T12:34:00.000-08:00

In a distributed computing environment, it is difficult to figure out the ordering of events as they happen. The system needs real clocks to keep track of when events occur. However even, with real clocks, clocks belong to different machine/process which is difficult to synchronize together. Those clocks might not be accurate enough in order to give a precise time. The paper introduces a concept of partial ordering using logical clocks. Clocks are implemented using counter without real time awareness. Clocks increase the count one at a time and between a pair of events. Sending and receiving message are considered events. Processes synchronize their clocks by sending and receiving message. A process send out a message with a time stamp, another process receive the message and adjust its clock by choosing the maximum between its current time and a time which is greater than the time stamp of the message. Author showed that, using logical clocks could solve complicated deadlock problem when multiple processes compete for a scare resource.

Overall, we think the paper is not difficult to read. The paper is clear and easy to understand. However, author dismissed to quickly the important of dealing with failure. If one of the process or a machine goes down, how the system would maintain its correctness. Also, we are skeptical of the over head of sending and receiving message when the system grows larger.

Mike Olson & Hoang Bui

Lamport78

2008-12-01T12:10:00.000-08:00

Lamport describes a distributed algorithm for synchronizing a system of logical clocks which can be used to totally order events. A Lamport logical clock is a monotonically incrementing software counter maintained in each process. It follows some simple rules: 1. A process increments its counter before each event in that process. 2. When a process sends a message, it includes its counter value with the message. 3. On receiving a message, the receiver process sets its counter to be greater than the maximum between its own value and the received value before it considers the message received. A Lamport clock may be used to create a partial causal ordering of events between processes. Given a logical clock following these rules, the following relation is true: if a->b then C(a) means "happened before." The use of the total ordering is illustrated with a method for solving synchronization problems.

It is not clear whether this method can be used for all synchronization problems. Usage of logical clocks would add the overhead of maintaining and sending timestamps

Paxos is a family of protocols for solving consensus in a network of unreliable processors. Consensus is the process of agreeing on one result among a group of participants. This problem becomes difficult when the participants or their communication medium may experience failures. Lampson's paper describes how consensus is used to implement replicated state machines, the general mechanism for fault-tolerance. They described an abstract version of Lamport’s Paxos algorithm for asynchronous consensus. Then they derive the Byzantine, classic, and disk versions of Paxos from the abstract one and discuss their performances.

[OS-FA08]: Lamport78

2008-12-01T09:20:00.000-08:00

This paper introduced the concept of event ordering in a distributed system, which is still the key part of today's operating systems. Along with logical clock, there are "partial ordering", "arbitrary total ordering", and more importantly, "anomalous behavior" handling, but the most interesting and also the most difficult part of this paper is its discussion about physical clocks, aside from the proof of its theorem, however, there are also other factors which should be considered, such as clock skew (which happens pretty often), and "optimal" total ordering (instead of arbitrary total ordering), which could benefit scheduling in some sense. Another major contribution of this paper is that it requires that clocks are never set backwards, which is pretty natural in terms of clocking.
All in all, given the age of this paper, it laid down some ground work for clocking research in distributed systems, which is very valuable.

[OS-FA08]:Lampson 01

2008-12-01T08:28:00.000-08:00

This paper deals with implementing replicated state machines using consensus. Replicated state machine is a general method for fault-tolerance. Here an abstract version of an algorithm for asynchronous consensus is explained,then a disk version is derived from the abstract one. Lamport's Paxos algorithm is the one discussed. Byzantine is the disk version.Finally the abstract and derived one is compared to show how they are related and the safety,performance,liveness of each one is discussed.

A consensus decides on one from a set of input values.In this paper agents are termed as set of processes. The simplest form of fault-tolerant consensus decides when majority of agents decide on the same value.The idea of Abstract Paxos (AP) is to collect a sequence of views to form a quorum that will be noticed. In case of Disk paxos (DP) we use commodity disks as agents and hence the name.

In conclusion ,authors state that AP uses agents that can perform actions like Close,Accept and Finish and Choose only. AP's agents are memories that can do conditional writes whereas DP is a generalization with read-write memories. Finally the main application for Paxos is replicated state machines.

[OS-FA08]:Howard88

2008-11-24T13:24:00.000-08:00

This paper mainly discussed a prototype of AFS, which was intended to have better scalability than its predecessor. The scalability is primarily measured in terms of the number of supported workstations. On the way to this prototype, a few changes were made in order to maintain system performance, which included cache management, name resolution, etc. From my point of interest, in section 5, there is a comparison between AFS and NFS, and it concluded that NFS was not designed for operation in a large environment, which may explain NFS has poorer performance than AFS when environment scales up. Read-only replication in the paper is also intriguing, which is similar to copy on write but not the same (no write), personally, I hope other file systems can integrate such mechanism: I had some experience with NFS when multiple processes/nodes access the same readonly file concurrently, the performance is pretty bad. AFS is good, but it's not for everybody, in my oppinion, AFS is designed for large network groups, not for single user or small networks.

[OS-FA08]:Howard88

2008-11-24T13:16:00.000-08:00

The paper describes the improvement of the AFS prototype by reducing context switches, the reduction of cache coherency checks (by implementing callbacks) and improvement in path resolution. They reduced server overhead by making the server multi-threaded.

It would be interesting to study cache size on modern AFS systems. The paper mentions caching data on disk but with modern memory size cache could be expanded dramatically and might have significant effect on performance. The study was well done.

[OS-FA08]:Howard88

2008-11-24T12:54:00.000-08:00

The Andrews File System (AFS) is a network file system developed at CMU. AFS supports various popular operating systems such as Linux, UNIX, Windows, and Mac OS, allowing users to access files across the network as if they are in a local storage device.

AFS uses a set of trusted servers, collectively called Vice, to present a homogeneous, location-transparent file name space to all the client workstations. The OS on each workstation intercepts file system calls and forwards them to a user-level process, called Venus, on that workstation. Venus caches files from Vice and stores modified copies of files back on the source servers.

To maximize the number of clients that can be supported by a server, as much of the work as possible is performed by Venus rather than by Vice. Venus contacts Vice only when a file is opened or closed. When a file is open, Venus makes a request to fetch the whole file from the server. This copy is called a snapshot. Any file operation such as a read or write is done on the snapshot. Because client performs file operations on a local copy, AFS outperforms NFS in any single client benchmarks.

The paper describes an initial prototype implementation using a synthetic benchmark as the basis of performance comparison. This experience led to some design changes, broadly categorized as to improve performance and to increase operability.

Changes to improve performance include cache management, name resolution, communication and server process structure and low-level storage representation. The results confirmed two things:

Scalability: remarkable improvement; in the revised system, it takes less than twice as long at a load of 20 as at a load of 1.
CPU and disk utilization on the server: CPU utilization rises from about 8 percent at a load of 1 to over 70 percent at a load of 20; disk utilization is below 25 percent even at a load of 20. This indicates that the server CPU still limits performance.

Changes to increase operability aimed at building an easily maintainable system that will offer minimal inconvenience to users. They used a data structuring primitive called Volume, which is a collection of files forming a partial subtree of the Vice name space. Their experience showed that volumes provide operational transparency - the ability to associate disk usage quotas with volumes and the ease with which volumes may be moved between servers proved valuable.

In summary, scaling had impact on performance, operability and other issues, and results showed that AFS copes up well with scaling. However, as they confessed, it could not alleviate the major problems of fault-tolerance: in the worst case, access of a Vice file can involve multiple servers, every one of which has to be up simultaneously.

By S. M. Niaz Arifin, Mike Olson and Hoang Bui

[OS-FA08]:Howard88

2008-11-24T12:05:00.001-08:00

This paper discusses the Andrew file system as it was being developed in the late 80s on 4.2BSD with respect to scalability. It was very interesting to see how they used a prototype system with a small(ish) number of users to determine the design of the larger system. This one fact seems to eventually lead to many of the success of AFS.

In order to improve performance, the following areas were addressed: cache management, name resolution, communication and server process structure, and low-level storage representation. The authors describe how each of these played a role in performance, and the steps taken to overcome any problems.

Overall I thought the paper was good. They fully explained all assumptions they made to the best of their ability. They also discussed alternatives, showing that they at least knew of other possible ways to implement the system. What was slightly lacking seemed to be a better rational for discarding other potential options other than "we believed [our technique] would provide superior performance in a large scale system." [Howard88, page 69]. This was quite disappointing, as some kind of justification would have gone a long way.

Howard88

2008-11-24T10:27:00.000-08:00

SUMMARY
“Scale and Performance in a Distributed File System” examines the scalability of the Andrew File System and explains modifications made to it to enable it to support 50 users per server. The first part of the paper verified the suitability of AFS as a distributed file system architecture. A prototype system of the initial design was built that supported up to 20 users although “there were occasions when even a few persons … caused performance to degrade intolerably.” (p.54) Besides a scalability issue there were several operational problems such as disk quotas which the authors also tried to address.

Using a synthetic workload, the authors ran a series of tests including a benchmark of the workload running on a computer where all files were local. The tests showed that a workload of 1 (corresponding to 5 distributed users) took approximately 70% longer than the local or standalone case even though the cache hit rate for AFS was in excess of 80%. CPU utilization was over 40% averaged over an 8-hout period with peaks of 75% during particular 5 minute intervals. They also looked at which server calls were consuming the most time.

The modifications made to the AFS were in four areas:
--Cache management
--Name resolution
--Communication and server process structure
--Low-level storage representation

Cache management was improved through the use of a callback feature which turned the server into a stateful condition. Name resolution was improved by implementing a mid-level naming protocol which separated the workstation pathname from the physical location of the file. Introducing a Lightweight Process at the user level allowed a single server process to serve multiple users. Finally, pathname lookups by workstations were replaced by a new mechanism.

The results of these modifications achieved the authors’ goals regarding scalability as measured by their benchmark. Moreover, the revised AFS seems like it will support well beyond 50 users by increasing the speed of the server hardware or software. Comparisons with NFS show that the modified system is a significant improvement over the Sun product for their synthetic workload. They also implemented three major operational improvements over the initial AFS—volume movement, user quotas and read-only cloning.

OBSERVATIONS
The paper did an excellent job of presenting the basics of AFS as related to scalability and the modifications made by the authors to improve upon AFS. Their published data not only supported their stated success but provided enough detail to allow readers to verify their claims. For example, by providing standard deviations, a reader could judge whether an average value was indeed typical of all results.

Probably, the only issue that I had with their results is that most of the published results for the prototype used Sun2 workstations while the enhanced version used RT/25s. Given their description of Venus, I don’t think the processing power of the workstation would have dramatically altered their results; however, I would have liked the authors to have addressed that issue.

ISSUES
I agree with the authors’ contention that it isn’t completely fair to compare AFS and NFS since the latter “was not designed for operation in a large environment”. (p.70) However, since NFS was perceived to be the de facto standard, it is reasonable to compare AFS to it.

Several times the authors raise the point that even the modified AFS may not be suited for all types of applications. For example, latency is greater using AFS especially for large files. Since AFS caches an entire file, it is difficult to have multiple programs updating different pages simultaneously. Finally, this paper did not address the issue of catastrophic recovery. As discussed in Srinivasan and Mogul, recovery is much simpler with a stateless server. The authors didn’t show how recovery is implemented in AFS.

A question raised by this paper is how an organization can choose the “best” file system to use for its applications. How can the tradeoffs between different file systems be judged by an organization? Should an organization consider the use of multiple file systems even given the substantially greater operational costs this imposes? These answers were outside the scope of this paper, but I’d be interested in seeing further research in this area.

Jerry Kruczek

[OS-FA08]:Howard88

2008-11-24T09:20:00.000-08:00

In this paper, a distributed file system Andrew file system is discussed. It is intended to span more than 5000 workstations in Carnegie Mellon University. Such a large scaling can affect performance and complicate system operations. Here a prototype implementation is described along with how Andrew scales gracefully. To demonstrate the importance of caching and whole file transfer in Andrew it is compared with NFS.

The main idea of building a prototype was to validate the basic architecture and based on the feedback design a better system.There were some performance degradation as expected,but it was not unifrom. To quantify performance penality, authors ran a series of controlled experiments with a benchmark was carried out.This helped them to evaluate various file system implementations.

Comparisons between Andrew and NFS were carried out by operating a set of experiments in NFS and another set in Andrew.The conclusions drawn from the observations indicate that Andrew is far superior to NFS when it comes to improved scaling. Also Andrew is implemented in user space whereas NFS is in kernel,there was a reduction in overhead when Andrew was moved to kernel,showing a potential for improved performance.

In this paer stess is given on the scaling feature of Andrew,however other features like security,network topology,hardware etc may also have an impact on performance. The changes suggested from experiments work well for about 500 to 700 workstations,but the goal of 5000 is still a long way to go. However authors state that they are satisfied with the present state of Andrew and believe that with further work,the goal can be achieved.From the time this paper was written and to this time,how much has been achieved in this area deserves much thought.

[OS-FA08]: Srinivasan89

2008-11-19T13:50:00.000-08:00

The paper deals with modifying NFS to use Sprite cache consistency protocols. In NFS, cache consistency, performance, and crash vulnerability are inextricably linked together. NFS requires
clients to write blocks immediately to the server; this writeback policy is necessary to maintain consistency, but performance is reduced. Through its consistency protocol, Sprite is able to separate performance from consistency, and thus improve both. The NFS write-through policy alsolimits the amount of data lost in a crash: Sprite allows clients to select this policy only when they need it. Spritely NFS borrows Sprite caching model to provide cache consistency for NFS.

My main objection to Spritely NFS is that it sacrificed the server’s statelessness. This would make it difficult for a client to recover from a server crash. As we see Crash recovery for Spritely
NFS wasn’t added until 6 years later, in 1994.

[OS-FA08]: Srinivasan89

2008-11-19T12:04:00.000-08:00

Spritely NFS was an attempt to improve the consistency of NFS. Spritely NFS implements caching on the client side. The server uses callbacks to allow caching of writes on the client side. This allows write backs of data from the cache when a read occurs. When multiple writers are present, writes happens immediately. We are unsure of the semantics of the Sprite File System and how it differs from Spritely NFS. Adding cache coherency seems to break the simple design goals of the early NFS versions (read, write).

[OS-FA08]:Srinivasan 89

2008-11-19T11:58:00.000-08:00

In this paper NFS is modified to use Sprite cache consistency protocols to improve the performance. NFS is a stateless server system ehich cannot manage client file caches. File caching is very important in improving performance. Sprite on the other hand has server state and an explicit consistency protocol and it offers better performance than NFS. In order to modify NFS,the consistency policy of Sprite is isolated from its other features. The modified system is called Spritely NFS. Authors here mainly try to answer two questions whether the superior performance of Sprite compared to NFS,result of its cache consistency mechanism and can NFS performance be improved by adding Sprite like features to it.

The modified NFS-Spritely NFS was then benchmarked,and the results prove that Sprite approach is superior than NFS,however it is not exactly due to the cache consistency protocol,but due to its delayed write-back policy.Though modifying NFS was not so difficult,it didn't produce the desired behavior,i.e SNFS didn't perform better than NFS as Sprite did. One of the reason for this maybe NFS has been used to give importance to performance rather than consistency. Even though memory and processor speeds are rapidly increasing,disk speed is still far behind,making caching of file an important factor in system performance. An efficient caching mechanism is becoming all the more important nowadays.

[OS-FA08]: Srinivasan89

2008-11-19T10:27:00.000-08:00

Spritely NFS is basically fighting against NFS write-through policy, which is reasonable, since write-through limits client caching benefits and needs synchronization with disk all the time. And the Spritely NFS did bring some good figures in terms of perfomance, such as CPU utilization, etc. However, from my perspective, Spritely NFS was not a complete file system, especially when it touches crash recovery, and the authors stated that "such (crash recovery) protocol could involve changes to both the client and server implementations, and would reduce performance to some extent", which makes me question the results in the paper, since I cannot imagine a server file system crash could bring down the whole network, fortunately, crash recovery was added serveral years later. There are trade offs that were involved with this paper: 1) performance vs correctness 2) write-through policy vs write-back policy, and both of them are of significance today.

Srinivasan89

2008-11-19T10:07:00.000-08:00

SUMMARY
“Spritely NFS” presents an approach to incorporating the cache consistency methods of Sprite into NFS in order to achieve the consistency of Sprite cache management while maintaining or improving the network file performance of NFS. As a stateless server system, NFS requires clients to physically write blocks to the server hard drive whenever the block is modified. In order to assure cache consistency, a client must periodically check if a file has been modified. NFS makes file recovery simple at a cost of poor performance and synchronous application behavior.

Sprite uses a stateful server which only writes data to a hard drive when a file is closed or a variable period of time elapses. Using explicit file opens and closes and limiting write access to a single client helps to enforce cache consistency. File recovery in Sprite is much more complex and involves activity from the client as well as the server. The benefits of Sprite are guaranteed cache consistency and better performance when a client’s computing is split evenly between CPU and I/O and when the application uses a substantial number of temporary files.

The authors incorporated the cache consistency methodology of Sprite into NFS and implemented their Spritely NFS (SNFS) on an experimental Titan workstation using a variation of the Ultrix O/S.

Their results using the Andrews benchmark and a sort routine showed that SNFS behaved as expected. When the /tmp directory was local to the client, elapsed time of the Andrews benchmark using SNFS decreased by 16% compared to NFS and by 22% when /tmp was remote. For the sort test, elapsed time dropped by 46% because of the large number of temporary files used by a sort.

OBSERVATIONS
The authors answered their two basic questions. Sprite’s performance improvement over NFS can be at least partially attributed to the differences in the way the two file systems handle cache management and at least some of these performance improvements can be transferred to NFS by porting Sprite cache management protocols to NFS without unduly increasing the complexity of the NFS implementation. Their explanation of the two cache management schemes was clear and most importantly, the tests run on their implementation seemed to accurately assess the performance of the two systems.

One issue that the paper didn’t address was the network used to support their tests and the effect the two file systems had on performance. The authors didn’t state if a heavily loaded network would reduce the performance of SNFS given its reliance on RPC. (I made the assumption that their tests were run on a network without any other users.)

They also did not implement crash recovery in SNFS. Since this is one of the key costs of Sprite, I would be interested in seeing how adding the needed crash recovery code to NFS would affect both the complexity and performance of SNFS.

Finally, on p.53, the authors assert that “there may be insignificant inaccuracies in the counts [of RPC operations]”. I’m always skeptical of papers that use terms such as “insignificant” to describe inaccuracies in a study. Why not give an actual measure of the errors?

ISSUES
I have two primary issues related to the development of SNFS. First, it forces clients to act as an RPC host. For security reasons, this may be undesirable. Given the relatively generic behavior of RPC, this might open the client to unauthorized intruders. While RPC can be secured as described in the Sandberg paper, this still represents another security administrative requirement and creates another security vulnerability.

The second issue is also related to security. Since the paper didn’t describe the network infrastructure, it’s impossible to determine if the RPC packets passed through a firewall. It’s possible that some network devices may block the transmission of RPC packets thus making it impossible for a client to connect to an SNFS file server on the other side of the firewall. NFS also uses RPC, but the packets seem to originate on a client with a server only sending a response. It seems that NFS servers do not need to initiate an RPC session to a client.

Jerry Kruczek

Srinivasan89

2008-11-19T09:48:00.000-08:00

The authors attempt to improve the performance of NFS by implementing a cache consistency protocol similar to that of the Sprite distributed file system. The primary improvement is that Spritely uses a write-back cache protocol instead of write-through. This helps the client take advantage of the fact that most files are temporary.

These improvements are good because they improve NFS's caching scheme. They are able to improve performance overall, although not on each individual benchmark. Using the write-back makes a lot of sense, because sending data to the server unnecessarily can be dangerous.

My first objection to this paper is that, by sacrificing statelessness and having the server send callbacks to the client, they are no longer remaining true to NFS. It actually becomes more like AFS.

My second objection with this paper is that, even when it was new, it was testing against an out-of-date version of NFS. They may have seen performance improvements associated with better caching and lack of a bug that hurts performance if they had used the newest version at the time. Today, NFS has a lot more options (such as an asynchronous mode, flexible block sizes and improved caching) that may render Spritely NFS even more unnecessary.

Lastly, they are changing consistency protocols, but they only run single-user benchmarks, which may also change the performance.

S.M. Niaz Arifin, Hoang Bui, Mike Olson

[OS-FA08]: Srinivasan89

2008-11-18T15:38:00.000-08:00

This paper described a modification to NFS which increases performance. Namely, it describes a way to add state to the NFS file system in such a way to provide a better caching system. This caching should increase performance, reliability, and correctness.

While the paper did conclude that their improved file system based on a hybrid of Sprite and NFS did perform well, their tests were, in my opinion, inconclusive. This is due to the fact that everything that they have tested is inconclusive. This is due to the fact their NFS implementation was out of date, and mutliple years old. Their implementation of SNFS was also incomplete, as it didn't have the crash recovery, and didn't implement the full functionality into the underlying filesystem. I am therefore wary of their results, as these factors and more could compound to give almost arbitrary results.

In all though, the results that they obtained were good. The new fs required less cpu utilization, better performance, and would theoretically be just as resiliant (if not moreso) to failure than vanila NFS.

Nightingale08

2008-11-17T14:17:00.000-08:00

SUMMARY
“Rethink the Sync” describes external synchrony, a new method of writing data to a hard drive while preserving the durability of synchronous I/O and the performance of asynchronous I/O. At the heart of the new method is what the authors describe as a change from an application-centric view to a user-centric view of operating systems. It seems their contention is that internal performance is subsidiary to the performance that’s seen by the user. The key seems to be the development of a “middleman” that separates the actual writing of the data from the acknowledgement that a piece of data has been actually written to disk.

The authors built the external synchronous file system which they called xsyncfs around the Speculator project developed in 2006. The two key improvements they made were adding a commit dependency and output-triggered events. In order to improve performance, they made two optimizations: handling multiple file modifications through an atomic commit and buffering screen output. They implemented the external synchronous file system on a Linux 2.4.21 kernel and for comparison with xsyncfs used the ext3 file system that could be mounted either synchronously or asynchronously.

While the authors provided no documentation, they asserted that xsyncfs provided the same durability as a synchronous file system with write barriers and better durability than either asynchronous or normal synchronous file system configurations. Three different benchmarks including one using MySQL showed that the performance of xsyncfs was less than 7% worse than asynchronous file systems and substantially better than the synchronous alternatives. They also showed that xsyncfs showed the same performance with shared memory applications.

OBSERVATIONS
The paper did a very good job of describing the goals and design of external synchrony along with the dual issues of durability and performance that must be addressed by all file systems. The results of the performance benchmarks were fully documented although I would have liked details on how they conducted the durability tests. One of the challenges in testing any form of malfunction, especially when the malfunction is externally caused such as in a power failure, is to make sure that the problem seems to occur at random if we assume that the problem will naturally occur at random. Also, depending on the internal operations of the hardware, it’s possible that simply “pulling the plug” to simulate a power failure might have different transient effects within a system. Finally, while they mention catastrophic media failure (p.6:7), there is no indication that they were able to test this event. Of course, simulating a media failure is extremely difficult.

The authors didn’t address any non-performance costs of xsyncfs such as software maintainability or memory usage. They also didn’t elaborate on any costs that might be associated with commit transfers between networked applications.

The results were very promising. Since this paper is only a few months old, it will be interesting to seem if xsyncfs becomes an accepted commercial file system.

ISSUES
I felt the paper raised two issues beyond the scope of the research. First, how far can user-centric views be extended? Is this the beginning of a new way of looking at computer design or is this a process that’s already reflected in developments such as client-server technologies? Should all O/S redesign be viewed not by measuring internal speed but by viewing its effect on the end-user, whether that be a human or another application?

Second, p.6:17 mentions “specialized hardware such as a nonvolatile cache”. If the performance of nonvolatile storage is improving while its cost decreases should the industry try to exploit this development in all places where temporary quick storage is needed? If we used nonvolatile cache with a hard drive, could we adopt solely asynchronous disk write methods with its maximum performance? I think even with nonvolatile cache, we would still need some O/S involvement to guarantee durability but it might provide a cheaper solution than xsyncfs.

Jerry Kruczek

Nightingale 08

2008-11-17T13:49:00.000-08:00

Clearly, generally speaking, asynchronous I/O has much better performance than synchronous I/O. However, it is usually considered to be unreliable. In this paper, the authors presented a new approach, which is called external synchrony to solve this problem. The new file system they developed was called xsyncfs. I think that is a promising technique. In particular, I think the idea of output-triggered commits is good. It tracks the causal relationship between xternal output and file system modifications, and then decide when do commit data. The system delays committing data until some external output is produced that depends on modified data. In a word, it seeks to find a balance between throughput and latency. Apparently it is much faster than traditional synchronous approach. The only thing I doubt is its necessity. Since power failure is extremely rare nowadays, I don’t think it is worthwhile to implement such a complicated file system at the cost of performance penalty. Since the main advantage of this technique is to prevent loss of data in the off-chance of a power failure, I think it would be more reasonable for us to develop some other fault-tolerant approaches.

[OS-FA08]: Nightingale08

2008-11-17T13:06:00.000-08:00

The authors of this paper seem to do a good job of describing their new file system, xsyncfs, and the advantages it presents over ext3. They provide some good data on the running times of xsyncfs versus ext3 in a variety of different situations, and explain why the results came out as they did.

The main problem that I had with this research is their lack of rigor. They explain the advantages of xsyncfs over ext3, but ext3 is nowhere near the state of the art of file systems. There are so many other file systems which do much better than ext3, (e.g. xfs, jfs, zfs, ext4 (beta)), and even just different file systems (e.g. reiserfs) that the authors just conveniently don't mention. While I'm not sure of the characteristics of these file systems in regards to what they're trying to measure, it seems incredibly disengenious to only use the oldest file system to benchmark against, when there are such better examples.

[Nightingale06] FALL 08

2008-11-17T12:52:00.000-08:00

The paper introduces a new technique for file i/o called external synchrony. This method combines the advantages of synchronous i/o with asynchronous i/o. An I/O is considered
synchronous if the calling application is blocked until after the I/O completes. The advantage of this is durability and disadvantage is a decrease in performance. In contrast, an asynchronous file system does not block the calling application, so modifications are typically committed to disk long after the call completes. Asynchronous I/O lacks durability but gives better performance. The aim of external synchrony was to achieve both good performance and durability in file i/o. It works by buffering all output that causally depends on the uncommitted modification.

The paper was well written and the method was evaluated reasonably. The authors did justice by listing the limitations in section 2.5. The complexity involved in maintaining a buffer of the output is well justified by the better performance and durability.

[Nightingale06] FALL 08

2008-11-17T12:22:00.002-08:00

The paper starts out by comparing synchronous and asynchronous I/O in term of performance and durability. Asynchronous I/O is fast because application is not block for I/O operation. However that makes asynchronous I/O unreliable because asynchronous I/O buffer write cache and out of order commits. On the other hand, synchronous I/O is durable but slow. Applications are forced to wait until data is committed.

Author proposed a “sweet spot” between synchronous I/O and asynchronous I/O in order to achieve acceptable file system performance while still guaranteeing durability. The new model for file system I/O is called external synchrony. The difference between external synchrony and synchronous I/O is that external synchrony guarantees durability not to the application but to the external entity that overlooks application output.

Authors developed a file system called xsyncfs. A synchronous I/O operation is logged to a file system transaction while control is return to the application without waiting for the operation to commit. A commit dependency is issued to the application, preventing it from outputting the result to external device such as screen or network. Xsyncfs uses the relationship between external output and file system modification to decide when to commit data. When there is no such relationship, Xsyncfs delays committing data within 5 seconds time out in order to achieve better throughput performance and to reduce latency.

Authors evaluated the idea by comparing xsyncfs with ext3 asynchronous, ext3 synchronous and ext3 synchronous with write barrier (disable disk cache to force write through). Only xsyncfs and ext3 with write barrier provide both durability and ordering, however there is no quantitative result to compare the performance between the two file systems. Other benchmarks show that xsyncfs has better performance than default ext3 synchronous file system and only 7%-9% slower than ext3 asynchronous file system. Since authors ran two separated benchmark for MySQL and Specweb99 , we are curious what the result would be if both the web server and database server are running concurrently in the same machine.

Mike Olson & Hoang Bui

[OS-FA08]: Nightingale08

2008-11-17T11:42:00.000-08:00

This paper is interesting, and it broke the tie between synchronous and asynchronous file systems, however, the basic idea behind it is not new at all. The first idea came to my mind after I read the first few sections is that it is the same idea as out of order execution in superscalar microprocessors. Yes, out of order, clear and sound, widely used in today's CPU, not just the idea, but the output-triggered commits, is it comparable to reorder buffer?, which is a queue for saving all the changes the cpu core can modify but once it reaches commit point, every change should be correct semantically. Another similar example of this is within data transaction management, where certain types of locks are used to control the granularity of data accesses. But out of all curiosity, the bottom line is to guaranttee correctness in order to gain performance.

[Nightingale] Fall:08

2008-11-17T10:06:00.000-08:00

External synchrony approaches the task of making file systems both reliable and low latency by synchronizing writes while prioritizing the user-centric view. The performance of xsyncfs is very close to ext3 asynch operation of ext3. The evaluation seemed thorough.
They use logical clocks so they can only provide a partial ordering of events. There is no guarantee of performance in a strict sense (eg. block size of 4096 bytes, write throughput is x). For some applications, guaranteed throughput may be necessary.

[OS-FA08]:Nightingale 08

2008-11-17T09:07:00.000-08:00

This paper discusses about a new model of local file I/O that can resolve the tension between durability and performance. The clash between performance and durability has led to the development of 2 models of I/O synchronous and asynchronous. A synchronous model ensures durability by blocking a calling application and provides clean abstrraction. However frequent blocking of applications can result in slow performance. On the other hand asynchronous file system does not block applications, but modifications are comitted long after a call is completed. This is fast,but not safe,as the data may be lost if system crashes or sudden power failure occurs.

This is where the new model becomes useful-external synchrony,it combines the advantages of synchronous system-reliability and durability and asyncronous system-improved performance. Using an external synchrony is all the more better as an external observer or user cannot distinguish between the output of a system with an external synchronous file system from the output of a system with synchronous file system. The model discussed here is an externally synchronous Linux file system,Xsyncfs. It uses output-triggered commits to balance throughput and latency. Output-triggered commit tracks the relationship between external output and file system modifications to decide when to commit data. Depending on the modified data,Xsyncfs may delay commiting to increase throughput. External synchrony is designed based on two principles-authors defined externally synchronous I/o by its external behavior rather than by its implementation and application state is defined as an internal property of the computer. However a limitation of external synchrony is that it complicates application-specific recovery from catasrophic media failure.

Xsynfs was created by modifying ext3,a journaled file system in Linux. In its default mode ext3 writes only metadata modification,whereas in journaled mode it writes both data and metadata modifications. Journaled mode is used as it guarantees ordering,that is if operation A precedes operation B,the effects of B should be visible only if effects of A are also visible. Authors evaluated xsyncfs using several benchmarks and the results are encouraging. It showed that performance of xsynfs is within 7% of the default implementation of ext3. Compared to ext3 mounted synchronously xsyncfs performance is up to two orders of magnitude faster.Also xsyncfs improves the performance of applications that do their own custom synchronization. Authors state their conclusion based on the results of checking under various benchmarks,overall this is a good paer proposing a better idea for building reliable software systems.

[OS-FA08]: Hartman 93

2008-11-12T12:34:00.000-08:00

This paper deals with Zebra, a network file system that provides greater throughput and availability. It does this by striping file across multiple servers.Striping distributes different pieces of data to different servers. Zebra system uses the techniques of both log-structured file system and RAID.A client collects all the data for its file into a sequential log that it stripes across servers. Using LFS technique improves write performance of small files and as well as for reads and writes of large files.The redundancy techniques from RAID are used to increase throughput and data integrity.Zebra stores a parity in one of the stripe, for the rest of the stripe,thereby allowing Zebra to operate while a server is unavailable or reconstruct lost data.RAID is a system architecture where many disks work to achieve improved performance and availability.

A prototype implementation of Zebra in Sprite system is also discussed. There are some performance benefits-the throughput is 4 times better than NFS or standard Sprite file system. For small files improvement is over 3%. Another feature of Zebra system is its scalability-new disks can be added and zebra's stripe cleaner recognizes this data to take advantage of increased bandwidth.Using ideas from RAID and LFS zebra can continue its operation while a server fails and manage parity for each stripe. On the whole Zebra system seems to provide better performance though several factors still need to be improved.

[FA08]Hartman 93

2008-11-12T12:24:00.000-08:00

Zebra was an approach designed to improve throughput using a distributed file system, combining ideas from RAID and LFS.
Several design decisions could cause reliability issues. First, the storage of file system metadata on one server seems problematic. They didn't implement all of the automatic error recovery features they discuss. They speculate on benchmark outcomes without performing them. The reliability gained by striping and parity is probably offset by the system's reliance on specific server for metadata, and the inherently unreliable nature of distributed systems. They did not discuss fault tolerance in terms of n replicated nodes to ensure data access.

[OS-FA08]: Hartman93

2008-11-12T12:10:00.000-08:00

Zebra utilizes two basic ideas borrowed from log-structured file systems (LFS) and RAID.

It uses the LFS idea with some modification: each client forms its new data for all files into a sequential log that it stripes across the storage servers. This allows even small files to benefit from striping, as well as large files (the latter being a performance benefit of LFS itself). It also reduces network overhead, simplifies the storage servers, and spreads write traffic uniformly across the servers.
Zebra uses redundancy techniques from RAID disk arrays to improve availability and data integrity. RAID is a storage system architecture in which many small disks work together to provide increased performance and data availability. In Zebra, one of the fragments of each stripe stores parity for the rest of the stripe, allowing the stripe’s data to be reconstructed in the event of a disk or server failure. It distributes file data over several file servers while ensuring that the loss of a single server does not affect the availability of the data. It can reconstruct the lost data even if a disk is totally destroyed. Thus, RAID technology allows Zebra to provide scalable file access performance while using parity instead of redundant copies.

The three comments we have on this paper:

Though RAID was comparatively new while Zebra was born (1993), today we have various levels of RAID (i.e. RAID Level 0 to RAID Level 6). It would be interesting to see how the other levels affect Zebra's performance.
The paper avoided discussing the case for small reads. The way Zebra works, a client needs to send a read file request to the file manager for each file to read, potentially turning the file manager into a bottleneck. In fact, the open and close RPCs are the major bottleneck for small writes. It would have been interesting to see how the performance is affected by small reads.
The experimental setup was, in our opinion, not broad enough in terms of some parameters. For example, it would be nice to learn how Zebra behaves (e.g. with respect to cleaning/fragmentation performance) if the time span (on which the experiments were done) was stretched longer.

By S. M. Niaz Arifin, Mike Olson and Hoang Bui

[OS-FA08]: Hartman93

2008-11-12T11:56:00.000-08:00

Zebra is a network file system, and it is an extension from log-structured file system, and it provides further improvement in terms of large files read/write speed and network support. And such improvements were made possible by per-client file striping, which in return use parity for crash recovery.
The most interesting part of Zebra is its network file system support, which utilized RAID concept but with dynamic storage server management, but it did have problems like cache consistency when multiple processes share the same file, stripe cleaning, etc. From today's perspective, there are a couple of potential solutions which can benefit Zebra, such as copy on write mechanism for file sharing, etc.
All in all, Zebra provided higher throughput, availability and scalability, than log-structured file system.

Hartman93

2008-11-12T09:04:00.001-08:00

SUMMARY
“The Zebra Striped Network File System” by Hartman and Ousterhout combines the throughput and redundancy benefits of RAID with the performance benefits of LFS. Client files are written through logs similar to LFS but the data is striped across numerous storage servers to provide a greater bandwidth than can be offered by a single disk controller or even a SCSI bus. Parity is used to insure that a file is readable even if one of the storage servers goes down. Mechanisms are also developed to insure the all aspects of a write operation are complete before a piece of data is considered validly written. Two additional servers are specified—a file manager to manage the storage of metadata and a stripe cleaner to free up fragmented disk areas.

A prototype of Zebra was developed using on DECstation 5000 workstations using the devices for clients, storage servers, file managers and stripe cleaners. Preliminary (p.39) performance measurements were made using the prototype and comparing the results to NFS and the Sprite LFS. Some comparative descriptions were also given contrasting Zebra with FFS. The results showed that Zebra performed 4-5x faster for large file writes and 20-300% faster for small files.

The prototype did not implement most redundancy mechanisms so the results did not show the effects of these mechanisms nor their success in preventing loss of data. The sole exception was the result labeled “1 client (recon)”.

OBSERVATIONS
While the paper provided a possible starting point for a more effective file system, I felt there were several omissions which made its practicality still questionable. First, since the prototype contained only limited capabilities for redundancy, it’s impossible to gauge how much full fail-safe implementation would affect file system performance. It’s also impossible to determine if these mechanisms would work under a normal work load given potential types of failures.

The tests were very limited in nature and did not seem to reflect a real world scenario. Would the Zebra File System be able to keep up with high-volume demand?

Other than one statement on p.39, there is not data concerning the effect of the file system on network performance. The description seemed to indicate that the servers were connected via a dedicated 100Mbps FDDI ring. Do the authors recommend a dedicated SAN for Zebra? If not, what type of network demand does the file system put on a shared network? How would the file system performance over Ethernet with its latencies?

Client cache consistency should be a major issue, but the paper virtually dismisses the question in a single paragraph (4.4).

Finally, on p. 37, the authors state that stripe inconsistencies can be eliminated by storing “a simple checksum for each fragment”. Was that implemented in the prototype and if not, what would be the cost of the additional write. Where would the checksum be stored?

ISSUES
The Zebra File System represents an interesting way to expand upon the LFS. It provides a possible direction for future SAN development, taking network file storage in a different direction than that used by normal network file servers. A search on the web seems to indicate that work is being done on the Zebra File System assuming tools such as the Zebra Disk Array by Addonics is using a Zebra-like file system to store data across an array of disks.

Rosenblum92

2008-11-10T14:59:00.001-08:00

SUMMARY
The paper by Rosenblum and Ousterhout describes a new way in which an operating system can manage the orientation of a file system in order to improve application performance. The paper begins with a great discussion describing the problems caused by improvements in CPU performance and memory capacity without commensurate improvement in the performance of disk systems. It points out that while disk capacity has been growing, transfer bandwidth and access time have been improving at a slower rate than CPU speed. While bandwidth can be increased through technologies such as disk arrays, there is no easy way to increase the speed with which a head locates a particular sector on the disk platter. There are two results of these non-parallel improvements. First, applications are becoming disk-bound as the systems are unable to make full use of CPU power as they continually wait for disk I/O. Second, the increased amounts of memory can be used for greater sizes of read cache which increase the likelihood of a read operation finding the data in memory. Unfortunately, since disk writes must occasionally be physically written to the hard drive, increased memory means that most physical disk activity is in the form of writes.

The authors developed a log-structured file system (LFS) where all disk sectors are laid out in a sequential fashion rather than spread throughout a disk platter. While it greatly increases the actual efficiency of a disk write, this log-structured file system requires large contiguous areas of free disk space. In order to provide those areas, the file system must periodically clean up fragmented areas on disk.

The paper uses results from a disk simulator to verify that the log file system is more effective than the Unix Fast File System in reading and writing files including both small and large disk files. It also provides evidence from a small real world implementation that verifies the effectiveness of the LFS.

OBSERVATIONS
I thought the authors’ description of the issues surrounding improvements in CPU speed, memory capacity and disk performance were fascinating. Although the paper was published in 1992, many of their observations seem valid even 16 years later. They did a very good job of combining high level concepts with technical details to provide an excellent picture of a log-structured file system. In particular, I liked their discussion of write costs—a way of comparing the efficiency with which different file systems complete write activity. They also did a good job of describing the need for building recovery in the file system to reduce the amount of data lost in a system crash.

The paper also highlighted that writing a single piece of data often requires five separate write activities considering inodes, metadata, directories and the data itself. File systems such as FFS often spread that information across one or more disk platters which results in substantial disk activity before the data is truly written to the hard drive. This both increases the I/O activity required for the write as well as increases the duration during which a system crash will result in only a partially-completed write.

The authors seemed to perform only limited testing on an implemented form of their file system and provide only limited information on the tests they did perform. For example, they use a disk simulator in Section 3.5 to confirm their analysis of Write Costs. However, they do not provide information about the nature of the simulator or the loads that the simulator uses to create the results in Figure 4. (It’s possible that the simulator was a well-known tool in 1992.)

Their results in Section 5 seemed confined to one micro-benchmark and they provide limited information about the files, file accesses, users, types of activities, etc. that are involved in the benchmark. It may be that they were looking at the benchmark to provide proof-of-concept and not a rigorous analysis of the usefulness of LFS.

ISSUES
Despite the limited testing, I believe the authors did show that it was beneficial to investigate different types of file systems. In particular, their initial analysis showed that non-symmetrical improvements in system components could result in systems not achieving the complete benefit of improvements in CPU or memory. Even though the authors contend that “no major improvements seem likely for access time” (p.28), I was wondering why disk manufacturers haven’t spent more time and money seeking to decrease this important aspect of computer performance.

This paper also raises the question of whether a file system should be considered a discrete part of a computer system rather than a device that must be controlled by an operating system. Should a file system be a “black box” that receives a request from an operating system and then returns a result? The black box file system would be responsible for everything from caches to disk speeds to drive geometry. In that way, CPU cycles wouldn’t be needed for manipulating inodes, performing defragmentation operations and other file-system related tasks. The black box could be optimized for just file system tasks.

It seems that log-structured file systems are once again being investigated. LinLogFS, NILFS and LogFS are examples of log-structured file systems that have been implemented in the past few years (http://en.wikipedia.org/wiki/Log-structured_file_system).

Jerry Kruczek

[OS-FA08]: Hartman93

2008-11-10T13:37:00.000-08:00

In this paper the authors talked about an extension to the LFS discussed in the last paper. Their extension turned it into a distributed file system, which allowed for higher throughput than the standard techniques by turning a bunch of file servers into one logical server from the clients perspective.

While overall I thought the paper was good, I am concerned that they didn't actually solve one of the main problems that they pointed out, namely that of a "hot" server which handles to much of the workload. The reason I feel this might still be a problem is that all file accesses must still go through a single server. This defeats the purpose of distributing the data (to some extent), and I don't think this was adequately addressed.

I also find it interesting that the authors didn't take into consideration how much larger hard drives were getting, and consider "the Google approach" to distributing files. That is, instead of using RAID to store parity for each stripe written, instead just save all data to n hard disks, where n is sufficiently large such as to avoid the likelihood of catastrophic failure of all n disks. Their approach does make some sense, however, in instances where hard drives are still around a gigabyte and space is expensive, as it provides vastly improved performance over the other techniques mentioned in their benchmarks.

[OS-FA-08] Rosenblum 92

2008-11-10T13:06:00.000-08:00

This paper described a new type of file system, called a log structured file system. The main advantage of a log structured file system over the implementations of the time is the caching of writes, and the policy of writing data in a temporal fashion, as opposed to logical.

While this paper was the first to develop an entire file system from a log structure, logging was not a new concept in the file system community. The other implementations, however, used logging to help recover from crashes, while the authors used it as the basis of their entire file system.

Their solutions for the two main problems faced when writing such a file system (file location and free space management) were very clever. I was surprised to see that they assumed that cleaning "hot" files would be more productive at first, as their conclusions were more along with what I have assumed. Namely the price paid to clean short lived files would be compounded by the fact that those files were quickly overwritten/deleted, and thus the space would be freed normally.

In all it was an interesting paper, and one that gave good insights into the challenges faced in the early 90s when developing a new file system.

Rosenblum92

2008-11-10T12:57:00.001-08:00

The paper describes an attempt to create a file system that was a whole deal more efficient than existing file systems. The idea was to use log-structured file system which writes all modifications to disk sequentially in a log-like structure, thereby speeding up both file writing and crash recovery. The log is the only structure on disk; it contains indexing information so that files can be read back from the log efficiently. In order to maintain large free areas on disk for fast writing, they divide the log into segments and use a segment cleaner to compress the live information from heavily fragmented segments. They implemented a log structured file system called SpriteLFS. It outperforms current Unix file systems by an order of magnitude for small-file writes while matching or exceeding Unix performance for reads and large writes.

One possible criticism of this technique is that it speeds up only the write operation and not read operations. It assumes that read depends on caching and proceeds to assuming that all the time taken is for writing. This is not true especially while reading very large files. But it is also worth noticing that Sprite FS introduced reliability and crash recovery.

[OS-FA-08] Rosenblum 92

2008-11-10T12:44:00.001-08:00

In this paper, the authors mainly discussed some techniques to improve system performance by shorten the time spent in writing data to disk. By using cache, the time spent in read can be shortened, so how to prevent wasting a lot of time in writing is a critical issue. In this paper, the authors suggested using a log-structured file system. The basic ides of this technique is to reduce the number of disk write operations by storing a sequence of file system changes in the cache and writing all of the changes to disk in one operation. Apparently, since the time spent in reading is the same as traditional systems, and the time spent in writing has been cut, the total system performance would be improved.

However, this technique requires enough space on the disk. Threading and copying are used to ensure that there is enough free space on the disk. Threading would make the free space severely fragmented, which will impair the system performance. I think copy and compact is a better approach. Windows operating systems also provide this useful tool.

Crash recovery is also an important issue. Because to determine where the last changes were made is very difficult, so for traditional UNIX file systems, the recovery is very time consuming. But for the log-structured file system, it is relatively easy, because we just need to look at the end of the log.

[FA08]Rosenblum 92

2008-11-10T12:04:00.000-08:00

The paper implemented a log structured file system. The paper was well written. They improved performance over the FFS file system to approximately 70% disk utilization. The main challenge was to come up with an appropriate cleaning policy. Sprite LFS optimizes disk read and write use by storing file system structure information sequentially rather than spread throughout the disk as in FFS. The authors tested the Sprite LFS system thoroughly and acknowledged when their simulations were overly optimistic and overly pessimistic.
One remaining question is how does the file system react with workloads that stress the file system to the point where the cleaning process was inhibited or CPU load starves the cleaning process from running.

[OS-FA08]: Rosenblum92

2008-11-10T10:22:00.000-08:00

Log structured file system can improve write performance by collecting large amount of new data to write them in a single large disk I/O operation, which is good for sequential write and read according to the results in the paper. Furthermore, log structured file system can provide certain levels of crash recovery as well. However, there are also limitations in this approach, such as overhead from segment cleaning, etc.
But there are a couple of things bothering me: 1) high disk bandwidth utilization does not imply better overall system performance, a failing paging mechanism or even caching mechanism can increase disk bandwidth dramatically, but I assume the paper used the same paging or cache mechanisms for both its baseline and Sprite LFS; 2) this paper stressed too much on write performance improvement, especially for sequential writes, and in some sense it isolated writes from reads, even though it has random read/write test in figure 9, intuitively, sequential writes/reads should perform the best for log structured file system, but what if reads and writes are interleaved and there are data dependances between the previous writes and the later reads? in this case, we cannot put all the writes in a single log if the later read is not in cache/memory.
All in all, there are problems with this approach, however, log structured file system has a queue (log) between memory and disk, which could improve write bandwidth usage, nevertheless, it can even perform better if it can handle interleaved read/write operations effciently, such as forwarding the latest values in the log (but not in the cache/memory) to later reads.

[OS-FA08]: Rosenblum 92

2008-11-10T09:30:00.000-08:00

This paper deals with a new disk management scheme called log structured file system. It is based on the assumption that increasing memory sizes will make caches more efective.This system writes all modifications to disk in a log like structure. The log structure is sequential in nature and this helps in faster crash recovery.One of the challenges involved in efficient operation of log-structured file system is ensuring enough free space. The solution presented in this paper is largely based on segments. Here a segment cleaner which produces free space by compressing live data from heavily fragmented segments. The log is threaded on segment-by-segment basis,such that if the entire live data can be collected into a segment then that segment can be skipped and ther is no need to copy again. The size of segment chosen should be large enough so that the whole-segment operation can be run at full bandwidth of disk.

The authors have implemented a prototype log-structured file system called Sprite LFS,its performance for small-file writes is better than UNIX. For reads and large file writes it matches or exceeds UNIX performance. Sprite LFS use 70% of disk bandwidth for writing while UNIX file systems use only about 5%. Sprite LFS use segment sizes of 512 kilbytes or 1 MB for efficient usage of disk bandwidth.

Segment cleaning is a process that copies live data from segments. In Sprite LFS segments are read into memory,then live data is identified and copied to smaller segments. After this,segments that were read are marked clean. This method of cleaning in Sprite LFS saves memory and disk space and eliminates free block list and bit map and this simplifies crash recovery.

The authors built a file simulator to analyse cleaning policies under various conditions.Files are divided into 2 categories-hot and cold. One set has 10% of files,it is called hot as 90% of its files are selected. Other has 90% of files but only 10% of it is selected,making it cold. Some of the results showed that with locality system performed worse. Another observation is hot and cold segments should be treated differently. Also free space in cold segment is more valuable than its counterpart.

Simulation results and Sprite LFS suggest that the problem of obtaining free space can be solved by a simple policy based on cost and benefit. Though log-structured file system was developed mainly for small files it worked well for large ones also and there was no cleaning overhead for large files. Authors state that log-structured file system uses more disk bandwidth and thus it can take advantage of faster processors but in the present time of fast processors why then we don't find much log-structured file systems.

Rosenblum92

2008-11-10T08:16:00.000-08:00

This paper describes a file system that is based on writing changes sequentially to a log, rather than trying to actually write the whole file to a disk. Instead of keeping maps of where each file lives on the disk, it keeps track of changes to the disk.

Sprite LFS uses an indexed inode map to keep track of the locations of the files for reading. In this way, you can find a file for reading with less indirection, so it will be as or more efficient for reading than Unix FFS.

For writing, they explore the various ways that free space can be managed to make writing as efficient as possible, and explore the following two questions:
-Which segments should be cleaned?
-How should blocks be grouped when they are written out?

They find several interesting results. For example, they find that layout policies with a lot of locality perform worse. This is because when there is a lot of locality, segments get reduced to "cold" status much slower and don't get cleaned out by the cleaning routine as quickly, so a lot of data tends to hang around, so they had to create a policy that accounted for this fact.

One problem with this paper is that they explicitly say the benchmarks they used to measure are not realistic. However, this may not be a very big deal because they "illustrate the strengths and weaknesses of the two file systems".

They also did not consider the overhead of the cleaning function in their primary results, which probably gives an overly generous result, but the results will still pretty good when they took the cleaner overhead into account.

We were concerned that the cleaner process would have to do a lot of copying, and they did not give a very good explanation of how they decided which files to be cleaned. It will also probably use a lot of memory to maintain all these data structures, which they do not address.

The logging system seems like a good idea for crash recovery at first, but when they say that they assume it's OK to lose a small amount of data (say from the last 30 seconds to a minute), which may not hold true for certain applications.

We wondered if there was something about this idea that did not work that was not obvious from the paper, because it seems like a lot of log-structured file systems have been attempted, but few have caught on (See Wikipedia page on Log File Systems).

Mukusick 84

2008-11-05T13:48:00.001-08:00

In this paper, the authors described two different file systems, i.e. the old 512-byte UNIX file system and BSD. Considering this paper was written in 1984, some of the techniques discussed in the paper may not seem to be “new”, as what they claimed in the paper. For example, the cylinder group they discussed in the paper is considered to be a normal approach today.

The authors mainly focused on how to implement larger blocks. It is very important to optimize storage utilization. The advantages of larger blocks are apparent. By increasing the size of blocks, we can increase the file system throughput. However, that may lead to a waste of space. As we can see in Table 1 in the paper, when use a block of size 4096 byte, nearly half of the space was wasted.

The authors solved this problem by dividing the blocks into fragments. By doing so we can reduce internal fragmentation. Besides, the authors also employed some other techniques to improve system performance. For example, they increased the locality of reference to minimize seek latency, and improved the layout of data. I think these approaches look reasonable. And their output also demonstrated the effectiveness of these approaches.

[FA08]McKusick 84

2008-11-05T13:09:00.000-08:00

FFS was implemented on the VAX11. The earlier iterations of the Unix file system failed to take into account the hardware properties of the hard drive and "hid power" from the OS. Allowing the OS to schedule read and write requests proved to result in an almost 50% utilization. They introduced the concept of defragmentation and internal block fragments to emulate smaller block sizes with one fixed block size on the file system.
We are wondering what aspects are still relevant today. We think the notion of fully exploiting hardware properties to improve performance is a valid observation and something that should be taken into account when developing any OS drivers.

[OS-FA08]: Macusick84

2008-11-05T13:01:00.000-08:00

This paper discussed a reimplementation of Unix file system, and it introduced valuable ideas of configurable block size for each file system in the same operating system, cylinder groups for better block organization, fragments for reducing space wast with blocks, file system parameterization for optimal file system configuration based on cpu speed and disk characteristics, layout policies for optical block placement based on cylinder groups, larger file support with limited level of inodes, etc. And the performance improvement from the reimplementation was obvious. And the new file system has more contributions in terms of long file name support, file locks, symbolic link, file renaming, quotas, etc.
The first impression is that this paper has laid down some serious ground work for file system development, especially in those ideas and contributions list above, amazingly enough, most of those areas are still active research topics. However, from today's perspective, file system tends to be large, distributed, etc, which could incur more complications, therefore, a reevaluation of today's file system could be potentially beneficial for further file system development.

McKusick 84

2008-11-05T12:57:00.000-08:00

The paper talks about improving the Unix file system which existed. The use of variable block segments to improve the file system throughput was interesting. Blocks were now larger, but segments could now vary according to the size of the file. Reading larger files showed performance improvements. Another improvement in the file system was in reliability. By storing redundant information appropriately, any single track, cylinder or platter can be lost without loosing all copies of the superblock. It is interesting to note that the paper introduced many features like file locking, long file names, symbolic links etc which are being used even today.

[FA08] McKusick 84

2008-11-05T12:09:00.000-08:00

The paper started with the description of the Old File System and its limitations. A super-block holds the basic description of a file system, which includes a pointer to a linked list of free blocks. A file is represented by an inode and one or more fixed size blocks (512 byte block). The Old File System is inefficient because the block size is small which means more trips to the disk to access indirect blocks, especially for large file. The list of free block becomes fragmented as files are created and deleted. Consecutive blocks of a same file are scattered across the disk. In that case, each block access suffers an overhead cost of an expensive seek.

One of the quick fix is to increase block size. However, increasing the block size to 4KB introduces 45.6% of disk space because of internal fragmentation. The file system studies we discussed on Tuesday showed the domination of small files’ percentage. No matter how small a file is, it still requires a 4KB block. The New File System introduced a notion of segments. Block can be broken down in to 2, 4, or 8 addressable segments. A small file can be stored in a segment instead of a block, thus cut down the waste space causes by internal fragmentation. New File System also organizes disk in cylinders, blocks from a same file are allocated in a same cylinder to improve the locality and reduce seek time.

The experiments were conduct in one month old systems and showed the performance improved significantly compare to the Old File System on both read and write through put. The CPU utilization also increased. The CPU utilization percentage increased more in write benchmark because the CPU have to figure out which segment or block to allocate. The last section described functional enhancements of the New File System. They were long file names, file locking, symbolic links, rename and quotas.

The paper made a claim that the performance of the New File System did not degrade overtime. However there was no performance result to back up that claim. We would like to see the performance comparison over a longer time period for example: from the beginning, after 1 month, after 2 month, etc. The paper also mentioned that using 512 byte and 1024 byte segments reduce the waste space percentage to the level of 512 byte and 1024 byte block size respectively. However, there was no data to support the claim. We agree that bigger block size help with the performance, especially sequential read/write. However, the performance for many small write at the end of file should yield a worse performance than the Old File System. In many case, the New File System has to allocate a new block, and copies the old segmented data, and writes new data to the new block. Thus it causes data has to be written twice. Lastly, when a file system is created, user has to specify block and segment size. If user wants to change those parameters, he or she has to rebuild the whole file system. We wonder how long that process would take.

Niaz Arifin, Mike Olson, Hoang Bui

[OS-FA08]: McKusick84

2008-11-05T11:59:00.000-08:00

This paper discusse a new fast file system for UNIX.It also deals with the motivations,the ideas behind design decisions,summary of the results obtained.The old 512-byte file system was not able to provide the data throughput needed by some applications.This led to think of a file sytem that provides higher bandwidth than the original 512-byte file system.The first work on UNIX file system was to increase the throughput and reliability. On changing block size from 512 to 1024 there was an increase in file system performance. However there was one problem with large block sizes-as UNIX file systems are made of small files this led to wastage of space. The new file system developed, was able to overcome this hurdle by storing small files in an efficient way.

Two ways to improve file system performance are to improve the layout of data to make larger transfers possible and to increase the locality of reference to minimize seek latency.Every file has a descriptor called inode-it contains details regarding ownership of the file,time it was last modified,access times of the file etc. One such allocatable resource is inode and the global layout policy utilizes inode to achieve larger transfers. Another feature of new file system over the old one is that transfer rates do not change over time. The percentage of bandwidth shown in the table in paper is a measure of the effective utilization of the disk by file system.Also both reads and writes are faster in the new system.One drawback of the new file system is that it requires data to be moved from disk buffers during memory to memory copy operation.
On the whole this is a good paper giving a clear description of the traditional file system in UNIX and the improvements of the new file system.

[OS-FA08]: McKusick84

2008-11-05T11:51:00.000-08:00

This paper described one of the first modifications to the original UNIX file system, which was added into BSD 4.2. It gave a very in depth review of the design decisions that went into the new file system, mainly based on their observations on file system usage.

Overall their explanations were very good. They made very good points as to how file systems are used, and realized that the performance penalties that the UNIX file system were suffering from was not inherent to the interface, mainly to their implementation. This meant that their implementation could be immediately plugged into any system without requiring a total rewrite of the underlying code. This is a major gain for any project.

I was, however, disappointed with the performance information which was given. While it seemed extremely good, I am a bit wary of drawing any conclusions as they give no explanation of the data sets used. Since there is no way to tell if they optimized their tests for their scheme, it is unclear whether their technique is as amazing as they claim it to be.

Overall it was a good paper which gives a very good history of the state of file systems in the mid 80s.

McKusick84

2008-11-04T23:37:00.001-08:00

SUMMARY
“A Fast File System for UNIX” describes a file system developed in 1984 (before the findings in the Ousterhout paper) as an improvement to the UNIX file system then in existence. I believe this file system is identical to the one tested in the Ousterhout paper as 4.2 BSD. Its goal was to increase the bandwidth available to applications running on UNIX. The major changes introduced by the new file system to accomplish this goal were:
--A larger block size (4096 bytes)
--The ability to subdivide a block into fragments
--A more flexible way to handle Inodes
--Cylinder groups to optimize the placement of blocks on a partition
--Global and local disk allocation policies
The validation consisted of calculations and empirical studies that were done on a single variety of computer using an unspecified series of test programs. They showed that the new file system achieved its primary goal by increasing the bandwidth by a factor of 10 without any calculated increase in the wasted or unusable disk space.
The new file system also introduced some improvements independent of performance including long file names, file locking, symbolic links, a better way to rename files and disk quotas for users.

OBSERVATIONS
The paper focused on the design of the new file system rather than exhaustive tests of its performance. The data it presented did indicate that it met its goal of higher bandwidth, but it would have been interesting to see the tests run on a variety of CPUs using a wide variety of workloads. (I would also have liked a better description of the workload that was used.)
I thought the paper did a good job of explaining the concepts of the new file system and the way the concepts were implemented; however, it seemed somewhat inconsistent in providing technical details. For example, on p.195, it states that “lock files can never be left active after the processes exit or if the system crashes” but doesn’t describe how this is actually accomplished.

ISSUES
The paper explained the motivation for the changes made in the original UNIX file system. I would like to know what research was done to identify the problems that 4.2 BSD UNIX was designed to fix. The authors also didn’t state if they had a target level of improvement that they tried to reach. While a 1000% improvement in bandwidth is significant, there was no indication if this was enough improvement.
Table IIa and IIb have a column labeled “% CPU” but the paper didn’t explain what this was measuring or its significance.
Finally, the way they implemented file locking was interesting to me. I believe this is similar to the locking that was used by early releases of Lotus 1-2-3 to prevent simultaneous updates to the same spreadsheet. My experience with this mechanism is that it was often flawed so the locking file stayed locked even after the associated worksheet was released.

Jerry Kruczek

[OS-FA08]: Ousterhout85

2008-11-03T13:16:00.000-08:00

This paper does a good job of presenting the typical use case for (an older) server-type operating system. Some of the conjectures made (e.g. about the usability of optical disks as backup as opposed to magnetic storage) turned out to be not necessarily true, however this doesn't detract from the paper.

Importantly this paper discusses the general use case of files from a user perspective. The authors determine that most files accessed are small, and short lived. This lead the authors towards a better understanding of how cache size effects file accesses, and how different cache policies (i.e. write-through versus delayed-write versus everything in between) effect performance. They then discuss various problems with each approach, and how they affect usability.

The one thing they say which is interesting is that bandwidth will not be the limiting factor to a network file storage. The authors say that since most files accessed are small, that the small data sent is not a problem. The problem they failed to account for was growing file sizes as computers became larger and larger. This was further exacerbated by the explosion of multi-media, and the large file sizes typically seen for such files. For most cases, however, their claim remains true even today. The problem is bandwidth isn't the killer for file access, latency is. Thus the argument of whether or not there is enough bandwidth seems to miss the point.

[Ousterhout85]

2008-11-03T12:29:00.000-08:00

Ousterhout collected file system trace data from UNIX 4.2. They presented several important observations. The majority of file accesses are to small files. 20-30% of files are deleted within 30 seconds. One interesting note is that block size is 4KB and the default today is still 4KB for Windows and Linux.
One potential problem is that they didn't capture file system meta data accesses and took an educated guess on their expected behavior. Overall the papers were well written and presented a lot of data typically expected in a file system study.

2008-11-03T12:25:00.000-08:00

[OS-FA08]: OUSTERHOUT85 & BAKER91

In the OUSTERHOUT85 paper, the authors performed a trace-driven analysis on the UNIX 4.2 BSD file system. The main goal was to investigate the network bandwidth requirement, file access patterns and cache organization effects. They ran a reference pattern analyzer and a cache simulator. The first one collected trace data on three different timeshared VAX systems, and they analyzed it to see the file system activity, file access patterns and file lifetimes. The second program performed a disk-block cache simulation by varying the cache parameters such as the cache size, write policy and the cache block size.

The major findings are as follows:

Individual users don't use much file data on average, meaning that the network bandwidth will not be a limiting factor in building network filesystems.
Most file data is deleted or replaced within a few minutes of creation.
Most files accessed are short, though long files account for a large fraction of the data transferred;
File accesses tend to be highly sequential; and file system activity is bursty.
Large disk caches with large blocks result in substantial reductions in disk I/O, and occasional flush-backs provide safety against crashes without destroying the benefits of the large caches.

The BAKER91 paper is a logical extension of the previous one, performed after six years at the same place (UC Berkley). It analyzed the same aspects (e.g. user-level file access patterns and caching behavior) on the Sprite distributed file system.

The first part just repeated the OUSTERHOUT85 study, and found that file accesses show many of the same trends as mentioned above. However, the two major changes they found are:

File throughput has increased by a factor of 20 to an average of 8 Kbytes per second per active user over 10-minute intervals. Also, as Sprite supports it, they found that the use of process migration for load sharing increased burst rates by another factor of six.
Sizes of large files in 1991 are more than an order of magnitude larger than those in 1985. Large files account for much of the increase in throughput and burstiness, and they stress many parts of the system, such as the file caches.

They also found that the overheads for implementing data consistency are low, since write-sharing occurs for a tiny fraction of all file accesses. Also, performance of different cache consistency mechanisms greatly depended on the particular application mix. Lastly, they found that process migration did not seem to degrade the performance of file caches or increase cache consistency overheads.

Our comments on the above file system study are as follows:

It would be interesting to learn about similar studies performed during the more recent years, probably on (other) different types of machine architectures and computing environments (e.g. Windows).
The advent of Internet has invaded almost every computer application, and raised numerous sources of network traffic over the past several years that increased the network data volume by several orders of magnitude. It would be interesting to see how this affects the file system performance with the presence of these factors.
The question of generalization of their results to other networked systems is not settled, and perhaps does not have any definitive answer, since it would largely be affected by the particular application mix.
The selection of user groups might have a deeper impact nowadays on the system performance, considering the fact that computers are now used in hundreds of more problem solving areas by substantially more different types of users than 30 years ago.
The conjecture that "most files accessed are short" would not be true these days when the machines are having increasingly larger amount of main memory, avoiding the need of writing those small files to disks. It would be interesting to see how the access pattern varies with respect to this.

By S. M. Niaz Arifin, Mike Olson and Hoang Bui

Ousterhout 85

2008-11-03T09:59:00.000-08:00

In this paper, the authors measured the performance of the UNIX 4.2 BSD file system. The authors mainly focused on the following aspects: network bandwidth, file access patterns, disk block cache organization and management and cache performance. I think the most valuable part of this paper is their analysis of cache in BSD. They did a comprehensive analysis of cache using a cache simulator. The data they got is very important for the design of computer architecture. I also like some other parts, such as network bandwidth, etc. Using these techniques, we can optimize the system performance and maximize the effectiveness of the system with the minimum cost. Considering the face that this paper was written over twenty years ago, the authors were really far-sighted.

[OS-FA08]: Ousterhout85

2008-11-03T09:15:00.000-08:00

This paper uses trace files to analyse the UNIX 4.2 BSD file system.
A series of measurements were made on the file system to gather
information
that would be useful in designing a shared file syetem for a network
of personal workstations.User level activity in trace files were
recorded.
This analysis showed that most of the files accessed are open only for
a short time. Also the average file system bandwidth per user is very
low.
Most files are accessed sequentially and are usually overwritten
or deleted soon after its creation.They also predicted the performance
of caches
for disk blocks by a simulator that uses traces.

It was found that disk traffic was reduced by 50% when moderate-sized
caches were used. On using larger caches(of several megabytes) there
was a
redution of about 90%.Two programs were written to process the trace
files: a reference pattern analyser and a block cache simulator. The
results
obtained are stated above. To reduce the volume of data,file system
related
events were recorded at logical level.

The paper suggests that network bandwidth is not a limiting factor in
building networks as average bandwidth per user is very low. The
results
of the measurments done confirm some suppositions like most of the
files
accessed are short, file system activity is bursty etc. As block sizes
becom larger and
disk block cache becomes more effective,then I/O for things other than
file data
becomes an important factor in overall file system performance.

[OS-FA08]: Ousterhout85

2008-11-03T08:47:00.000-08:00

This paper did a comprehensive analysis of unix file system in terms of bandwidth requirement, file access pattern, etc. Even though it is over 20 years old, some of its conclusions still hold as of today: network bandwidth is not a limiting factor, large disk caches are important, etc. When I started reading the paper, it kept reminding me of trace related research in other fields, especially for trace scheduling in compiler and trace cache in computer architecture. However, compared to those, only analysis is not enough, the point here is how we can use those analysis to further improve file system performance, etc. In this respect, this paper pointed out the research direction for efficient caching, which, I believe, is still a very significant topic today. But time can change a lot of things, I also think today's network/distributed file system should be of a different scenario, at least in terms of those numbers presented in the paper.

Ousterhout85

2008-11-03T08:09:00.000-08:00

SUMMARY
The papers assigned for the November 4 class are an attempt to study the use of files on a Unix BSD system and an attempt to update that study six years later. The first paper written in 1985 by Ousterhout, et.al. had as a primary goal the design of a shared networked file system. It was looking at the following questions:
--How much bandwidth is needed to support a diskless workstation
--What are typical file access patterns
--How should disk block caches be organized
--What performance advantage is provided by disk caches.
The second paper in 1991 by Baker, et.al. (including the John Ousterhout who worked on the original study) reproduced the 1985 study and extended it in three additional ways:
--Further examination of cache behavior
--The impact of paging traffic
--Changing the algorithm for concurrent write-sharing

The Ousterhout paper reached the following conclusions about user activity in 1985:
--The average user generated only a small amount of disk access
--Most files are transferred sequentially
--Most files are closed just seconds after they’re opened
--Half of all disk information is deleted within five minutes of creation
--Adjusting the cache size and disk block size can affect system performance
Baker, et.al. reached the following conclusions about user file activity in 1991:
--File use per user has increased by a factor of 20
--The observations reached in the BSD Study regarding sequentiality, file open duration and information lifespan are still valid six years later.
--Changing cache and disk block size is still an effective way to improve performance
--Paging traffic does not skew the observations on file activity
--Write-sharing has a minimal impact on overall file activity

OBSERVATIONS
The systems used in the two studies show how processing power changed in just six years. The BSD study used VAX-11/780 1 MIPS workstations with between 4KB(!) and 16MB of memory. The later study used a variety of 10 MIPS workstations with 24-32MB of memory. I thought it was interesting that Baker, et.al. noted that while “computing power per user [increased] by a factor of 200-500, yet the throughput requirements only increased by about a factor of 20 to 30.” (p.202) Does this indicate the University of California was buying more computing power than needed or does this indicate that the programs running during their traces weren’t indicative of the demand users normally put on those workstations?

While the paper provides extensive information on their findings, I would have liked more information on the mix of applications that used the files. While ucbcad in the BSD study seems to run only CAD programs, the other two traces involved a mix of applications. The authors of the first paper even point out how printer spool files can affect the results. It would be interesting to know what word processing programs they used since many of them have the user edit a temporary file rather than the original source document thus requiring two files to be opened for every file that’s edited. The authors of the second paper also note that “workloads for these two traces [3 and 4] are very different from the rest of the traces, causing them to stand out in some of our measurements.” (p.200)

It also seems that they didn’t use any database programs since that might have increased the need for random access to the disk files.

I was also surprised by the observation on p. 208 of the Baker paper that “dirty blocks almost never leave the cache to make room for other blocks; they are usually written out to make new data permanent.” This might be strongly influenced by the mix of applications that were running on the workstations.

ISSUES
Tim Berners-Lee made the software for a web client and web server available on the Internet in the summer of 1991 (http://www.w3.org/People/Berners-Lee/Longer.html). Undoubtedly, the usage of files changed dramatically after that date. This change affected not just the use of existing file types but the creation and distribution of a wide variety of multi-media files (.jpg, .mov, .mp3, etc.) While these new file types don’t negate the work done in these two papers, I think they raise questions about the current applicability of their conclusions. It would be interesting to replicate these studies in a modern computing environment.

Workstations and servers running some version of Microsoft Windows are a powerful competitor to Unix. It would be interesting to see how file sizes, lifetimes, etc. would have differed in a Windows environment. Of course, even in 1991, Windows NT hadn’t been delivered so existing Windows workstations were still running DOS as their O/S. It’s possible that we wouldn’t see significant performance differences at that time. It might be different with Windows XP and its more powerful GUI interface.

Finally, even in 1985, researchers were promoting the idea of a diskless workstation. While current vendors promoting SOA or Cloud Computing aren’t necessarily requiring a diskless workstation, the concepts behind these architectures are very close to the original architecture studied by the BSD project.

Jerry Kruczek

Navarro02

2008-10-29T15:46:00.001-07:00

SUMMARY

The paper by Navarro, et.al. discusses the design, implementation and testing of a new approach to the use of superpages in memory management. Superpages involve the use of memory pages greater than the regular-sized or base pages. The need for superpages seemed to have started as the amount of physical memory grew without a corresponding increase in the number of memory pages referenced in virtual memory. The result was an increase in TLB misses which could degrade performance by 30-60%.

The authors designed a system to allocate variable-sized superpages as well as control the use of these pages to prevent fragmentation and insure the likelihood that there would be enough memory available for the creation of superpages. The system was implemented in FreeBSD on an Alpha 21264 CPU with 512 MB of RAM. The base page size was set by the processor at 8KB with superpage sizes of 64KB, 512KB and 4MB.

The results showed that out of 35 benchmarks, 34 would run faster with variable superpages with a matrix transposition improving by a factor of 7.5x! They also showed that variable superpage sizes improved performance compared to a static size by over 5% in 13 of the benchmarks. They also tested three different “pathological” workloads and showed that superpages didn’t significantly decrease performance even in extreme conditions.

OBSERVATIONS

The implementation and tests were thoroughly discussed and enabled the reader to understand their objectives and results. I thought two interesting observations were the authors’ discussion of wired page clustering and the performance of web servers under superpaging. To reduce fragmentation caused by non-pageability, the authors used a means of identifying kernel pages that could not be paged and then clustering them into pools of physical memory. It seems that web servers access a large number of small files (e.g. HTML pages) which do not require superpages. For these servers, the benefit of superpaging is less that 2%.

The authors also used a wide variety of applications to test their system including memory and processor intensive programs. I was somewhat surprised that most applications did not require 4MB superpages. It would have been interesting to see what the results would have been had superpage sizes been confined to 64KB and 512KB. Would there have been a reduction in reservations and demotions that might have offset the costs of not having a very large superpage?

ISSUES

The first issue the paper raised was the statement in Section 1 that “most general-purpose operating systems either do not support superpages at all, or provide limited support”. I was curious to see if that has changed, but a web search showed no new developments since 2004. Alan Cox, one of the authors, is teaching a course at Rice University that discusses superpages. Despite the benefits stated in this paper, there doesn’t seem to be a lot of recent work done in using superpaging to improve system performance. This could be due to an increase in the size of base pages on different processors. (http://www.ibm.com/developerworks/wikis/display/hpccentral/A+Performance+Evaluation+of+64KB+Pages+on+Linux+for+Power+Systems). Also, Intel is introducing a new hierarchy of TLB to improve performance (http://www.intel.com/technology/architecture-silicon/next-gen/whitepaper.pdf).

I’m also interested in whether application should be designed in order to reduce the memory footprint thereby reducing the need for superpaging to mitigate against TLB misses. Just as web servers show little improvement from superpages, would applications perform better if they were modularized and only increased memory needs when additional features were called? For example, most users probably employ only a fraction of the features in Microsoft Word or Excel. Would the performance of these applications improve if only a minimal set of features was loaded when a program started and additional features requiring additional memory were invoked only when needed? Would non-powerusers benefit by having a mini-Excel that had much lower memory needs?

Jerry Kruczek

navarro02

2008-10-29T13:46:00.000-07:00

The performance of TLB has become increasingly important to overall application performance. So we need to figure out some methods to increase TLB coverage. In this paper, the authors proposed some very good ideas. I think superpage itself is a good approach, the problem is that, how are we going to deal with the problems that superpage may bring about. My major concern is that, how did the authors control internal fragmentation. The authors proposed one possible solution to this problem in Chapter 5.1. However, personally, I do not think it is a very good solution, although they claimed it was a good tradeoff. Sacrificing system performance should not be an option.

[Navarro-2002]

2008-10-29T13:43:00.000-07:00

TLB size has not been increasing proportionately to memory increase. As program size and working set size increase this results in increased TLB misses. In "Superpages" the authors present increased and variable page size and various page mamangement methods as a solution.

We are unsure why stacks and heaps are considered special cases for page allocation. We are curious as to whether superpages are used in any more modern OSes and why this project wasn't implemented in linux.

[OS-FA08]: Navarro02

2008-10-29T12:56:00.000-07:00

Superpage is a way to reducing TLB misses, however, in the mean time, it has side effects, such as increased memory requirement, high page traffic, etc. This paper proposed an approach to trade off the balances of superpage by introducing a transparent superpage management system, which utilizes concepts of memory region reservation, allocation anticipation, varying superpage sizes, etc. And according to the paper, their superpage management system has impressive performance improvement upon the baseline.
My thoughts:
My major concern is that logic complexity of their superpage management system, which could need additional computing resources, especially in terms of cpu, memory itself, etc. Another concern is about hardware support for flexible superpage sizes, which could put another level of indirection or difficulty.
Overall, this paper did come up with some originality by combining their previous works.

[os-Fall 08]:Navarro 02

2008-10-29T12:01:00.000-07:00

This paper discusses about superpages-memory pages of large sizes. They enable each entry in a translation lookaside buffer to map a large amount of physical memory to virtual address space. This has several advantages like increasing TLB coverage,reducing TLB miss etc which can result in an improved performance. However there are some drawbacks also like managing superpage alloaction,fragmentation control etc. This paper deals with these issues and tries to present an efficient design for superpage management system.

The design was implemented on an Alpha CPU in FreeBSD and results indicate that there is about a 30% performance gain. But improper management of superpages result in greater physical page requirement and higher page traffic.The design in this paper manages the problem of superpage allocation without affecting system performance,but allows certain degradation in pathological conditions.

In case of allocation issue,they tried reservation based alloaction,there by avoiding reallocation of physical pages and additional copying. To write a dirty superpage to disk,the OS usually write out the whole of superpage,even if only few of its pages have been modified,the cost associated with this operation can outweigh any benefits obtained by using superppages,the authors provide a bettet way of doing this by demoting clean pages and repromoting them later if the pages are dirty.

In the end authors claim that system performance gain is 30% to 60% even under memory pressure,complex workload and small overhead. In case where overhead is high, will the design give a decent performance.

Navarro02

2008-10-29T10:58:00.000-07:00

This paper described a method of mapping physical memory to virtual memory addresses that made much more efficient use of the TLB. The basic problem is that the TLB is not large enough to cover all available memory, and it can't really be made bigger without slowing it down. The authors propose grouping contiguous pages into superpages, which together only take up one TLB entry.

This paper was very well-written and easy to understand. Their method of mapping superpages seems to be very clever, and makes good use of available resources. The performance gains far outweigh the overhead of maintaining all the extra information.

The idea of reservation-based allocation is very smart, because it gives the processes the ability to promote a group of pages to superpages without having to copy whole segments of memory.

They did an excellent job measuring performance. They not only tested the basic cases (of just one program running on the machine), but also situations where several programs were running, and the pathological cases.

We would have like to see if this could have any impact on commodity operating systems like Windows or Linux. It seems like it should be possible, but they don't really address it.

[OS-FA08]: Navarro02

2008-10-29T10:34:00.000-07:00

I was very impressed with the extensive testing that the authors managed to perform on their implementation under no memory pressure. That being said, I think it would have been interesting if they would have used the same level of rigor in the remaining sections.

Also, the authors state that there is no support for multiple dirty bits for a super page, but then go on to say that dirty/reference bits are emulated in the OS. This makes me wonder why they did not merely extend the OS so that instead of a single dirty bit per super-page, they didn't use a single dirty bit per base page. It seems like this would solve their problem of flushing to disk on page outs, and reduce the overhead (20x according to their numbers) which would be huge.

While the authors managed to do good testing with what they had, it would have been potentially interesting to see some of the other architectures they talked about (e.g. Itanium, however it wasn't yet out so they would have needed a prototype), however it seems that the "normal" architecture (i.e. x86) only has two superpage sizes. It would have been interesting to see what some of the other architectures (e.g. sparc, powerpc, etc) support, and if this technique would be useful on them as well.

LaRowe91

2008-10-27T13:50:00.000-07:00

SUMMARY
The paper “Robustness of NUMA Memory Management” analyzes whether a highly-parameterized memory management system can improve the memory performance of an operating system compared to a UMA approach. It also studies whether hardware architecture can affect NUMA performance. The research uses a specialized operating system called DUnX which allowed the modification of 6 NUMA memory management parameters. Two parameters describe the frequency of events which the other four set thresholds on measured memory parameters.

The tests were conducted on two different types of computers using six different applications. The six memory management parameters were also varied across test iterations.

The results showed that varying memory management parameters made little difference in performance (from a 5.9% improvement to a decrease of 1%). Also, the performance didn’t vary between the two different hardware architectures. The report also indicated that dynamic placement policies could be effective since “the measured performance of the UMA versions of the workload programs running with appropriate tunings often approaches the performance of the hand-tuned NUMA versions.” (p. 130)

OBSERVATIONS
The study seemed to build upon and confirm existing research rather than forge new ground. A significant assumption is that the DUnX operating system appropriately modeled the operation of a commercial operating system. There was substantial evidence backing up the contentions of the authors and there didn’t seem to be any anomalies that needed explanation. The paper did assume that the reader was familiar with previous research regarding NUMA as well as the parameters used to tune memory management in DUnX.

While the tests used a variety of processor-intensive applications, it would have been interesting to know the amount of memory used by each of them.

ISSUES
Since the paper was written in 1991, I was curious about the modern state of NUMA. According to one source, “…NUMA support is now in server operating systems like Microsoft’s Windows Server 2003 and in Linux 2.6 kernel.” (http://practical-tech.com/infrastructure/numa-theory-and-practice/) It also seems that NUMA is a consideration in VMWare (cf.:http://www.vmware.com/support/esx2/doc/esx20admin_res-NUMA-options.html).

It seems that faster cores and multiprocessor systems combined with faster and diverse types of memories make tuning memory access to the processor-memory combination more important. There are even manual NUMA optimization parameters in the ESX Server’s platform. There might be an opportunity for further research into the best way to tune Windows, Linux and ESX in a multiple processor, shared memory environment.

One additional area of research that this paper may have instigated is the ability to tune NUMA in an environment featuring multiprocessing or I/O intensive applications. The paper’s tests involved running a single application but a mix of memory-intensive and non-memory-intensive applications may have produced different results. Also, while it seems I/O bound applications would probably lessen the need for NUMA tuning, it might be interesting to see if that was actually the case.

Jerry Kruczek

[OS-FA08]: LaRowe91

2008-10-27T13:42:00.000-07:00

Various memory access patterns effect memory performance, and this is especially true in a distributed system environment. In order to provide a robust memory management mechanism, this paper proposed a NUMA memory management, which is built on a page scanner based dynamic page placement policy. Traditionally, page replacement is triggered by page faults, however, in this paper's approach, it scans page usage information first before making the decision.
My ideas:
In terms of memory performance improvement, this paper certainly is one of the way to try, however, concerning its application to only shared memory architecture, which is a drawback, as we know, the scalability of shared memory systems is way limited that distributed memory system. Therefore, I'm more interested if this paper's approach can be ported to distributed memory systems. Another issue I realized is the default parameter settings for NUMA memory management, which could not be an easy task for system users, especially when the systems are supposed to be general purpose...

[OS-FA08]: LaRowe91

2008-10-27T12:53:00.000-07:00

I thought this paper was very well written, and dealt with the problem of NUMA memory management in a very thorough way. That is, they tested their assumptions on two different architectures, as well as 6 different programs. This gave a very large sample size, and a good diversity in terms of the data they were collecting.

Their observations regarding the importance of various factors on different architectures was interesting and somewhat counter-intuitive, Namely the effects of freeze-window on performance.

While I would have liked a few more architectures, overall I think the paper was quite interesting. More specifically that all of the parametrization can be boiled down to the choice of two values, recent-mod and freeze-window. This was unexpected, however makes sense upon thinking about it in more depth.

[OS-FA-08]Waldspurger02

2008-10-15T14:05:00.000-07:00

In this paper, the authors presented the mechanisms and policies used to manage memory resources in ESC Servers. In particular, the authors discussed several techniques and algorithms for allocating memory across VMs running unmodified commodity operating systems. Some interesting approaches were discussed in the paper. In particular, I like the memory sharing part. Shared memory is a memory that may be simultaneously accessed by multiple programs with an intent to provide communication among them or avoid redundant copies. Depending on context, programs may run on a single processor or on multiple separate processors. Using memory for communication inside a single program, for example among its multiple threads, is generally not referred to as shared memory. In this paper, the authors discussed two different approaches: transparent page sharing and content based page sharing. It seems that the authors prefer content based sharing. I think it is a good approach too. The drawback of this approach is obvious: comparing the contents of each page is really time-consuming. Although the authors claimed that there are many ways to do the comparison more faster, I doubt whether it really works. Besides, I think the discuss of Shares versus Working Sets really makes sense.

Waldspurger 02

2008-10-15T13:38:00.000-07:00

The paper talks about memory management techniques used in VMware's ESX server. The 3 techniques described are 1.A ballooning technique reclaims the pages considered least valuable by the operating system running in a virtual machine. 2. An idle memory tax achieves efficient memory utilization while maintaining performance isolation guarantees. 3. Content-based page sharing and hot I/O page remapping exploit transparent page remapping to eliminate redundancy and reduce copying overheads.

While running multiple virtual machines on ESX server, managing memory is a challenging task. One concern is whether a frequent inflating or deflating of the "balloons" would cause performance issues in the guest OSes. I also liked the idea of page sharing, while the actual implementation sounded complex. Overall I felt the paper was well documented with quantitative experiments to support their claims.

]FA08]WALDSPURGER02

2008-10-15T13:30:00.000-07:00

The paper addressed managing memory issues among multiple virtual machines and their host. Author proposed new techniques to multiplex memory resource more efficiently. Those techniques are: ballooning, content-based page sharing and idle memory tax. Author introduced VMware ESX server, a thin software layer, which virtualizes the Intel A-32 architecture. ESX server is in charge of managing memory. ESX server defined physical address as guest OS address, and machine address as actual physical memory hardware address.

When reclaiming space from a virtual machine, some memory pages have to be swapped out. In worst case scenario, the pages are swapped out twice, one time by the virtual machine, another time by ESX server. Ballooning is the technique that makes the guest OS choose which pages to be swapped out. Balloon is a device driver, that can be inflated (reducing memory available to the guest OS) or deflated (granting more memory to the guest OS). The Balloon pings the ESX server in a fix interval to obtain the balloon size. Author also pointed out, the limitation of this technique is that it can be easily disable by guess OS’s user.

Sharing pages among virtual machines is another way to improve memory management efficiency. Because virtual machines may run the same guest OS, thus they may use the same programs, or load the same libraries. With page sharing, multiple guest physical pages can be map to the same machine pages. ESX server uses a hash table to identify pages with identical contents. ESX periodically scan guest pages to identify identical pages. Using hash table seems to reduce the overhead cost of comparing pages.

In order to guarantee quality of service to guest OS, ESX server introduced a notion of idle memory tax. This strategy charges a virtual machine more for an idle page than an active page. ESX server samples 100 pages every 30 seconds without guess OS’s involvement. Memory will be reclaimed from the clients that are not actively using their full portion of assigned memory.

Overall, we think this as a good paper to read. Author divided the paper into small sections which make the paper easy to follow. The proposed techniques are good ideas and seem to work. For the Ballooning technique, author ran experiment to show a low overhead cost of inserting balloon driver into guess OS. However for other two techniques, author only mentioned that the overhead cost for pages sharing was dismissible and there was no solid quantitative experimental result to back the claim. Lastly, we were left wondering what the performance would be when ESX combines all proposed techniques together.

Michael Olson
S M Niaz Arifin
Hoang Bui

[FA08]:Waldspurger

2008-10-15T13:15:00.001-07:00

The paper summarizes the memory reclamation and sharing mechanisms employed in ESX Server. Ballooning was an interesting technique to reclaim memory. Page sharing takes advantage of the inherent commonality in data. We are unsure of what is new in regard to memory sharing. The ballooning technique seems new.
The experimental section confirmed their technique. We are unsure if this is a valid technique for providing mission critical services due to the low cost of memory.

[OS-FA08]:Waldspurger02

2008-10-15T12:57:00.000-07:00

I thought this paper was very well written and describes some very interesting techniques for how to maximize memory availability in the context of VMs. I had a few questions regarding what they did however, with regards to how they implemented certain features.

First, they state one of the problems with paging out some pages to disk is that the guest OS might also want to preform the same operation. This results in double paging, which is a large performance hit. However since the OS is running inside the VM, I question the inability to foresee this as a possibility. Perhaps not considered at the time of writing, the language community has made great strides in interpreters, enabling them to find hot spots in code and optimize them accordingly. This seems like a similar case, as the VM has access to all code executing in the guest OS, and can (potentially for at least the most popular OSes) interpret this and optimize it accordingly.

While if the above could be done with minimum overhead it would provide the best performance, it would obviously be more complicated to implement. It would, however, be interesting to see if it were possible.

[OS-FA08]:Waldspurger02

2008-10-15T08:26:00.001-07:00

This paper mainly discusses about the memory management in VMware ESX Server and some ESX server mechanisms. ESX sever is stated as a thin software layer that is helpful in efficiently multiplexing hardware resources across virtual machines. Some mechanism described in this paper are ballooning, idle memory tax,content based memory sharing and hot I/O page remapping.ESX server virtualizes each physical address by adding an extra level of address translation. Some terminologies are used here-machine address refers to actual hardware memory,physical address is a software abstraction used to give VM the illusion of having hardware memory. When memory is over committed there comes the problem of regaining space,a technique called ballooning,it reclaims those pages that are considered least valuable by the operating system in a VM is then used.
Another problem in memory management is that of reclaiming idle memory,to solve this problem ESX uses idle memory tax mechanism.This technique ensures efficient memory management while maintaining performance isolation guarantees. To reduce redundancy and copying overheads content-based page sharing and hot I/O page remapping are used.
In this paper some techniques and algorithms to allocate memory across VMs are discussed.

[OS-FA08]: Waldspurger02

2008-10-15T08:21:00.001-07:00

This paper presented the memory management mechanisms and policies used in VMware ESX Server. There were three major techniques: 1) ballooning technique, 2) idle memory tax, 3) content-based page sharing. Ballooning is basically an approach to achieve predictable performance under varying guest os memory usages, while idle memory tax is like reclaiming those memory which are seldom recently used for more important uses, content-based page sharing was to explore possible memory sharing between virtual machines.
My thoughts:
While memory virtualization is one way to achieve virtual machine high performance, it definitely is not the only approach to the goal, the paper will be more convincing if it related memory virtualization to other mechanisms, like processor virtualization, etc. As of today, memory is cheap, further indirection via memory virtualization cannot match the performance by adding additional physical memory. However, from computer science perspective, those mechanisms and policies mentioned in the paper were pretty efficient in solving memory resource management issues.

Waldspurger02

2008-10-14T21:11:00.000-07:00

SUMMARY
Waldspurger’s paper, “Memory Resource Management in VMWare ESX Server” describes how VMWare manages the allocation of a host’s “actual hardware memory” among the guest operating systems running in virtual modules. In particular, the paper focuses on several techniques ESX uses to effectively share the memory and allow the VMs to collectively use more memory than physically installed on the host. The four techniques described are:
--Ballooning which allows each VM to determine which memory pages are least valuable and should be written to disk
--Content-based page sharing which allows pages from different VMs that are completely identical to be shared by the VMs that use the page
--An idle memory tax which preferentially reclaims memory from VMs that aren’t using their full allocation
--Hot I/O page remapping which handles “hot” pages in a VM that may be mapped to an area above the lowest 4 GB of hardware memory

The article also presents the results of several experiments that attest to the effectiveness of ESX’s memory management techniques.

OBSERVATIONS
I feel the paper provides some very clear explanations of how memory is managed within ESX especially how hardware memory can be overcommitted to the virtual modules. The paper didn’t provide many technical details on how the techniques were actually implemented either because that wasn’t the purpose of the author or because the details were confidential to VMWare. The paper also didn’t provide many details on how ESX Server is implemented directly on the hardware as opposed to VMWare Workstation which runs on a host operating system (and consequently consumes more resources just to establish the virtual environment than its ESX counterpart).
The author also presented a good selection of tests that “prove” that the memory management techniques work as promised. Of course, I assumed that VMWare did these types of tests before releasing the product, so the results were no surprise.
I’ve worked with VMWare in many different environments and it was interesting to read how memory is managed. It’s always just worked! I was especially intrigued by the memory sharing algorithms.

ISSUES
Security is becoming a major issue in virtualization. I am concerned that while a user could spend substantial time securing their O/S environment in Linux or Windows Server 2003, they are ultimately dependent on VMWare to insure that another guest O/S can’t access a memory page that is shared between the two guests. I wonder how many ESX users are even aware of this potential risk. The author doesn’t explain how VMWare mitigates this risk. (Maybe that’s why he doesn’t describe how ESX is actually implemented on the hardware.)
In section 4.3, the author contends that “all shared pages have unique hash values”. Since the hash algorithm isn’t claimed to be one-way, is it possible to reverse the hashing process and determine the contents of the page from the hash? If so, anyone with access to the hash table could use this to determine the contents of a memory page.
Finally, there does not seem to be any way for a user to mark a memory page as “unshareable”. This seems to be an important security feature to have in ESX.
On the other hand, this paper was written in 2002. By now, ESX Server has had over 6 years in actual practice. It’s possible that many of these security concerns have been addressed.
The author also mentions in the footnote to section 5.2 that the possibility of assigning different tax rates to different VMs is possible but “not currently exposed to users”. It seems the ability to assign different “priorities” to different VMs might be attractive to managers of virtual server farms whether to differentiate among corporate priorities or to provide the ability to charge users a higher cost for better performance.

Jerry Kruczek

[OS-FA-08] Young87

2008-10-08T17:04:00.001-07:00

In this paper, the authors mainly discussed the relationship between memory and communication in Mach, and its influence on the performance of the multiprocessor operating system. The authors described some design techniques of Mach. In particular, I am interested in the External Memory Management part. A big difference between Mach and some other operating systems is that they treat the secondary storage in different ways. This mechanism allows the single level store to be made available to ordinary user-state servers. Besides, in Mach, the kernel acts as a cache manager. It is also in charge of page replacement. Although this paper was published over twenty years ago, many ideas in this paper have never become outdated. Some of the techniques described in this paper have been used widely in the design of operating systems. So I think the authors are really far-sighted.

Young 87

2008-10-08T13:20:00.000-07:00

The paper talks about the relationship between memory and communication in Mach. They examined the design and implementation of key Mach memory management operations, how Mach memory objects can be managed outside the Mach kernel by application programs etc. Mach takes basic abstractions from Accent- Task, Threads, Ports, Messages and Port set.A Fifth abstraction introduced in Mach talked about in this paper is Memory Objects.

It is interesting to note that the paper introduced the notion of IPCs as "Ports and Messages". Even though the paper claims to have improved the performance of Mach no experimental data was given to back this. I feel that frequent message passing may infact cause degradation in performance.

[FA08]:Young

2008-10-08T12:40:00.000-07:00

This paper introduces some memory models that continue to influence the field. The discussion of remote memory is thought provoking. The idea to use memory mapping for communication is a key concept of the paper. It was interesting that Mach keeps a reserved memory pool to handle paging operations. It reserves an estimated amount of memory because applications have control over memory allocation.
We are unsure of how this work fits into the discussion of IPC and memory (for example, was this the first paper to discuss memory as a communication mechanism?).

[OS-FA08]: Young87

2008-10-08T12:04:00.000-07:00

After reading this paper I think it did a good job of addressing the memory management problem for distributed architectures. The implementation looks interesting, and claims are made about performance, however not substantiated in any meaningful way. Making the assumption that this paper started addressing the issue of memory management for distributed systems (which seems valid considering we're reading it), I think it does a very good job summarizing the problem, and explaining some of the techniques which were in use or being developed at that time.

The example of usage about AI was also very attractive, and quite interesting. They don't give any real explanation of why the work is being done on Mach (other than they're at CMU, and that's what their systems are), however their brief explanation of the techniques which are used to enhance the usage of their work are very interesting.

All in all a good paper, whose main weakness is the lack of description of the performance of their implementation, and potential future directions.

[OS-FA08]:Young 87

2008-10-08T12:01:00.000-07:00

In this paper the goals,design and implementation of Mach and its external memory managemnet facility is discussed. The memory objects is an important part of Mach design,as it can be managed either by kernel or user programs. The overall performance of Mach is related to the relationship between memory and communication,which is examined in this paper.As Mach is a multiprocessor operating system,applicability of Mach to other multiprocessor architectures is also covered.There are certain advantages in treating memory and communication as duals,which include increased flexibility in memory management,improved performance etc.The Mach design is an attempt to carry over from an earlier approach called Accent. Four basic abstractions were inherited from Accent mainly task,thread,port and message and Mach uses a fifth abstraction-memory object,useful in secondary storage management.Some problems related to improper usage of external memory management include data manager not reurning data or corrupting it.Some of the techniques to overcome this is also explained.One advantage of Mach's external memory managent is that it allows user provided objects to take advantage of the physical memory caching.In the end authors stae that external memory mangaemnt is the most recent and most experimental addition in Mach,so the effectiveness of this approach is not fully explored at the time this paper is written.

Young87

2008-10-08T11:17:00.000-07:00

This paper describes how memory mapping and IPC are implemented in Mach. Essentially, they create "memory objects" that provide management of the memory. Any task that needs memory can allocate space within the virtual memory. It can then make these memory objects available to other processes by giving them access to a port, which is basically a queue of messages. Then, processes can use the ports to pass memory objects between them. This allows processes to see each others' data without actually copying it.

This seems like a reasonable idea, because it allows IPC to take place without requiring context switching into the kernel. It also gives individual applications more control over how their virtual memory is allocated by providing an interface to the memory through the memory objects.

The biggest problem with this paper is that they only briefly touch on performance issues. They appear to have not done any kind of experiment to indicate the performance, although it's hard to imagine a control against which they could test, because this is an integral part of Mach, and can't easily be removed from Mach or added to another OS.