Last Updated: 9/25/2001

A_Buffer.rb

Purpose

License

Description

Dependencies

Limitations

Performance Considerations

To Do

Usage

Class Methods

Instance Methods

Testing

A_Debug Usage

 

Purpose:

This class quickly stores and retrieves key/value pairs in a fixed size buffer. This has been optimized to used as little disk space as possible and store/retrieve key/value pairs as quickly as possible. This class is used very heavily by the A_BTree class. This class stores key/value pairs in a malloced block of memory. You can insert and delete items similar to an Array. The items are put into the buffer using apack/aunpack or Marshal.dump/load. Apack/aunpack are methods very similar to Array.pack and String.unpack but have been modified to support database type objects such as date, time, varchar, char, etc. This class was created as a replacement for the Array class to store data in pages in the A_BTree class. The A_BTree class runs twice as fast, on average, using the A_Buffer class verses using an Array.

 

Description:

This class puts key/value pairs into a fixed size buffer for reading and writing to and from disk. This used by the A_BTree class. I don't expect there will be much of a need for a class like this, so I kept the methods to a minimum, creating only what I needed to support the A_BTree class. I wrote this in C to maximize performance because some of the functionality was difficult in Ruby. Apack/aunpack are methods written in C that very similar to pack and unpack but have been modified to support database type objects such as date, time, varchar, char, etc. They can be found in aruna.c.

Additionally, this module contains several C methods added to the A_FileStore class for performance reasons. These are used internally by the A_FileStore class to read and write A_Buffer class directly to disk. They are:

• read_direct() - reads and returns an object of A_Buffer class.
• read_direct_string() - reads and returns an object of String class.
• write_direct() - writes an A_Buffer or a String object and returns the A_Pos where the write occurs.
• seek_end_direct() - returns the A_Pos for the end of a file in the FileStore. 

This module also contains a new class call A_Pos. This is returned and used by A_FileStore and the C methods mentioned above. See the documentation for A_Pos for a description of this class.

The a_buffer.c module also contains the following additions to the Array class:

• asearch(key) - this works just like A_Buffer.asearch. It performs a modified binary search on Array for key. This is a binary search on the elements in the array where the index of the first element >= key is returned. This is used by A_BTree to determine where to insert new rows.
• a_cmp(key) - this is exaclty like Array.<=> except the it supports nil. This is used internally by asearch(). This is also used internally by the A_BTree class instead of Array.<=> when the key or the value is an array. For example:
• ( [1, nil, 3].a_cmp([1, nil, 2])) == 1
• ( [1, 0, 3] .a_cmp( [1, nil, 2])) == -1
• ( [1, nil, 3] .a_cmp( [1, nil])) == 0 # missing elements are treated as nil

This module also contains a new class call A_DeleteNode. This class is used internally by A_Filestore to track deleted file space in a filestore. There is no documentation on the A_DeleteNode class at this time.

This defines new errors standard errors called BufferIsFull and FileStoreIsFull. BufferIsFull is raised when you insert or update and the buffer it too full to accommodate the change. FileStoreIsFull is raised when you try to write to a filestore that has no space left.

The internals of A_Buffer. The first and second bytes in the filestore is number of items in the buffer (assuming index_data_type is an unsigned short). The next series of bytes are two byte pointers (offsets from the start of buffer) for each key/value pair in the buffer. Basically, it is an array of unsigned shorts containing one unsigned short for each key/valu pair in the buffer. These are used to quickly pinpoint the start of each key/value pair in the buffer. The key/value pairs are filled from the end of the buffer toward the front. The first pair is at the very end of the buffer, the second pair is in the second to last bytes of the buffer. The pointers and key/values fill up until they meet in the middle of the buffer. This design is not simple by any means, but it stores variable length records efficiently and the pointers are automatically optimized out when the key and value are fixed in length (when both are fixed in length, the position of each key/value pair can be easily calculated). In Aruna (A_BTree), A_Buffer.asearch(key) is called to find the slot to put the key/value pair in. This insures the keys are sorted in the buffer. Here is a sample of a buffer with 9 key/value pairs (8 bytes needed for each key/value pair) where buffer_size = 128 bytes. A | separates each value:

|09|120|112|104|094|086|078|070|062|054| … |k9v9|k8v8|k7v7|k6v6|k5v5|k4v4|k3v3|k2v2|k1v1|

Technically, if the key/value pair was 8 bytes for all pairs, then buffer would actually look like this because the pointers would get optimized out: 

|09| … |k9v9|k8v8|k7v7|k6v6|k5v5|k4v4|k3v3|k2v2|k1v1|

 

Dependencies:

• Aruna.c - there are several methods or functions defined in aruna.c that are used. Apack and aunpack are two them.

 

