index bloom filter

I experimented with a bloom filter to reduce the number of index files I need to search when looking for the volumes that contain a particular block.

I found that the filter was quite effective at reducing the number of indexes to search for single blocks, but when I went to search for several thousand blocks I would get at least one false positive in each index. Because I was dealing with probabilities this stands to reason.

compressed index searching

I am continuing to try to make searching my disk indexes faster, this time I tried compressing the index files to reduce the IO required to get them into memory, however the run time went up.

First, the uncompressed index has a size of 3017824 K, and the times of two consecutive scans are

real    2m35.547s
user    2m18.172s
sys     0m6.146s

real    2m36.304s
user    2m17.152s
sys     0m6.242s

Next, the compressed index has a size of 1164228 K, and the times of two consecutive scans are

real    3m20.342s
user    3m4.939s
sys     0m8.805s

real    3m20.269s
user    3m3.866s
sys     0m8.699s

Since the system time went up I wonder if some extra buffering would work, also since this machine has two cores I wonder if I could do the scan in parallel.

Uncompressed with buffering makes it slower:

real    2m42.024s
user    2m15.048s
sys     0m6.214s

Compressed with buffering is slower too:

real    3m34.062s
user    3m3.281s
sys     0m5.488s

I ran each timing multiple times, and the times were mostly the same for each run.

So far straight reading of uncompressed data is fastest when scanning the whole data set.

At a later time I will try and make a parallel version.

searching for many lines in a text file

I spent the day working on my archive system project trying to improve the speed of searching the indexes for batches of keys.

I remember this being slow even when using a relational database, taking several minutes when the list and index were both in the database. If the list was not in the database it was painfully slow.

I have the indexes, sorted by key, one file per volume (768 files).

I have a list of keys to find in a file (24309 entries).

I try to do a binary search of each index file for each key and it takes about 27 seconds per file to do the search, and I have not wanted to wait to see how long the entire search takes (a quick estimate is 6 hours). I would expect that if the indexes were merged into one sorted file then it would still take 27 seconds to search that and get the whole answer I am looking for, but that is extra management to deal with. I am already caching reads in the binary search, they only improved the performance slightly when they were added.

To do a straight linear scan of all the files and pick out the lines I am looking for takes 177 seconds (almost 3 minutes).

Just reading all of the files with no processing

cat */* > /dev/null

takes 63 seconds.

The size of the data set on disk is almost 3G.

excited:~/archive.d/index$ du -h
1.5G ./offsite
1.4G ./onsite
2.9G .

The total number of lines of text in the data set is 26283702.

I am not even sure if it is possible to do faster than the linear scan for performance without merging all of the files together, which I would rather not do to save the size of the volume set and name fields.

reformat iso date

I was given a tiny challenge, write a function that changes "yyyy-mm-dd HH:MM" into "mm/dd/yyyy".

First I wrote a test:

package org.yi.happy;

import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class DateReformatTest {
    @Test
    public void test1() {
        String have = DateReformat.isoToAccess("2010-02-01 14:40");

        assertEquals("02/01/2010", have);
    }

}

Then I wrote the code, and used a regular expression to do the work:

package org.yi.happy;

public class DateReformat {

    public static String isoToAccess(String value) {
        return value.replaceAll(
                "^(\\d\\d\\d\\d)-(\\d\\d)-(\\d\\d) \\d\\d:\\d\\d$",
                "$2/$3/$1");
    }

}

All it does is capture some groups of digits, then re-arranges them. If it does not match it just returns the original string.

binary search of a sorted text file

This is my second time implementing a binary search of a sorted text file, the previous time was many years ago using PERL, this time it is in Java.

Here is the code to do a binary search of a sorted text file.

/**
 * Find the position of the start of the first line in the file that is
 * greater than or equal to the target line, using a binary search.
 * 
 * @param file
 *            the file to search.
 * @param target
 *            the target to find.
 * @return the position of the first line that is greater than or equal to
 *         the target line.
 * @throws IOException
 */
public static long search(RandomAccessFile file, String target)
        throws IOException {
    /*
     * because we read the second line after each seek there is no way the
     * binary search will find the first line, so check it first.
     */
    file.seek(0);
    String line = file.readLine();
    if (line == null || line.compareTo(target) >= 0) {
        /*
         * the start is greater than or equal to the target, so it is what
         * we are looking for.
         */
        return 0;
    }

    /*
     * set up the binary search.
     */
    long beg = 0;
    long end = file.length();
    while (beg <= end) {
        /*
         * find the mid point.
         */
        long mid = beg + (end - beg) / 2;
        file.seek(mid);
        file.readLine();
        line = file.readLine();

        if (line == null || line.compareTo(target) >= 0) {
            /*
             * what we found is greater than or equal to the target, so look
             * before it.
             */
            end = mid - 1;
        } else {
            /*
             * otherwise, look after it.
             */
            beg = mid + 1;
        }
    }

    /*
     * The search falls through when the range is narrowed to nothing.
     */
    file.seek(beg);
    file.readLine();
    return file.getFilePointer();
}

I tested this on a 33MB text file, it took about 15ms to find a line where grep took 600ms. I will be trying to make this faster using caching, and the result will likely be posted later.

