6 ms·

Ask HN: Key-Value Store Database with Historical Lookup?

• karterk 12y ago
  HBase will fit nicely for this use case. Columns can be versioned: http://hbase.apache.org/book/versions.html http://hbase.apache.org/book/versions.html
• rohanprabhu 12y ago
  I don't know of any dedicated package that does this, but at my previous company, we had a similar requirement, for which we used DynamoDB with a Range key, where the range key was the timestamp. So, if the value of a key 'x' was 'y' at time '4', then you could do get(x, 4) to get the value at 4 or even get(x, <5), get(x, <6) to get the value at times where a specific entry wasn't there and it will return the latest value entered at a particular time. Plus sortation by time was a plus :)
  • huy 12y ago
    Thanks for the pointer. I'm reading more about Secondary Index and Range Key in DynamoDB and it seems to fit well to what we're looking for. The only slight concern at the moment is it's AWS-hosted service so we have to be reliant on AWS (and its cost structure), so we might have to do some cost analysis there. But other than that it seems to fit the use case!
    • rohanprabhu 12y ago
      Glad to help. Feel free if you need any more pointers from my experience with this solution!
• Argorak 12y ago
  I used event sourcing for this. We were doing recording of live interactions and wanted to know the state at any given time. So the "current" state of any item was the result of all events happening until now applied in order, the state at any given time was just the same, with another time boundary. Don't fear the computation, we were doing all this in CouchDB with list functions and never had huge performance problems. Range queries are present in all databases. Constructing the events properly so that they apply conveniently to any kind of state is a different kind of story.
• DanWaterworth 12y ago
  You could just use redis, but at each key, store a sorted set time -> value.
  • eric_bullington 12y ago
    I like this idea for its simplicity, but what about looking up time values that fall in between the intervals you've set values for? You'd have to normalize the time value you're looking up to whatever timestamp granularity you're saving to, I guess (ms, s, hr, etc.). Or is there a better way to do this with Redis?
    • DanWaterworth 12y ago
      You can do range queries on sorted sets.
      • eric_bullington 12y ago
        Ah, ok, thanks.
• transitorykris 12y ago
  Take a look at influxdb (influxdb.com). It gives you the ability to store arbitrary values at specific times and a subset of SQL to query it.
• Goranek 12y ago
  Use Spanner, if you're working for Google. :)
• lgas 12y ago
  Datomic does this.
• zo1 12y ago
  It's not exactly a key-value store, but have a look at this: https://en.wikipedia.org/wiki/Temporal_database https://en.wikipedia.org/wiki/Temporal_database Though, if I personally had this requirement, I would just roll my own as it sounds very basic and easy to represent in a plain RDBMS. No way am I going to base my DB choice/design or infrastructure impementation for something this small.
• chippy 12y ago
  times or revisions?
• marknadal 12y ago
  huy, we're in the middle of building this right now - http://gunDB.io http://gunDB.io (talks about other nifty aspects of it, too). We just got into an incubator program in SF, so if you are around that area we should meet up, send me a message (see my profile).
• tfb 12y ago
  My startup www.loggur.com is essentially a really advanced service that does this. Please pardon the text for now. I recently replaced the old landing page with it to prevent any confusion, as things have taken a bit of a turn (for the best). There are roughly only 3 things left to do before launching!
• ah- 12y ago
  I'm just in the middle of building a similar system. As another commenter mentioned, you can use a log / event sourcing for this. A log basically is a stream of changes to a DB. I found this the best introduction to it so far: http://engineering.linkedin.com/distributed-systems/log-what-every-software-engineer-should-know-about-real-time-datas-unifying http://engineering.linkedin.com/distributed-systems/log-what...
  • huy 12y ago
    Thanks. We did study this article a while back while building our data infrastructure. We wrote about our infrastructure here: engineering.viki.com/blog/2014/data-warehouse-and-analytics-infrastructure-at-viki/ In fact, to give you a little bit more background on the problem, if you look at our data infrastructure diagram (in the posted link), the thing we're trying to improve is the hydration system (where it takes in a record in real-time and try to inject more time-sensitive information into it). E.g. When a user watches a video (thus a video_play event sent), we want to know if it's a free user or a paid user. Since the user could be a free user today and upgrade to paid tomorrow, the only way to correctly attribute the play event to free/paid bucket is to inject that status right right into the message when it's received. Building the system this way (using the hydration service) makes our service very prone to error and indeterministic (since you only have a short window to hydrate the message, and you can't replay a hydration). That's why we're looking at building a historical lookup service that remembers all the different changes of a data object over time, so that replaying a hydration becomes deterministic. At the moment we're processing around 100M records a day and growing. Not a lot but still at some scale that puts us in the position to think about scalability and performance.
