Remote, in-memory key-value stores: An idea whose time has come and gone? [pdf]

http://pages.cs.wisc.edu/~rgrandl/papers/link.pdf

by Terretta • 7 years ago

146 72 7 years ago

pages.cs.wisc.edu

stcredzero2• 7 years ago

Instead, data center services should be built using stateful application servers or custom in-memory stores with domain-specific APIs, which offer higher performance than RInKs at lower cost.

I'm in the midst of implementing a stateful application server-cluster with custom in-memory stores with domain-specific APIs. Basically, it's a way of implementing a game loop and a multiplayer game by specifying lambdas going against in-memory entity databases and in memory spatial databases. However, to do this, I have gone from using PostgresSQL to the Badger fast key-value store as a database. I'm mainly motivated by the desire to keep everything in golang and eliminate all outside dependencies.

That said, what I'm doing is increasing the granularity of the server processes. The server processes are composed of Actor-like things which are responding to async input queues. So my experience both confirms and contradicts some of the the things said in the paper.

kitotik2• 7 years ago

I’m looking more and more at Erlang/OTP for many of these same reasons. Ets/Dets/Mnesia seems to address a ton of typical stateful app use cases right out of the box, and it was built for the Actor model with mass quantities of fine-grained processes you mentioned.

It’s cool to hear a similar approach can be done in golang without a ton of external deps.

jrumbut3• 7 years ago

Would you mind sharing what made you go with a stateful application server?

I've never found myself in the situation of wanting to go that direction.

stcredzero2• 7 years ago

Would you mind sharing what made you go with a stateful application server?

I'm implementing a MMO game loop. Even though I am exposing the API as what amounts to a bunch of lambdas, under the covers, I am holding onto state and mutating it, basically for performance.

EDIT: To put it another way, there is a level of abstraction at which my system is stateless. To implement that with enough performance, I have to hold onto state, so I can deliver data to the implementation of those abstractions in a timely fashion.

zemo8• 7 years ago

the main function of a multiplayer game server is to contain the game state. Depending on the game, it may also run a simulation. You couldn't, for example, write a database record every time someone shot a gun in an FPS, the whole thing would come to a crawl.

And game clients generally only care about the present. Only the current game state is of interest to the client in most situations; the past is rarely queried. The outliers here are things that are naturally transactional and persistent like character progression and item ownership; those things you'd stick in a database.

zemo8• 7 years ago

ha, I ... also am working on a stateful game server in Go, the multiplayer servers that power Jackbox Games' line of games. I don't currently need disk persistence though, I just do it all in memory. It's also way easier than an MMO because the game is entirely instanced, so you can just partition the data by the game instance.

estsauver• 7 years ago

Just wanted to say playing Jackbox with my family has been really enjoyable, and it's really great how easy it is to get everyone set up and started.

neeleshs2• 7 years ago

It's a balance between how inprocess stores bring instability to the main application vs cost of n/w & marshalling. Out of memory errors crashing the application, instead of providing a degraded experience etc. Answer as usual is, "it depends".We moved from inprocess to remote, because we valued application stability more than raw performance.

kahnjw• 7 years ago

Question: for data keyed by user, did you find you'd actually be better off using an distributed in-process cache than a remote cache? I find that hard to believe but maybe I'm just not up to speed on how advanced these caching solutions are.

neeleshs2• 7 years ago

Our use case was not for data keyed in by user, but system generated events that were cached in memory (on a remote cache) for deduplication. We started with distributed in-process cache (Apache Ignite), but found out that failure modes of the cache were not acceptable for the core application. Hence we moved the cache out, to Redis. App behaves far better now.

klodolph• 7 years ago

This is a misleading title: it’s talking specifically about remote in-memory key-value stores. I thought that this would be against e.g. Badger.

kitotik2• 7 years ago

Agreed. It’s clearly targeted at the memcached/redis model.

dang• 7 years ago

Fixed above. Thanks!

nostrademons• 7 years ago

The stateful application server is actually a common architecture for initial prototypes of new apps, because of its simplicity. Hacker News, Mailinator, Plenty of Fish, and IIRC StackOverflow were all built with this architecture.

Where it really falls down is when you have a team of developers all trying to add new features. Code changes a lot more frequently than data. With stateful app servers, every time you deploy new code you need complex and error-prone routines to bring the new process up, have it read the existing state, make sure it's consistent with the new features, and if not migrate it to the new format.

