raw database

Fast circular buffer in MySQL

Robert Eisele

A while ago, I wrote a class to implement a circular buffer with memcached. Today, I want to experiment implementing a fixed size storage in MySQL. A nice real world problem is a queue in MySQL. To use this solution as a queue, you have to choose an appropriate size of the buffer and split the read and write pointer.

While I wrote this article, I had an idea. The most common problem on websites is, that you list a fixed size box, like "10 last comments", "15 newest posts" and so on. When you try to cache this result, you'll delete the cache and read everything from the database. With a fixed size circular buffer, you have an elegant way to update the cache without a new database-query.

But let's try to find a fast solution for MySQL. My first attempt was bringing the idea from the memcached-implementation to MySQL. For this setup, we need two tables. One for the position and one for the data. If you want to use global variables for the pointers, that's your decision. I made bad experiences with that and so I'll use a second table.

CREATE TABLE buffer (
  id int(10) unsigned not null key,
  value varchar(64)
);

CREATE TABLE bufpos (
  pos int(10) unsigned not null,
  max int(10) unsigned not null
);

The circular buffer is fixed in size, so we have to fill the table once, and then only use UPDATE to change the values in the table. In this example, I use varchar(64) for the value. In general, it doesn't matter what type you use. We focus here on the projection, not the selection.

INSERT INTO buffer (id, value) VALUES
(1, null),
(2, null),
(3, null),
(4, null),
(5, null),
(6, null),
(7, null),
(8, null),
(9, null),
(10, null);

You also have to fill the "bufpos"-table with one line. Set the max-value to 10, and the position to 1. This table will ever have one line. You can also add a column with a unique id, and add a WHERE-clause in the UPDATE. So you have the chance to reuse this table for different pointers.

INSERT INTO bufpos (pos, max) VALUES (1, 10);

Now I tried to update the pointer and the data-table with maximal 2 querys. If you want to use this, stick it in a procedure, make a LOCK and everthing is fine.

UPDATE bufpos SET pos=@p WHERE @p:= IF(pos=1, max, pos-1) LIMIT 1;
UPDATE buffer SET value='<STRING>' WHERE BID=@p LIMIT 1;

The write solution is okay, but to read from the data-table you have to do 2 querys and the second query with a union which is not really fast:

SELECT @p:= pos FROM bufpos LIMIT 1;
SELECT *
FROM buffer
WHERE id >= @p
UNION
SELECT *
FROM buffer
WHERE id < @p;

Okay, lets see how we can optimize this first approach. There were a few other steps between the first and the final step, but I don't want to bore you.

So my final version uses a single table, with a new column:

CREATE TABLE buffer (
  id int(10) unsigned not null key,
  value varchar(64),
  pos int(10) unsigned not null,
  key(pos)
);

INSERT INTO buffer (id, value, pos) VALUES
(1, null, 1),
(2, null, 2),
(3, null, 3),
(4, null, 4),
(5, null, 5),
(6, null, 6),
(7, null, 7),
(8, null, 8),
(9, null, 9),
(10, null, 10);

The id is not needed, but handy to find the initial-beginnung of the buffer if you lost the table-sorting. If you want to write something to the buffer, you can easily run the following query:

UPDATE buffer SET value='<STRING>', pos=pos+10 ORDER BY pos LIMIT 1;

...where "10" is the size of the buffer, like in the example above. I had a few intermediate steps with limitations, where you had to update the "pos"-column with every update, and the other problem was, that a extra query was needed to get the max value. In this setup, the only limitation is INT_MAX. But with a cron which reduces all positions by MIN(position), this should be the slightest problem. Now you can easily read the former ring by running:

SELECT * FROM buffer ORDER BY pos DESC;

Note, that the "pos" has to be initialized by the primary key value to have a default sorting.

Attention: You may hit bug #12195 with this approach, which decreases the performance a lot, so be sure you're testing your application!