Limitations:

• There could be some machine dependant code in this module that has not been tested on hardware other than Intel. My goal was to not have any machine dependant code in this class but I am sure how successful I was because this is a C module (a_buffer.c). There is machine dependent code in aruna.c. If you are running on a Mac, OSF, HP, or other hardware than Intel, then please run and review the tests (tst_a_buffer.rb) careful and make sure this class works okay. Please email: new_hardware@arunadb.org if you successfully test a new platform so this page can be updated. Please email support@arunadb.org if are trying to port to an untested machine and you are having problems. This has been tested on the following platforms:
• Win95/WinNT 4.0/Win2000 on Intel
• FreeBSD 4.2 and linux (Red Hat 6.2) on Intel.
• If you want to use this class, be prepared to add some of the methods that make the Array and Hash classes so useful. This class meets a single specific need for the A_BTree class, to quickly store and retrieve key/value from a fixed sized buffer.
• The buffer size must be less than 64K in size. You could easily expand this to 4G by changing the following line in a_buffer.c (this has not been tested):

#define index_data_type unsigned short

to

#define index_data_type unsigned int

The draw back is that the 2 byte buffer pointer for each key/value pair will now be a 4 byte buffer pointer.

 

Performance Considerations:

• Use key and data pack strings when possible. Providing valid pack strings for both the key and the value is faster and uses less memory (disk space) per key/value pair than not using them. If provided and both the key and the value are fixed in size, then certain optimizations are performed on the buffer to used even less memory and perform better.  In other words, not using a pack string or using an '*' is slower and requires more disk than using a more specific pack string such as 'I' or 'v'. The '*' is a catch all that uses Marshal.dump/Marshal.load.
• Determining memory requirements (how many key/value pairs can I fit in this buffer?). This is a difficult thing to determine and depends on many factors. Here are some guidelines to help out:
• If you provide a key pack string and a data pack string and they are both fixed in size (i.e. you are not using a varchar in the key or value) then the size can be exactly determined by calling the methods key_size() + data_size(). This is the most efficient use of the buffer and there is no per record (key/value pair) overhead.
• If you provide a key pack string and a data pack string and either the key or value are not fixed in size (you are not using a varchar in the key or value or the value pack string is nil or '*'), then the size can be determined by size of the key + the size of the value + 2 bytes for a pointer that is needed to determine where each key/value pairs is in the buffer. Basically, there is 2 bytes (4 bytes if your buffer size is > 64K) of overhead per key/value pair stored in the a_buffer.
• If the key pack string is nil or '*', then the size can be calculated by adding the Marshal.dump.size of the key + size of the value + 2 bytes of overhead for the pointer + 2 bytes of overhead for the Marshal.dumping the key. Basically, there is 4 bytes (8 bytes if your buffer size is > 64K) of overhead per key/value pair stored in the a_buffer (2 bytes for the pointer to the key/value pair and 2 bytes for the size of the key). Using a key pack string of nil or '*' is the most inefficient use of the buffer.

 

To Do:

• Add a sort method and use this in the A_FileSort class rather than an array for processing rows.
• Add support for large buffers greater than 64K.

 

 Usage:

N/A

 

Class Methods:

A_Buffer.new (buffer_size, key_pack_string, key_is_array, data_pack_string, data_is_array)

Creates a new A_Buffer object. The key and data pack strings are used specify how to pack the data into the buffer. When provided, apack and aunpack are used to store and retrieve data to and from the buffer. When not provided or a '*' is used then Marshal.dump and Marshal.load are used to store and retrieve the data. Using pack strings typically use less memory for each key/value pair and are faster than using Marshal.dump/load. Marhsal.dump/load many be slower but it allows you put almost any Ruby object into a buffer (see the documentation on Marshal for details). Valid pack strings are provided for a small set of objects that are typically found in most databases. See apack for details on supported pack strings.

