Re: Grace 0.51 released

From: Nick Roberts (nick.roberts_at_acm.org)
Date: 10/30/03 

Date: Thu, 30 Oct 2003 22:17:18 +0000

Simon Wright wrote:

>> [Tenet implementation will use clustering]

> I would be fairly amazed if anyone produced such an implementation in
> a general library without needing it themselves (certainly I won't for
> the BCs, partly at least because I feel I don't understand the concept
> totally!)
>
> I guess what you have in mind is some performance requirement; state
> that, maybe Charles or the BCs or whatever will do what you want,
> maybe not ..

Clustering is applicable to unbounded lists and unbounded maps (which I
call 'lookups'). As with other implementations, I intend to implement these
(in Tenet) by a (doubly) linked list and a linked tree respectively.
However, rather than having just one data element per node, as with usually
implementations, I will have a small array -- of fixed length -- for each
node, so that several data elements can be stored in each node (in the
array). This array is called a 'cluster array', and the nodes are called
'clusters'.

The basic idea is that by varying the length of the cluster array, it is
possible to adjust the trade off between higher memory efficiency (longer
arrays) and speed of operations (shorter arrays). At one extreme, the array
might have length 1; obviously this is the same as the usual
implementation. At the other extreme, one might have a very big array length.

For linked lists, each cluster (node) will be able to store the number of
data elements actually stored in its cluster array (from 1 to N, where N is
the cluster array length). In this way, arbitrary insertion and deletion of
elements can be achieved by the appropriate combination of inserting or
deleting clusters (nodes), and inserting or deleting data elements within
cluster arrays (by moving items and/or adjusting the dynamic length).

For lookups (maps), data elements are stored within cluster arrays sorted
by key. Insertion requires finding the correct position in the array (by
binary-chop search), and copying up the remainder. If the array is full, a
new cluster (node) has to be created. Deletion works the reverse way. The
tree is kept balanced using a standard AVL or RB algorithm.

I do indeed wish to use clustering for a particular application (which will
be called TDL, but that's another story). However, I feel that it is a very
general-purpose technique, suitable for most applications, and that it
should enable applications to achieve the right balance between memory and
speed efficiency.

Are there any existing container implementations which provide clustering? 

-- 
Nick Roberts

Relevant Pages

  • Re: Clustering Newbie - SAN Advice
    ... You are right to observe that we probably don't want cost of full-blown SAN ... piggy backing them on some sort of shared disk array. ... The disks in the array doesn't need anything special. ... single-instance cluster. ...
    (microsoft.public.sqlserver.clustering)
  • Re: Clustering Newbie - SAN Advice
    ... The disks in the array doesn't need anything special. ... single-instance cluster. ... a properly configured dedicated SQL server should ...
    (microsoft.public.sqlserver.clustering)
  • FileStream problem...
    ... It's a distributed application across a cluster of machines ... from there, the character array is blahblahblah, right? ... Offset and length were out of bounds for the array ...
    (microsoft.public.dotnet.distributed_apps)
  • Re: restoring quorum after array and logical drive repartitioning
    ... The previous setuppartioned 6 logical drives in a single array, with the quorum drive being on a logical drive in that array. ... I've removed SQL and moved it to a new cluster(Yea!!!!), but Exchange still runs on this cluster, and will remain on this cluster until Exchange 2007 rolls out and we replace the hardware with 64-bit servers. ...
    (microsoft.public.windows.server.clustering)
  • Re: Is it possible to delete an element from a sorted array with O(1) time?
    ... Is it possible to delete an element from a sorted array with Otime? ... integers in constant time" as asking whether there are sequences that can ... "it is possible to add requirements such that deletion of an arbitrary ... more natural) interpretation. ...
    (comp.programming)