COMP 3000 Essay 1 2010 Question 12

Question

There have been multiple attempts to have operating systems use databases or database-like stores. What have been some of the major past attempts at this? What was their fate? Why? Key examples (not exhaustive): WinFS, ReiserFS, PalmOS, Newton OS, BeOS

Answer

There have been many attempts at creating file systems that use database-like stores. While the idea is an interesting one, database stores are just not ready for the consumer market. Traditionally, databases are used in applications where a project focuses on accessing large amounts of data quickly and efficiently, such as banking systems, telecommunications, web servers and more. A personal computer did not traditionally need as much storage, and is organized in an easy-to-navigate tree structure. However, the recent shift towards object-oriented programming styles, along with the tremendous increase in the amount of data that can be stored on a home computer, has led to the idea of object stores, and file systems that function as databases.

There have been various implementations of operating system using a database driven file system, each developed to satisfy its individual needs. We will visit five different operating systems that used a database as file system. First, both Palm OS and WinFS implemented a database file system for their operating systems for improve efficiency. NewtonOS was produced to be used on a desktop machine, but evolved into one of the best and most secure PDA operating systems. BeOS was a new operating system and decided to use a database driven file system to leverage both improved efficiency and compability. Lastly, ReiserFS seemed to have started as a proof-of-concept, which found it's place with Linux. The success of each of these file systems is intrinsically tied to that of its host operating system, and vice versa. One cannot succeed without the other. With that in mind, by closely examining each file system and operating system combination individually, it is clear that none have been successful.

We will first examine the trials of Palm OS.

Palm OS

History

PalmOS was developed from Graffiti, a hand-recognition software which was believed to be doomed from the very beginning[1]. Graffiti’s fast and accurate hand-recognition software was thought to be useless because many companies did not see a purpose for it; there were no companies that wanted to make the hardware for it[1]. The company Palm then decided to make their own hardware with Graffiti as the OS, which became what is known as Palm OS today.

Database Structure

Palm OS has two different database types, record and resource database. There are similarities between these two databases, they both have headers which stores information onto the database and are both stored in the storage heap. The difference between the record database and resource database is how the information is stored, called, handled and how it is named. The record database is used to store data, and the resource database contains all applications. Furthermore a record database is a collection of records (blocks of memory) each record can only store up to 64KB of memory. It has information that is unique to the record; it has the location of the record, an ID, and an attribute, which contains delete, dirty, busy, and secret bits [2]. The resource database stores application code, name, icon, forms, alerts, menus, strings, and all other elements of the application [2]. Applications can be referenced by an ID number and a type (four-character constant).

Problem

Record and resource databases are stored in storage/database heap, which in turn is stored in the RAM (Random Access Memory). The database heap has a limit of 64KB of memory and since a record had to be small enough to fit within the heap, this made memory hard to manage. For example, when a record is 50KB and there are three heaps which can only hold 64KB each, a total of 192KB of memory; say these three heaps are half full therefore there is 96KB of free memory, but the record of size 50KB cannot be stored because not a single heap has enough memory to store the record[2]. This problem arose in versions before OS 3.0 because the database heap was divided into smaller parts. This allowed for free space in memory, but some of those heaps were occupied by data, and there might not be enough space to store the record into the heap. Palm OS 3.0 and later solved this problem by to making a single large storage heap instead of multiple smaller heaps.

Fate

In 2005, Palm OS was acquired by Access Systems Americas, Inc. Access decided to expand the breadth of the operating system’s offering to include more tools, a better user experience, and increased compatibility across many more devices.[3] In 2007, development of Palm OS shifted to a new operating system called Garnet OS. [4] Its latest release, Garnet version 6, still includes a database based file system.

Unlike the Palm OS, WinFS was not as fortunate and leads a different path, we will examine their fate in the next section.

WinFS

History

