Persistent In-Memory Data Storage in Common Lisp (B.K.N.R)

This article provides a brief introduction to the BKNR.DATASTORE & BKNR.IMPEX libraries in Common Lisp, suitable for those working with CLOS-based data sets that they need to frequently manipulate within Lisp.

The BKNR developers are Hans Huebner, David Lichteblau and Manuel Odendahl. As per the developers:

BKNR is a software launch platform for LISP satellites. You could replace “launch platform” with framework and “satellites” with “applications”, but that would be too many buzzwords.

BKNR is made of facilities that are not very useful on their own, but they can be used to quickly build shiny and elegant LISP satellites. For example, a very important component of BKNR is its datastore, which brings persistence to CLOS in a very simple way. By adding a few declarations to your class definitions, you can have persistent objects. You can also add XML import/export to your objects in a similar way. I think this is the single most attractive feature of BKNR: no more mapping from a relational database to LISP objects, no more XML parsing and XML generation, you just write plain application code.

A basic understanding and usage of CLOS is assumed — no point attempting this guide without it. I will write a guide on CLOS later, but for now, you can try this.

Whilst the below guide is a bit long-winded, experienced Lisp programmers can readily just follow the working example uploaded on GitHub. A more detailed guide can be found in the BKNR manual, available here.

Introduction — Why store data in memory?

Data access in memory (i.e. RAM) is significantly faster than fetching from hard drives or solid state drives. Historically (and to be fair, this is slightly outdated, so we are going all the way back to the 1980s or 1990s here), in memory data storage has not been a practical option due to two limitations:

  • RAM is a volatile store of memory — any data stored in RAM disappears when the power is turned off or when the computer is reset
  • RAM is more expensive and persistent data storage devices like hard drives, tapes and solid state drives can generally hold much more data (for example, at the time of writing, my laptop has 8gb of RAM and 128gb of SSD)

The first limitation remains today. The second is disappearing for many use cases as RAM becomes cheaper and more plentiful — unless we are working with very large data sets (typically video, audio or big data), our computers have more than enough RAM for most tasks. Chances are the data you need to store for the application you are building can easily fit within RAM.

To overcome the lack of persistence of RAM, one can periodically save the data to a persistent store (i.e. your hard disk) and load it on startup. By doing so, and by keeping your entire dataset in memory, you are now able to readily apply any lisp functions to your data. A persistent in-memory solution thus has the following benefits:

  • Faster access to your data (after initial loading from a persistent store)
  • Seamless ability to apply Lisp functions to your data

There are downsides of course. I don’t want to go too much in detail here (partly because I’m not an expert), but basically:

  • If your data is well structured and would benefit from the use of SQL, use a database. Learn the principles of database normalization and avoid taking a shortcut approach (NOSQL), which BKNR.DATASTORE falls under to some degree. In fact, I would recommend learning databases in depth before considering whether to use a persistent in-memory solution in its place
  • If multiple users need to access and write to the data, again a database approach is appropriate. They are robust, well designed and have solved nearly all the problems one could possibly face when it comes to persistent data
  • I assume there is less functionality and potentially less reliability in using BKNR.DATASTORE or other persistent in-memory alternatives. They don’t have the man hours of development that major databases have, so you are venturing slightly in uncharted territories at times. Buyer beware

All that said, I will be using BKNR.DATASTORE for some of my projects, the benefits at this stage appear to outweigh the disadvantages.

About BKNR.DATASTORE & this guide

The BKNR developers are Hans Huebner, David Lichteblau and Manuel Odendahl, and I’m very grateful for their work (remember its a free, open-source library!) and also for the high quality documentation they wrote. Ours is a much simpler version of their manual, and one would likely refer to the manual and the source code (available on GitHub) as they get more acquainted with the library.

