Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Failed to load latest commit information.


This is a very simple C library for dealing with "foreign keys" (a term which I
am using very loosely). It depends on glib.

You can download the latest version of this software using git. The clone URL
for this project is git://

Build & Install
To compile this software you'll need to have the glib development headers and
libraries installed. For Ubuntu/Debian, the name of that package is
`libglib2.0-dev'. For Fedora, the name of the package is `glib2-devel'.

To run the unit tests, you will need GraphViz installed (but it is not
necessary to have GraphViz installed in order to use the library).

To build everything, just run `make'. To install, run `make install'. If you
want to change the installation prefix, you simply edit the Makefile and change
the definition of `prefix'.

Theory & Use
This library is used to keep track of relations between keys, and to provide
cascading operations on deletes by invoking a special destroy callback that is
registered when the library is initialized. The intention of this library is to
be used with memcached, so the semantics of it are similar to those of

The most basic kind of operation is adding a relation. A relation consists of
two parts: a source key, and a (possibly empty) list of destination keys. The
interpretation of this is that the integrity of the source key depends on the
integrity of all of the destination keys.

Any key in the system can be in one of two states: active or inactive. The
primary difference between an active key and an inactive key is whether or not
the destroy callback is called when a key is deleted. Inactive keys also have
the property that they can only be kept alive if there is some kind of
dependency on them. For example, say there is a dependency chain A -> B -> C,
where A is active and B and C are inactive. The fact that A is active
"supports" the chain. If a delete operation is done on C, it will propagate up
to A. If A becomes inactive then the whole chain is inactive, and will
therefore be deleted. Likewise, if there is a chain A -> B -> C where A and B
are both active and C is inactive, if A becomes inactive it is removed (since
it is unsupported), and the new chain becomes B -> C.

The other two main operations supported by the library are marking a key as
inactive, and deleting a key.

Memcached Extensions
Normally a memcached storage command looks like this:
<command name> <key> <flags> <exptime> <bytes> [noreply]\r\n

This is extended to look like this:
<command name> <keys> __ENDKEYS <flags> <exptime> <bytes> [noreply]\r\n

Keys are separated by spaces (this is permissible because memcached forbids
whitespace from appearing in keys). There must be at least one key. The first
key is interpreted as the key that the storage command is for, i.e. in the
usual context that a key is interpreted in in memcached. All of the normal
rules for keys apply, except that there is one additional rule: no key may be
named "__ENDKEYS", since that could lead to ambiguity.

Because of the protocol change, you need to use a modified client that knows
the new protocol.

The dependency graph is stored by libfk, not memcached. This means that the
memory is allocated and released by GLib, not memcached. Memcached could
potentially use a lot more memory than you tell it to use, because the memory
used to store the dependency graph is not taken from the slab allocator. Of
course, the dependency data is fairly compact, so this probably won't be a big
issue for most uses.