With RInKs, a huge benefit is that you can take the application up and down and all persistent state is already there, and usually the RInK itself handles persistence & error-checking (because it enforces a common data model itself). For minor UI tweaks and per-request features (which are a large portion of changes in the early part of the product lifecycle), you don't need to do a migration at all, the new version just magically appears. For more complex data format changes, you make it so that the application code can read both the old and new formats, converts old to new if necessary, and writes back only in the new format, and then you can drop the old format once it is no longer present in the persistent store. This lets you do the upgrade piecemeal, and avoids corrupting your entire data store if you do it wrong (because the architecture functions as a canary on every deployment, and you can rollback with zero to a handful of corrupted records if things aren't working properly).

The other situation where stateful app servers are useful is when scalability is much more important than change velocity. This may be why Google is coming out with this paper now. This would never have flown within Google when I was there (2009-2014), but I've heard that the focus on maintenance, performance, and architectural improvements is now much greater than that on new features, so it may be appropriate for the Google of today.

sonnyblarney2• 7 years ago

"every time you deploy new code you need complex and error-prone routines to bring the new process up, have it read the existing state, make sure it's consistent with the new features, and if not migrate it to the new format."

Pardon my ignorance ... but wouldn't a stateful model that used mem as true 'cache' not avoid that problem? As if to say the in-memory store is not 'pre loaded' persey, rather, it's loaded incrementally on a on-demand basis from the app itself?

So 'rebooting' has the effect of flushing the cache thats built up over time after reboot, hopefully seamlessly?

Or am I (probably) missing something?

latch• 7 years ago

Your upstream needs to be able to handle 100% of the load, which could be several orders of magnitude more traffic than it normally has to handle. Handling that huge spike in traffic for, what might not be more than a few minutes a year, can be insanely expensive.

Also, you're potentially giving users a noticeably worse experience as you rebuild the cache.

shereadsthenews• 7 years ago

Only problem is the network caches in wide use at Google are significantly faster than what they are using as a baseline in this paper. It’s pretty misleading.

graycat11• 7 years ago

Nice.

The paper anticipated in good detail just what the heck I did with its

"These stores enable services to be deployed using stateless application servers [16], which maintain only per-request state; all other state resides in persistent storage or in a RInK store. Stateless application servers bring operational simplicity: for example, any request may be handled by any application server, which makes it easy to add and remove application servers, to handle server failures, and to handle skewed workloads."

Yup, I thought that was a good idea.

After reading more of the paper, for my project, I still think it is a good idea. Your remarks add weight to that view!

bostik• 7 years ago

In all honesty, the paper describes a solution to a problem most companies won't need to care about. If processing latency for remote cache lookups is a performance bottleneck, it's likely you're already dealing with either enormous scale (Google/FB/Twitter/Uber/...) or some form of HFT (exchanges/hedge funds/banks/adtech/...)

Amusingly enough, I have reason to believe those groups are over-represented in HN audience. They are also environments where computing capacity can make up a significant fraction of your overall engineering costs.

In practically any other scenario the sub-millisecond delay is dominated and completely masked by your business logic taking tens to even hundreds of milliseconds per request. Remember - if you can return a response and a visual update to a client action within 100ms (including the network roundtrip), you're already operating in the lowest Nielsen band.

Another funny thing about this paper is that it feels to me like people are rediscovering zero-copy network processing. Again, a topic dear to many HN hearts but unlikely to be a prime consideration for most companies.

akkartik• 7 years ago

Sounds like their argument hinges on the efficacy of systems like https://eng.uber.com/intro-to-ringpop

sytse• 7 years ago

Yes, Ringpop was reference number 8 in the article. It is interesting that https://github.com/uber/ringpop-go says: "This project is no longer under active development"

So the time of Redis has passed but the successor has passed away as well?

roskilli2• 7 years ago

Basically it's been deprecated in favor of using projects that are more mature like Apache Helix (but conversely more operationally intense to get started, requires Zookeeper and a bunch of things on top if you want to use it in a non-Java setting, i.e. with Go).

bozoUser2• 7 years ago

Reading about ringpop, came across this statement

Ringpop, a library for building cooperative distributed systems, solved some of Marketplace’s problems before its adoption in other teams at Uber and beyond. It gives the high-availability, partition-tolerant properties of distributed databases like DynamoDB or Riak to developers at the application level.

I am wondering about the need to have your app services communicate with each other (is that because these are stateful applications ?) or have I missed the point completely ?

roskilli2• 7 years ago