In this guide, we plan to cover the following:

  1. Setting up BKNR.DATASTORE
  2. Using it to (persistently) store CLOS Objects
  3. Accessing Objects by ID
  4. Modifying and Deleting Objects
  5. Taking Snapshots and Restoring from them
  6. Importing and Exporting to XML (via BKNR.IMPEX)
  7. Accessing Objects by Custom Index (Part 1)
  8. Accessing Objects by Custom Index (Part 2)

If you prefer avoiding walls of text and just reading code, a working example is saved on my GitHub repo Common Lisp by Example. Star the repo if you find this guide helpful ;) Likes are the currency of the free software movement after all.

Let’s Get Started!

1: Installation & Setup

Installation of BKNR.DATASTORE is via QuickLisp, per below. I read online it may not work correctly on Windows. It works for me on macOS and I assume it works well on Linux machines.

(ql:quickload :bknr.datastore)

The package name is bknr.datastore, so you may want to add it to your USE-PACKAGE list to avoid having to type bknr.datastore in all of the below (for a guide on packages, click here).

The first thing we need to do after this is to create a datastore. There can only be one datastore at any point in time, and this datastore is saved into the global variable bknr.datastore:*store*. The following is an example of creating a datastore (note how you need to configure where the datastore will be saved — replace the part in bold with your chosen directory):