The history of WinFS is relatively long, as we can find trace of the project back in mid-90's with Storage +. Microsoft had the idea to remove the NTFS file system and instead use a relational object-oriented file storage, which was based on SQL server 8.0. This new file system was supposed to be implemented in Windows 2003 Server. But then in 2000, Windows announced that Storage + was to be forgotten, with Relational File System (RFS) as its successor. RFS was supposed to be included in SQL Server 2000, but never made the cut. Another reason for the continual delays was that, in 2000, Oracle announced a new file system which was also a relational file system, Independent Internet File System. Microsoft had to rethink RFS to be ahead of the competition and that added additional delay.[5]

RFS was forgotten about until the public heard in 2002 about a new file system that would be present in Longhorn (later renamed Vista). The system would be once again be based on its predecessor, RFS, but it would have run on top of a NTFS file system. WinFS was included in a few public builds for Vista, but in 2004 it was removed from the beta builds. It was said it would be downloadable again after the release, but was definitely cut for good in 2006 from Vista.

Brief Concept

With today’s data, we are facing a crisis of finding what we want, when we want, at a reasonable speed on our own computer. Data is stored in many different ways. We can recognize the uses of certain files by their file extensions, but the amount of file extensions that exist is astonishing, so it is quite difficult to remember each one. Also, a simple file may be stored with different extensions, in different databases, which makes finding, relating to, and acting on the file quite difficult to achieve. [6]

Microsoft had an idea to solve this problem by using a relational database as a file system, where data would be treated like it should be, as data and nothing else. To understand how WinFS works, we must have a general idea of the relational database. The data in this kind of database is spread into specific tables, like in a normal database, but there are multiple relations between these tables. This gives the programmer the power to search, find and present the result in an efficient way. In the case of WinFS, the main goal was to "Enable people to Find, Relate, and Act on their information"[7].

As already pointed out, data files are very broad nowadays. With that many file formats using complicated data storage methods, the "...current file system does not know how to collect and find information within these new types of data"[7], but with data treated as data inside a database, we could find what we are looking for quite easily.

Another important point of WinFS is the notion of how data relates to each other. In our current file system we can't, unless doing it manually, add a picture of our good friend Bob, and in the same time see all the picture related to Bob. On top of that, we can't find the picture of Bob, all the received emails, documents, movies, or whatever else we would want to find in the same request. In order to find them, we have to search for them one by one. If we treat data as data, once again, we can simply search in the tables of the database for the pictures, received emails, videos, and documents containing the name Bob, and present them to the user. As we can see, data can be related to each other with keywords, in our example it was the name Bob, but it can be anything.[8]

The last problem that WinFS was aiming to overcome was to run on top of NTFS. Basically, WinFS would scan all the data in the NTFS file system, and put it into its database. Thus, it would work as a file system, but it would be totally dependent of NTFS.

Fate of WinFS

As we have seen in the history of WinFS, its fate wasn't as desired. In 2006, on the team blog, Microsoft announced that it wouldn't include WinFS as a system file package, but instead deliver it into the next Microsoft SQL server, which was SQL Server 2008. "These changes do mean that we are not pursuing a separate delivery of WinFS, including the previously planned Beta 2 release"[9], but instead, they will keep working on it and some "...may be used by other Microsoft products going forward."[9] So, we can see that WinFS didn't succeed as a file system, but some of the logistics will continue to live on in Microsoft’s database software.

Why

Microsoft never released publicly what exactly went wrong. There was much speculation about the design of WinFS, but on the team blog Quentin Clark, Product Unit Manager of WinFS, answered that "[i]n fact, the Beta was coming together really well."[7] He then replied that the technology used wasn't easy to build onto, so they had to rewrite some parts, but that this wouldn't have caused the end of WinFS. Some also speculate that no serious software used WinFS, nor did it receive the attention needed from the developers to have a good start. In an interview with Channel 9, Quentin Clark said, "We were building too much of the house at once. We had guys working on the roof while we were still pouring concrete for the foundation."[10] This shows that the team might have had some management problem, which evidently led to the termination of the project.

We will now talk about NewtonOS.

Newton OS

Brief History of Newton OS

