enum which is referenced by code generated by the WSDL compiler. The workaround is to compile just this generated source with the -source 1.4 flag. svn co https://mulgara.org/svn/mulgara/trunk/kowari-1.2org.kowari packages over to org.mulgara. This would be easier with the refactoring tools in Eclipse, but these won't use the required svn mv command. Much of the first round will be a simple search/replace, so I may just be dusting off my perl/sed skills. To anyone with suggestions on how to do this more intelligently, please get in touch!owl:cardinality of "1". The data type for owl:cardinality is xsd:nonNegativeInteger, so that's what I used. So far, so good.xsd:int. However, when looking at the full contents of the model I was surprised to see the following numbers in the sequence: "3"^^<http://www.w3.org/2001/XMLSchema#int>
"2"^^<http://www.w3.org/2001/XMLSchema#int>
"1"^^<http://www.w3.org/2001/XMLSchema#nonNegativeInteger>int and nonNegativeInteger are both subtypes of integer, but they are not in the same branch. So neither can be used in the place of the other, unless an application specifically calls for an integer (their closest common ancestor).Session interface.ItqlInterpreterBean. It seems that a single error (often avoidable as they are normally caused by programming bugs) can render the Session nearly useless. There is some kind of synchronization issue after an Exception is thrown, that a Session can't seem to overcome, at least for a couple of operations after that. I'm not sure why this is, but it bears investigating.otool in OS X. The author had been looking for an ldd replacement for finding the dynamically linked libraries that a binary uses, which is something I've wanted as well. I just didn't know about otool.otool seems to be a Swiss-army-knife for inspecting Mach binary files. The array of switches seem quite large, particularly since each function seems quite unrelated to most of the others. It makes the tool feel a little overloaded./usr/bin/crt1.o contains the entry point code for all programs in OS X. I've been interested in the structure of universal binaries, particularly dynamic libraries, so this seemed like a good library to apply otool to. otool -f lipo -detailed_infootool flags duplicate the functionality of other programs?0xcafebabe. I was shocked at this, as this is the same magic number used by Java class files. Why would they share this value?cctools package in the Darwin project:Changes for the 5.16 release (the cctools-520 release):Looking at the code in question, it now looks for bytes at a particular offset to try to avoid mistaking a Java class file for a Mach binary. I don't know if it's justified, but I always feel uneasy when a programmer leaves a note to say that the implemented approach is a hack.
- Fixed a bug that caused otool(1) to crash when it was called with a bad fat
file (a java class file). The calls to ofile_first_arch() in ofile.c was not
checking its return value and later causing the code to crash when it should
have returned in case of an error. Radar bug #3670740.
java.util.logging.ErrorManager: 5
java.util.MissingResourceException: Can't find bundle for base name sun.text.resources.DateFormatZoneData, locale en_US/etc/weekly, so I decided to check who was supposed to call it and when./etc/weekly is a symlink to /etc/periodic/500.weekly, so I grepped through /etc and discovered: crontab:# The periodic and atrun jobs have moved to launchd jobs/sbin/launchd, which did little more than tell me it is an admin command (obviously). So I checked out the man pages. ~/Library/LaunchAgents Per-user agents provided by the user.
/Library/LaunchAgents Per-user agents provided by the administrator.
/Library/LaunchDaemons System wide daemons provided by the administrator.
/System/Library/LaunchAgents Mac OS X Per-user agents.
/System/Library/LaunchDaemons Mac OS X System wide daemons.com.apple.periodic-monthly.plist which appeared to be what I was after. Looking inside I found that it was all XML, as advertised, including the following fragment: <key>ProgramArguments</key>
<array>
<string>/usr/sbin/periodic</string>
<string>weekly</string>
</array>/System/Library/LaunchDaemons/com.apple.periodic-monthly.plist.file /usr/sbin/periodic, and was told:/usr/sbin/periodic: Bourne shell script text executableAbstractBlockFileBlockFile, but it has a few internal details worth mentioning.AbstractBlockFile contains a static block which determines the byte ordering to be used for all files. This is generally the native format for the platform, but maybe overridden by setting the system property tucana.xa.useByteOrder to native (the default), big_endian, or little_endian. This should usually be left alone, but it may be necessary if files have been moved from one computer to another with a different CPU architecture. Upgrading an Apple from PowerPC to the new Intel Core Duo is an good example of the need for this option.AbstractBlockFile performs several checks. It starts by checking if the file is already present in a static set of files. If so, then this JVM has already opened the file, so an exception is thrown. Otherwise, the file is added to the set once it has been opened.IOException will be thrown, and the mapping must be removed. Running the garbage collector is usually enough to clean up any unused file mappings, but on Windows it is necessary to run the collector several times for this technique to work.for (;;) {
try {
fc.truncate(fileSize);
break;
} catch (IOException ex) {
if (retries-- == 0) {
logger.error(
"Could not truncate file: \"" + file +
"\" to size: " + fileSize, ex
);
throw ex;
}
System.gc();
try { Thread.sleep(100); } catch (InterruptedException ie) { }
System.runFinalization();
}
}clear(), close() and delete().openBlockFile() methods each take an IOType to determine which of the implementing classes to return an instance of. However, these methods also check the tucana.xa.forceIOType system property to see if this value should be overridden. If the property is set to mapped or explicit then that will dictate if MappedBlockFile or IOBlockFile should be used. Otherwise, the requested IOType will be used.ensureOpen() method. This method makes sure that a file is open, and if it is not, then it attempts to perform the open operation. The operation is called in this way to try to cover occasions where a problem occurred (such as a "rollback" operation), and there is some code in the method to handle these conditions.AbstractBlockFile also call ensureOpen before performing file operations, in case anything has happened to close access to the file.ensureOpen and the isOpen set is all synchronized.
BlockFileBlockFile is an interface for accessing files full of identically sized "blocks" of data. This interface is like IntFile, in that they both describe the abstract methods for accessing their respective files, and both have two concrete implementations: one for mapped file access, and the other for normal I/O access. In the case of BlockFile these are MappedBlockFile and IOBlockFile.IntFile, the concrete implementations for BlockFile share a significant portion of their code. This is shared between the two classes by having them both extend an abstract class called AbstractBlockFile, which in turn implements BlockFile. So MappedBlockFile and IOBlockFile do not implement BlockFile directly.BlockFile superfluous, since AbstractBlockFile can be used in every context where BlockFile might have been. However, using an interface in this way is a well established technique in Kowari. It allows for the rapid development of alternative implementations as the need arises. It also permits an object that fulfils a number of roles to implement more than one interface. These advantages both help the codebase stay flexible for ongoing development.BlockFile is to store a series of records of identical structure in a file. Each record will be exactly the same size. The data structure within that record is left up to the caller. Kowari uses BlockFiles to store numerous data types, including strings (of defined lengths), numbers, tree nodes, and linked lists.setNrBlocks() andgetNrBlocks() are used to set and get the length of the block file. Since the file may only be viewed as a collection of blocks, then its length should only be measured in units of blocks.clear() is used to remove all data from the file, and set it to zero length. force() is used to block the process until all data is written to disk. unmap() attempts to remove any existing file mappings, close() closes the file, and delete() closes the file and removes it from the disk. See IntFile for a more detailed explanation.Block class was created to abstract away access to the records stored within a BlockFile. The block is always tied back to its location on disk, so any operations on that block will always be to the specific location on disk. This is important for memory mapped files, as it means that a write to a block will be immediately reflected on disk (though disk I/O can be delayed by the operating system) without performing any explicit write operations with the block.BlockFile are also expected to manage Blocks through an object pool. This was particularly important in earlier JVMs, where object allocation and garbage collection were expensive operations. Fortunately, recent versions of Java no longer suffer these effects, and an object pool can even slow a process down.BlockFile methods all accept an ObjectPool as a parameter. This may appear unnecessary, since a pool would usually be associated with an instance of the BlockFile class, but in this case there are several pools which may be used, depending on the needs of the calling code.Block MethodsallocateBlock() is used to get a Block for a particular file position, defined by a blockId parameter, but not to read the file for any existing data. This is for new positions in the file where the data was previously unused. There is no reason to read the data at this point, and the read operation will be time consuming. Writing the resulting block will put its contents into the file at the given block ID.readBlock is similar to allocateBlock, but the block is already expected to have data in it. The Block object is allocated and associated with the appropriate point in the file, and data is read into it.allocateBlock() and readBlock() methods are identical in the MappedBlockFile class.allocateBlock() and readBlock() should be passed to releaseBlock() once they have been finished with. This allows the block to be put back into the object pool. While not strictly necessary, it should improve performance.writeBlock() writes the contents of a Block's buffer to that Block's location on disk. This performs a write() in IOBlockFile and is an empty operation (a no-op) in MappedBlockFile.copyBlock() method sets a new block ID on a given Block. This now means that the same data is set for a new block. On IOBlockFile this is a simple operation, as the buffer remains unchanged. However, on MappedBlockFile the contents of the first block have to be copied into the new block's position. This is unusual, since MappedBlockFile usually does less work in most of its methods.writeBlock simply writes a block's buffer back to disk. This is a no-op in MappedBlockFile.modifyBlock() and freeBlock() should be removed from this class, as they are operations which are designed for ManagedBlockFile. This class provides a layer of abstraction over BlockFile and will be described later. The only implementations of these methods is in AbstractBlockFile where an UnsupportedOperationException is thrown.BlockFile interface also includes a static inner class which defines an enumeration of the types of BlockFile. This is the standard enumeration pattern used before Java 1.5.AbstractBlockFile to determine which concrete implementation should be instantiated.
MappedIntFileget() and put() operations, which in turn get passed into direct memory accesses.MappedByteBuffer called (funnily enough) mappedByteBuffers. Enabling access to the same data in ints or longs is a pair of associated arrays labeled intBuffers and longBuffers.mapFile(). This method loops through the array of buffers, and for each element it sets up the mappings to the appropriate areas of the file. This method is also called when a file is expanded, in which case it copies all the existing mappings from the original array, and appends the new mappings to the end of the new array. Any failed attempts at mapping will result in the garbage collector being run, and the mapping attempted once more. This process is in a loop that will run 10 times (yes, that's a magic number that seems to work well. It should probably be configurable).setSize(). There are currently no use cases to shrink a file, except for cases where the file is shrunk to zero size (with clear()), so smaller sizes than the current size are ignored. Once the size is determined, mapFile() is called again to update the mapping arrays and create the new mappings.get and put methods first need to determine the correct mapping to use (by taking the absolute offset divided by the size of the mappings) and the offset into the mapping (by taking the absolute offset mod the size of the mappings). Does this remind any Intel "protected mode" programmers of selectors and offsets? :-)MappedIntFile which can be expanded while mapping a large portion of memory, can handle more than 2GB, and is as fast or faster on all operations than a single large mapping would have been.
Grammar
The week was filled with lots of extra-curricula stuff, mostly (though not entirely) due to a visit from the client whose project I'm working on. But by the end of the week I finally had the grammar code parsing a lot of straight forward English into RDF. I also have a few "hacks" to make it a little more RDF friendly, such as picking up prepositions in predicates.
For instance, when I first parsed, "The quick brown fox jumps over the lazy dog." I was getting a subject of fox a predicate of jumps, and an object of dog. This says a something a bit different to the original intent. By picking up the preposition for the adverbial phrase, I instead get a predicate of jumps over, which is what I wanted.
It's still rudimentary, but it's very cool to stick in natural English and get out sensible RDF. I'd love to open source this stuff, but I did it on the company's dime, so it's their call. Probably not, but they want to get more involved with OSS, so maybe.
On the other hand, it wouldn't hurt if the code were never open sourced. I didn't really know what I was doing when hacking the grammar code, so it could be a lot prettier (and more extensible). Releasing dirty code into the wild can just be a recipe for embarrassment. :-)
Advanced Degrees
DavidW posted his result on the What Advanced Degree Should You Get test. OK, so these tests are far from giving a definitive portrayal, but I couldn't fight the temptation to fill it in. What do you know? I got:
| You Should Get a PhD in Science (like chemistry, math, or engineering) |
 You're both smart and innovative when it comes to ideas. Maybe you'll find a cure for cancer - or develop the latest underground drug. |