• buffer_size - the actual size of the buffer in bytes.
• key_pack_string - the key pack string used to pack the keys. If this value is nil, then '*' is used. There must be a key_pack_string for every buffer in order to correctly determine how big the key is for each key/value pair in the buffer. See the description of apack for details on the supported pack strings. If you are not sure what pack type to use or your key is does not have a pack type then use '*'. The '*' tells apack to Marshal.dump/Marshal.load the key. The key could be a single String or Fixnum, an array with many elements, or any other Ruby object that be Marshal.dumped. If the key is an Array, then there must be a type in the pack string for each element in the key array. Here are some examples:
• The key is a String - use 'v'. You could use '*', this is less efficient than 'v'.
• The key is a Fixnum - use 'I' or 'i' or 'S' or 's' depending on how large the Fixnum is. If you are not sure then use a '*'. '*' is the only way to guarantee that all possible Fixnum/Bignum values are stored correctly. 'I' or 'i' or 'S' or 's' are much more efficient that '*'.
• The key is an array of two Fixnums that fit in the range of an integer - use 'ii'. You could could use '*' but 'ii' is more efficient.
• The key is an array of two strings - use 'vv'.
• The key is an array of Fixnum, String, Fixnum - use 'ivi'. You should use '*' if the either of the two Fixnums could grow to a value that is out of range for an integer.
• key_is_array - If this is true then key_at() will always return an array, even if the key has only one element. If nil or false and the key is a single element (such as a fixnum or a string), then the single element is returned. If nil or false and the key is an array with more than one element, then an array is returned.
• data_pack_string - the data pack string used to pack the values. If this value is nil, then '*' is used and the value is Marshal.dumped/loaded. See the description of apack for details on the supported pack strings. Also see the description of the key_pack_string above. Keys and values are handled the same way.
• data_is_array - If this is true then data_at() will always return an array, even if the value has only one element. If nil or false and the value is a single element (such as a fixnum or a string), then the single element is returned. If nil or false and the value is an array with more than one element, then an array is returned.

 

Instance Methods:

asearch(key, exact_hit)

This performs a modified binary search on A_Buffer for key. This is a binary search on the elements in the a_buffer where the index of the first element >= key is returned. This is used by A_BTree to determine where to insert new rows. There is a similar method in a_buffer.c called Array.asearch.

key - is the key you are looking for in the buffer.

exact_hit - if 0 or nil, then return the index of the first element >= key. If != 0, then return nitems if the object is not found.

buffer_size()

Returns the actual size of this buffer in bytes.

clear()

Empties the buffer.

clear_pending()

Clears, deletes, or remove a pending insert/update. When an insert or update fails because the buffer is too full, the insert/update is remembered as a pending insert or update and an error is raised. There are three ways to clear a pending update/insert. 1) call move_rows to move rows to another buffer and make room for the insert/update. The pending update/insert is performed as rows are moved. 2) call clear_pending to clear or delete the pending insert/update. You will loose the inserted or updated data. 3) call complete_pending(). This will attempt to reapply the insert/update. This will fail unless you have deleted one or more rows from the buffer.

complete_pending()

Attempts to post a pending insert/update. This will likely fail unless you have deleted one or more rows from the buffer. When an insert or update fails because the buffer is too full, the insert/update is remembered as a pending insert or update and an error is raised. There are three ways to clear a pending update/insert. 1) call move_rows to move rows to another buffer and make room for the insert/update. The pending update/insert is performed as rows are moved. 2) call clear_pending to clear or delete the pending insert/update. You will loose the inserted or updated data. 3) call complete_pending(). This will attempt to reapply the insert/update. This will likely fail unless you have deleted one or more rows from the buffer.

copy(buffer)

Copies the internal data stored in self to buffer. For a complete copy of self do the following: new_buffer = buf.dup; buf.copy(new_buffer).

data_at(idx)

Returns the value stored at idx.

• Idx - is a number between 0 and nitems - 1. -1 will delete the last element in the buffer. Only -1 is supported, -2 will raise an error.

data_is_array?()

Return true if the values stored in this array should be returned as an array. Returns false if the values are returned as an individual object. It allows you to put 64 in and get 64 back out; [64] in and [64] back out.

data_is_array=(value)

Sets the data_is_array value. See description of data_is_array?() for more details.

data_pack_string()

Returns the data_pack_string currently assigned to this buffer. You can't change this value.

data_size()

If you have provided a valid data pack string and it contains a fixed size, then the fixed size of the value is returned. Otherwise 0 is returned. Certain optimizations are performed on the buffer when valid pack strings are provided and both the key and value have a fixed size. This is calculated from the data_pack_string. You can't change this value.

delete(idx)

Deletes the key/value pair stored at idx. Same as Array.delete_at(5).

• Idx - is a number between 0 and nitems - 1. -1 will delete the last element in the buffer. Only -1 is supported, -2 will raise an error.

dup(buffer)

This returns a new A_Buffer object that is a dup of self. This is a shallow copy of buffer. A new internal buffer is created but the objects in buffer are not copied to the dup.

empty()

Empties the buffer.

exists?(key, value)

Return true if this key/value pair exists in this buffer. If value=nil, then return true if this key exists in this buffer. Otherwise return false.

fits?(key, value)

Return the number of bytes this key value pair will use. Raise a NoMemoryError error if this key value pair does not fit in the buffer.

fixed_size?()