Newton OS was created by Apple and was used with their line of PDAs, becoming one of the world's first PDAs. Newton was originally meant to be an innovative OS to reinvent personal computing, but it was changed to become a PDA, due to fear of eating up Macintosh sales and because of project delays [11]. The first iteration of the Newton system came as the MessagePad. The MessagePad sold out its 5,000 copies within a few hours of release, despite its price of $800 US [12]. Apple released several different PDAs with Newton OS between 1993 and 1997, which despite its popularity were plagued by flaws in the applications of the device [13].

Newton OS uses a database-like store for data. The object storage system within Newton OS has frames, slots, soups, and union soups to handle the data for the OS. The frame is essentially the same as a record database, as that used in Palm OS. “Frames are flexible and can represent a wide variety of structures.”[14] A slot is like a database field. The slot is used to hold single pieces of data and these slots are contained in a frame. Related frames are stored in soups, Newton's equivalent of a database, that are automatically indexed and can be queried by the index directly, or searched through by keywords. A union soup is a collection of soups of the same name[14].

The main reason why Newton PDAs became so well-known was because the Newton OS was the most advanced operating system of any personal computing device of its time. The OS kept the user from accessing the inner workings of the device, keeping users away from creating problems by tampering with the wrong settings, and used a database-based file management that simplified the system to a higher degree than any previous OS [12].

Flaws of Newton OS

Even with the innovation that came from Newton OS and its computing devices, it had several deep-running flaws that caused critics to pan the Newton devices. First and foremost, the Newton devices were known for their failure at implementing their handwriting system, which was supposed to recognize entire words. The Simpsons television show even had a joke about this flaw in one of their episodes [15]. The main problem behind the handwriting system was that it had a hard time recognizing cursive writing, even though Apple insisted that its engineers ensured it worked correctly [16]. Another main problem with the Newton devices was that their overall size was too large for most pockets. Since Newton devices were expected to be carried similarly like a wallet or a cellphone, most people found their size too great for daily use [17][18]. Earlier Newton devices were also found to be very slow due to the virtualization of the NewtonScript and the lack of necessary RAM [18]. In the end, the Newton devices were fated to fail.

Fate

Although the Newton OS was revolutionary when it was released, it was doomed to fail due mostly to impracticality. In early 1997, Newton Inc. was created as a subsidiary company of Apple [18], but after a relatively short run, Newton Inc. was reabsorbed into Apple [19]. In December of 1997, Apple effectively ceased development efforts on the Newton OS [20], and in February 1998, Apple announced the discontinuation of the Newton OS development [21].

Why

After his return as CEO of Apple, Steve Jobs canceled or restructured many of Apple's failing products to refocus Apple's energy towards more successful endeavors, like the iPod and Macintosh computers. Not surprisingly, Newton OS was one of these products. Although Newton was canceled, the development of the OS and its devices have had impacts on other Apple products. Mac OS X 10.2 has a handwriting recognition software called Inkwell that uses an external tablet to recognize words, but like the Newton handwriting software, it requires you to right each letter individually. Pixo, the company that created the operating system for the iPod, was founded by two of the developers that worked on the Newton OS [22]. Pixo was subsequently acquired by Apple after the shipping of the first iPods.

We will now explore BeOs in the next section.

BeOS

Brief History

BeOS is released by Be, Inc which is founded in 1990 by Jean-louis Gasee and Steve Sakoman. Be OS is a brand new operating system running on it’s own hardware called BeBox. The system is giving a better performance on digital media works because of better use on system resources. This system is initially made for AT&T Hobbit hardware, but since AT&T decide to stop producing Hobbit processor, the system is modified to Apple’s PowerPC hardware.[23]

Operating System

BeOS is an operating system that was first developed from scratch in 1991 to run a proprietary hardware. The goal for BeOs was to compete with both Apple and Microsoft, by creating a new platform. Since both Apple and Microsoft were putting considerable effort into covering legacy versions of their systems, BeOs hoped to gain ground through efficiency.[24]

BeOS was designed to be a better use on modern hardware. Compared to Windows and Mac OS, it greatly improved on digital media performance by using modern hardware facilities like symmetric multiprocessing, pervasive multithreading and preemptive multitasking.[25] Compared with other modern operating system, pervasive multithreading is allowing the system to better utilize system resources. It also has a simple and clear GUI and powerful command-line interface through BASH shell. However, since the system is not UNIX based, it is also compatible with POSIX. Furthermore, the API of BeOS is developed under C++ which facilitate application development.

