I have built a tick database to store all ticks indexed by contract, then by
timestamp (There are 60,000+ contracts, so storing each contract in a separate
file was not practical).
The source files include NxCore stream tapes(www.nxcoreapi.com), and several
nightly tapes direct from the exchanges (mostly bonds etc). All of these files
are read into memory and converted to tightly encoded structs and then sorted
first by contract Id, then by timestamp. I then write out two files, one is the
raw structs to a master file ~15 GB with all of the ticks for all contracts for
a single day. Then I also write out an index that includes the Contract name to
Contract Id translation, along with pointers(index and length) to each block of
ticks by session Id (there may be more than one session in a 24 hour day),
along with meta data like the volume per session, high/low, tick counts etc.
After building these files each night, I then combine all of the index files
into one master index which allows for coalescing all sessions for a given
contract, and maintain pointers to each file/offset/count for each session.
The main goal of all these layers of abstraction is to allow for extremely
rapid addition of new tapes (~20 minutes to add an entire days worth of ticks),
with extremely fast lookup by contract / session O(logn*logm) where n is the
number of distinct contract names, and m the number of distinct sessions. N is
generally at 500,000 contracts or less, and m is roughly 3600 days in the
database at most, making this a very fast lookup. Once you have the contract
and session looked up, it is an O(1) operation to get the ticks.
This actually collapses into two groups
Master index: Containing contract/session tuples with pointers to raw tick file
locations
Raw Tick Data: Collections of ticks loaded from a 24 hour exchange file. ~7200
files at 1-15gb/file.
The database as it stands right now is ~10 TB, and is actually stored on a ZFS
SMB share on a freebsd computer, as many of my raw tick files were suffering
from bit rot (I then cache a lot of files locally to improve lookups).
I would like to keep the indices as series files as they are now for rapid
lookup reasons, and store the ticks in compressed files, but need an O(1)
lookup mechanism for compressed files. I have tested adding a numerical index
to each tick and using it as a lookup mechanism, but it increases the sizes of
the files by ~10-20%, and seeks over SMB (network share to ZFS) are incredibly
slow, thus I actually cache all indexes local / in memory, and would like to do
a single seek/read over the network to get the ticks. Having to do a binary
search on the compressed file is quite expensive.
As I write the bulk tick files, I could use some sort of callback/output
parameter to keep track of which logical block we are in, and use that along
with a sequence id to create pointers to the blocks that I care about. In this
manner, it would be an O(1) operation to load up the blocks over the network,
and then decompress / further filter exactly the ticks I requested.
This would require a way to request ticks by index (like series files) and to
track the blocks used for each tick as it is written, to store in the index.
Let me know what you think / how to best go about this,
-Karl
Original issue reported on code.google.com by
kar...@gmail.comon 27 Mar 2012 at 3:22