Early in 1996 a new recovery algorithm reminiscent of shadow paging was invented at HUT. The new algorithm, baptized Shades, is particularly apt for versions (snapshots), small objects, and a main-memory environment (Oksanen; 1999). Shades is essentially a run-time of a persistent programming language.
Versioning increases concurrency under heterogeneous transaction load. For example long read-only transactions, such as backups and billing, can be performed within their private versions without obstructing other transactions. Avid development of Shades has furnished it with other desirable features, such as a real-time compacting garbage collector with negligible memory overhead. A mechanism for replicating the Shades database transparently to the application programmer has also been implemented and experimented with.
Depending on the update pattern, we have been able to achieve a sustained performance of 32.000 to 130.000 updates, or 30.000 TPC-B -like transactions per second with 50% memory utilization on a 200 MHz Pentium Pro.
The project did extensive experimental work in the field of index and collection structures. Data structures implemented on Shades must be copy-on-write, or (strictly) functional, whereas most data structures described in literature require update-in-place, or mutation.
Numerous collection data structures such as lists, functional queues, priority queues, balanced trees, tries, and character strings have been implemented for Shades at HUT. Some of them are discussed in Paajanen's Master's Thesis and Oksanen's Licentiate's Thesis.
At Nokia Networks work concentrated on various tries, both copy-on-write and update-in-place, and with varying compression methods, fanouts and implementation details in addition to a telecom-specific analysis tree and a full-fledged internal node AVL-tree library.
The work on a database programming language called Shines was initiated during the project, but is currently being finished on a voluntary basis. Our primary goal is not, however, to introduce yet another programming language. Instead, a programming language is merely used as the most powerful and general means to interface Shades and the index structures with application domains.
The execution mechanism of Shines is a bytecode interpreter structured according to the continuation passing style (CPS), which is more expressive than that of e.g. JavaTM. CPS can be used to implement other control structures, including first-class functions, exceptions, co-routines, and threads. Furthermore, since the byte code interpreter's internal data structures are managed by Shades, running byte code processes can be treated with the same tools as data. For example, processes can be replicated and they are recoverable from disk. Migrating processes, e.g. for purposes of load balancing, is as easy as migrating data.
Shines computations are real-time, i.e. they are guaranteed to receive a reasonable fraction of the CPU-time given to the database manager. Both the data manipulated by Shines programs and even the computations expressed in Shines are persistent in the sense that they are resilient to power failures, system crashes, etc. Shines computations can be automatically replicated over two or more computers. Therefore Shines programs are automatically resilient even to hardware failures.
Work at Nokia Networks concentrated on research in type systems and type inference. The type inference algorithm was found unsatisfactory and the Shines that will be published under GPL will be based on a simple static type checking algorithm developed by volunteers after Nokia aborted the project.
We have implemented a set of tools and libraries needed for efficient software development. The toolset includes a profiler and a graphical user interface kit HiGUI and related tools. Unfortunately a debugger and a Shines reference manual were never completed. Fortunately the byte code interpreter of Shines has numerous features that help debugging, and a tentative documentation of Shines will be written in fall of 2001 on by volunteers.
The HiBase server can be connected through TCP/IP or through a smart pointer interface. The code, mostly developed at HUT, has been tested to work without modifications on numerous UNIX-like platforms, including 64-bit architectures.