It's to avoid the complicated routing problem (i.e. building a router microservice that sits in front of it), and encapsulate that in the service itself (by proxying internally to another part of the service after inspecting the request).

graycat11• 7 years ago

I don't get it: Key-value stores is a topic that just won't go away. I was interested in key-value stores, did a little work, solved the problem for my needs, and don't care anymore. Sure maybe there can be some high end, challenging aspects, but what I did was dirt simple, childishly simple to do, blindingly fast, with plenty of capacity -- maybe will cover 75% of the need for everyone?

Heck, if we want something with really deep functionality, we are just back to relational database, right?

So, I wanted a key-value store for session state for users of the Web site of my startup.

When a user sends a page back to my server, it has in a "hidden field" the value of an encrypted token with identifies the user's logical session. And I have in VB.NET a class for the data I want to keep on that user, their session state.

So, in my VB.Net Web server code, I have defined some classes: (1) An allocated instance of one class sends a new or updated key-value pair to the key-value server. (2) An allocated instance of another class requests from the key-value server the value that corresponds to a key. (3) An allocated instance of a third class gets the value back from the key-value server.

For communications, just take an instance of a class, serialize it (thank you VB.NET), copy it to a byte array, and send that via old TCP/IP sockets. Then the receiver gets the byte array and does a deserialization to get the corresponding object instance.

The key-value server is based almost entirely on just two instances of a standard .Net collection class. One instance has the key-value pairs where, right, the key in the pair is the key in the collection class. The other instance has a time-date pair as key and for a value a key from the key value store. Here there is the time-date when the corresponding key-value was last written or read and is used for session time outs. So, for session time outs, just read this time-date and session key instance in ascending order on the time-date key and for any session time-outs delete that collection class element and also the corresponding element in the other collection class.

It's a few hundred lines of code and was a simple exercise in TCPIP, object instance de/serialization, and collection class usage.

I also have code to permit sending some system management commands to the key-value server.

It runs as just a console application.

The code is single threaded, and I'm counting on just the standard TCP/IP FIFO queue to hold the backlog of work to be done.

All the data is held in main memory so should be blindingly fast. Some simple arithmetic indicates that the main memory needed is not very large for even a quite busy Web server computer.

The session state server can serve any reasonable number of Web server computers, and a particular user doesn't need session affinity with a particular Web server.

Looked simple and easy to me.

How much of the need will something so simple satisfy?

What needs will such a simple solution not satisfy?

zemo8• 7 years ago

that's ... literally what people do with redis and memcache, you just wrote a slower memcache with fewer features.

that's on one server and the data is all in process memory?

throwmeawy• 7 years ago

GP has shown a long-term tendency to create a naive implementation, in VB.NET even, and then get surly about folks who refuse to acknowledge its sufficiency. No good can come from engaging / trying to educate.

N.b. built-in .NET object serialization is a slow, wasteful, brittle solution, but it could be okay if one doesn't mind the performance or portability issues. Heck why not use XmlSerializer then?

graycat11• 7 years ago

Thanks.

I'd heard of Redis -- it looked like overkill and more work just to understand than what I wrote.

I'd never looked at memcache.

With your mention of these two, I did a little Google search. Google has some of their little nutshell relevant descriptions right away and a also a link to an informative article:

https://www.linkedin.com/pulse/memcached-vs-redis-which-one-...

This article seems to say that now Redis has the memcache functionality built-in implying that never need to use both.

The article does seem to claim that memcache is multi-threaded and Redis, single.

I've been hoping I could get by with single threaded and the TCP/IP FIFO queue -- IIRC .Net has a multi-threaded version of the collection class.

Or, maybe if want multi-threaded, better just to run that many instances of the software, each single threaded, and f'get about the overhead for the multi-threaded collection classes?

Again it looks like memcache and Redis are more complicated just to use than what I wrote.

"You just wrote a slower memcache with fewer features."

Well, well almost anything will have more features than I included!

What I wrote should be plenty fast internally if the .Net collection classes I used are from AVL trees, Red-Black trees, or something similar. Then what I wrote would be slower because (i) get to it via TCP/IP sockets instead of some addressing more direct that would have to be on the same machine.

But I didn't really want my session state store to have to be on the same machine as the Web server software that is using it. So, that essentially implies that a Web server has to get to the session state key-value store via TCP/IP sockets and stands to be about as fast as anything else with such socket access.