But since BeOS is a fully multithreaded system, programs which are written for the system need to be really well programmed in order to stop deadlock or errors from doing multiple simultaneous threads.[26] Also not a lot of hardware is supported by BeBox, the machine designed for BeOS. And maintaining the system is another problem due to database like file system.

File System

The file system used by BeOS is called BFS. BFS is a custom file system developed by the same team as BeOs. BFS is a 64-bit journaling file system which logs all data before storing it. [24] This journaling increases both the stability and security of BeOs, by preventing system crashes from jeopardizing the file system’s integrity as well as offering quicker recovery from crashes. However, this comes at the expensive of rapid data acess since a journaling file system is based on random memory access. Uniquely, the BFS journaling file system was implemented by BFS to be a high performance file system that stores all data in a database, but also allows users to view it in a more traditional heirachical way. [24] It also boost flexibility by allowing users to store any possible data format of their choosing.

Since BFS is a custom file system developed solely to be used by BeOs its success is intrinsically tied to that of its operating system. BeOs poses a threat to BFS both because of its inability to reach the masses as well as the potential memory errors caused by its unfiltered multithreading capability. This is because the system reliability is placed in the hands of the programmer.

Fate

In the mid-1990's BeOs was pursued by Apple to serve as their new operating system. BeOs demanded a purchase price that Apple was not willing to pay and instead Apple decided to acquire NeXT and implemented NeXTSTEP OS. BeOs then tried to penetrate the personal computer market but ran into compatibility issues. BeOs needed custom hardware to function correctly. Development ensued to port BeOs onto standard PCs, but ultimately fell flat when Be could not convince any manufacture to use their operating system. This was largely due to restriction and exclusive rights held by Microsoft which blocked BeOs' entry into the market. By 2001, BeOs had failed to obtain even marginal market share and was acquired by Palm to be integrated into Palm OS. An small community driven open source project named Haiku OS has resumed development of BeOs and released Haiku Alpha 2 in May 2010.

And now we will explore ReiserFS.

ReiserFS

History

ReiserFS is the product of Namesys, a Californian company stared by Hans Reiser [27]. ReiserFS was first introduced in version 2.4.1 of the Linux kernel, and was the default file system on several Linux distributions, most notably SUSE. ReiserFS's successor is Reiser4, which released in 2004[28]. However, in 2008, Namesys dissolved and commercial production of ResierFS and Reiser4 halted [29]. Since the removal of commercial support, ReiserFS has become less popular, probably due to the many bugs that have no hope of being resolved.

Concept

ReiserFS is driven by a few major concepts. The first and probably main idea is the ability to handle many files that are smaller than a block of storage on the storage media. This is accomplished through the use of B+ Trees. [30]. Instead of balancing in order to keep the height of the tree fairly stable (as an AVL tree balances), ReiserFS balances so that the height of the storage tree is constant. This type of balanced tree reduces overhead by reducing the number of internal nodes, or i-nodes needed. Each node in the B+ tree maps to a block on the storage device, and each node can hold multiple objects, each of which has a unique key[31]

Another concept in ReiserFS is the use of unified name spaces[32]. Unified name spaces are simply a more refined definition of an object store, in which all stored data is made up of objects that are both 'files' and 'directories'. Objects are stored in such a way so that you can use directories to quickly access different types of objects, then further traverse the directories in order to access specific objects, and go even further to access an object's attributes. This maps extremely well to different programming styles, especially object oriented programming. Lookup of data can also done using attributes of the data, much like in WinFS[1]. This type of access would be more often used by the end user.

Flaws and Fate

While ResierFS preforms very well in terms of speed [33], ReiserFS has many bugs that can lead to instability of files. One problem is that link() and unlink() are not synchronous in ReiserFS, which can lead to data corruption[34]. Another is that, if ReiserFS's tree structure becomes unusable for any reason, a rebuild risks further corrupting the file system [35]. There are also issues with the journaling which can lead to corruption [36]. Issues like these are a bad idea in any file system, as the risk of unstable data is a serious drawback. Considering that the root of these issues are often synchronization problems, ReiserFS is a very poor choice for many modern, multi-core systems, as the increased need for synchronization would increase the level of instability.

