Search in files with large memory
I have a large data structure stored in a memory mapped file. The data structure is very simple:
struct Header {
...some metadata...
uint32_t index_size;
uint64_t index[]
};
This header is placed at the beginning of the file, it uses a hack structure - a variable dimensional structure, the size of the last element is not set in stone and can be changed.
char* mmaped_region = ...; // This memory comes from memory mapped file!
Header* pheader = reinterpret_cast<Header*>(mmaped_region);
The memory mapping area starts at Header
, and Header :: index_size contains the correct length for the Header :: index array. This array contains the offsets of the data items, we can do this:
uint64_t offset = pheader->index[x];
DataItem* item = reinterpret_cast<DataItem*>(mmaped_region + offset);
// At this point, variable item contains pointer to data element
// if variable x contains correct index value (less than pheader->index_size)
All data items are sorted (less than the relationship defined for data items). They are stored in the same memory card as the title, but from end to beginning. Data items cannot be moved because they are variable in size, not - the indexes in the header are moved during the sorting procedure. This is very similar to the B-tree page in modern databases, the indexed array is usually called the direction vector.
Search
This data structure is done with an interpolation search algorithm (with a limited number of steps) rather than a binary search. First, I have a whole array index
to search for, I am trying to compute - if the element I am looking for can be stored, if the distribution is uniform. I am getting some calculated index - look at the element in that index and it usually doesn't match. Than I narrow the search range and repeat. The number of interpolation search steps is limited to a small number. After that, the data is searched in a binary search. This works very well with small datasets as the distribution is usually even. Few iterations of interpolation search and we're done.
Definition of the problem. The memory display area can be very large in reality. For testing I am using 32GB file share storage and looking for some random keys. This is very slow because this pattern causes a lot of random disk reads (all data cannot be cached in memory).
What can you do here? I think setting MADV_RANDOM with madvise
syscall might help, but probably not much. I want to match the speed of B-tree search. Maybe syscall can be used mincore
to check which data items can be painlessly checked during interpolation lookups? Maybe I can use prefetch?
source to share
Interpolation search seems like a good idea here. This usually has a slight advantage, but in this case even a small number of saved iterations helps a lot since they are slow (I / O disk).
However, real databases duplicate the actual key values in their indexes. The indirect overhead for this is fully justified in improving performance. Btrees are an additional improvement because they pack multiple related nodes into a single contiguous block of memory, further reducing disk requests.
This is probably the right solution for you. You must duplicate keys to avoid I / O. You might be able to avoid duplicating keys in a separate structure and keep this completely in memory if you cannot change the existing header.
a tradeoff is possible when you just cache the top (2 ^ N) -1 keys for the first N levels of binary search. This means that you have to give up your interpolation for this part of the search, but as noted before interpolation is not a huge win anyway. The disc saved will easily pay off. Even caching only the median key (N = 1) will already save you from one corrupted file to search. And you can use interpolation as soon as you run out of cache.
In comparison, any attempt to tinker with the memory mapping options will give you a few percent speed improvement at best. "Along with B-trees" will not be . If your algorithm needs these physical suits, you will fail. No amount of pixel magic dust will fix a bad algorithm or bad data structure.
source to share