Real-time multiple (1000) data file access (C/C++ Windows App)

Is there anything you know about the access patterns that you can use to your advantage? Are the queries going to be coherent (within files, or within regions of files, or ...). If not, and the files are truly too large to keep all in memory, then I think you're pretty much created the solution through your requirements. When a request comes in, you open a file, read the data you need, and then close the file.

The only obvious things that could help are keeping a LRU cache of data if things are going to be coherent (eg, more requests for data that was just accessed). Alternately, you could memory-map all of the files at the start, and just use that. Although if the files are truly that large together, then you could run out of address space, so this might not work. If they will all fit in your address space, then this will effectively use the OS virtual memory system to create an automatic caching mechanism for you.

Thanks for your quick reply, osmanb.

Yes, I know the pattern of the data stored in each file (i.e. header and then actual data in tabular format). Each file is a little less than 1 MB in size, but there's a lot of files.

Quote:

Original post by faculaganymede I need to write a Windows application in C/C++ that can efficiently access data from a large number of binary files (may be more than 100 files) in real-time.

Real-time means that event scheduled at some deadline is guaranteed to happen at that deadline. It may be seconds, days or weeks in the future. If you really need real-time, then there's a constraint on how soon these actions must be performed, if so, what is it?

Quote:

Essentially, what the application needs to do is: if an event happens, it needs to determine which file

So file is a mapping from event-to-key.

Quote:

and where in the file the desired data is located

Another key lookup, is this key passed by event? First lookup is trivial, just hundreds of files, performed in memory.

For second lookup, keeping index tables in memory shouldn't be a problem either, with files being only several GB, you could keep half of them in RAM. B-tree or something similar should be more than enough for second lookup.

Quote:

retrieve the data,

How much? If it's hundreds of Mb per second, disk throughput may be a problem.

Quote:

Each file is a little less than 1 MB in size, but there's a lot of files

Hundreds of files is not a lot. It's not until you get into hundreds of thousands that things can get problematic, depending on FS of course.

Quote:

I can’t load all the data files into memory because that would take several GBs of RAM.

16Gb of RAM is really cheap.

Quote:

Any suggestions is greatly appreciated.

If you write a simple fstream-based application to perform this task, using trivial algorithms, how far does it go before it breaks?


There's a lot of unknowns here. Disks have seek times and limited bandwidth. Processing may be non-trivial.

To get basic metrics, find the upper bound on number of events, the amount of data to be read, and cost of processing. This allows you to determine potential bottle-necks and processing model.

OSes (which one?) provide asynchronous file IO, which may help reducing disk latency. RAID systems, or SSDs may help with throughput. Multi-core, or perhaps even several machines may help with CPU throughput.

There's lots of possibilities, but without numbers, it's just a lot of options with nothing to lean on.

... So is there a problem, beyond a vague desire for "efficiency"? Have you tried writing things the straightforward way first? What kind of data do you have? What are your performance requirements? Can you pre-cook the data in some useful way?

Have you considered that if you're *starting* another process to deal with the data, the overhead of file I/O might not matter that much anyway?

Thanks for your suggestions and comments, Antheus and Zahlman.

This application needs to run on any regular PC (e.g. 1-2 GB RAM, duel-core). The data file access part should be completed within seconds of event occurrence. There'll be other processes running concurrently.

The files contain collected data from experiments. Each file is a little less than 1 MB, so the data to be retrieved from each file will be a certain percentage of that. Depending on the event, the application may need to access more than one file to get the desired data.

Yes, efficiency is the key here. I have not started implementing this yet, knowing the straightforward way would not be efficient enough. I thought this is one of those common tasks that there may be well developed techniques/algorithms for doing it efficiently.

Quote:

Original post by faculaganymede Yes, efficiency is the key here. I have not started implementing this yet, knowing the straightforward way would not be efficient enough. I thought this is one of those common tasks that there may be well developed techniques/algorithms for doing it efficiently.

In my experience, the best way to tackle any "unknown" problem is to start with the naive approach first. At the very least, that'll give you a baseline "worse-case" yardstick which you can use to measure any improvements against.

It seems to me, though, if for any given "event" you know which file and which parts of which file(s) to read, then the naive approach would have no trouble returning "within seconds" (sub-seconds I'd say) so there must be more to it than that...

Quote:

Yes, efficiency is the key here. I have not started implementing this yet, knowing the straightforward way would not be efficient enough.

You do not know that. You simply don't.

My math may be weak, but hundreds_of_files * under_one_megabyte equals well_under_one_gigabyte. So keeping all files in memory is viable option.

You can be memory-efficient, computationally-efficient, cost-efficient. Pick any two.

Quote:

I thought this is one of those common tasks that there may be well developed techniques/algorithms for doing it efficiently.

There are. But they depend on actual problem. Several seconds per request is HUGE amount of time. Your CPU can go on vacation in exotic places during that time, and come back in time to process next request.

If all you need is read access, and same chunks of data are read, then you can expect 100Mb/sec reads from disk. Assuming worst case latency, you will need 10ms to access any file, up to maximum size of file. So you can run 100 file queries per second without any optimization at all.

If you frequently access same files, they'll be cached in memory, meaning reads will be similar to direct memory access.

Crucial design decision here will depend on whether you're IO bound or CPU bound. But that is impossible to say without some actual numbers, or experience with workflow of application.

But since this sounds like streaming processing, asynchronous design is unlikely to be invalid. Under Windows, you can use IOCP to read files and perhaps even to communicate to other process. This would also allow trivial use of multiple cores for processing, and is completely trivial to implement as long as files are only read, and events may be processed in any order.

Very sorry, I left a "0" out. I meant more than a 1000 files.

Thanks so much for all your feedback!

The only optimization I can think of that doesn't require special hardware is to stop storing your data as thousands of files. If you can store them in a custom archive format without reimplementing a full filesystem, access to individual files should be much faster. You could then defragment the archive file to make seeking inside it more efficient.

With special hardware, you could get a 64-bit machine with a 64-bit OS and have enough RAM to load all the files, or you could go with solid-state drives to improve load performance and then implement caching based on the amount of RAM available.

I'll assume you've considered it but seeking data efficiently among a vast amount of data while using only the available amount of RAM sounds quite a lot like a database.

You could "cook" your data by sending it into a DB as it comes in.