Let's see: For some much heavier loads with lots of Web servers and lots of session state store key-value reads/writes, startup 20 such session state stores and have each key start with a number 1-20 to specify which key-value store. Then do a crude load leveling -- for a new key-value pair, send that to 1 plus the number of the last number used modulo 20, that is, round-robin. So, that would be my approach to something scalable, distributed, IIRC, sharding. Yes, could do more where could have an instance of the session state store start a shutdown be accepting no new key-value pairs and then after the time out value with all its pairs deleted send a message somewhere saying it is shutting down. A Web server trying to sent a new pair to such a shutting down server would receive back a going out of business message and not bother that server again until it has received another message. Or when intending a shutdown of a session state server, just send a notification to each Web server that the particular session state server was shutting down. So, could have some system management features for better continual operation. Maybe Redis has all this already and the details of such features are what I don't want to take time to read just now!

Sounds like if my startup is successful, I'll be converting over to Redis!

nullwasamistake4• 7 years ago

I'm astounded at the number of developers in my own company that reach for Redis when they just need a cache. It's a huge waste of effort for far worse performance and less reliability than something like Java's Caffiene.

Stateful servers run into huge problems when other people try to access them from non-static ip (usually sticky sessions are IP based). We, at least in apps I work on, stuff all the shared state into JWT tokens to avoid this.

Everything else that needs to be cached goes into an in-memory in-app store. If you're using a "fast" language to start with, you won't need more than a dozen servers unless you're at Google scale so cache hit rates are good even though each instance maintains it's own.

Again if you're using a "fast" language memory overhead from in app storage isn't much more than putting things in a dedicated KV store. There's really no point to it when the performance drop is usually 20x. We use DropWizard and Vert.X extensively, and most of our endpoints can handle many thousands of requests per second. The ones that use the cache instead of hitting the DB every time hit upwards of 1 million requests/sec. You're very lucky to get 50k with any remote KV store in the same app.

Most load balancer strategies send many requests in a row from a client to the same backend server anyways for TCP performance reasons.

The only reason for a KV cache is if you're running a slow language like Ruby, PHP, Python, where the memory overhead for objects is large and the speed of a remote cache is roughly the same as one in memory. If you find yourself needing a cache for good enough performance you shouldn't be using these languages in the first place. In memory caches don't work well when you need 100+ server instances to handle the load anyways

zemo8• 7 years ago

Stateful servers run into huge problems when other people try to access them from non-static ip (usually sticky sessions are IP based). We, at least in apps I work on, stuff all the shared state into JWT tokens to avoid this.

They're not saying that an application server should never query another server, they're saying that the server that functions as a state container should host a domain-specific api for manipulating the state. See figure 2 b; the frontend and stateful application server layers are separate layers.

alexchamberlain2• 7 years ago

I run several Python servers backed by Redis; Redis was added when we profiled the apps and determined that loading data from several databases was taking too much time. Using a different language wouldn't have changed how much time various RDBMSs take to return an answer to your query.

I think there's some citation needed on the performance of in memory vs out of process caches in interpreted languages.

nullwasamistake4• 7 years ago

In my experience with Postgres at least, our queries average less than a millisecond in Java. Our slowest query averages 5. We're not running anything crazy, pretty generic CRUD app.

We can hit about 50k queries per second on one server from our limited stress testing. Redis was around 150k. In memory cache is ~1.2 million. This is JSON requests using Vert.X on Java.

I just don't see the advantage to an out of JVM cache when your service is so fast that you only need more than one instance for failover. In slower languages where you need a bunch of front end servers to handle a reasonable load, out of app caches look more appealing. The hit rate for in app caches becomes too low when you have a bunch of instances.

But my point is that you get a lot more performance with a simpler setup if you use a language fast enough that you can run just a few instances and cache locally. Out of app caches are usually an anti pattern brought about by needing too many front end servers because your app is too slow for in-app cache to be useful(more instances means too low hit rate without shared cache).

You're effectively forced to use slower out of app caching because of the number of instances you need to run

twa927• 7 years ago

The only reason for a KV cache is if you're running a slow language like Ruby, PHP, Python, where the memory overhead for objects is large and the speed of a remote cache is roughly the same as one in memory. If you find yourself needing a cache for good enough performance you shouldn't be using these languages in the first place. In memory caches don't work well when you need 100+ server instances to handle the load anyways

You're saying reading a serialized Python object from Redis and deserializing it is comparable to accessing a ready in-memory object? No, it's an order of magnitude slower. I think the reason in-memory caches are not used much in Python/Ruby is a concurrency model, ie. in Python/Ruby you usually have to run multiple processes and in Java you run multiple threads, so the in-memory cache can be just a regular data structure normally accessed.

