4 ms·
The kivaloo data store
- wladimir 16y agoSo it's a key value store that supports mapping keys of up to 255 bytes to values of up to 255 bytes. Isn't 255 bytes a bit short, especially for values? What usecases does this have in Tarsnap? Filename <-> Hash mapping?
- cperciva 16y agoIsn't 255 bytes a bit short, especially for values? No. Values, not blobs. What usecases does this have in Tarsnap? Filename <-> Hash mapping? (Machine, block name) -> (object on S3, offset within object, length of block) And a few others to deal with in-progress transactions and suchlike. But I think the largest values I need are 20 bytes long.
- wladimir 16y agoThanks, that makes a lot of sense.
- deleted 16y ago[deleted]
- mml 16y agoi needed to get to work one day, and i didn't like all the available cars, bikes, trains, motorcycles and the like, so i built myself a dandyhorse.
- cperciva 16y agoA closer analogy would be "I needed to cross the English channel, and planes, helicopters, boats, and trains weren't suitable to my needs, so I built myself a jet pack instead".
- jerf 16y ago20 years ago, we figured when we had this level of computing power available to us at these costs, we would stop worrying about performance. But it hasn't happened at the "cloud" layer; when you're trying to perform at scale, every additional little quirky feature some existing solution may provide may be the thing that breaks your use of it, and the diversity of ways that cloud services can function is quite amazing. From 20,000 feet they may all look the same but down on the ground even two "disk bound" services may have radically different properties and requisite solutions. You don't know enough to judge whether this was good, necessary, or an effective use of time.
- mjb 16y ago> It is a durable, consistent, high-performance key-value data store built out of a background-garbage-collected log-structured B+Tree. Some questions for Colin, if he reads this thread: I assume log-structured implies 'append-only'. Is that correct? This seems to be fairly similar in spirit to the design of BDB-JE, but without offering many of JE's features (like ACID). This similarity is a good thing - JE does a really great job in many situations. Have you done any comparisons of kivaloo with BDB and BDB-JE, especially looking at IO constrained performance? Although its pretty clear why BDB-JE wouldn't be ideal for Tarsnap (starting the the Java thing), why did you chose not to go with BDB? Just a licensing issue, or more technical? How do you trigger garbage collection? What kind of effect does garbage collection have on the throughput of the database? What kind of performance drop do you see with very sparse trees/logs, for example with workloads that are very insert and delete heavy? I haven't had time to look at the source yet, so I apologize if these questions have obvious answers.
- cperciva 16y agoI assume log-structured implies 'append-only'. Is that correct? Yes. (Technically, append-at-head and delete-from-tail only.) Although its pretty clear why BDB-JE wouldn't be ideal for Tarsnap (starting the the Java thing), why did you chose not to go with BDB? Last time I checked, BDB was a library. I wanted a server (because a server can cache data structures). How do you trigger garbage collection? The code keeps track of how much garbage is present and keeps a running tally of how much garbage collection it "owes" based on maintaining a long-term optimal GC rate. When that value is large enough, it looks for some old pages to clean. What kind of effect does garbage collection have on the throughput of the database? "It depends". The optimal cleaning rate depends on the amount of I/O you're already doing, so it turns out that cost-optimization automatically results in you doing more cleaning when the active I/O load is lower. In the common case where the load on the data store varies (either because it's bursty or because of daily/weekly load cycles) there won't be any cleaning happening during the high-load periods. What kind of performance drop do you see with very sparse trees/logs, for example with workloads that are very insert and delete heavy? The B+Tree is rebalanced every time pages are written to disk, so "sparse trees" aren't possible.
- narag 16y agoKivaloo is said to be based on B+ and to support a "range" operation. So in fact it's more than a key-value store, isn't it?
- cperciva 16y agoSome key-value stores support RANGE; some don't. I don't see what you're getting at here.
- narag 16y agoI'd read that some key-value stores are implemented using hash tables and erroneously assumed that was the general case. Good to know it isn't.
- cperciva 16y agoA lot of key-value stores use hashing at the distributive layer but not within individual nodes. Since kivaloo is currently single-node-only there's not much point using a hash.
- jetz 16y agocongrats. performance-wise it does not look like the best but durability and consistency would be the key points. > default 128 MB memory limit on kvlds. this can be changed i suppose? i hope docs will be coming. > services requests upon it from a single connection; and a request multiplexer (mux) which accepts multiple connections and routes requests and responses to and from a single "upstream" connection. does this mean it support multiple requests in one round-trip?
- cperciva 16y agoperformance-wise it does not look like the best Show me a networked data store which does better on the same hardware. (FWIW, with trivial keys and values, kivaloo gets significantly more operations per second.) default 128 MB memory limit on kvlds. this can be changed i suppose? i hope docs will be coming. Command-line option to kvlds, documented in a text file in the kivaloo tarball. services requests upon it from a single connection; and a request multiplexer (mux) which accepts multiple connections and routes requests and responses to and from a single "upstream" connection. does this mean it support multiple requests in one round-trip? Yes, and responses can come back out-of-order, too.
- davidyu 16y agoNice! Btw, on concurrency, is it multiple reader/single writer?
- cperciva 16y agokvlds is single-connection. Using mux you can have as many connections as you want, and they can send whatever requests they want -- mux doesn't care what the requests are, and as far as kvlds is concerned, all the requests are coming from the same place.
- jetz 16y agoi didn't get what you mean by networked data store. afaik almost all of kv stores are similar wrt "network". i checked http://redis.io/topics/benchmarks http://redis.io/topics/benchmarks and saw that kivaloo performs better within given constraints like value limit at 255 bytes. your benchmark page makes numbers worse because of that 128 mb option.
- deleted 16y ago[deleted]
- seiji 16y agoIt even has dollar cost aware adjustment knobs: -S <storage:I/O cost ratio> Cost of one GB-month of storage divided by the cost of 10^6 I/Os. Used to control how aggressive the background log cleaner is. Good values range from 0.08 (3 TB SATA with 100 random I/Os per second) up to 1600 (40 GB SSD with 25k random I/Os per second). Setting -S 0 disables background log cleaning. Defaults to 1.0 (which is a good value for Amazon EBS).
- cperciva 16y agoThis is mostly for the benefit of SSDs. You want to be far more aggressive with cleaning on them.