<!-- MHonArc v2.4.4 --> <!--X-Subject: Re: [MUD-Dev] Persistant storage.... My current idea. --> <!--X-From-R13: ptNnzv-pt.UenlEntr.Sqzbagba.OP.QO (Quevf Uenl) --> <!--X-Date: Sat, 04 Apr 1998 23:21:42 +0000 --> <!--X-Message-Id: 9804041833.8w9r@ami-cg.GraySage.Edmonton.AB.CA --> <!--X-Content-Type: text --> <!--X-Head-End--> <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN"> <html> <head> <title>MUD-Dev message, Re: [MUD-Dev] Persistant storage.... My current idea.</title> <!-- meta name="robots" content="noindex,nofollow" --> <link rev="made" href="mailto:cg#ami-cg,GraySage.Edmonton.AB.CA"> </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="msg00017.html">Previous</a> | <a href="msg00019.html">Next</a> ] Thread: [ <a href="msg00012.html">Previous</a> | <a href="msg00019.html">Next</a> ] Index: [ <A HREF="author.html#00018">Author</A> | <A HREF="#00018">Date</A> | <A HREF="thread.html#00018">Thread</A> ] <!--X-TopPNI-End--> <!--X-MsgBody--> <!--X-Subject-Header-Begin--> <H1>Re: [MUD-Dev] Persistant storage.... My current idea.</H1> <HR> <!--X-Subject-Header-End--> <!--X-Head-of-Message--> <UL> <LI><em>To</em>: <A HREF="mailto:mud-dev#null,net">mud-dev#null,net</A></LI> <LI><em>Subject</em>: Re: [MUD-Dev] Persistant storage.... My current idea.</LI> <LI><em>From</em>: <A HREF="mailto:cg#ami-cg,GraySage.Edmonton.AB.CA">cg#ami-cg,GraySage.Edmonton.AB.CA</A> (Chris Gray)</LI> <LI><em>Date</em>: Sat, 4 Apr 98 11:33:42 MST</LI> <LI><em>>Received</em>: by ami-cg.GraySage.Edmonton.AB.CA (V1.17-beta/Amiga) id <8w9r#ami-cg,GraySage.Edmonton.AB.CA>; Sat, 4 Apr 98 11:33:42 MST</LI> </UL> <!--X-Head-of-Message-End--> <!--X-Head-Body-Sep-Begin--> <HR> <!--X-Head-Body-Sep-End--> <!--X-Body-of-Message--> <PRE> [Cynbe, as forwarded by Chris L:] :Meanwhile, I keep a cache buffer in ram of recently accessed objects: :I'm not comfortable with the time and space overhead of LRU management, :so instead I manage them essentially as a FIFO queue that objects :cycle through once loaded into cache: They are loaded at one end :and deleted at the other. Since deleted objects will still be in the :OS file system cache in general, frequently used objects will get :'read' back in very quickly, giving (I hope, no performance studies :yet) much of the performance of an LRU system in practice, without :much of the overhead. : :I allocate a (very) carefully tuned hashtable about 1/8 the size of :the ram buffer to map abstract pointers to current addresses: This :mapping takes about 15 risc cycles, which may sound like a lot :compared to single-cycle access via a hard pointer, but (given a :little intelligent coding, like looking up a string address just :once when copying it, not once per byte) turns out according to gprof :to be consuming only about 5% of my CPU time when Muq is running: I :feel this is a very reasonable price to pay for disk-based :operation... If you keep an index table in memory all the time, then there will also be no more than one disk read to get any DB entry. This is all somewhat similar to what I do in AmigaMUD, but different enough that I think its time (it being a weekend also gives me the time) to overview my setup. I made a very early decision which many people would disagree with, but which has worked out not badly. That decision was to encode the type of an object in the references to that object, rather than in the object itself or in fields beside the reference. So, my 32 bit reference consists of a six bit type code in the upper bits, and a 26 bit index number in the rest. That limits me to 64 million DB objects, which is enough for now. The big advantage to this scheme is that all "values" occupy the same size. 32 bit ints, fixed-point numbers, in-memory pointers, and typed DB references, all take the same 32 bits. This allowed me to have a 'value' union, which can be used to contain anything needed. So, for example, each local variable occupies 4 bytes, regardless of its type. In many situations the type field is redundant (since my in-MUD language is strongly typed), but in others it isn't. I use two disk files for the DB. One is the index file, and one is the raw data file. After a few header words, index file is an array of small structs, containing a 16 bit slot length, a 16 bit 'used' length, and a 32 bit file offset. By having the full size of this struct be a power of two, indexing it as an array was fast on my early target machines, which didn't have a 32 bit hardware multiply. The 26 bit index number of a DB reference indexes this index file, which is kept in RAM at all times. That yields the file offset of the actual data. The high bit of the file offset is set if the file slot referenced by this index entry is currently free. Having the 'used' length present allows me to find space in the in-memory cache that is no longer than actually needed, and also reduces the actual disk-read length to the minimum. Having the slot length present sometimes allows entries to be replaced in-place if they don't grow too much. An in-memory table contains pointers to some of the free file slots, which allows best-fit allocation from among that set. It is replenished by scanning the entire index occasionally, and freed DB slots are put into the table, so that they are re-used in preference. Backing up the actual database file is an in-memory non-write-through cache. It is maintained in an LRU ordering via a linked-list (so the LRU maintainance is quite cheap). There is also a list of free cache slots. The cache is flushed to disk in whole, when top-level MUD code requests it, or when the DB code cannot find a free or non-dirty cache slot that is big enough for a current request. Providing a quick short-circuit to the LRU mechanism is a map table, indexed by the DB index modulo the table size. The vast majority of DB lookups hit in this mapping table. Such lookups probably take on the order of 30 instructions, including some statistics code and the LRU maintainance. The system also has some higher-level caches, such as for MUD-code routines. I use a reference-counting scheme to know when DB entries can be freed, so there is potentially a lot of DB-writing to modify them. To counter this, I have another mapping table, the entries of which store the current ref-count, along with the DB's idea of the ref-count. These mappings are also non-write-through, thus eliminating most of the DB-writes for ref-count fiddles. As an example, consider what happens when something being carried by a player is dropped. In my system, it is added to the contents list of the current location, and removed from the list of things being carried by the player. This is two ref-count changes, but they cancel out, a situation handled nicely by the ref-count mapping table, resulting in no dirtying of the DB entry for the item itself. Whew! That's likely far more detail than anyone wanted! -- Chris Gray cg#ami-cg,GraySage.Edmonton.AB.CA </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="msg00017.html">GRUMPS</A></STRONG> </LI> <LI>Next by Date: <STRONG><A HREF="msg00019.html">Re: [MUD-Dev] Persistant storage.... My current idea.</A></STRONG> </LI> <LI>Prev by thread: <STRONG><A HREF="msg00012.html">Re: [MUD-Dev] Persistant storage.... My current idea.</A></STRONG> </LI> <LI>Next by thread: <STRONG><A HREF="msg00019.html">Re: [MUD-Dev] Persistant storage.... My current idea.</A></STRONG> </LI> <LI>Index(es): <UL> <LI><A HREF="index.html#00018"><STRONG>Date</STRONG></A></LI> <LI><A HREF="thread.html#00018"><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>Re: [MUD-Dev] Persistant storage.... My current idea.</STRONG>, <EM>(continued)</EM> <ul compact> <ul compact> <ul compact> <ul compact> <LI><strong><A NAME="00049" HREF="msg00049.html">Re: [MUD-Dev] Persistant storage.... My current idea.</A></strong>, J C Lawrence <a href="mailto:claw#under,engr.sgi.com">claw#under,engr.sgi.com</a>, Tue 07 Apr 1998, 16:56 GMT <UL> <LI><strong><A NAME="00063" HREF="msg00063.html">Re: [MUD-Dev] Persistant storage.... My current idea.</A></strong>, Ben Greear <a href="mailto:greear#cyberhighway,net">greear#cyberhighway,net</a>, Wed 08 Apr 1998, 00:50 GMT </LI> </UL> </LI> </ul> </ul> </ul> <LI><strong><A NAME="00011" HREF="msg00011.html">[MUD-Dev] Persistant storage.... My current idea.</A></strong>, J C Lawrence <a href="mailto:claw#under,engr.sgi.com">claw#under,engr.sgi.com</a>, Fri 03 Apr 1998, 23:42 GMT <UL> <LI><strong><A NAME="00012" HREF="msg00012.html">Re: [MUD-Dev] Persistant storage.... My current idea.</A></strong>, J C Lawrence <a href="mailto:claw#under,engr.sgi.com">claw#under,engr.sgi.com</a>, Sat 04 Apr 1998, 00:04 GMT </LI> </UL> </LI> <LI><strong><A NAME="00018" HREF="msg00018.html">Re: [MUD-Dev] Persistant storage.... My current idea.</A></strong>, Chris Gray <a href="mailto:cg#ami-cg,GraySage.Edmonton.AB.CA">cg#ami-cg,GraySage.Edmonton.AB.CA</a>, Sat 04 Apr 1998, 23:21 GMT </LI> <LI><strong><A NAME="00019" HREF="msg00019.html">Re: [MUD-Dev] Persistant storage.... My current idea.</A></strong>, Chris Gray <a href="mailto:cg#ami-cg,GraySage.Edmonton.AB.CA">cg#ami-cg,GraySage.Edmonton.AB.CA</a>, Sat 04 Apr 1998, 23:21 GMT <UL> <LI><strong><A NAME="00022" HREF="msg00022.html">Re: [MUD-Dev] Persistant storage.... My current idea.</A></strong>, Ben Greear <a href="mailto:greear#cyberhighway,net">greear#cyberhighway,net</a>, Sun 05 Apr 1998, 02:02 GMT </LI> </UL> </LI> <LI><strong><A NAME="00271" HREF="msg00271.html">[MUD-Dev] Persistant storage.... My current idea.</A></strong>, J C Lawrence <a href="mailto:claw#under,engr.sgi.com">claw#under,engr.sgi.com</a>, Wed 22 Apr 1998, 23:26 GMT </LI> </ul> </LI> <LI><strong><A NAME="00004" HREF="msg00004.html">Re: [MUD-Dev] (fwd) Re: Roleplaying</A></strong>, J C Lawrence <a href="mailto:claw#under,engr.sgi.com">claw#under,engr.sgi.com</a>, Wed 01 Apr 1998, 22:26 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>