Chicago PD
I was going to complain cathartically tonight, but Anne's done it for me. I've started going to the gym again tonight, so that's helped me feel a bit better, despite my lack of catharsis.
We have a chain on the door now, so hopefully we'll have no more incidents. I'm still feeling paranoid though.
Bottom Up
There is a lot to be said for describing a system from the top down. The overall structure comes into view very quickly, and there is a concentration on the general architectural concepts which are so important for understanding and modifying the code.
However, I have found that describing Kowari at a high level always seems to lead to questions about the details. There are concepts that people seem to struggle with until they see how all the details are managed. This encourages me to approach the system from the ground up. An obvious advantage of this approach is that there are no dependencies on unexplained systems. Conversely, a lot of ground has to be covered before the overall structure comes into view.
There are also a number of operations at the bottom levels which are created to support higher level concepts. While the operations are easy to follow, the need for them may be unclear until the higher level code is viewed.
Possibly the best compromise is to start at the top, explain the requisite lower-level details as needed, and to return to the top whenever possible. My main problem here is that the theme of the discussion jumps around a lot, I may also end up discussing details which people didn't need, while skipping those which were more interesting.
In the end I've decided to go bottom-up. At least there I can be consistent with this approach, and I don't have to be concerned about missing details. More importantly, once I start getting higher up in the architecture, it will be possible to refer back and forth as required (that's an advantage of written explanations over spoken ones). The one piece of architecture that I feel is important to know at this level is the Phase Tree design. This was covered in my last entry.
The descriptions I'll provide for the lower level classes should be considered a supplement to the Javadoc. If anyone would like to see more info on anything, then please let me know.
I'll start in the org.kowari.util package.IntFile
This class provides the semantics of an array of 64 bit long values, backed by a file. It has operations to set the size of the array (setSize(int)), and to set and get values from any position from 0 to the end of the array (putLong(long, long) and getLong(long)).
A less used set of options, are the getters and setters which can be used to treat the structure as an array of 32 bit int values (putInt(long, int) and getInt(long)), or 8 bit byte values(putByte(long, byte) and getByte(long)).
This class also provides storage for an array of "unsigned" 32 bit integers. This is handy for file access, and managing some data types. However, unsigned values are not directly supported in Java (which the exception of the char type). To manage them, they are passed around in 64 bit longs so they get handled correctly, but they are still stored on disk in a 32 bit pattern. The methods here are called putUInt(long, long) and getUInt(long).
Concrete ClassesIntFile is an abstract class, and implements minimal functionality. The real work is done in a pair of concrete classes called ExplicitIntFile and MappedIntFile.MappedIntFile uses the New IO (NIO) functionality introduced in Java 1.4. It memory maps a file, allowing the underlying operating system to manage reading and writing of the required memory buffers. This leverages the efficient management of disk and memory that is essential in modern operating systems, and avoids the traditional copy to or from additional memory buffers.
Unfortunately, memory mapping files in this way is restricted by the size of the address space of the process. On a 32 bit system, this creates a maximum limit of 4GB, though the program and the operating system must use some of this space. 64 bit systems don't do much better, as many 64 bit operating systems impose limits within their address space for various operational reasons. In Java, the addresses for NIO are all 32 bit int values. Since this is a signed value (the sign using up one bit), the maximum size for a single file mapping is 2GB.
All this means that if a Kowari instance needs more space, it has to revert to using standard read/write operations for accessing the files. This is the purpose of the ExplicitIntFile class. This class implementation of each of the put/get methods calls down to read/write methods on the underlying java.nio.channels.FileChannel object. This implementation is not as fast as MappedIntFile, but it can operate on much larger files, particularly when address space is at a premium.
More IntFile
The constructors for each of the concrete implementations of IntFile are all default (not public). Instead, the IntFile class contains factory methods which instantiate the appropriate concrete class according to requirements.
The factory methods are all called open(...), and accept either a String or a java.io.File object. They will open an existing file when one exists, or create a new file otherwise.
First of all, the system properties are checked for a value called "tucana.xa.forceIOType". If it doesn't exist, then it defaults to using MappedIntFile. Otherwise, it makes a choice based on the expected values of "mapped" or "explicit". Any other value will fall back to MappedIntFile and give a warning in the log.
Unfortunately, we have found a bug that occasionally manifests in ExplicitIntFile. DavidM tracked it down, but it is tough to reproduce. I don't have the details, but on hearing this I audited this class, and it all appears correct. Until we have a solution to this problem, the factory method is temporarily using MappedIntFile in all cases (this has been a problem for some users, and needs fixing).
Forcing, Clearing, and Deleting
The remaining methods on IntFile are for managing the file, rather than the data in it.force() is used to ensure that any data written in the putXXX(long, XXX) operations has been written to disk. This relies on the operating system for the guarantee of completeness. This is relevant to both mapped and explicit IO, as both are affected by write-behind caching. This operation is essential for data integrity, when the system needs to know that all files have reached some fixed state.clear() leaves the file open, but truncates it to zero length, thereby deleting the entire contents of the array.close() simply releases the resources used for managing the file, and is primarily used during shutdown of the system. delete() also releases all the resources, but then deletes the file as well.
The final method to consider is unmap(). This method is only relevant to the MappedIntFile class, but it must be called regardless of the implementing class used. This is because any calling code cannot know which implementation of IntFile is being used (this is intentionally hidden, so it can be swapped with ease).
When unmap()is called on MappedIntFile, all the references used for the mapping are explicitly set to null. This allows the Java garbage collector to find the mappings and remove them, thereby freeing up address space.
This is an important operation, but it is difficult to enforce. Java does not permit explicit unmapping of files, since allowing it would permit access to memory which is not allocated (a General Protection Fault on Windows, a segfault on x86 Linux, and a bus error on Sparc Linux and Mac OS X). The closest we can come to forcing this behavior is to make the mapping available to be garbage collected, and run the garbage collector several times until the mapping has been cleaned up. This actually works on most operating systems, but needs to be iterated much more on Windows before it works.
Late Night
There are some specific details in MappedIntFile that need to be addressed, but I'll have to leave here and get some sleep. Hopefully I won't be woken by the Police tonight...
Expenses
No blogging last night, as I was working on expense reports. Somehow I doubt that work will appreciate that I had to stay up to 1am, but they'd certainly notice if I hadn't. Even so, I had to spend more time on them this afternoon.
As if that weren't enough, I've also filled in all the paperwork required to become a full-time employee. It's a little scary when you have no idea of the tax system in this country. It also doesn't help that I don't have an SSN.
I applied for an SSN last week (my first day in town), but they told me that USCIS (formerly the INS) have not yet entered our names into the system. Apparently that takes 10 working days. Getting an SSN after that will take another 10 working days. So it will take me a month to get the one piece of ID needed to do practically ANYTHING in this country.
It seems a little weird that it's this hard, given that every person who is given a work visa here will require an SSN. So why not process it all together and hand out the SSN with the visa? Not to mention that some official documents require a Resident Alien number, but I have to apply for that separately as well! I'm not sure where to get it either. Possibly USCIS.
In the meantime, Anne can't get an SSN because she's not entitled to work. This is despite the fact that her visa does allow her to work! It turns out that she has to go back to USCIS and apply for permission to work. Once she has that she can apply for her own SSN.
I'd hate to know what will happen to us if we have to talk to a doctor. We're insured, but won't they ask for an SSN?
Bus Error
It turns out that I was a little sloppy with some recent JNI code. If my Dictionary class failed to load in C, then it returned a null, as documented. However, I blithely stored this pointer and went on to use it.
Until now the Dictionary class always loaded, because I always made sure the dictionary files were available. But yesterday I started running a new set of tests in a separate directory, and they immediately reported: bus error.
I forgot how undescriptive a fault in C can be. :-)
It shouldn't have taken long to find this, but I used Eclipse to trace where the fault was occurring. While the GUI is slower on a Mac, for some reason the whole system brought my system to its knees. The trackpad was so jerky and intermittent that I started to worry that it would need fixing. It was only after tolerating this for an hour that I realized that the problem was not the trackpad, but that the machine was struggling too much. Shutting down Eclipse fixed the problem.
I'd be tempted to continue working from the command line, along with VIM, but Eclipse can't stand me fixing files outside of its domain. Why should it care?
At least I discovered the problem easily enough, and fixed it by bringing the dictionary files into the test area. I've also moved into the code and I now throw exceptions when a C library fails to initialize. I'm disappointed I hadn't done this in the first place, but at least I'll remember now (once bitten, twice shy).
BTW, has anyone else noticed that Intel (and x86 compatible) based systems report a segfault when dereferencing 0, while Apple and Sparc systems report a bus error? I always think of null dereferences as being segfaults, so I used to get confused when I saw bus errors like this. I wonder why there's a difference.
Oracle
After being aware of it for along time, today I finally had a brief look at Oracle's RDF support in 10g. I was really hoping that Oracle would bring their experience in developing database structures to the RDF domain, creating something very fast and scalable.
Unfortunately, it appears that 10g implements RDF as a schema in a set of standard relational tables, and have wrapped access to the system within Sesame interfaces, including SAIL. There's nothing wrong with building a Sesame system with an Oracle backend, rather than MySQL, but this isn't the Oracle system that I was hoping for. It doesn't bring in the extra efficiencies needed to make RDF really move. After all, RDF has a strict shape to the data, while a RDBMS needs to handle data of all kinds of shapes. This is why Kowari has such fast load times (when configured correctly).
Interestingly, the paper which describes the details of the system references Kowari. I was surprised at this when I read marketing phrases like:
Oracle Spatial10g release 2 introduces the industry's first open, scalable, secure and reliable data management platform for RDF-based applications.
Kowari was open, scalable, and reliable (to the best of my knowledge), and TKS was secure (one of the reasons for buying the commercial system over the Open Source Kowari).
Another quote says:
A key feature of RDF storage in Oracle is that nodes are stored only once -– regardless of the number of times they participate in triples.
The wording here suggests that Oracle is unusual in this regard, but almost all the RDF systems I am aware of share this feature, including Kowari. Perhaps the multiple indexing in Kowari caused some confusion here?
It appears that RDF support by Oracle has been implemented at the highest layers by RDBMS programmers. While it undoubtedly works, I'm disappointed that they haven't implemented RDF at a lower level. Still, it would be interesting to see how many triples a second it can load.
Free Lists
Now that I've discussed the principle behind phases, the next step is to discuss the classes which support this process. At the lowest level this is the class called FreeList. This class manages resources which are allocated and/or released in various phases. It enables new resources to be created as needed, and freed resources to be re-used efficiently.
The kinds of resources managed by the FreeList class are all the fixed-length records within data files, and also the numeric identifiers used for RDF nodes. The name of the class is an historical holdover from when it was simply used to hold a list of items which had been allocated and then freed. It does a lot more now.FreeList sits over the top of two other classes called BlockFile and IntFile, both of which are relatively easy to describe. Unfortunately, FreeList itself will take me some time to write about, and a late night is not the time to start. So I'll get into it in my next entry.
Files
With work and the move keeping me busy it's been a while since I last looked inside Kowari. To kind of ease myself back into it, I thought I should finally get around to writing some notes on the Kowari file system.
Phases
At all levels of abstraction inside the Kowari file system, the concept of phases keeps appearing. Phases are a way to keep track of a constant state in the system, regardless of any write activity that may be occurring. They are also used to serialize write access from different connections. While this does enforce consistency in the data on disk, the inability to allow multiple parallel writers is a current weakness in Kowari. (This is the principle reason the XA2 file system has been proposed).
Phases were borrowed from the TUX2 filesystem. In this approach, all data is laid out in a tree, with pointers going down from parent nodes to child nodes. This is a common pattern for data storage. (When I get OmniGraffle working again I'll put in a simple diagram of a tree here).
When a change needs to happen to a node in the tree, then that node is first copied to one side. The new copy contains pointers to the same children as the original node. Then each ancestor of this node is copied recursively, all the way up to the root of the tree. Each new parent node will refer to the copied child, but all the other children will be the same as the original node. The result is a pair of roots to two trees which are indistinguishable from each other, and which share many of the same nodes. (This is where I really need the diagram).
At this point, the new nodes can be modified without affecting the old tree. If modifications are required on any nodes in the old tree, these nodes can also be copied, along with all the parents up to an already copied parent. As soon as a node is found that has already been copied, then the existing copy can be adjusted to point to the new child node.
Once the write operation to the tree is complete, the old root will refer to the tree before the write, while the new root will refer to the tree after the write. The old tree was never touched, so it is guaranteed to be completely consistent. Once the new tree has been completely written, and is in a consistent state, then both trees will be completely consistent. That means that it is safe to use either root of the tree, without fear of power blackouts, OS crashes, etc.
At this point, a single number which holds the address for the current root of the tree can be updated. This can be performed atomically on any hard drive. Even if the power fails, every hard drive available today has enough capacitance to complete the write operation of a single block.
To guarantee an atomic write like this (ie. to guarantee a consistent tree on disk) the host operating system has to allow a force operation to disk. This is supported in Java, which in turn relies on the file system API of the underlying operating system. It is concerning that some operating systems have been known to postpone "force" operations (eg. Mac OSX), but this is a matter that is out of the control of user level code. Fortunately, the conditions required for this to cause a problem are far less likely to occur than the likelihood of hardware failure, so the risk is manageable.
Note also that the new root of the tree can be abandoned at any time with no consequences for the original tree. All that is required then is the ability to clean up or recover all the copied nodes created for the abandoned tree.
A new root to a tree as described here is called a new phase. Selecting a phase to be the new primary root of the tree, is known as committing the phase. Committed phases are always in a consistent state, removing the need to journal modifications.
Another feature of phases is that at any point in time a phase may be "kept" for reading. Any future modifications will start up a new phase (creating a new root to the tree). This means that it is possible to keep multiple phases active at any time, with each phase representing a "snapshot" of the data in the tree at the time that phase was kept. This is important for multiple readers to be able to get the latest available data while a long write operation is continuing. To ensure that the snapshots are kept consistent, they must not be modified. This means that only the most recent phase may be written to.
This describes Kowari's inability to allow multiple writers. However, this strategy is done to ensure that Kowari has a completely robust filesystem that is efficiently capable of withstanding any error, including the sudden removal of power. While speed and robustness are important, enterprise systems also require multiple concurrent writers. This has led to the plans for XA2.
XA2 will allow for multiple writers, but this in turn will require a form of journaling. Journaling is less efficient than phase trees, but we expect to gain in other areas of efficiency, making the overall performance even better. The system is more complex than the phase trees discussed here, so I will leave discussion of this for another time.
Landed
I resisted the title "Sweet Home Chicago", as I'm sure everyone who has ever moved here has said that. :-)
We got through the flight successfully, though we didn't get much sleep. It's harder to sleep when looking after children who aren't sleeping much either. Luc was amazingly well behaved. It was only in the last couple of hours that he started getting hyperactive (maniacal laughter, treating everything as a game, getting into everything, etc). Fortunately there were no tears or tantrums. Nic just slept.
Membership of the Qantas Club was wonderful at LAX. We got internet access (so I could confirm the flight time with JohnN at work), but more importantly, they had a room specifically for children. So we got a little private space, and Luc got to play with Tonka toys while watching Nickelodeon. Compared to sitting on a crowded concourse it was a little slice of heaven.
JohnN picked us up at O'Hare airport, and drove us into town. We had a lot of bags, so I'm glad we didn't have to arrange our own transport. I was also glad to have someone else driving, as it started snowing when we arrived. I've been in snow, but almost never seen it falling, so it was nice to see (though I'm sure the locals didn't enjoy it).
The apartment is minimally set up, which has been enough for the first day, but we need to get out and buy things like shelves if we want to stop living out of suitcases. We also need to buy some good cold-weather clothing for the boys, as they don't have enough. Frustratingly, most places have sold out, as they are bringing in the new season in preparation for Spring.
So yesterday and today are being spent shopping for essentials. I'm just grateful I don't have to deal with work, as I'm still suffering pretty badly from jet lag.
Wireless
The apartment came with cable access for the internet, but the company hadn't got around to brining over a wireless router. Fortunately, I had my AirPort Express with me, plus an extra US power adapter, so I plugged it in expecting it to all work.
While connecting the modem directly to my notebook worked fine, I couldn't make it work with the AirPort. The notebooks could connect to the AirPort just fine, but all routing stopped at that point, and there was no DNS.
I tried changing every setting I could think of, including setting the IP details statically to the details obtained when I plugged the notebook in directly. But the AirPort kept acting as if the ethernet was not there at all. I finally reset everything to what I thought it should have been (the settings I'd originally used, and then disconnected power to both the AirPort and the cable modem. 30 seconds later everything worked.
This isn't the first time I've seen certain devices fail connecting to a network, but not others. I wonder who was at fault in the protocol here... the AirPort or the cable modem?
Stress and Moving
This is probably my last entry from Australia for the time being. We've just spent the last few days in a mad scramble trying to finalize the things we thought were already done, or easier to complete than they really were. I hope we're near the end of it.
Tomorrow morning will see the moving company arrive, and take almost everything we own. We won't see any of it again for at least 8 weeks. We were told 8-14 weeks, so I'm expecting that it will really be around 16 weeks. Then off to a hotel, and onto a flight the next morning. It's a 12:10pm flight to LA... meaning that we have to check in no later than 9:10am! Sounds excessively early to me, but I suppose they need that to deal with the conditions set out at LAX.
In the meantime, we've been running all over town managing accounts, banks, and insurances. I've also had to spend a significant sum on travel insurance to cover us until my medical insurance becomes valid in April. This wasn't easy, as most providers won't handle people taking one-way trips. It had to be travel insurance, as we needed to be covered in case of problems on the trip, particularly if something happened to my notebook computer. Unfortunately, the only "one-way" insurance I found does not cover computers (only cameras), so I had to spend another couple of hundred to cover the computer as well. It all adds up, and I don't expect to see my credit card reimbursed soon. I'm going to be in a lot of debt for a while on this one.
Luc seems to be dealing with everything very well, and is still happy most of the time. I'm very grateful for this. He still needs his attention, so it can get difficult on occasion. Nic is as happy as ever. Anne and I are both very tired, and I'm looking forward to it all being over.
We've been told that we'll have internet access when we get there, so here's hoping I can get online quickly once we do.
Drowning
The visas finally arrived, and now I can do all the last minute things I have to get done before leaving Australia for good. The power will go off at the appointed time, as will gas, phone, internet, etc. Annoyingly, I can't cancel my mobile phone until I want it cut off, so I'll have to wait until the appointed time. I'll do that from overseas, as I'd like a bit of overlap so I can continue to make calls.
More frustrating is my health insurance. The Australian government gives a small subsidy to private health insurance but this is reduced if you spend any time after turning 30 without private cover. Because of this, I can only cancel my account without future penalties if I show my travel itinerary at an office. I have the itinerary now, but I'd rather not have to travel in.
My main problem at the moment is that I'm swamped with paperwork. Flights (obviously), visas (done, thank goodness), mail redirection (sorted), insurance (travel, landlords, shipping), mortgage (refinanced because the CBA would be a nightmare to deal with from the USA - they're bad enough in Australia), shipping forms, customs declarations, car sale, and rental documents. In the midst of this, our printer has decided to start mangling paper, so all those PDF documents I've been sent to fill in aren't helping.
Most of it takes a little time, but my "Supplemental Declaration for Unaccompanied Personal and Household Effects" form has one sticking point. It requires my "Resident Alien No." only I know nothing about this. My visa isn't forthcoming, and I have no other documents.
The visa has a 14 digit "Control Number" on it, but that seems to be a different number altogether. I found a document on the web (an application for info form at Sandia) which asks for both the Visa Control Number and the Resident Alien No. There is also an 8 digit number in red on the visa, but it's completely unlabelled, so I don't know what it might be. Google was surprisingly unhelpful in this regard. The best I've been able to do os to find the same form provided by other shipping companies, with all of them saying that the questions should be "self-explanatory". Great.
While writing some of this, my brother has come online and has started explaining some of it. I knew that I have to apply for an SSN once I get there (why not make it a part of the visa process?), but I didn't know that I also need to get a "permanent residence card". He also told me that he didn't get his "Resident Alien Number" until he'd been living there for a few months.
I'm starting to get confused about how I can actually move to this country. Is it possible?
Work
Unsurprisingly, work has slowed right down now, though I'm still trying to keep my hand in.
Someone had a problem the other day about using decision trees. They weren't scaling all that well (they scale by log(n) obviously), and he was trying to pick up some scalability from somewhere. He thought of breaking the tree into several subtrees, which might make the structure more manageable, but still requires the same number of decisions.
I started thinking about the first decision, which determines the sub-tree to go to. It occurred to me that several layers of decisions could be merged into a single "hashcode", which then finds the tree through a hash map. This tries to trade time for memory (less time for decisions, but more memory in the hash table). It's possible to go this route, but it requires careful merging of the data into the hashcode. If each of the elements going into the code require a test of some sort, then the number of tests to find the final data will not change. It's one of those things where you really need to see the shape of the data involved to see whether or not a particular optimization will work.
Merging data into a single "hash" is kind of like representing each of the elements of the data as separate dimensions. The hash code then leads to a point in N-dimensional (N-D) space representing the data you have so far. Using the hashcode to find the decision tree to use, means that these trees represent the work to be done for various regions of N-D space. This then brought me back to neural networks, as this is similar to how they are modeled.
This made me realize that in some ways a hash table can act like a neural network. The main difference here is that neural networks are forgiving for unexpected data. Hashtables can only be made to work this way if they can cover all allowable points in space. If the space isn't sparse, then that means that the hashtable might as well be an array - just so long as there is a way to map co-ordinates to something.
Anyway, it has me thinking that I might have to pull out some neural network algorithms, dust them off, and have a go at applying them to some of our problems in document categorization. I haven't used them in years, so it will be a real blast of retro for me.
RDF
In the meantime, it's about time that I look at RDF again. I still plan to use Kowari (since it's under the MPL, and that can't be changed), but while NGC are making things awkward I've been considering other routes. I'm tempted to use Sesame for a while, to learn more about it if nothing else. However, I'm not sure that I can make my thesis work in this framework, so I still need to look at other options.
I've been thinking of having a go at DavidM's skiplist code, to see if I can use it as the core to a new storage layer. If that works out, then I can start building some of the other layers on top, avoiding the problems that have had to stay in Kowari for historical reasons. Many of the top layers in Kowari were developed (as open source software) in the last year, so these can be transplanted easily.
I don't pretend that this would turn into a fully fledged RDF store (at least, not without a lot of time and help), but it could be a useful exercise. It would be enough for what I want to do OWL inferencing anyway. It might also go a bit quicker than Kowari, since I've already done a lot of this stuff once before! :-)
I'd rather work with Kowari (for the time being), but at least this way I don't have to worry about NGC interfering. It also starts introducing the skip list code that Kowari has needed for some time.
I'll see if I get any time for this in the coming week. It may be hard. I can't even do much on the plane, as we will be watching two young children. Still, it doesn't hurt to keep thinking these things over.
| CURRENT MOON |
