Hacker News Reader

Comment by londons_explore | Hacker News Reader

Isn't this the idea behind MIPMAPS in computer graphics?

In the tracing world, I believe the opensource pulseview/sigrok does this. It makes the UI very responsive even with gigabytes of data. I just wish it also integrated data compression of some kind so I could fit more trace than I have RAM (it can't be all that hard to intelligently compress a super repetitive signal in a way which still allows this fast zooming and scrolling - replacing some tree nodes with LZ77 style backreferences ought to do the trick)

View on HN

Yah mipmaps are an N-dimensional generalization of the breadth first layout of implicit aggregation, where the aggregation function is averaging.

It may in theory be possible to generalize the in-order layout I talk about in a similar way, but I'm not sure it would be that useful, maybe it would allow you to append rows or columns to your mipmapped image more easily, but I don't know of any applications where that's useful.

Check out Facebook’s Gorilla paper (https://www.vldb.org/pvldb/vol8/p1816-teller.pdf) which features some clever compression techniques for time series data generated at regular intervals.

What do you mean by needing to fit more trace than you have RAM? Are you saying those systems require you to load the entire raw trace into RAM before constructing the relevant data structures for efficient zooming? If so, that seems very limited since you can just use a storage-friendly data structure that also supports efficient zoom so you can put the bulk of the data on disk or across the network and just use your RAM as a cache for the full data structure. This is no worse than a RAM-only solution and allows you to operate on effectively arbitrarily sized traces for when you need to handle those hundred TB traces.

The use case is "I have binary data coming in at 5 Gbytes/sec from a logic analyzer, and I normally want say 30 seconds of trace"

That data is too big for RAM, and coming in too fast to write to disk. But the data is usually very compressible. Some channels will be a million '0's. Other channels will be a clock signal of '0 1 0 1 0 1' forever. Other signals will be more complex, but probably still be near repeats of patterns.

I just want to compress it in realtime in such a way the GUI tools I want to use can still work. They need to do fast-ish random access on the data, and answer questions about chunks of the data (eg. is all the data between time X and time Y all 0's).

Ah, I see, it is a data ingress problem not a UI/UX/visualization problem and you are in that awkward gap between RAM and disk bandwidths. So, you want a scheme to reduce ingress bandwidth which would allow you to store more data since you can not offload it anywhere else. From this perspective you would want a log optimized for useful entropy per unit storage which you can translate into a different data structure offline later on that is optimized for UI/UX. The most likely scenarios for that would require a very low level integration with the logging infrastructure itself and be either, as you say, a lossless streaming compression or some kind of lossy aggregation/compression, probably domain-specific, that retains the important data. The key problem here being creating an algorithm fast enough to operate at those data rates given that you get at most a few clocks per byte and no way of pushing the data to more parallel compute otherwise you would be able to just push it into storage.

> too big for RAM

64gb ram sticks are about $700 AUD, which brings the problem into range via RAM.

> coming in too fast to write to disk

Good PCIe4 NVMe drives are pretty fast these days. Samsung 980 PRO is under $300 for 1tb, and claims it can write 5gb/sec.

Even if you only get 2 gb/sec, that brings your RAM requirements down to 90gb, which is not an exotic configuration for a high-performance desktop.

I'm eternally astonished by how far hardware has come. Of course, preprocessing the stream on a cheap FPGA would be more elegant, but it's pretty amazing that consumer hardware could do it at all.

Ok, then imagine you are getting data at 10/g a second.

Of from a 200g adapter (or 4). Connect-X 6 EN. Network (LAN at least) almost always has at least 1 order of magnitude over storage... Oh yes I could put in a 10-disk nvme raid array and a liquid cooling system for all this. But then why not compress on the fly if I can anyway...

https://github.com/google/snappy is ~250 MB/second per core and you can compress in chunks of whatever size is convenient for your GUI to uncompress and render.

My current solution for anyone reading is "capture just 0.5 seconds of trace, and try and time that 0.5 seconds to contain whatever it is I want to see"

blosc comes to mind.

Reply on news.ycombinator.com