Skip to content
This repository

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
branch: master
Fetching contributors…

Cannot retrieve contributors at this time

file 73 lines (60 sloc) 3.629 kb
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73
Introduction
==================
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://github.com/eklitzke/libfk.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
memcached.

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.
Something went wrong with that request. Please try again.