Return true if the key and value are both fixed in size. Otherwise return false. A_Buffer optimizes by eliminating the 2 byte buffer pointers when this is true. This value is automatically set when the buffer is created based on the key_pack_string and data_pack_string. You can't change this value.

insert(idx, key, value)

Insert the key/value pair at idx. Similar to Array[5, 0] = [key, value] where idx = 5. BufferIsFull is raised if the buffer is too full to hold this key/value pair.

• Idx - is a number between 0 and nitems. Idx == nitems or -1 will insert as the last element in the buffer. Only -1 is supported, -2 will raise an error.

key_at(idx)

Returns the key stored at idx.

• Idx - is a number between 0 and nitems - 1. -1 will delete the last element in the buffer. Only -1 is supported, -2 will raise an error.

key_is_array?()

Return true if the keys stored in this array should be returned as an array. Returns false if the keys are returned as an individual object. It allows you to put 64 in and get 64 back out; [64] in and [64] back out.

key_is_array=(value)

Sets the key_is_array? value. See description of key_is_array?() for more details.

key_is_byte_comparable?()

Return true if all the elements in the key are byte comparable. Otherwise return false. This is automatically set when the buffer is created by using the key_pack_string. If each element in the key_pack_string is byte_comparible then this returns true. Some types are byte comparible and others are not. When true, asearch is optimized by calling memcmp() on the data stored in the buffer. When false, the aunpack or Marshal.load is called to get the key out of the buffer before the compare is done. Byte comparable keys are faster than non byte comparable keys. You can't change this value.

key_pack_string()

Returns the key_pack_string currently assigned to this buffer. You can't change this value.

key_size()

If you have provided a valid data pack string and all of the keys elements are fixed in size, then the fixed size of the value is returned. Otherwise 0 is returned. Certain optimizations are performed on the buffer when valid pack strings are provided and both the key and value have a fixed size. This is calculated from the key_pack_string. You can't change this value.

move_rows(buffer, rows_to_move, force_move)

Move rows from one buffer to another. Returns the actual number of rows moved. There are many possibilities. You can even the rows out between the two pages, move all rows from one page to the other, or move a couple of rows from one page to the other.

If there is a pending update or insert, it is applied while the rows are being moved. When an insert or update fails because the buffer is too full, the insert/update is remembered as a pending insert or update and an error is raised. There are three ways to clear a pending update/insert. 1) call move_rows to move rows to another buffer and make room for the insert/update. The pending update/insert is performed as rows are moved. 2) call clear_pending to clear or delete the pending insert/update. You will loose the inserted or updated data. 3) call complete_pending(). This will attempt to reapply the insert/update. This will fail unless you have deleted one or more rows from the buffer.

• buffer - the buffer to share rows with.
• rows_to_move - If 0, then rows are moved until the buffers are close in size as possible. If < 0 then move all rows according to the direction provided below. If > 0 then this many rows will move until the buffers are even (when force_move == 0) or the receiving buffer becomes full.
• force_move - if 0, then rows are moved from the more full buffer to the less empty buffer. If < 0 then rows are moved from buffer to self. If > 0 then rows are moved from self to buffer.

Examples:

buf1.move_rows(buf2, -1, 1) # move all rows in buf1 to buf2 (prefix buff2 with rows in buff1 )

buf1.move_rows(buf2, -1, -1) # move all rows in buf2 to buf1 (append buff1 with rows in buff2 )

buf1.move_rows(buf2, 0, 0) # moves rows from the more full buffer to the less empty buffer until they match in size

buf1.move_rows(buf2, 1, 1) # move one row from the end of buf1 to the beginning of buf2

buf1.move_rows(buf2, 1, -1) # move one row from the beginning of buf2 to the end of buf1

nitems()

Return a count of key/value pairs stored in this buffer.

size()

Returns the actual size of the bufferin bytes, same as buffer_size.

unused()

Returns the number of unused, free, or available bytes in this buffer.

update(idx, new_value)

Updates the value stored a idx. BufferIsFull is raised if the buffer is too full to hold this update of the value.

• idx - is a number between 0 and nitems - 1. -1 will update the last value in the buffer. Only -1 is supported, -2 will raise an error.
• new_value - is the new value to store in the buffer for the key at idx.

update_key(idx, new_key)

Updates the value stored a idx. BufferIsFull is raised if the buffer is too full to hold the update of this key.

• idx - is a number between 0 and nitems - 1. -1 will update the last key in the buffer. Only -1 is supported, -2 will raise an error.
• new_key - is the new key to store in the buffer at idx.

used()

Returns the number of used bytes in this buffer.

 

Testing: 

tst_a_buffer.rb - tests the basic functionality of the A_Buffer class. To run these tests type:

ruby -I.. tst_a_buffer.rb

 

A_Debug Usage:

N/A