reordering columns in a text grid

I just wanted to quickly move a column around in a grid file (tab separated text data file), and had to look up a few commands to do it.

cut - I use this program quite often to select columns from a grid.

paste - join two files line by line with corresponding lines separated with a tab.

file=2007-01-23-1520
out=index.txt
paste <(cut -d $'\t' -f 3 $file) <(cut -d $'\t' -f 1,2,4,5,6 $file) | sort > $out

Basically the two cuts run in parallel, and are piped into paste which reads each a line at a time and outputs the pasted lines, the rest of the command line just sorts the result and saves it to a file.

I am doing this to try and do a binary search on the text file.

large set calculations on the command line

I was working on Happy Archive a little bit, burning some backup disks.

To figure out what to put on a disk, I need to figure out which keys are not stored in a particular volume set, and not stored on any volume set.

There are two volume sets, offsite and onsite.

I have a list of keys in the store (store.lst), and a table of what keys from the store exist on what volumes (volume.grid: volume-set, volume, file-name, key).

First I make a list of what keys are in each volume set already:

grep $'^onsite\t' volume.grid | cut -d $'\t' -f 4 | sort > on-onsite.lst
grep $'^offsite\t' volume.grid | cut -d $'\t' -f 4 | sort > on-offsite.lst

Then I take those sets away from the store list (outstanding = store - exist).

sort on-onsite.lst | comm -13 - store.lst > outstanding-onsite.lst
sort on-offsite.lst | comm -13 - store.lst > outstanding-offsite.lst

Now I take the intersection of those sets to find the keys not on either disk set, and the difference to find the keys that are only on one of the disk sets.

comm -12 outstanding-onsite.lst outstanding-offsite.lst > outstanding-common.lst
comm -23 outstanding-onsite.lst outstanding-offsite.lst > outstanding-just-onsite.lst
comm -13 outstanding-onsite.lst outstanding-offsite.lst > outstanding-just-offsite.lst

And finally make the list in the order of preference for burning, giving priority to keys that are not on the backup disks yet.

cat outstanding-common.lst outstanding-just-onsite.lst > outstanding-onsite.lst
cat outstanding-common.lst outstanding-just-offsite.lst > outstanding-offsite.lst

I am going to be embedding this into a java program, but in a pinch this data processing is not hard to do.

There were 141k keys in the store list, and 80k keys in the resulting outstanding lists, and it did not take long to run these commands.

dumping a table from a sqlite database

While trying to extract the text messages from an iPhone backup, I found a need to extract a table to a text file to make it easier to work with. This extraction ended up being the final result, since it was good enough and could be imported into a spreadsheet for easy viewing.

The table extraction just does a grid escape of the results of a select statement.

#!/usr/bin/env python
import sys, sqlite3

if len(sys.argv) != 3:
  print "expected database file name and table name"
  sys.exit()
file = sys.argv[1]
table = sys.argv[2]

def grid_escape(x):
  if x == None:
    return "\\N"
  x = unicode(x)
  return x.replace("\\", "\\\\").replace("\t", "\\t").replace("\n","\\n")

conn = sqlite3.connect(file)
c = conn.cursor()

c.execute('select * from ' + table)
print "\t".join([col[0] for col in c.description]).encode('utf-8')
for row in c:
  print "\t".join(map(grid_escape,row)).encode('utf-8')

conn.close()

the grid escape function demonstrates how simple it is to encode that format, which is part of why I like it, it is trivial to produce in many languages.

dumping the list of tables in a sqlite database

I was poking through an iPhone backup for a friend, trying to recover the text message log after he accidentally deleted a bunch of messages. I found that the text messages were stored in a SQLite database. It also turned out that the backup was before the time that the messages were deleted, so most of the deleted messages were intact.

I decided to try and dump the whole database to the simple grid format discussed previously. First I needed a list of tables to dump, and I decided to make this an exercise in learning some Python database API.

Here is a Python program to dump the list of tables in a SQLite database.

#!/usr/bin/python
import sys, sqlite3

if len(sys.argv) != 2:
  print "expected database file name"
  sys.exit()
file = sys.argv[1]

conn = sqlite3.connect(file)
c = conn.cursor()

c.execute('select name from sqlite_master where type=\'table\'')
for table in c:
  print table[0]

conn.close()

grid file format

I do data analysis on the command line at times. One of the tools that gets much use is cut, which extracts delimited columns from lines. Another that gets well used is PERL, to make simple summary or translation filters.

When doing this kind of data analysis I like to use tab and newline delimited text, which I like to call grid. I find CSV to be harder to work with because it does not have delimiters that can not also show up in the values.

grid := line*
line := field* ( cr | lf | cr lf )
field := ( [ not cr lf tab "\" ] | "\r" | "\n" | "\t" | "\\" )* | "\N"

This is actually an 8-bit clean format, any binary value can be put in the field as long as the escape character (backslash), newline characters, and tab character are escaped. Finally this format can also support database NULL values, with "\N". I typically use UTF-8 encoded text in this format.

I originally saw this format in the MySQL manual, it is the import data format.

The main reason I use this format is that it is extremely easy to parse and write, and it also works with many of the stock text processing tools that come with the shell.