<!-- MHonArc v2.4.4 --> <!--X-Subject: [MUD-Dev] A variation on persistent store techniques with notes on distributedprocessing support --> <!--X-From-R13: X Q Znjerapr <pynjNhaqre.rate.ftv.pbz> --> <!--X-Date: Mon, 29 Jun 1998 13:34:58 -0700 --> <!--X-Message-Id: 199806292033.NAA05435#under,engr.sgi.com --> <!--X-Content-Type: text/plain --> <!--X-Head-End--> <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN"> <html> <head> <title>MUD-Dev message, [MUD-Dev] A variation on persistent store techniques with note</title> <!-- meta name="robots" content="noindex,nofollow" --> <link rev="made" href="mailto:claw#under,engr.sgi.com"> </head> <body background="/backgrounds/paperback.gif" bgcolor="#ffffff" text="#000000" link="#0000FF" alink="#FF0000" vlink="#006000"> <font size="+4" color="#804040"> <strong><em>MUD-Dev<br>mailing list archive</em></strong> </font> <br> [ <a href="../">Other Periods</a> | <a href="../../">Other mailing lists</a> | <a href="/search.php3">Search</a> ] <br clear=all><hr> <!--X-Body-Begin--> <!--X-User-Header--> <!--X-User-Header-End--> <!--X-TopPNI--> Date: [ <a href="msg01250.html">Previous</a> | <a href="msg01252.html">Next</a> ] Thread: [ <a href="msg01272.html">Previous</a> | <a href="msg01237.html">Next</a> ] Index: [ <A HREF="author.html#01251">Author</A> | <A HREF="#01251">Date</A> | <A HREF="thread.html#01251">Thread</A> ] <!--X-TopPNI-End--> <!--X-MsgBody--> <!--X-Subject-Header-Begin--> <H1>[MUD-Dev] A variation on persistent store techniques with notes on distributedprocessing support</H1> <HR> <!--X-Subject-Header-End--> <!--X-Head-of-Message--> <UL> <LI><em>To</em>: <A HREF="mailto:mud-dev#kanga,nu">mud-dev#kanga,nu</A></LI> <LI><em>Subject</em>: [MUD-Dev] A variation on persistent store techniques with notes on distributedprocessing support</LI> <LI><em>From</em>: J C Lawrence <<A HREF="mailto:claw#under,engr.sgi.com">claw#under,engr.sgi.com</A>></LI> <LI><em>Date</em>: Mon, 29 Jun 1998 13:33:54 -0700</LI> <LI><em>Reply-To</em>: <A HREF="mailto:mud-dev#kanga,nu">mud-dev#kanga,nu</A></LI> </UL> <!--X-Head-of-Message-End--> <!--X-Head-Body-Sep-Begin--> <HR> <!--X-Head-Body-Sep-End--> <!--X-Body-of-Message--> <PRE> Quick aside: For those interested in the heavily threaded distributed processing end of things, the following may be of interest: URL:<A HREF="http://theory.lcs.mit.edu/~cilk/home/intro.html">http://theory.lcs.mit.edu/~cilk/home/intro.html</A> URL:<A HREF="http://ltiwww.epfl.ch/sCxx/index.h">http://ltiwww.epfl.ch/sCxx/index.h</A> I could easily see them both being applied to server designs, even possibly on a Beowolf-style cluster. URL:<A HREF="http://plg.uwaterloo.ca/~pabuhr/uDatabase.html">http://plg.uwaterloo.ca/~pabuhr/uDatabase.html</A> --<cut>-- uDatabase Abstract Programmers working with complex and possibly large persistent data structures are faced with the problem that there are two, mostly incompatible, views of structured data, namely data in primary and secondary storage. In primary storage, pointers are used to construct complex relationships among data; establishing these relationships without pointers is often cumbersome and expensive. Significant research has occurred over the last decade on efficient and simple-to-use methodologies for constructing, storing, and subsequently retrieving large persistent data structures in a fashion that makes the secondary storage transparent to the programmer. The approaches extend primary storage practices and tools so that they also apply to secondary storage. Merging primary and secondary storage in this way produces a single-level store, which gives the illusion that data on secondary storage is accessible in the same way as data in primary storage. This uniform view of data eliminates the need for expensive execution-time conversions of structured data between primary and secondary storage and allows the expressive power and the data structuring capabilities of a general purpose programming language to be used for secondary storage. For complex structures, a single-level store offers substantial performance advantages over conventional file access, which is crucial to database applications such as computer-aided design, text management, and geographical information systems. While there are several ways to implement a single-level store, many projects do so using memory-mapping. Memory mapping is the use of virtual memory to map files stored on secondary storage into primary storage so that the data is directly accessible by the processor's instructions. In this environment, there are no explicit read and write routine calls to access data on disk. All read and write operations are done implicitly by the operating system during execution of a program. When the working set can be kept in memory, performance begins to approach that of memory-resident databases. All approaches to implementing memory-mapped single-level stores have to deal with the address consistency problem. When data is copied from secondary to primary storage (actually virtual storage), either the data must be positioned exactly where it was created (to maintain integrity of references), or the addresses must be modified to reflect its new location. The former case is difficult to handle because data from two or more memory-mapped files may map to the same location, producing an irreconcilable conflict. The latter case is difficult to handle because it must be possible to locate all pointers so they can be updated, and there is the additional runtime cost of modifying the pointers. Pointer modification may be handled eagerly or lazily; in general, eager modification of pointers is called relocation and lazy modification is called pointer swizzling. We argue that a significant performance advantage of a single-level store is lost if all the pointers within it have to be relocated or swizzled. This loss of advantage is especially significant for operations that incur high overhead in data preparation; examples include operations like sequential scans, where the data is accessed only once, and operations that deal with large data structures with small primary storage, where the data is implicitly fetched and prepared multiple times. Therefore, we are pursuing the alternative approach of exact positioning of data so relocation or swizzling of pointers is significantly or completely eliminated during transfers to and from secondary storage. To this end, we are developing uDatabase, a toolkit for building persistent data structures using the ``exact positioning of data'' approach to memory mapping. uDatabase employs a novel technique that allows application of an old solution to the problem of address collisions when mapping multiple memory-mapped data structures. The old solution is hardware segmentation; each hardware segment is an address space starting at a virtual zero, in which a persistent data structure can be built, stored, and subsequently retrieved and modified. Multiple segments can be simultaneously accessed in a single application because each segment has its own non-conflicting address-space. When a segment is mapped into memory, pointers within the segment do not require modification; pointers outside the segment do require modification, but in general, these pointers represent a small percentage of the total number of pointers in a data structure. Our technique uses the UNIX system call mmap to mimic segmentation on hardware that does not support it. Furthermore, uDatabase has direct access to the concurrency facilities provided by uC++, which allows a high level of concurrency through multi-threading. PAPERS uDatabase : A Toolkit for Constructing Memory Mapped Databases by Peter A. Buhr, Anil K. Goel, and Anderson Wai Parallel Pointer-Based Join Algorithms in Memory-Mapped Environments by Peter A. Buhr, Anil K. Goel, Naomi Nishimura, and Prabhakar Ragde Exact Positioning of Data Approach to Memory Mapped Persistent Stores: Design, Analysis and Modelling by Anil K. Goel --<cut>-- -- J C Lawrence Internet: claw#null,net (Contractor) Internet: coder#ibm,net ---------(*) Internet: claw#under,engr.sgi.com ...Honourary Member of Clan McFud -- Teamer's Avenging Monolith... </PRE> <!--X-Body-of-Message-End--> <!--X-MsgBody-End--> <!--X-Follow-Ups--> <HR> <!--X-Follow-Ups-End--> <!--X-References--> <!--X-References-End--> <!--X-BotPNI--> <UL> <LI>Prev by Date: <STRONG><A HREF="msg01250.html">[MUD-Dev] Re: Levelless MUDs</A></STRONG> </LI> <LI>Next by Date: <STRONG><A HREF="msg01252.html">[MUD-Dev] You think users won't number crunch and statistise your MUD?</A></STRONG> </LI> <LI>Prev by thread: <STRONG><A HREF="msg01272.html">[MUD-Dev] Re: You think users won't number crunch and statistise your MUD?</A></STRONG> </LI> <LI>Next by thread: <STRONG><A HREF="msg01237.html">[MUD-Dev] the why of online worlds</A></STRONG> </LI> <LI>Index(es): <UL> <LI><A HREF="index.html#01251"><STRONG>Date</STRONG></A></LI> <LI><A HREF="thread.html#01251"><STRONG>Thread</STRONG></A></LI> </UL> </LI> </UL> <!--X-BotPNI-End--> <!--X-User-Footer--> <!--X-User-Footer-End--> <ul><li>Thread context: <BLOCKQUOTE><UL> <LI><strong><A NAME="01252" HREF="msg01252.html">[MUD-Dev] You think users won't number crunch and statistise your MUD?</A></strong>, J C Lawrence <a href="mailto:claw#under,engr.sgi.com">claw#under,engr.sgi.com</a>, Mon 29 Jun 1998, 20:56 GMT <UL> <LI><strong><A NAME="01255" HREF="msg01255.html">[MUD-Dev] Re: You think users won't number crunch and statistise your MUD?</A></strong>, Dr. Cat <a href="mailto:cat#bga,com">cat#bga,com</a>, Mon 29 Jun 1998, 22:02 GMT </LI> <LI><strong><A NAME="01266" HREF="msg01266.html">[MUD-Dev] Re: You think users won't number crunch and statistise your MUD?</A></strong>, Ling <a href="mailto:K.L.Lo-94#student,lboro.ac.uk">K.L.Lo-94#student,lboro.ac.uk</a>, Tue 30 Jun 1998, 12:58 GMT </LI> <LI><strong><A NAME="01272" HREF="msg01272.html">[MUD-Dev] Re: You think users won't number crunch and statistise your MUD?</A></strong>, Travis S. Casey <a href="mailto:efindel#io,com">efindel#io,com</a>, Tue 30 Jun 1998, 19:13 GMT </LI> </UL> </LI> <LI><strong><A NAME="01251" HREF="msg01251.html">[MUD-Dev] A variation on persistent store techniques with notes on distributedprocessing support</A></strong>, J C Lawrence <a href="mailto:claw#under,engr.sgi.com">claw#under,engr.sgi.com</a>, Mon 29 Jun 1998, 20:34 GMT <LI><strong><A NAME="01237" HREF="msg01237.html">[MUD-Dev] the why of online worlds</A></strong>, Mike Sellers <a href="mailto:mike#bignetwork,com">mike#bignetwork,com</a>, Mon 29 Jun 1998, 03:42 GMT <UL> <LI><strong><A NAME="01238" HREF="msg01238.html">[MUD-Dev] Re: the why of online worlds</A></strong>, Ben Greear <a href="mailto:greear#cyberhighway,net">greear#cyberhighway,net</a>, Mon 29 Jun 1998, 05:10 GMT </LI> </UL> </LI> <LI><strong><A NAME="01236" HREF="msg01236.html">[MUD-Dev] Re: what's fun?</A></strong>, Richard Bartle <a href="mailto:76703.3042#compuserve,com">76703.3042#compuserve,com</a>, Sun 28 Jun 1998, 10:21 GMT <LI><strong><A NAME="01235" HREF="msg01235.html">[MUD-Dev] Re: Quotes from Marcus Ranum</A></strong>, Chris Gray <a href="mailto:cg#ami-cg,GraySage.Edmonton.AB.CA">cg#ami-cg,GraySage.Edmonton.AB.CA</a>, Sat 27 Jun 1998, 19:46 GMT </UL></BLOCKQUOTE> </ul> <hr> <center> [ <a href="../">Other Periods</a> | <a href="../../">Other mailing lists</a> | <a href="/search.php3">Search</a> ] </center> <hr> </body> </html>