2

Assume a text file with 150m unique records.

Each record has two columns: (1) string and (2) integer.

The string is a unique label, and the integer is the label's value.

The only query will return the integer value for a given label.

We are exploring multiple architectures for exposing this text file as an API.

This text file is regenerated every 72 hours. ~90% of the data remains the same across regeneration, but this regeneration is controlled by a 3rd party. We simply get a new text file every 72 hours.

We are aiming for query performance of 100ms - 500ms per read.

Architecture 1

  • Store the text file on disk. Query the text file. Cache queries in memory.
  • Pros: Simple implementation. Easy to update data.
  • Cons: Inelegant. Uncached read queries are slow.

Architecture 2

  • Parse the text file into a traditional/NoSQL database, with each line treated as a database record/document. Run queries against the database.
  • Pros: Seems like standard architecture.
  • Cons: Updating 150m database records is slow and seems wasteful, especially since ~90% of records remain the same.

Architecture 3

  • Use Redis or in-memory database to store the 5GB text file. Run queries against in-memory database.
  • Pros: Fast queries. Easy to update data.
  • Cons: Expensive.

Architecture 4

  • Use ElasticSearch to query records.
  • Pros: ElasticSearch is designed for search.
  • Cons: ES may be overkill for such simple queries.

Questions:

  1. Should we consider other architectures, or are there pros/cons we overlooked?

  2. This engineering challenge seems common: what is the most "standard" architecture for balancing cost/performance when trying to produce fast reads against a data store of 150m records that change?

  • 1
    Which time lag between getting a new file and having the data online for querying do you think is acceptable? Do queries pause during that interval, or do they still happen with the previous version of the file? – Doc Brown Aug 20 '20 at 8:29
  • @DocBrown Depends if you're 30 years from the past or future. :) Awesome username! Good question: assume queries pause for all intents and purposes. < 10 min between receiving new file and updating the database would be ideal, but could live with 60 min. – Crashalot Aug 20 '20 at 8:34
  • Why the downvotes? From reviewing other questions, architecture questions seem appropriate here. If not this SE site, which one would be best suited for advice on architecture questions? Thanks in advance for the guidance. – Crashalot Aug 20 '20 at 8:35
  • Forget about the downvotes, I tried to fight this behaviour last year, but parts of the community is obviously not getting the message. One cannot change other people, one can only change theirselves. – Doc Brown Aug 20 '20 at 9:01
  • @DocBrown agreed, more about compliance and not violating guidelines. Don't want to be like Biff Tannen. :) Given the answers to your original questions, do you have any suggestions? – Crashalot Aug 20 '20 at 10:27
6

Generally speaking this seemas like a classic case for an ETL flow: get the new file, Extract the data, Transform it to your format and Load to your DB. Some notes:

  1. The important thing to remember is that loading and querying are to different and entirely unrelated operations. One question is "how do I efficiently load a daily 150m record file into a data store when 90% of the records are duplicates", and the other is "how do I query a 150m-record key/value store efficiently". Answer these two questions separately, because they're independent.

  2. For your first question, you worry that loading 90% identical records is a waste. Have you measured the time it takes? Reading 150m records from a text file should take seconds, and a good key/value store should be able to optimize redundant UPDATE operations. Alternately, diff the new file against the previous one to create a the actual change list as part of your ETL flow, then proceed to load. Define metrics for this solution (total time to read, diff, load, interruption to query operation while loading, etc) so you can evaluate your solution.

  3. For question #2, avoid implementing custom solutions when off-the-shelf options exist. ElasticSearch might be overkill because you're just storing keyed integers, but there are plenty of key/value stores out there that will give you good performance for reads including disk-backed memory caching, MRU caching or different caching strategies depending on your usage, perhaps the aforementioned no-op UPDATE operation, and more. Again, as in question #1, define metrics for success. You said "loading 5GB into RAM is expensive. Is it? How much RAM does your server have? You consider caching common queries. Is it necessary? How fast are uncached reads? Measure! Do you need a custom caching strategy like precaching related records? Examine your usage pattern.

I can't tell you what the best approach is. There are too many variables only you an know - your budget and your usage pattern, future plans for the system and potential for extensibility, relationship with 3rd party data source (e.g. can they be convinced to generate just diffs, or add timestamps/version tags for records, etc). All I can do is suggest core patterns: separate ingestion flows from query flows, use tried and tested tools, and above all measure, measure, measure.

  • Hi Avner! These are great points. Thanks for the help. To clarify, 90% of records are the same across data regenerations, not within one. That is, each text file will contain 150m unique label-integer pairs. The metric: total time to ingest new file and update data store. Expensive because we will use Google Cloud Platform, Google Memstore is more expensive than a NoSQL database. We are willing to pay for infra and scaling, but prefer the more cost-effective cloud architecture. – Crashalot Aug 20 '20 at 5:05
  • We haven't tried measuring querying a text file with 150m lines because that seemed way too slow and inelegant? Are you saying queries could come back < 100ms even when querying a text file with a 150m lines, and that we should try it? – Crashalot Aug 20 '20 at 5:07
  • Exactly: don't assume, measure. Maybe a GCP machine with more RAM will allow you to load a local Redis instance to RAM for only a few dollars more. Don't just assume it's too expensive. Measure. – Avner Shahar-Kashtan Aug 20 '20 at 5:16
  • Thanks for the help. If all four options prove cost-effective, do you think the in-memory option is the best? ES seems like overkill right plus would mostly live on disk. – Crashalot Aug 20 '20 at 5:33
  • 1
    Thanks, agreed. It's more about compliance with the site guidelines. Don't want to be a bad actor! – Crashalot Aug 20 '20 at 10:25
1

You may consider approach taken by D.J.Bernstein's cdb, which is:

cdb is a fast, reliable, simple package for creating and reading constant databases. Its database structure provides several features:

Fast lookups: A successful lookup in a large database normally takes just two disk accesses. An unsuccessful lookup takes only one.

Low overhead: A database uses 2048 bytes, plus 24 bytes per record, plus the space for keys and data.

No random limits: cdb can handle any database up to 4 gigabytes. There are no other restrictions; records don't even have to fit into memory. Databases are stored in a machine-independent format.

Fast atomic database replacement: cdbmake can rewrite an entire database two orders of magnitude faster than other hashing packages.

Fast database dumps: cdbdump prints the contents of a database in cdbmake-compatible format.

cdb is designed to be used in mission-critical applications like e-mail. Database replacement is safe against system crashes. Readers don't have to pause during a rewrite.

Probably you will want a more modern implementation, that doesn't have the 4GiB limit, such as this one.

  • thanks for the answer. do you know how this compares to a nosql database like mongo or firebase? – Crashalot Aug 28 '20 at 20:35
  • @Crashalot cdb is more of a Unix-way solution: i.e. do one thing and do it well. I am unsure whether Mongo or Firebase can function as a library without a server component. Assuming they can not, the cdb will save you a round-trip to server (even if it runs on the same machine, it is still requires extra context switches). OTOH, Mongo or Firebase give you room for growth should your requirements change so much that they do not fit within the cdb's abilities and workflow. I would suggest prototyping and benchmarking both approaches prior to making a decision. – Kyrylo Shpytsya Aug 31 '20 at 12:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.