• stdbrouw 12y ago
  AWS DynamoDB is actually quite nice for this. You set a composite (id, timestamp) index, and then you query on id and a timestamp range or "first match before or at timestamp x". As `zo1` mentions, though, this doesn't really seem like the kind of requirement that would necessitate obscure database technologies, especially because even in a relational database these are easily optimizable queries.
• gk1 12y ago
  Have a look at FoundationDB (https://foundationdb.com https://foundationdb.com) and its time-oriented data structure[0]. If you want to go a step farther, you can use their SQL Layer to run all sorts of queries on the Key-Value Store[1]. [0] http://blog.foundationdb.com/designing-a-schema-for-time-series-data-using-fdb http://blog.foundationdb.com/designing-a-schema-for-time-ser... [1] https://foundationdb.com/layers/sql https://foundationdb.com/layers/sql
• DocSavage 12y ago
  Timestamping was described in the original BigTable paper and is included in the new open-source CockroachDB [1] (see Versioned Values in the design doc [2]). A big question is whether you will be storing all mutations permanently or whether the database needs to provide either a time-to-live (TTL) or maximum # of maintained mutations. If you are just keeping everything or use a keyvalue store with TTL, this can be accomplished easily with any key-value store by using fixed key sizes and appending the timestamp. In an ordered keyvalue store, you can do an efficient lookup of some time span. Some dbs like FoundationDB provide a framework to manage key space using tuples, so it's even easier to tailor and manage different key types to get the desired access speeds. Rocksdb, a leveldb variant which is the engine beneath CockroachDB, does have TTL [3]. [1] http://cockroachdb.org http://cockroachdb.org [2] https://docs.google.com/document/d/11k2EmhLGSbViBvi6_zFEiKzuXxYF49ZuuDJLe6O8gBU https://docs.google.com/document/d/11k2EmhLGSbViBvi6_zFEiKzu... [3] https://github.com/facebook/rocksdb/wiki/Time-to-Live https://github.com/facebook/rocksdb/wiki/Time-to-Live
  • Goranek 12y ago
    Cockroach is still away from being usable in production.
• bjpirt 12y ago
  Cassandra is very good at storing ordered sets of data which you can then pull out the nearest value to a key. There are a load of layers on top of this that are more specifically time-series which it probably makes sense to use rather than building your own: - https://code.google.com/p/kairosdb/ https://code.google.com/p/kairosdb/ - https://github.com/OpenNMS/newts https://github.com/OpenNMS/newts - https://github.com/rackerlabs/blueflood https://github.com/rackerlabs/blueflood - https://github.com/pyr/cyanite https://github.com/pyr/cyanite
• skram 12y ago
  You might want to check out https://tempo-db.com/about/ https://tempo-db.com/about/
• Tinned_Tuna 12y ago
  If you can't find a product below that suits you below, MIT OCW has a course on advanced data structures which covers this, they're know as persistent data structures, and the lectures on them are very informative. Edit: The lectures: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-851-advanced-data-structures-spring-2012/lecture-videos/ http://ocw.mit.edu/courses/electrical-engineering-and-comput...
• amirmc 12y ago
  An interesting requirement. You might like to take a look at Irmin, which is a git-like distributed storage system. It's still being actively developed but it's far along enough to be worth kicking the tires. http://openmirage.org/blog/introducing-irmin http://openmirage.org/blog/introducing-irmin
• grizzles 12y ago
  Treode https://github.com/Treode/store https://github.com/Treode/store has this feature. Speaking as someone who's used Apache Cassandra a ton, I'd stay the hell away. They break shit all the time to drive sales at Datastax and personally I'm over it. Also hyperdex (hyperdex.org) is one of the better (imo) 2nd gen nosql datastores that might be worth building this on top of.
• huy 12y ago
  OP here, thanks a lot for the overwhelming suggestions, I'm trying to slowly digest all of them. To give a little bit more context about the problem. This is related to our data analytics infrastructure that we're building (we did a technical writeup of it here - http://engineering.viki.com/blog/2014/data-warehouse-and-analytics-infrastructure-at-viki/ http://engineering.viki.com/blog/2014/data-warehouse-and-ana... ) If you look at our data infrastructure diagram (in the posted link), the thing we're trying to improve is the hydration system (where it takes in a record in real-time and try to inject more time-sensitive information into it). E.g. When a user watches a video (thus a video_play event sent), we want to know if it's a free user or a paid user. Since the user could be a free user today and upgrade to paid tomorrow, the only way to correctly attribute the play event to free/paid bucket is to inject that status right right into the message when it's received. Building the system this way (using the hydration service) makes our service very prone to error and indeterministic (since you only have a short window to hydrate the message, and you can't replay a hydration). That's why we're looking at building a historical lookup service that remembers all the different changes of a data object over time, so that replaying a hydration becomes deterministic. At the moment we're processing around 100M records a day and growing. That translates to about 100M read requests. The key size should be around 1M. Not a lot but still at some scale that puts us in the position to think about scalability and performance. Before asking this question, we did look around and also looked into how we'd build it using existing database technology. We thought of 3 different ways using relational DB (PostgreSQL), simple K-V store (Redis/Riak), and Cassandra (with column family). Yet we want to get more opinions of you guys :)
  • garysieling 12y ago
    I did a write-up of something similar recently with Postgres, although I didn't do it with the key-value store types (i.e. hstore or json). The value of this is it shows you how you can use some of the built-in types - I don't know how it scales to 100 MM records though. http://www.garysieling.com/blog/postgres-time-travelling-debugger http://www.garysieling.com/blog/postgres-time-travelling-deb...
• smarx 12y ago
  Here's an implementation in Python built on top of Redis using sorted sets: class TimeStore: def __init__(self, redis_client): self.redis_client = redis_client @staticmethod def timestamp(time): return (time-datetime.datetime(1970,1,1)).total_seconds() def set_value(self, key, value, time=None): if time is None: time = datetime.datetime.utcnow() self.redis_client.zadd(key, self.timestamp(time), value) def get_value(self, key, time=None): if time is None: time = datetime.datetime.utcnow() for item in self.redis_client.zrevrangebyscore(key, self.timestamp(time), 0, start=0, num=1): return item return None def cleanup_before(self, key, time): self.redis_client.zremrangebyscore(key, 0, self.timestamp(time))
  • huy 12y ago
    I think this won't work because Redis' sorted set only allow members with different values. In this case the value mutations could be the same.
    • smarx 12y ago
      Oops, you're right! Here's a fixed version (just prefixing the timestamp to the value to make sure it's always unique). Of course, this entire class makes the assumption that you never write twice with the same timestamp. (That's hard to guarantee if you're actually using time instead of something strictly increasing.) class TimeStore: def __init__(self, redis_client): self.redis_client = redis_client @staticmethod def timestamp(time): return (time-datetime.datetime(1970,1,1)).total_seconds() def set_value(self, key, value, time=None): if time is None: time = datetime.datetime.utcnow() timestamp = self.timestamp(time) self.redis_client.zadd(key, timestamp, '%d:%s' % (timestamp, value)) def get_value(self, key, time=None): if time is None: time = datetime.datetime.utcnow() for item in self.redis_client.zrevrangebyscore(key, self.timestamp(time), 0, start=0, num=1): return item.partition(':')[2] return None def cleanup_before(self, key, time): self.redis_client.zremrangebyscore(key, 0, self.timestamp(time))
• walterbell 12y ago
  Have you considered a round robin time-series database? SQL example: http://techblog.tilllate.com/2008/06/22/round-robin-data-storage-in-mysql/ http://techblog.tilllate.com/2008/06/22/round-robin-data-sto... Research: http://pam2012.ftw.at/TMA/papers/TMA2012paper13.pdf http://pam2012.ftw.at/TMA/papers/TMA2012paper13.pdf
• sunilvirus 12y ago
  You may also want to consider Aerospike database. Aerospike is an open-source database known for its high performance. If you can represent your timestamp as an integer, you can built a secondary index on top and do a range query on it. The range definition looks something like this: Filter.range(name, begin, end) ) More details: http://www.aerospike.com/docs/client/java/usage/query/query.html http://www.aerospike.com/docs/client/java/usage/query/query.... The advantages of Aerospike is its going to be superfast as the index is co-located with the data and also the secondary indexes are always updated inline with writes. So, the indexes always reflect the current state of truth. While doing the secondary index query, its follows a scatter gather approach thereby achieving distributed parallelism of the query. More details: http://www.aerospike.com/docs/architecture/secondary-index.html http://www.aerospike.com/docs/architecture/secondary-index.h... On top of this, if at all you need to perform an aggregation on the secondary query result, you can use the Aerospike's Distributed Streaming Aggregation framework (http://www.aerospike.com/docs/guide/aggregation.html http://www.aerospike.com/docs/guide/aggregation.html). Where you an do the aggregation on the server side itself without pulling all the data to the client. Only the final aggregation happen on the client.