(make-instance 'bknr.datastore:mp-store
:directory "/Users/ashokkhanna/bknr/tmp/object-store/"
:subsystems (list
(make-instance
'bknr.datastore:store-object-subsystem)))

The above command not only creates the data store, but also is used to load it — so basically you will always use this code in your files.

One can “close” a datastore with the following:

(bknr.datastore:close-store)

You will not be able to create new store objects or modify or delete existing objects once the store is closed. You can re-open the store with the make-instance command noted above — this is used for both creating new stores and loading existing stores:

(make-instance 'bknr.datastore:mp-store
:directory "/Users/ashokkhanna/bknr/tmp/object-store/"
:subsystems (list
(make-instance
'bknr.datastore:store-object-subsystem)))

In general, I don’t personally see too much need to close a store, but I have included the above for completeness.

2: Creating Storable CLOS Objects

To use BKNR.DATASTORE, we only need to make a couple of basic modifications to our CLOS class definitions:

  • Inherit from bknr.datastore:store-object:
  • Add the metaclass bknr.datastore:persistent-class
(defclass book (bknr.datastore:store-object)
((author :accessor book-author
:initarg :author)
(title :accessor book-title
:initarg :title)
(book-id :accessor book-id
:initarg :book-id)
(subject :accessor book-subject
:initarg :subject))
(:metaclass bknr.datastore:persistent-class))

To then create instances of our objects that can be stored, we use make-instance as normal:

(make-instance 'book
:author "Guy Steele"
:title "Common Lisp the Language"
:book-id 1
:subject (list "Lisp" "Common Lisp"))
(make-instance 'book
:author "Gerald Jay Sussman and Hal Abelson"
:title "Structure and Interpretation of Computer Programming"
:book-id 2
:subject (list "Scheme"))
(make-instance 'book
:author "Paul Graham"
:title "ANSI Common Lisp"
:book-id 3
:subject (list "Lisp" "Common Lisp"))
(make-instance 'book
:author "Paul Graham"
:title "On Lisp"
:book-id 4
:subject (list "Lisp" "Macros"))

The above created objects are auto-saved into the data store. If you restart the program, you will be able to retrieve the stored objects.

Note that we actually need to define our CLOS objects before we load them, thus, the correct sequence of lisp forms for this and the preceeding section should be as follows:

(ql:quickload :bknr.datastore);; Define classes before loading:(defclass book (bknr.datastore:store-object)
((author :accessor book-author
:initarg :author)
(title :accessor book-title
:initarg :title)
(book-id :accessor book-id
:initarg :book-id)
(subject :accessor book-subject
:initarg :subject))
(:metaclass bknr.datastore:persistent-class))
;; Load datastore:(make-instance 'bknr.datastore:mp-store
:directory "/Users/ashokkhanna/bknr/tmp/object-store/"
:subsystems (list
(make-instance
'bknr.datastore:store-object-subsystem)))

3: Accessing Objects

Referring to the previous section, our store objects are automatically indexed and we can use their ID to access them (this will return NIL if no object found):

(bknr.datastore:store-object-with-id 2)> #<BOOK ID: 2>

You can access all objects as well as a list:

(bknr.datastore:all-store-objects)> (#<BOOK ID: 0> #<BOOK ID: 1> #<BOOK ID: 2> #<BOOK ID: 3>)

You can also access objects by class:

(bknr.datastore:store-objects-with-class 'book)> (#<BOOK ID: 0> #<BOOK ID: 1> #<BOOK ID: 2> #<BOOK ID: 3>)

The last example implies you can store many different objects in your data store, not just one class. As an example, in the succeeding sections, we will create a new class for book-custom-indices within the same datastore.

Note that store object IDs are across classes, so reflect the total number of objects (of any class) within the datastore.

4: Modifying and Deleting Objects

To modify the slots of CLOS object, we use bknr.datatore:with-transaction() and then supply a standard setf to it. For example, the below will update author of the datastore object with id 3 to “Paul”:

(bknr.datastore:with-transaction ()
(setf (book-author
(bknr.datastore:store-object-with-id 3))
"Paul"))

To delete an object, simply call bknr.datastore:delete-object:

(bknr.datastore:delete-object
(bknr.datastore:store-object-with-id 2))

You can test the success of the above two function calls by using the accessor functions noted in section 3 above.

5: Taking Snapshots and Restoring from them

We can easily take a snapshot of our data store (i.e. backup the data store to a new folder):

(bknr.datastore:snapshot)

You will then see a snapshot folder timestamped and created, alongside the main data store saved in current:

We have quite a few snapshots saved in the above folder!

Restoring from Snapshots

I wasn’t able to find an adequate solution to restoring from an old snapshot, and this functionality may be missing (I think it works when using the bknr transaction model, but not the bknr object model we used in this guide) — if somebody knows how to do it, please let me know!

The alternative approach I found is to simply:

  • Remove all the files in the current folder
  • Copy the same files from the relevant snapshot folder back into the current folder from.

You may need to play around with this, but hopefully not too painful.

6: Importing/Exporting to XML

I’m a very cautious person when it comes to data, in an ideal world I would have everything printed on paper so that there is zero risk of data loss. Looking past the extreme impracticalities of that, the next best thing is to have data available in a human readable, widely adopted format — i.e. XML. Let us briefly discuss how to export our data store to XML and also import it back in later.

Creating an XML DTD

Before we begin, we need to create an XML Document Type Definition (DTD) to define the structure of our XML documents.

Below is what we have (saved in its own file, e.g. books.dtd).

<!ELEMENT books (book)*>
<!ELEMENT book (author, title>
<!ELEMENT author (#PCDATA)>
<!ELEMENT title (#PCDATA)>
<!ATTLIST book id ID #REQUIRED
subject CDATA # REQUIRED>

That looks scary — so let us walk through it:

  1. books is the root element, and as the name suggets is a list of books. You can readily infer that (book)* means multiple books can be children of books
  2. book is our main element (matching the object class of this guide) and it is a combination of author and title
  3. author and title are children of book. (#PCDATA) stands for “Parsed Character Data” and text within it will be parsed by the XML parser, i.e. tags inside the text will be treated as markup and entities will be expanded
  4. ATTLIST allows us to add attributes to elements. ID is used for numerical attributes while CDATA stands for text that will not be parsed by a parser, i.e. tags inside the text will not be treated as markup and entities will not be expanded

As an example of a valid XML document against the above DTD:

<books>
<book id="1" subject="Common Lisp">
<author>Guy Steele</author>
<title>Common Lisp the Language, 2nd Edition</title>
</book>
<book id="2" subject="Scheme">
<author>Gerald Jay Sussman and Hal Abelson</author>
<title>Structure and Interpretation of Computer Programs</title
</book>
</books>

Exporting to XML

Let’s now export some data to XML. First we need to load the bknr.impex library:

(ql:quickload :bknr.impex)

Let’s now load our XML DTD into Lisp:

(defvar *book-dtd* "/Users/ashokkhanna/bknr/book.dtd")

Now is the tricky part. Unfortunately, bknr.impex is not fully integrated with bknr.datastore, so we need create a custom class for XML-related work:

(defclass book-xml ()
((author :accessor book-author
:initarg :author :element "author")
(title :accessor book-title
:initarg :title :element "title")
(id :accessor book-id
:initarg :id :attribute "id"
:parser #'parse-integer
:index-type bknr.indices:unique-index
:index-values all-books-xml
)
(subject :accessor book-subject
:initarg :subject :attribute "subject"))
(:metaclass bknr.impex:xml-class)
(:dtd-name *book-dtd*)
(:element "book"))

The relevant parts related to XML are bolded in the above, hopefully it is relatively self explantory when comparing it to our XML DTD from earlier.

Note that we can add indices to this class (refer next section for a discussion on this), which is useful in the above as it auto generates a function all-books-xml to extract all book-xmls created (refer bolded italics code above).

Lets now create a couple of instances of this class:

(make-instance 'book-xml
:author "Guy Steele"
:title "Common Lisp the Language, 2nd Edition"
:id 1 :subject "Common Lisp")
(make-instance 'book-xml
:author "Gerald Jay Sussman and Hal Abelson"
:title "Structure and Interpretation of Computer Programming"
:id 2 :subject "Scheme")

Now let’s test out all of the above and try to serialize this data to XML, noting:

  • In the preceding paragraph, we mentioned that by adding an index, the function all-books-xml was automatically generated for us to use to access book-xml objects created
  • We add :name "books" in the below as we didn’t define a class for the root element books (and never will):
(bknr.impex:write-to-xml (all-books-xml) :name "books")

The output is as follows. Not bad eh?

<?xml version="1.0" encoding="UTF-8"?>
<books>
<book id="1" subject="Common Lisp">
<author>
Guy Steele</author>
<title>
Common Lisp the Language, 2nd Edition</title>
</book>
<book id="2" subject="Scheme">
<author>
Gerald Jay Sussman and Hal Abelson</author>
<title>
Structure and Interpretation of Computer Programming</title>
</book>
</books>

Importing from XML

It’s pretty easy to import data from XML. Let’s first save the above to file:

(with-open-file (*standard-output* "/Users/ashokkhanna/bknr/book-export.xml"
:direction :output
:if-does-not-exist :create
:if-exists :supersede)
(bknr.impex:write-to-xml (all-books-xml) :name "books"))

Then simply do the following:

(bknr.impex:parse-xml-file "/Users/ashokkhanna/bknr/book-export.xml"
(list (find-class 'book-xml)))

Wait…what?! You get an error — something like #<INDEX-EXISTING-ERROR INDEX: #<UNIQUE-INDEX SLOT: ID SIZE: 2 {100488E793}> KEY: 1 VALUE: #<BOOK-XML {10048C8EA3}>>.

This is because the indices we created earlier automatically get filled, so there is a duplication of IDs (which must be unique since its a “unique-index”). First, try manually changing the IDs in book-export.xml to 3 and 4 respectively:

<?xml version="1.0" encoding="UTF-8"?>
<books>
<book id="3" subject="Common Lisp">
<author>
Guy Steele</author>
<title>
Common Lisp the Language, 2nd Edition</title>
</book>
<book id="4" subject="Scheme">
<author>
Gerald Jay Sussman and Hal Abelson</author>
<title>
Structure and Interpretation of Computer Programming</title>
</book>
</books>

Now try the parse command again. It should work and return a list of the two book-xml objects, e.g.:

> (:BOOK (#<BOOK-XML {100629F0E3}> #<BOOK-XML {10062A0303}>))

Of course the above was a hack. The correct response is to clear the indices before parsing and loading the XML (note that this is an internal function so we need the :: in the below):

(bknr.impex::clear-class-indices (find-class 'book-xml))

Now try parsing again the original file without the hacks and you will not get any errors.

Connecting XML to the Data Store

One outstanding issue is that our book-xml object is completely independent of our book store object. Unfortunately I didn’t find a ready made solution to link the two (something I will try to write in the future, or perhaps you can write it first ;), but we can get around this relatively easily as follows:

  • For exporting the data store to XML, do something like the following to create equivalent book-xml objects which you can then export
(let ((book-data (bknr.datastore:store-objects-with-class 'book)))
(loop for item in book-data
do (make-instance 'book-xml
:author (book-author item)
:title (book-title item)
:id (book-id item)
:subject (book-subject item))))
  • For importing data from XML to the data store, its a similar operation but in reverse (loop over book-xml and make instances of book )

That said, for relatively simple applications (and with memory and computer speed increasing every day, “simple” can capture a much larger scope of applications), you could just work exclusing with the aforementioned XML functionality and use export/import to achieve persistence. You will miss out on the ability to take snapshots and I assume its a bit slower as the data store is probably more optimised (but that is a guess).

7: Adding Custom Indices (Part 1)

The above accessor functions (by ID, by class and all objects) are too basic for practical usage as they don’t allow us to filter our data store by the attributes of our objects. Custom indices over the slots of our objects is what we want.

There are three types of custom indices we can add to our CLOS slots:

  • unique-index: A slot with a unique index will allow you to filter by individual value of the slot, but with the caveat that each value must be unique, similar to a primary key in a database. If you try to create new objects with values that have been used before, an error will be returned.
  • hash-index: A slot with a hash index can have multiple objects with the same value. This is a good default option to use for your indices
  • hash-list-index: A slot with a hash-list index can have a list of keys for its value, and you can filter by any of the keys. This is analagous to the concept of adding tags to your data

Below is a template to use custom indices, which will generate two useful functions for each slot:

  • index-reader is the accessor function to get objects by index
  • index-values is the accessor function to get all values of the index
(defclass book-custom-indices (bknr.datastore:store-object)  ((author :accessor book-author
:initarg :author
:index-type bknr.indices:hash-index
:index-initargs (:test #'equal)
:index-reader books-with-author
:index-values all-authors)
(title :accessor book-title
:initarg :title
:index-type bknr.indices:unique-index
:index-initargs (:test #'equal)
:index-reader book-with-title
:index-values all-titles)
(book-id :accessor book-id
:initarg :book-id
:index-type bknr.indices:unique-index
:index-initargs (:test #'equal)
:index-reader book-with-bci-id
:index-values all-book-ids
:index-mapvalues with-book-ids)
(subject :accessor book-subject
:initarg :subject
:index-type bknr.indices:hash-list-index
:index-initargs (:test #'equal)
:index-reader books-with-subject
:index-values all-subjects))
(:metaclass bknr.datastore:persistent-class))

Note that we usedbook-id for ID and not the more general id. The reason is that indices are global and not segregated by class:

  • So if we have a books object and an articles object, we will run into issues if they share the same index for ID (which will occur if we used id for both of them)
  • The same issue happens when having book-xml and book-custom-indices — indices are shared across the datastore and xml libraries.

Now let’s create a few objects of this new class:

(make-instance 'book-custom-indices
:author "Guy Steele"
:title "Common Lisp the Language"
:book-id 1
:subject (list "Lisp" "Programming" "Common Lisp"))
(make-instance 'book-custom-indices
:author "Gerald Jay Sussman and Hal Abelson"
:title "Structure and Interpretation of Computer Programming"
:book-id 2
:subject (list "Scheme" "Programming"))
(make-instance 'book-custom-indices
:author "Paul Graham"
:title "ANSI Common Lisp"
:book-id 3
:subject (list "Lisp" "Programming" "Common Lisp"))
(make-instance 'book-custom-indices
:author "Paul Graham"
:title "On Lisp"
:book-id 4
:subject (list "Lisp" "Macros" "Common Lisp"))
;; This will give an error as a book-id of 4 has already been used:(make-instance 'book-custom-indices
:author "Paul Graham"
:title "Hackers & Painters"
:book-id 4
:subject (list "Lisp" "Art"))

Finally, we can test out our accessor functions. Note how the global datastore ids are not starting from 0, but rather continuing on from the number of the last object created in the datastore.

(books-with-author "Paul Graham")
> (#<BOOK-CUSTOM-INDICES ID: 7> #<BOOK-CUSTOM-INDICES ID: 6>)
(book-with-title "ANSI Common Lisp")
> #<BOOK-CUSTOM-INDICES ID: 6>
(book-with-book-id 1)
> #<BOOK-CUSTOM-INDICES ID: 4>
(books-with-subject "Lisp")
> (#<BOOK-CUSTOM-INDICES ID: 7> #<BOOK-CUSTOM-INDICES ID: 6>
#<BOOK-CUSTOM-INDICES ID: 4>)

8: Adding Custom Indices (Part 2)

The BKNR.DATASTORE manual on page 22 details a way to create array indices that allow you to filter your datastore by more than one attribute (for example, select all books for a given author and a given subject). The issue with arrays is you need to specify their dimensions on initialization, so it would be a bit tricky to use this in practice if you don’t have clear upper bounds on the number of permutations for each attribute in the array key. However, it is a relatively clean solution worth exploring.

Two alternatives I think are better:

  • Create an additional attribute that is the composite of the attributes you want to filter on together (e.g. (author . subject)) and write some wrapper functions to automatically populate these, e.g.:
;; Note the below will not run by itself as we haven't created a class with a composite-key attribute, it is just an example:(defun make-book (author subject title id)
(make-instance 'book :author author :subject subject
:title title :book-id id
:composite-key (cons author subject))
  • Just write your accessor functions completely outside of your data store object. This is something you should do anyway when you want more granular control over accessing the data store. For example:
(defun get-author-title (author title)
(let ((all-author-books (all-authors)))
(loop for book in all-author-books
if (equal (book-title book) title)
collect book)))

Concluding Remarks

Wow, that was longer than I expected when I started writing this. All that said, if you refer to example code, hopefully its not too bad once you get your head around it. And then, you have a powerful and relatively straightforward mechanism at hand for storing CLOS objects in a persistent data store.

If you liked this guide, star my example repo, share the guide or just leave some comments. But even more importantly, start using BKNR.DATASTORE, share it with your friends and star their repo to show some love!

Enjoy!

--

--

--

Masters in Quantitative Finance. Writing Computer Science articles and notes on topics that interest me, with a tendency towards writing about Lisp & Swift

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Task 1: Explore the SimpleCalc project and app

I Finally Managed to Activate a Conda Environment in My CI Pipeline

Github Copilot, friend or foe?

Why You Should Be Using Per-Pull Request Environments (and how!)

An Isolated Environment

Deploying an ASP.NET Core Application to Amazon Web Services

What is the best IDE for developing in Golang?

Kubernetes goodies for your local workspace

How to Hire App Developers — A Comprehensive Guide

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Ashok Khanna

Ashok Khanna

Masters in Quantitative Finance. Writing Computer Science articles and notes on topics that interest me, with a tendency towards writing about Lisp & Swift

More from Medium

Migrating from IBM-DB2 on AS400 to SQL Server 2017

Introducing the ArangoDB-NetworkX Adapter

Introducing the ArangoDB-NetworkX Adapter

Data Abstraction and the Grivan-Newman Algorithm

Newton-type Methods for Optimization