In addition to the stability issues, ReiserFS has some design issues mainly contribute to why it is no longer used today. Since ReiserFS was designed to handle numerators small files, when trying to scale a ReiserFS system, behavior is inconsistent, again spawning from issues in synchronization. In addition, moving from the bug-ridden ReiserFS v3 to v4 required a reformat, as Reiser4 was re-written from scratch. This prompted SUSE to drop ReiserFS as it's default file system, as they preferred to use a tried and tested sytem update (ext3) instead of a new, yet-untested file system in their distribution [37].

Interestingly enough, the SUSE drop coincided eerily well with Hans Reiser being sent to jail. Left without an owner, Namesys lost most corporate sponsors, eventually only receiving funding from the DARPA initiative. With Namesys (mostly) gone, ReiserFS no longer has commercial support, and so the stability and scalability bugs are taking a fair amount of time to be resolved. This combined with low visibility that stems from no longer being used in any major Linux distributions largely explains why ReiserFS can be considered a dead project.

Conclusion

Looking at these examples of database-like systems, it becomes apparent that despite their potential, each did not live up to its expectations. Since the success of a file system is tied to that of the operating system, a harmonious relationship must exist between the two. In each case defined above, Palm OS, WinFS, Newton OS, BeOS and ReiserFS, that relationship did not manifest into success. There has not yet been developed a highly flexible design that would be useful on the average system. The increasing importance of digital information in today's world also means that people are extremely reluctant to switch from a tried and true system to a newer and possibly unstable technology. In the case of database-like file systems, the few implementations that are available to the public are unstable, and therefore an unattractive choice.

It is important to note that object stores are not the only alternative file system competing to improve upon traditional block storage[2], so there is no guarantee that database-like stores will ever become a widely used technology, as they may not mature quickly enough to beat out other technologies.

Reference

[1] Gloor, G. PalmOS from the Ground Up - http://www.iam.unibe.ch/~rvs/teaching/SS02/bs/arbeiten/Guido_Gloor-PalmOS.pdf

[2] McKeehan, J., & Rhodes, N. (2002). Palm OS programming: the Developer’s guide. Sebastopol, California, USA: O'Reilly and Associates, Inc.

[3] René Guadalupe Cruz Flores, Juan Ivan Nieto Hipólito, Gabriel López Morteo, and Elitania Jiménez García. - Mobile Operating Systems: a Comparative Analysis in Personal Devices. http://azul.iing.mxl.uabc.mx/~renecruz/papers/Unpublished-Cruz-Flores-2.pdf

[4] Company Website for Garnet OS - http://www.access-company.com/products/platforms/garnet/index.html

[5] Blog of established tech reporter, Paul Thurrott - http://www.winsupersite.com/showcase/winfs_preview.asp

[6] Presentation on WinFS by Ajilion consulting - http://www.slideshare.net/Severus/winfs

[7] MSDN Introduction to WinFS - http://msdn.microsoft.com/en-US/library/aa480687.aspx

[8] Video of the WinFS team discussing WinFS - http://channel9.msdn.com/Blogs/scobleizer/Shishir-Mehrotra-WinFS-beta-1-team-meeting

[9] Update on WinFS from MSDN - http://blogs.msdn.com/b/winfs/archive/2006/06/26/648075.aspx

[10] Interview with WinFS project lead on MSDN - http://channel9.msdn.com/blogs/jonudell/where-is-winfs-now

[11] Getting Started Newton video (that came with the product) - http://www.youtube.com/watch?v=64QuJdJmCbA&feature=player_embedded#!

[12] History of Newton by Pen Computing Magazine - http://www.pencomputing.com/frames/newton_obituary.html

[13] CNET news announcing end of Newton - http://news.cnet.com/Apple-scraps-Newton/2100-1001_3-208551.html

