4 ms·

Thanks. > ...adaptive succinct indexing structures We've been optimising for low-memory and compact / succinct data-structures have been super impactful (espe

• jandrewrogers 7y ago
  Physical storage density per server is driving this. You can fit upward of a petabyte of physical storage in a server and there are many applications where this makes sense. RAM is still on the order of a terabyte, and expensive. Everything else follows from trying to use all of this physical storage effectively. Needless to say, when working with this much storage you aren't installing a filesystem on it. When working with storage this dense, write performance matters immensely if you can't wait (literally) a year to index your data model. Scaling write throughput on indexing structures has a problem of write sparsity: given a fixed amount of cache, there is a scaling point where virtually every single insert requires at least one page fault. Indexing structures like B+Trees that consume large amounts of space will not only push the data pages out of cache, the index itself may no longer fit into cache at high densities. Every database exhibits this characteristic write cliff with indexing structures but the cache:data ratio where this occurs varies with indexing algorithm design. (This also impacts query performance but we'll ignore that for now.) Succinct indexing structures can eliminate the competition with data pages for cache space. Write sparsity is intrinsic though, so this only lets you maintain write performance for maybe another 1-2 orders of magnitude. Eventually the set of actively written data pages will exceed the size of the cache and write throughput will drop precipitously before leveling off. Being able to index tens of terabytes of data at wire speed is much better than typical but at least an order of magnitude short of what is desirable for a petabyte of storage in a single server. Ideally, you'd want the flat write throughput to extend out to the end of your storage, which means extending the write cliff at least another order of magnitude. There is not an obvious way of doing this without adversely impacting performance in other unacceptable ways. I started researching this problem a few years ago from a very different direction that does not require directly improving cache efficiency per se, since that is essentially tapped out as a strategy. Most software engineers don't understand the nature of caches as abstract mathematical objects but there are some interesting NP-Hard problems surrounding the behavior of caches that we essentially ignore for database architecture purposes because (1) NP-Hard and (2) exploitable efficient approximations are incompatible with many common database architectures in any case. I've worked through a couple new algorithm prototypes that attack these properties to significantly extend the performance party for even higher storage densities. I'm just starting to design kernels that are purpose-built to take advantage of this research but the heavy lifting is done in the schedulers. Yes, I do this kind of thing for fun.
  • moab 7y ago
    Could you provide some references for this work on caching and schedulers? I’m also curious what application domains are storing close to petabytes on a single machine with only a few terabytes of dram.
    • jandrewrogers 7y ago
      Ultra-dense database engines are typically used for data models created from measuring entities or places in the physical world, sometimes in real-time. This includes telemetry and sensors from mobile phones, automobiles, satellites, features extracted from video, network packets, the web, etc and sometimes all of the above. These are the largest data models that I know of; most medium-sized non-tech companies I work with have 10-100 PB data models now. The size doubles quickly even if you regularly truncate old data. The extremely high storage density saves both hardware and software engineering costs by massively reducing the required cluster size. This has become a great emerging market for new database tech, tremendous amounts of money are being spent on these data models and traditional data infrastructures are very poor for this. The size and velocity of the data implies that you need a single database instance that can run ingestion workloads concurrent with analysis workloads. The research on caching algorithms for ultra-dense storage is new, it is literally just starting to be worked into production designs, so I wouldn't expect references. Most advanced database research is done outside academia, so a significant fraction is published long after implementation or not formally published at all. Publication is not the objective per se and there is little time or incentive to do that work. Database research has a discovery problem, I hear about most interesting new research via informal community channels and much of that never shows up in literature.
      • moab 7y ago
        Thanks for the reply. I would be very interested if you could point me towards any private companies providing these kind of database solutions. I am particularly interested in their story around concurrent ingestion + analytics workloads. This is a tricky problem that most existing works solve by either doing stupid things a la. having a single-version system, or by using lots of synchronization + complex version-friendly concurrent data structures. Solutions I have seen in academia are usually tested well below the 1TB of data range, and I don't imagine they scale to the kind of data sizes you mention. The fact that the research is being done outside of academia and not being published is pretty sad imo. Hopefully those in the know decide to publish at least tech-reports/whitepapers once they have a share of the market.