Also, I think you are overestimating the Python's memory overhead compared to Java - Python's int is 24 bytes and Java's Integer is 16 bytes (and using PyPy is another story - it can use several times less memory compared to Java).

hliyan• 7 years ago

I have to agree. When I first moved from the C++ world to the Web world five years ago, I was surprised to see an entire generation of engineers for whom the idea of using application memory is alien. It's as if we're ignoring an entire layer of the memory hierarchy because we're afraid of managing the complexity of application state with load balancing / sticky sessions.

huffmsa• 7 years ago

But once you get to deployment, particularly if you're using shiny new containerized orchestration, in my experience, it is safer and easier to allocate the host node's memory to the redis container and keep it protected from application layer fires.

Same as you would do with a database.

It speeds up CI/CD and keeps things safe / reduces downtime in cases of roll back (assuming you're versioning your keys).

happythought• 7 years ago

Atul Adya and Daniel Myers work on Slicer[1] so they have some bias.

[1] https://www.usenix.org/system/files/conference/osdi16/osdi16...

dbmikus• 7 years ago

Would this just be like using RocksDB or something like that with extensions to auto-shard and balance between instances? That's what it looks like to me, but I could be misunderstanding it.

analyst74• 7 years ago

Another benefit in-memory cache vs remote key-value store is the reliability.

Redis/memcached servers are super reliable, but at scale, you'll run into non-trivial amount of failures when communicating to those servers, even a sub-second blip in network connections could result in hundreds of failures.

Now you have to deal with retry, ensure your application logic is failure tolerant, worry about timeout, consider impact of temporary delays in redis to your application server due to skyrocketing threads waiting for results and all that fun stuff.

alexchamberlain2• 7 years ago

At scale, don't you have the same problems with your in memory caching solution (specifically in the distribution and coordination parts)?

graycat11• 7 years ago

Nice. Sounds like the clients should be willing to retry any such remote communications due if only due to little blue ET men crawling through the server farm LAN cables.

philihp• 7 years ago

The author has missed a very very important feature: Redis as a distributed lock manager.

Redis’s SETNX is a very fast and very cheap solution to resolve race conditions and dining philosopher problems among shards and nodes in large clusters.

saurabhsharan• 7 years ago

I assume you've read https://martin.kleppmann.com/2016/02/08/how-to-do-distribute...

yenwel• 7 years ago

Event sourced persistent actors in cluster mode is where it's at!

d--b• 7 years ago

The title is annoying on purpose... This is a different, more complex and more-efficient-in-some-cases approach.

netik• 7 years ago

Article reads like an overview of 2008 technologies, but offers no actual, new solution to the existing solution that fuels Twitter and other social media sites.

pwpwp• 7 years ago

Funny that this doesn't mention parse-free data structures like FlatBuffers or Cap'n Proto that don't need unmarshalling.

https://google.github.io/flatbuffers/ https://capnproto.org/

jdalsgaard• 7 years ago

Love it; "if you fetch it over a socket, it ain't no cache"

hinkley• 7 years ago

When I'm explaining KV to a junior dev, I do it something like this:

Memcached got big during a confluence of two problems that have both been solved now. First, we had a bunch of big, semi-stateful web applications built in programming languages with GC, and server memory got bigger than you could reliably collect without long pauses. Pushing some of your data into a separate memory space raises the ceiling considerably.

Secondly, during this ten year window, ethernet cards were half an order of magnitude faster than hard drives. Putting stuff on another machine could be faster than sending it to swap, a memory mapped file, or some more sophisticated data store (like a database).

We don't have to struggle with these now, and half the time we avoid the first one altogether. They still have lots of places they are used, but you are way better off working to cache inbound requests instead of outbound requests. That lets you move a bunch of caching to the edge of your network, or to the user agent.

bakhy• 7 years ago

I'm currently working on a side project, a distributed in-process key/value store for .NET Standard, which might be interesting in this context. I hope you'll pardon the shameless plug, but I'm interested in getting feedback. Particularly, what to focus on, what use cases, missing features... And of course, if you see any issues with the approach.

https://github.com/jbakic/Shielded.Gossip

It needs more work, but I think the eventually consistent part could already be useful for a simple distributed cache layer atop a classic relational DB.

PunksATawnyFill• 7 years ago

It's "key/value" store.

Remote, in-memory key-value stores: An idea whose time has come and gone? [pdf]

Related Stories