How would you design parallel grep for huge JSONL files?
from dhruv3006@lemmy.world to programming@programming.dev on 30 Mar 15:25
https://lemmy.world/post/44947850

I need to scan very large JSONL files efficiently and am considering a parallel grep-style approach over line-delimited text.

Would love to hear how you would design it.

#programming

threaded - newest

Bazell@lemmy.zip on 30 Mar 16:12 next collapse

Splitting file in equal parts and analyzing in threads each part is basically the only efficient option to utilize modern CPU architectures efficiently for your task that I can think about. Since I doubt that the data stored in your files can be quickly processed by the GPU(I assume that you have text data).

bleistift2@sopuli.xyz on 30 Mar 16:31 collapse

Can a file really be split efficiently? And is reading from multiple files on the same disk really faster than scanning a single file from top to bottom?

Ephera@lemmy.ml on 30 Mar 17:32 next collapse

I think, you could open the same file multiple times and then just skip ahead by some number of bytes before you start reading.

But yeah, no idea if this would actually be efficient. The bottleneck is likely still the hard drive and trying to fit multiple sections of the file into RAM might end up being worse than reading linearly…

Bazell@lemmy.zip on 30 Mar 18:45 collapse

This approach will indeed hit bottleneck even in SSD. Thus, file can be read into RAM line by line in thread 0, then once specified amount of lines was gathered, schedule thread 1 to process them, while thread 0 still reads new lines. Once another chunk is ready, give to thread 2 and so on. This way you can start processing data in asynchronous regime in the fastest way possible. Slightly slower but more convenient approach is to firstly read all the file into RAM and only then assign parts of it to each thread at the same time.

entwine@programming.dev on 30 Mar 18:38 next collapse

You don’t actually need to “split” anything, you just read from different offsets per thread. Mmap might be the most efficient way to do this (or at least the easiest)

Whether or not that’s going to run into hardware bottlenecks is a separate issue from designing a parallel algorithm. Idk what OP is trying to accomplish, but if their hardware is known (eg this is an internal tool meant to run in a data center), they’ll need to read up on their hardware and virtualization architecture to squeeze the most IO performance.

But if parsing is actually the bottleneck, there’s a lot you can do to optimize it in software. Simdjson would be a good place to start.

Bazell@lemmy.zip on 30 Mar 18:38 collapse

If the task to just read the data quickly without processing it(doing calculations, sorting, transformation, etc.), then yes, reading line by line is the fastest way. But the OP mentioned some processing operations on data, which may require additional time and computing power, thus it will be efficient to firstly load file into ram splitting it into chunks, give each thread a chunk to process and then combine results.

In fact, my first comment suggested that you can read file line by line and once enough lines were read in RAM, thread 1 can start processing them while thread 0 still reads new lines from hard drive. Once another chunk is ready, thread 2 can start processing it and so on.

In conclusion, it all depends on what exactly you need to do with data. Simply transferring it from HDD to RAM must be done by reading line by line. But processing of data can be split among cores of CPU to maximize the speed of computations.

vfscanf@discuss.tchncs.de on 30 Mar 17:07 next collapse

The question is, what will be your limiting factor: CPU or disk I/O? Parallel processing doesn’t do much good if the workers have to wait on the disk to deliver more data. I’d start with an async architecture, where the program can do its processing while it is waiting on more data.

Lysergid@lemmy.ml on 30 Mar 17:11 next collapse

How large is very large? Would it be something that jq can’t do? Is it purely string search or JSON-tree search?

Generally you would want to get file size, split it into ranges which can be read as valid UTF-8. Feed each range into reader thread. Can be inefficient for HDDs because each thread will try to access random location on disk forcing needle to jump back and forth. Also you’ll need reread ranges at split point with some positive and negative offset in case desired content got split. Things are getting much more complicated if you want JSON-tree grep. Branches may get split from parent nodes across multiple ranges.

bizdelnick@lemmy.ml on 30 Mar 18:28 collapse

Bad idea. First, file is read sequentially, and you can’t parallelize this. Second, grep is a bad solution for structured files. Better use jq or something similar.