CrimsonDB: A Self-Designing Key-Value Store
daslab.seas.harvard.edu
daslab.seas.harvard.edu
But for the Web site for my startup, early on it was clear that I needed a good key-value store as a Web user session state store (server). So, I designed one, coded it up, and have been using it. It seems to work fine.
But on key-value stores, I don't get it because what I did was easy, too easy, really, to say much about it except how easy it was to do.
So, a Web server has a user and their session state. For the user, I also have a GUID (globally unique identifier) that is the key for the user and their session. The session state is in an instance of a class I've defined.
So, the Web server serializes the instance of the class to a byte array and passes that and the GUID key to a subroutine that uses TCP/IP sockets to start a TCP/IP session with my session state store. To Windows, my session state store is just a simple, console application.
The session state store is listening for a TCP/IP connection request, accepts the request, and gets the GUID key and serialized object instance with the session state.
The session state store has two instances of a standard .NET collection class, say, A and B. Instance A uses the GUID as the key and the serialized session state as the value. Class B uses the then current system time-date (GMT) as the key and the GUID as the value.
So, whenever the session state store runs, before it returns, it looks at the earliest time-date stamp in instance B and deletes from A and B all the key-value pairs that are too old, that is, timed out, that is, have encountered session time out.
The code of the session state store is simple -- single threaded. Then the code needs a first-in, first-out (FIFO) queue, and for that I am using just what TCP/IP offers with a maximum queue depth of 100 which I hope is enough -- will be able to tell by looking at the site log file.
That's about it.
It's simple. It's darned fast and nicely scalable via virtual memory and, then, sharding, etc.
I designed the whole thing in a few minutes and implemented it in about a day, but I'm no expert in session state stores, key-value stores, Redis, etc.
So, what is wrong with what I designed?
Thanks.
For example, we run a globally distributed application with 1TB+ of session data running in sync across 4 global regions with 200K/sec of requests. We could build it, but that would be an incredibly complex undertaking, so we decided to use ScyllaDB instead and worry about more important things.
Interestingly enough ScyllaDB is a great example of building a faster and smarter self-tuning database, in this case as a next-gen evolution of Cassandra. More choices are good, and we are nowhere near the limits of what can be done.
WOW!
1 TB+ of session data; wow! My back of the envelope arithmetic indicates 10 MB -- different ballpark.
My first cut guess would be to have something as simple as my code, see what the transaction rate was, and then start up enough separate instances plus some to give the desired data rate and have something to recover from too busy or a sick server.
If you have found a product that can handle the 200K/sec and the 1+ TB, then, sure, just use that and get back to work more particular to your business.
So, you answered my question: What is the interest in key-value stores? The answer being, at 200K/sec transactions and 1_TB of session state data, a key-value store becomes a challenging problem. I designed a small airplane -- you need a C5A or bigger. Okay, that's a good answer.
I've heard of Cassandra but have not looked into it -- likely for my startup don't need it yet.
That's not a "what if your startup becomes the next Facebook?!?!" suggestion of premature optimization; these types of breakages happen early. If you went from 10s of MB in your store and 100s of hits per second to 100s and 1000s respectively, it's possible that previously unexpected conditions would occur. I've seen cache and auth systems buckle under 10x load long before the real heavy lifters (RDBMS and backend communication points with other webservices) felt any strain at all--but only in places with esoteric or hand-built cache and auth systems.
Now, none of these may be problems for you, and I hope they're not. You may have coded with that type of growth in mind (and your mention of possible future sharding indicates you've thought about it--good on you). But the sheer ease with which Redis/Memcached/pick-a-KVS can be deployed and scaled, coupled with the difficulty of replacing all call-points to a session store (easy on a disciplined, low-developer-head-count stack; much harder on a stack that had to grow in traffic/LoC/engineers in a hurry--hooking into session management to track request state all over the place is something of a siren song), is, I suspect, an additional motivation besides "we have huge amounts of data/traffic" for the widespread popularizations of off-the-shelf key/value stores.
> hooking into session management to track request state all over the place is something of a siren song
Yup. The scary part is to discover that occasionally, and too often, the site gets sick, and due to non-determinism, etc., I can't easily reproduce the behavior to analyze it, find the cause, and correct it. Using a log file, etc. to trace the work in detail of each user for some 60 second interval that showed the problem is likely a siren song, big muddy swamp, but, still, maybe one of only a few choices with any promise. I'll be thinking of such tracing as I continue to get my code ready for production. Right, turn on full tracing, run for two weeks, get a 20 TB log file, and discover that somehow with the tracing on don't get the problem!!!! Nightmare scenario!!!
My home brew, DIY, roll your own, just some serialization, TCP/IP sockets, and two instances of a standard .NET collection class, session state store (server) has worked fine in my testing so far. The session state server has been one of the easiest parts of my code and work so far. Some TCP/IP, serialization and two instances of a collection class should not be considered a challenging development or debugging job!!
But currently I'm doing some grunt work, ..., and racing to go live on the Internet. So, currently I have 0 users per second.
When I get to 1 user a second, that will be a big day.
You are correct: I'm a sole, solo founder, CEO, CFO, CIO, ..., software manager, server farm manager, ..., software installer, cable puller, etc. so, could easily change all my Web site software to use a different session state store.
Uh, I've already designed the Web server software and session state store so that there need be no user affinity between users and a particular executing instance of the Web server software.
Generally as you suggested, since I'm a solo developer, who still does good documentation, it's easy for me to make some likely changes, much easier than if I had rows and columns of developers filling floors of a 20 story building with 300,000 square feet of space.
My planning for implementation now is for 1 to a few users a second, on average, 24 x 7. I do want to look at the whole server farm architecture and determine just what would happen, where my site would break, at, say, 100 users a second, from a DDoS attack, an article in the the tech press, something viral, etc. Maybe Cisco has a box that could help me. So, if the site is overloaded, then I want the users to get a simple message back apologizing for the overload or at least just a slow response. Basically I want to know where the performance bottlenecks and limitations are and have just one bottleneck that can handle the overload gracefully and throttle what reaches everything else. Heck, the electrical system has circuit breakers; electronics commonly has overload protection; my Web site should, too!
For 10, 100, 1000 users a second, each of those steps is a factor of 10 more. Point: Factors of 10 are not just different quantitatively but different qualitatively.
At 100 users a second, I'll be hiring for the 100 and also planning for 1000 and 10,000.
I'll be thrilled at 1 user a second, but there is a chance that people will like my work and cause usage to grow to 1000 users a second.
Good to know that some people already know how to handle 200K/second!!!
Thanks!
However, if you're asking why people spend so much time writing Key-Value stores, the answer is that what you've designed is, I'm assuming, using the filesystem to store session state for each user, which is pretty much a Key-Value store unto itself. So people who write databases feel the need to reimplement the algorithms in that filesystem layer, and expose them over a TCP api rather than system calls. There can be performance and scale reasons for this. But the filesystem is the oldest trustiest Key-Value store and if it's good enough for your purpose it's so much easier.
No, in the key-value store, the storage is all in the two instances of the standard .NET collection class and, thus, in main memory. If the classes get really big, say, GBs, then maybe Windows will use some virtual memory. Or maybe someday, if I have a big company, I'll program some big, 14 TB or so solid state disks as direct access files, say, B+ trees, to do the storage.
But for a long time, the storage for the key-value pairs will be just in main memory.
So, for a user a second, 20 minutes active time per session, and after that 40 minutes of time until session time out, can calculate how many key-value pairs need and, if I just look up the size of the values, get a decent estimate of the main memory needed.
I did that: For the 16 GB of main memory for my first server, the storage seemed reasonably small.
E.g., assume users arrive at 1 a second. Keep each user's session state for 20 minutes for their active time plus another 40 until time out for 60 minutes total. So, after running for 60 minutes, the server has reached a steady state of
60 * 670 = 3,600
Besides, if I get a user a second and they interact with my Web site for 20 minutes each, I'll be getting a new Corvette in a few weeks and have lots of money for new, larger servers, racks, UPS boxes, emergency motor-generators, etc.!!! :-)!!!
Thanks.
Sure, there is
Ronald Fagin, Jurg Nievergelt, Nicholas Pippenger, H. Raymond Strong, 'Extendible hashing-a fast access method for dynamic files', "ACM Transactions on Database Systems", ISSN 0362-5915, Volume 4, Issue 3, September 1979, Pages: 315 - 344.
with a graceful way around collisions.
Our group used that paper in our work in a high end, cross memory (one address space gets data to/from another address space, calls code, etc. in another address space), active (generalization of, say, triggers common in relational database), dynamic (the object definitions change during execution) object store.
There is also a good article with good details and some Python code at:
http://en.wikipedia.org/wiki/Extendible_hashing
Actually the code we used was nicely simple -- I have some notes someplace, but the paper itself is good enough documentation.
But also have to have some persistence of the session state across different HTTP POST operations from the user; so, if have no user affinity with a particular executing instance of the Web server software, and I'm looking forward to having several executing instances of my Web server software, I want no such affinity, then I need something in a different Windows appdomain, e.g.,
http://msdn.microsoft.com/en-us/library/system.appdomain.asp...
process, address space, etc. like an external server for the session state data.
Sure, that server could use the extendible hashing paper. But, since the .NET collection class is there, and no doubt by now used successfully more often than McDonald's has served a hamburger, I just used what Microsoft provided. I'm willing enough to beg, borrow, buy, or (hush!) steal a wheel instead of reinventing it!
I did my DIY session state store partly because I guessed that I could write my own code in less time than it would take me just to understand how to use something highly regarded and off the shelf.
I guessed that I wrote my code in less time than I would need just to understand Redis. That IBM work was intended as a high end object store -- I knew how hard it was to use something like that. And from some of my notes I see
"Microsoft Unveils FASTER – a key-value store for large state management"
as at
https://www.microsoft.com/en-us/research/blog/microsoft-unve...
and
https://news.ycombinator.com/item?id=17267403
But I discovered this option long after I wrote my own. Again, I suspect that I wrote my own is less time than it would take me just to understand the Microsoft documentation for their FASTER. If my DIY work gets weak in the knees from too much load, etc., then, sure, I'll consider options off the shelf.
Well depending on what error scenarios you might run into your code will work until it runs into those scenarios.
Few ideas what could go wrong you can get from this video:
Yup.
So far the server side of my Web site has servers of 6 types -- Web server, session state store (server), log server, SQL Server, and two core servers for the real work, doing some applied math to get the users the good stuff that will make them happy. Soon there will also be an ad server for a total of 7.
As in the sense of the video, that sounds like a non-deterministic hell to debug. Ah, in this case, I don't think the debugging is so difficult. Mostly the reason is that so far all the interactions are conceptually and as in the architecture quite simple. E.g., the code seems to run fine, and I never encountered any significant problems getting the code, first version and first production version, running fine.
But I do intend to add to the code lots more writes to the log server and be able to turn on/off those writes while the system is live. Then I could write some code to look at the log file and for each user session check all the traffic and work.
Yes, things could fail. I do have a lot of reasonable value checks in the code and, thus, could get some diagnostics then.
Eventually I'll want to implement some fault tolerance: E.g., if a log server becomes unresponsive, then switch to another one -- there maybe several anyway due to load and desire for redundancy. Similarly for the session state store -- a user might lose their session, but that would get logged, but the Web server would then start to use a different session state server.
So far my site is simple enough in purpose, work, architecture, etc. that some reasonably careful thinking, documentation, coding, and testing should continue to be okay.
But, sure, if the site gets to 1000 users a second, I'll have to rethink the architecture in big ways.
Then I'll try to keep using the "keep it simple, stupid" KISS principle and be willing to waste a factor of 2 to 10 or so in checking and being sure and being able to do the right things for some failure scenarios. Uh, my Web site is not for banking, exchanging crypto tokens, etc.!!!
Thanks, especially for the video.
Right, for non-deterministic systems, can be tough to duplicate a problem in order to analyze it! So, tough, in practice, try never to have to confront directly the non-determinism -- i.e., have enough in tracing in logs that have in effect converted the work to something deterministic, the randomness removed.
So, first cut lessons, try to avoid non-deterministic designs; if have one, then try to keep it dirt simple and likely relatively isolated from everything else; and if can't do all that, then during development and testing, at various levels, have lots of scaffolding and for production put in lots of checks, redundancy, thought, system management, monitoring, reporting, and analysis infrastructure, etc.
E.g., I did and published some high end work in anomaly detection for real time monitoring to detect problems never seen before, and I intend to use that work when appropriate. The intuitive idea is that if the system is not humming like it usually does and should, then I'll discover that right away and, then, be able to zoom down a tree of partitions of the systems to localize the problem -- hopefully in a usefully large fraction of such cases. My work is good because it is multi-dimensional, distribution-free, has adjustable, known in advance, exact control over false alarm rate, and in a useful sense is the most powerful such monitoring possible from any means of processing the data.
No way should ever have to see that the system occasionally gets sick and just look at the system, in racks in 100,000 square feet of floor space, and start to guess. Instead should have a LOT of darned good additional data from the various over-designed internal checks, logs, redundancies, etc. Really, the system should come close to just making it obvious about where the problem is.
No joke: In 100,000 square feet of racks of humming servers, want some darned good health and wellness monitoring that, at least in the design, architecture, development, testing, and first months of production operation, appears to be able to localize problems.
Suggesting that such work is important; not suggesting that it's easy or will get it good enough right away. Am suggesting that should take the problem seriously and try. For some important systems, may spend several times as much computing checking and monitoring as doing the actual production work.
But no way do I ever want to have to know there is something wrong and have to be forced just to look at 100,000 square feet of servers and start with Ethernet diagnostic hardware, reading files, etc. I hope never have to consider a main memory dump.
My first development computer got flaky -- I became able just to smell flaky. It really stinks!
> what is wrong with what I designed
You've not described an authentication mechanism, so it has to be kept firewalled - a lot of people have made the same mistake with memcached.
The scalability of your system depends entirely on the standard collection class, which will be OK but not optimal. As you say, when you're not at the scaling limit this isn't so important.
I don't quite understand what you mean by TCP/IP queue; it sounds like you might be exposed to the risk of one client blocking?
> I don't quite understand what you mean by TCP/IP queue;
Suppose Web server code thread A sends a request to session state store (server) thread X in another AppDomain, process, address space, virtual machine, physical machine, etc. About the same time, threads B, C, D, ... similarly send requests to thread X.
Now, suddenly, poor thread X is working on the request from the TCP/IP session from thread A. So, what the heck happens to the requests sent to X from B, C, D, ...? Even if thread X does the work of thread A in one millisecond, the requests from the other threads might all arrive in just 10 microseconds during the 1 millisecond. So, there has to be a place, a queue, in the TCP/IP stack at thread X for the requests B, C, ....
So, a standard part of the design of TCP/IP for receiving such requests is a queue. Well, of course, we want a first-in, first-out (FIFO) queue. And the storage for the queue will be finite. It turns out, the queue depth, IIRC, can be set, adjusted, by ordinary system management of the TCP/IP stack software. So, if my server farm has 100 Web server threads and only one session state store, then that session state store can get at most 100 requests at once. So, a queue depth of 100 should be enough!
Now, sure, think about Microsoft's IIS (internet information server) that starts threads in my Web server software; want IIS to start no more than 100 threads! So I'll need to check on how to do this. In that case, some user 101, when 100 users are already waiting, will have to wait before IIS creates a thread for them. Then, sure, should arrange a graceful way to handle that overload situation, e.g., send that user 101 a message about the site being too busy.
This issue of the site being too busy is bigger than that and likely needs more careful thinking than just some one parameter in IIS.
> The scalability of your system depends entirely on the standard collection class, which will be OK but not optimal.
The session state store collection class is all in main memory and blindingly faster than the real work for the users; some of that real work involves skipping down a SQL Server table with a clustered key -- the table is on rotating hard disk! Sure, SQL Server may cache in main memory some of the data; as SQL queries go, it's quite fast, e.g., no joins and only that one table; since the SQL Server table is read only except for maybe write once a week, that table is a candidate for some solid state disk; still, even on solid state disk, the time for the session state store is only a tiny fraction of the work, and wall clock time, for serving one user request, small potatoes, and not a main candidate bottleneck.
> You've not described an authentication mechanism, so it has to be kept firewalled - a lot of people have made the same mistake with memcached.
Thanks for the authentication issue! So, maybe I should consider adding checks on the IP addresses to make sure they are as expected within my server farm! Nice!! Maybe I should also talk to Cisco!
All the servers are inside the server farm, and it is supposed to be nicely firewalled from the public Internet by my router(s), e.g., just using IP addresses that don't work on the public Internet.
Sure, if someone gets some malware running inside my server farm, then I'll have a fox feasting in the chicken coop.
On one client blocking: Hmm .... Maybe! NICE point. So, a Web server sends a key to the session state store (server) key-value store requesting a value for the session state for the user identified with the key. The session state store looks up and returns the value, but in the meanwhile the Web server thread waiting, via its TCP/IP stack, on the session state store goes belly up and dies. So, the TCP/IP stack at the session state store will eventually notice the bad TCP/IP session, the failure at the other end of the wire, and give my session state store a timeout. My session state store, noticing the timeout from its TCP/IP stack, will write a note to the log file and continue on. The time for the time out (which I should set to be short) will hold up all threads that depend on that session state store. Since 99+% of the work at the Web site is NOT going to/from the session state store, nearly all the real work of the Web site can continue while the session state store thread waits for the time out for its session with the dead Web server thread. The next HTTP POST from a user should cause Microsoft's code, IIS (Internet Information Server), to start another executing instance of the Web server software which will, on a good day, let the work continue. Users with work in progress might get something unresponsive and, if they POST again, get a message from the fact that the Web server code notices that the user's state is not right, or maybe it still is right and okay and the user is not bothered. The time involved might be only a second or few and not too bad.
My Web site is not dealing in money or crypto tokens, etc. And my users don't log in, and I'm making no use of cookies. So, for such an error, about the worst that can happen to a user is a lost logical interactive session, which is no threat to the solar system! NICE consideration! Thanks!
Suppose you had decided to use Redis, Memcache, or any number other things that are available off the shelf. This would have let you get going faster, have more features, it'd be more scalable, and you would have a smaller code-footprint in your project (which is good from a maintainability perspective). Lots of web frameworks also provide integration with these stores out of the box with trivial code changes (i.e. with Rails, you just list Redis as your session store, provide the connection string to the instance, and you're done, Tomcat is about as easy, I feel reasonably certain this is true for all full featured web frameworks out there). We're talking a couple of lines of configuration here. This has the benefit of being written being battle tested by other people in production and with a variety of use cases. No guarantees it doesn't contain any bugs, but you're unlikely to be the one to encounter them first.
Also, your use case sounds relatively small. By contrast, at my last startup we were running tens of millions of cache hits per second with an ehCache/Memcache system (ehCache was a local hot-cache, cache misses went to Memcache). Other than some parameter tuning, it worked out of the box. It took me less than a day to have the whole thing working and set up for production use. Once it was set up, it never needed much attention except for the occasional Memcache param tweaks. For a vanilla use case like yours, you probably could have been running it in less than an hour and you'd never have to touch anything (with Rails and Heroku which I'm familiar with, it would take less than 10 minutes). We also get documentation and support for free (thank you stackoverflow, mailing list folks, and OS project maintainers).
So, I would wager that it took us less time to set up and maintain our fully-featured, massively scalable, distributed cache than you took to set up yours; and I'd also wager that our setup significantly outperforms yours. If we needed a feature in the future, we could also likely just add a config param vs. having to write it ourselves (5 min vs 5 days). And finally, we never had any tests for our caching or eviction management and we knock on wood never hit any bugs in either system.
Long story short, if I came across a project with a custom key-value store, it would have to be pretty darn specialized for me not to rip it out and replace with something standard.
So nothing sounds wrong with your design, but I would conjecture that the decision to design it in the first place was a mistake for any reason other than a learning experience.
Maybe it was a mistake, but I just started with Microsoft's .NET, ASP.NET, and IIS and no more than that as a framework. Maybe that was not so good.
I had to find, download, read, abstract, and index 5000+ Web pages from MSDN -- a big delay and not so good.
For the session state store, I just thought that it was an obvious, easy, routine, normal, expected little bit of programming based on TCP/IP, serialization, and collection classes.
I'd heard of Redis but guessed that just reading the documentation enough to understand it and get it installed would be more work that what I did DIY. What I did was awfully easy.
Yes, you have some good 5 minute solutions, but I didn't have the background to have the knowledge, infrastructure, and code that offered the 5 minute solutions -- I didn't know such things existed. No such things were clear chasing around among and reading Web pages at MSDN.
Well, my session state store work is done well enough now for now and clearly easy enough for me to change to something else later if necessary.
I'm learning, which was the main objective of my first post here.
Thanks.