[14] Bey C., et al. (1996). Newton Programmer’s Guide for Newton 2.0. Cupertino, California, USA: Apple Computer, Inc. - http://newtonpda.com/docs/NewtonProgrammerGuide20/53.php

[15] http://www.youtube.com/watch?v=xc3JzS0K3ys

[16] Analysis by an Apple-centric magazine - http://www.roughlydrafted.com/RD/Q4.06/600D65E6-A31E-45CA-AFC5-42BC253F5337.html

[17] Opinion piece via CNET - http://news.cnet.com/8301-13512_3-9754359-23.html

[18] BNET reporting on Apple merger - http://findarticles.com/p/articles/mi_m0EKF/is_n2169_v43/ai_19494161/

[19] BNET reporting on Apple merger - http://findarticles.com/p/articles/mi_m0EKF/is_n2189_v43/ai_19892982/

[20] CNET reporting on uncertain future of Newton - http://news.cnet.com/2100-1001-206664.html

[21] Apple announcing the discontinuation of Newton - http://www.apple.com/ca/press/1998/02/NewtonDisco.html

[22] San Fransisco Chronicle discussing Pixio - http://articles.sfgate.com/2004-08-16/business/17438885_1_pixo-user-interface-ipod

[23] http://en.wikipedia.org/wiki/BeOS

[24] Giampaolo, D. Practical File System Design with the Be File System. Be Inc. - http://www.letterp.com/~dbg/practical-file-system-design.pdf

[25] History of file systems on ARS Technica - http://arstechnica.com/hardware/news/2008/03/past-present-future-file-systems.ars/7

[26] http://translate.google.com/translate?hl=en&sl=zh-CN&tl=en&u=http://www.techcn.com.cn/index.php%3Fdoc-view-135996%235

[27] Archive of the Namesys product page for Reiser4 - http://web.archive.org/web/20071024001500/http://www.namesys.com/v4/v4.html

[28] http://en.wikipedia.org/wiki/Reiser4

[29] CNET discussing end of Namesys - http://news.cnet.com/8301-13580_3-9851703-39.html

[30] Reiser, H. Kernal Korner: Trees in the Reiser file system. Namesys. - http://delivery.acm.org.proxy.library.carleton.ca/10.1145/610000/603630/6267.html?key1=603630&key2=4060996821&coll=ACM&dl=ACM&CFID=105645345&CFTOKEN=72691832

[31] Analysis of the structure of ReiserFS, by an employee of Namesys - http://homes.cerias.purdue.edu/~florian/reiser/reiserfs.php

[32] Bar, M. (2001). ReiserFS for Linux. In Linux File Systems. McGraw-Hill Companies. - http://www4.informatik.uni-erlangen.de/Lehre/WS01/PS_KVBK/docs/reiserfs/MosheBarReiserFS.pdf

[33] Sun file system benchmarks - http://www.sun.com/software/whitepapers/solaris10/fs_performance.pdf

[34] Commentry on ReiserFS by Wietse Venema, PhD - http://archives.neohapsis.com/archives/postfix/2001-05/1749.html

[35] Discussion between kernel developers on the University of Indiana Mailing List - http://lkml.indiana.edu/hypermail/linux/kernel/0506.3/0219.html

[36] Arpaci-Dusseau, A., Arpaci-Dusseau, R, Prabhakaran, V. Analysis and Evolution of Journaling File Systems. University of Wisconsin, Madison. - http://users.cis.fiu.edu/~yangz/teaching/reading_list/Analysis%20and%20Evolution%20of%20Journaling%20File%20Systems.pdf

[37] Discussion of dropping ReiserFS, by the kernel team lead for SUSE, Jeff Mahoney - http://lwn.net/Articles/202780/

Other Links

• http://membres.multimania.fr/microfirst/palm/pdb.html - Information on Palm OS

• http://mobile.eric-poncet.com/palm/tutorial/db.html - Tutorial on Palm OS programming

• https://docs.google.com/document/d/1MgtOOuggnKvutmqpL2rR8ZD4vuKs9wYObX0ifGujUaA/edit?authkey=COnbkrIB# Group discussion 10/13/2010