> We actually had a race condition here that allowed users to place multiple tiles at once. There was no locking around the steps 1-3 so simultaneous tile draw attempts could all pass the check at step 1 and then draw multiple tiles at step 2.
This is why you use a proper database.
I'd probably add a Postgres table to record all user activity, and use that to lock out users for 5 minutes as an initial filter. Have triggers on updates to then feed the rest of the application.
At reddit it's much easier for us to stand up a new Cassandra column family than a new postgres table (not saying this is how it should be, but just how it is).
All we needed to do here was add some simple locking and we would have been fine.
Your parent commenter seems to have no idea as to the true scale you planned for. Most of the criticism I've read here on HN and on Reddit threads regarding your implementation seems to have come from people who have never had to code something that has real-world scaling requirements. This wasn't some pet project initially launched to 100 concurrent users, with the ability to slowly and incrementally scale to millions of users over a period of weeks or months. You had one shot to get it right. A majority of those criticizing would have crashed their entire production stack upon deploying. Hundreds, possibly thousands, of queries per second returning one million rows each? Not going to happen, no matter which database backend you choose. The foresight you had to get it right the first time was well played on your part.
Ideally, you would have also used redis to limit the per-user activity without having to hit Cassandra. Also not sure why you hit Cassandra instead of redis for the single-pixel fetch endpoint (redis GETBIT operation rather than a database hit); if you already conceded to not-quite-atomic operations across the entire map, a GETBIT would have rarely returned a stale data point. But these are minor nice-to-have criticisms that would have pushed the scaling capabilities even further beyond your expected requirements. All in all, again I highly commend your results. You had one minor snafu, and managed to overcome it. Well done!
Aside: my brain is spinning as to how I would provide a 100% guaranteed atomic version of /r/place - without any point of failure such as a redis server not failing/restarting, or a single-server in-memory nodejs data structure. Really tough to do so without any point of failure or concession to atomicity. :)
Second aside: more than anything, I am surprised you have a CDN that allows 1-second expiries. While perfect for this kind of project, too many CDNs find a 1-second expiry as a risk to permit, as they tend to expect too much abuse/churn. ie: How is a CDN supposed to trust you enough to use a 1-second expiry for reasonably high traffic, rather than cycling so much caching effort for something that could have used a 5 minute expiration? I can't imagine being the developer of a CDN that trusts its users to use a 1-second expiry that wastes an insane number of CPU cycles for an origin that is not legitimately sustainable.
tldr (still long, but on point): You guys did an amazing job for something that lasted, what was it, 3 days? Great job! Many of your critical audience members would not have managed any better, let alone being viable and functional. I would submit my résumé to work for you, but I fear my personality is far too... um... abrasive... to get along with the organisation as a whole. In any case, your team as a cohesive unit - design, backend, and frontend (especially the mobile support) - did an incredible job. +1 to the Reddit team here, you should be immensely proud of yourselves for pulling this off.
We don't have a normal CDN, we have Fastly. They are really incredible at what they do, and this would not have been possible with our previous CDN partners.
So in that case, each pixel would be stored as a separate row in a relational database? And to query the whole canvas you'd query a million rows on every read?
I lean towards just using the ratelimiting stuff we already have in place (via memcached, which we talked about in a previous post). We just overlooked it.
I'd most likely have two tables - one for user activity and one for each pixel (1 million rows only in that table). Selecting a million rows from that pixel table might be 200ms or whatever. I'd still have Redis cache, though, since you're getting 100ms.
Consider exactly what you are proposing. One table to store the entire history (one billion or more rows). A second denormalized table, whether updated at the application layer or via triggers, to store the most recent update to each of the one million cells (1000x1000 pixel grid = one million data points).
The simple fact of introducing a one-million-row read for the latest data of each "pixel cell" is fairly insane. You must have a cache for such data. "I'd still have have Redis cache, though" is not even debatable. It doesn't have to be Redis, but is definitely has to be a cache of one kind or another.
So, I just did a SELECT * from a table with 1 million single-byte character rows, and it ran in 90.51ms:
place=> explain analyze select * from board_bitmap ;
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------
Seq Scan on board_bitmap (cost=0.00..14425.00 rows=1000000 width=6) (actual time=0.009..57.295 rows=1000000 loops=1)
Planning time: 0.160 ms
Execution time: 90.510 ms
(3 rows)
And, with triggers from an activity table, the entire write operation can be atomized so there aren't any race conditions.
I don't think you understand how fast Postgres is on modern hardware. What took a large cluster 5 years ago can be done on a single system with a fast NVMe drive today. We really might not even need Redis in this situation.
And, yes, I have to deal with viral content, so this is right up my alley.
Easily doable. On a 10$/month server I frequently run queries doing text operations over 120 million rows for fulltext search of an IRC client backlog.
In 64ms.
Without caching.
Using PHP.
It's definitely doable, but you'll need to heavily fine-tune your queries. My first one was at over 2 hours for the same.
> It's definitely doable, but you'll need to heavily fine-tune your queries
Misrepresentation; then it's not actually over 120 million rows. You're basically encoding which subset to actually search in the query, rather than building a proper overall schema that trivializes queries.
Or just use redis for everything :) One instance for the bitfield, one for atomic locks (done with a lua script) and one for tile data (with a few slaves for reads). Simple and independently scaleable.
Database choice aside, I'm shocked that this wasn't noticed when designing the app... It's clearly not a design decision because they refer to it as an error later in the paragraph.
With all due disrespect, you're wrong. Go ahead and implement your solution, and you will find it falls apart. So tired of people pretending to know better, without any data or real details to back it up. A "proper database" would not scale, regardless of whether it is Cassandra or Postgres.
You're completely ignoring, or completely oblivious of the fact, that the entire 1000x1000 grid must be provided to every connected client. You're not going to read out one million aggregated rows by most recent timestamp per cell, from a billion rows of history, in a scalable amount of time.
Please post your GitHub link that proves your solution as superior, or even viable. Make sure it includes database triggers, for which you don't explain how they would help scale the app whatsoever. Are you going to have a denormalized table containing each of the one million cells' most recent rows? All you are doing is eliminating a GROUP BY on the indexed cell+timestamp columns. It's still a million rows returned per query. Please explain how that scales. Eagerly awaiting your proven solution that defies common sense scaling logic.
It took a while for members of the community to realize what was happening and start recording snapshots of the canvas, so there are a few time periods early on that got skipped
This was such an amazing demonstration of human collective collaboration. It sort of makes me fee like humans could do anything, even tho the result is sort of in some sense trivial. As well as simply being enjoyed, this could be studied in so many ways. Competition of memes and cultural representations. 'Evolutionary' convergence upon some optimum. Mainstream vs Fringe. Accepted vs Taboo concepts. Implicit spontaneous emergence of behaviour norms for participants: self regulating systems. I also like this timelapse which contains an overview, and then a close up of each of 12 sections ( 333 x 250 ) - https://www.youtube.com/watch?v=RCAsY8kjE3w
> Users can place one tile every 5 minutes, so we must support an average update rate of 100,000 tiles per 5 minutes (333 updates/s).
It only takes a couple of outliers to bring everything down. I'm not exactly well-versed in defining specs for large scale backend apps (not a back-end engineer) but it seems to me that preparing for the average would not be a wise decision?
For example, designing with an average of a million requests per day in mind would probably fail, since you get most of that traffic during daytime and far more less at the nightly hours.
Is that hyperbole or are you really experiencing that much downtime of Reddit? I see it occasionally but it's never down for long, the odd "servers are busy" message usually disappears after a single refresh.
Pages take a long time to generate all day, but during peak hours they take a minimum of 4 seconds each (depends on what page you're loading, if it's got lots of comments, etc), and many times they simply timeout. The engineers at reddit have been unable thus far to fix it.
I'm not the same guy you were just talking to but in my experience on mobile Safari, I get "something went wrong, visit the homepage" when I navigate around reddit far too often. What's funny is it actually tends to resolve itself if I wait a second or two, but yeah, reddit engineering and infrastructure is not well equipped to handle the amount of traffic they receive. It's gotten better, but it's still not what you'd expect from the internet's front page.
The main website is OK as is i.reddit.com but their mobile client is hilariously bad in a "I can't believe they thought this was ready" way, it takes an age to load, it stalls out all the time, the tap targets are too small, it has the classic "oh you hit this when you meant that and then clicked that, lets spin the wheel on where you really end up" problem that slow mobile apps have.
I know they deal with insane scale yadayada but it's simply not ready.
That and the horrific dark pattern on the "We want you to have the best, massive red/orange button marked continue that takes you to the app store and the tiny weeny little "continue to mobile site" underneath".
I don't want your damn app, stop asking me.
If I was cynical I'd think they didn't care about the mobile site been awful as it drives people to the app.
I can't agree with you. The sheer fact that I know well what the reddit error page is refutes this. In fact it's one of the few sites I frequent that I know even have an error page.
It probably is regional, yes, because I simply can't believe every time I write a comment like this here or somewhere else I'm told reddit works fine. It gets on my nerves every single time I visit at night. (Western Europe)
I almost never have a problem on desktop, but using iOS safari (and the mobile reddit site), I often see the error page. I think it's a view/rendering issue, and ends up being displayed rather than a loading modal, but I could be wrong.
maybe three years ago it did, but reddit has gotten drastically more stable since then. It still has the occasional downtime, but now it's more like every couple months than every couple days.
>We should support at least 100,000 simultaneous users.
This line makes me think that this is what they expected the peak (or near peak) to be.
>Users can place one tile every 5 minutes, so we must support an average update rate of 100,000 tiles per 5 minutes (333 updates/s).
So assuming that they mean that 100k is the peak and that clients are limited to 1 update per 5 minutes, they can expect 333 updates per second on average. The "average" is taken over this 5 minute period. This average represents the number of queries per second they will get if everyone's 5 minute cooldown is spread out evenly over each 5 minute period.
It is possible, for example, for half of the peak population's cooldown to expire at 1300 and the other half to expire at 1305. In this case the average updates/s over the 5 minute period from 1300-1305 would still be 333 updates/s even though there were really 2 bursts of 50k a second at 1300 and 1305. It's far more likely that cooldowns are not excessively stacked in this way, so you prepare for the average and hope for the best.
They prepared for the worst (peak 100k users). The "hope" that those 100k would be spread out was based on the statistical likelihood that these 100k wouldn't line up too much over a 5 minute period.
I didn't follow /r/place that much, but I haven't read any complaints about latency or failures so it looks like they did just fine.
They say elsewhere that they were prepared for 100k updates all at once. Which is the worst.
Edit: you're an sre, you probably have more experience planning these things than I ever will. I just can't help but think about what would happen if some trolls realized they could synchronize their updates and bring down the service. (Although based on the infrastructure it doesn't seem possible to cause lasting damage.)
Yeah, I understand what you're saying. It is conceivable that a bunch of people would coordinate their updates. To prevent new-comers from spoiling the fun, they only allowed users with accounts created before /r/place was launched to send updates.
I can shed that 333 [something/s], for any uncomplicated something, is so little that a single-core 10YO laptop running a single-process non-blocking webserver (a-la node) could probably handle it, and likely x10 it.
Sure in a perfect scenario with a well behaving load test client. In production you often encounter scenarios which place unexpected load on your servers.
Ah yes, the self-inflicted unintentional DDoS attack that doesn't appear when you do a semi-idealized load test. I may or may not have been responsible for one of those once or twice in my life.
> It only takes a couple of outliers to bring everything down. I'm not exactly well-versed in defining specs for large scale backend apps (not a back-end engineer) but it seems to me that preparing for the average would not be a wise decision?
It's not an average: Reddit controlled the 5 minute user cool-down period, a.k.a. request throttling. 333 updates/s was the capacity. As alluded to in the article, the 5 minutes was dynamically configurable: if more than 100,000 had users showed up, they would have increased the cool-down period to a value that would yield 333 updates per second at most.
With 100K users and a minimum cooldown time of 5 minutes, there's 100K tiles per 5 minutes would be an upper limit. Only bots would hit that 5 minute cooldown every single time, and bots make up a very small minority of the users. They even point out later in the article that they only peaked at 200 updates per second.
> For example, designing with an average of a million requests per day in mind would probably fail, since you get most of that traffic during daytime and far more less at the nightly hours.
That depends. If you're talking about a public website, then yes. But this is just a single API endpoint with a very fixed time-based rate limit.
I thought it was interesting that one of their requirements was to provide an API that was easy to use for both bots and visualization tools. I remember reading some speculation when this was running that r/place was intentionally easy to interface with bots, while there were also complaints that the whole thing had been taken over by bots near the end.
Without bots, I doubt that /r/place would have been very interesting. It's a nice thought that a million random strangers can be cohesive without automation, but for some reason I don't find that to be particularly realistic..
As a concrete example, as far as I can tell the entire Puella Magi Madoka Magica section, starting from Homura Did Nothing Wrong next to Darth Plagueis The Wise, was hand-crafted and hand-maintained. On their discord they were actively discouraging community members that wanted to use bots.
I remember taking part in a big drawing canvas exactly like this about twelve years ago between several Art/Photoshop communities, Worth1000.com, SomethingAwful, Fark.com etc. There wasn't bots at the time but it was still very socially interesting.
r/Place is really awesome. This is how you grow the community. The 2D and 3D timelapses are super cool to watch, as well. Glad Reddit decided to make this a full-time thing.
Some redditors have created /r/place derivatives already. I'm not aware of one prior to /r/place but it seems impossible that it hasn't been done before
A long time ago, I built http://www.ipaidthemost.com/, which is kinda related, at least to TMDH anyhow. Far, far less collaborative than /r/place, but similar in terms of staking out ownership.
Not quite the same, but my startup, Formgraph[0], also does public, real-time collaborative drawing. I even did a similar write-up about the stack behind it the other day[1]. Looks like they're relying on Cassandra and Redis. I went with RethinkDB. Should probably do a write-up about the front end in the future.
Actually this idea has been around for years, and sadly isn't new at all. I just checked and there is one that's been around since at least 2006, http://da-archive.com/index.php?showtopic=42405
Right, true. Collaborative drawing was basically the "hello world" of real-time platforms back in the day (Firebase, Parse etc). But I think most of those were ephemeral canvases.
Yeah, collaborative drawing is kind of old hat, but when you can use the context of the modern, social web to provide some new modes of interaction around it, it can be interesting again. Same applies to more mundane things like text.
There were definitely a few that popped up after /r/place closed down. (pxls.space being the most popular) They were nowhere near as successful as /r/place though.
That was not realtime nor collaborative on a single pane. It was a "remix" platform where one user created the initial drawing, then people used it as a base and drew around/over it to change it - in a new picture.
So I got hit by an unfortunate bug on the first day of /r/place.
I was trying to draw something, one pixel at a time, and all of a sudden, after a bunch of pixels, it stopped rate-limiting me! I could place as many as I wanted! So I just figured that they periodically gave people short bursts where they can do anything. This was backed up by my boss, who was also playing with /r/place, saying that the same thing happened to him not long before that (yes, my whole team at work was preoccupied with /r/place that Friday). So I quickly rushed to finish my drawing.
And then I reloaded my browser... and it wasn't there. Turns out that what I thought was a short burst of no rate limiting was just my client totally desyncing from Reddit's servers. Nothing was submitted at all.
Not too long after that, another guy on my team got hit by the same bug. But I told him what happened with me, so he didn't get his hopes up.
It happened to me as well. I did verify that my changes actually made change (from the same IP, but in incognito mode). Didn't bother to check if the changes stayed.
That data was recorded by the community. It took everyone a while to figure out how to grab a snapshot of the canvas though, so a few hours of data near the start are missing.
Given the scale described, it sounds like they could have had a single machine that held the data in memory and periodically flushed to disk/DB to support failing over to a standby.
I would be slightly more careful and just use a cluster of servers with a simple consensus algorithm (like raft). A simple C++ server with a raft library plus uWebSockets should be able to handle a lot of load.
Did you even bother reading the first few paragraphs? They talked about their usage of Redis for this. Next time please read the article before replying.
It gets weird when the cursor leaves the box while dragging. Now, when you go back inside, you're still in drag mode since the box did not get the "mouse up" event and you end up selecting and dragging random text.
In the end this does not seem to have mattered. Reddit's hardcore "contributors" are the kind of people who enjoy a challenge, even when it's stupid. I think it even turned into some kind of pride for some of them, being able to "master" an idiotically programmed system.
Myself, I just get so frustrated about the idiocy.
> We used our websocket service to publish updates to all the clients.
I used /r/place from a few different browsers with a few different accounts, and they all seemed to have slightly different view of the same pixels. Was I the only one who experienced this problem?
When /r/place experiment was still going, I assumed that they grouped updates in some sort of batches, but now it seems like they intended all users to receive all updates more or less immediately.
I experienced this as well. I have a different account logged in on mobile than what is logged in on my desktop. I wouldn't say things were drastically different, but when there was a location with a ton of activity (like OSU or the American flag towards the end), I saw different views between them.
Yeah, we went into it a bit in the "What We Learned" section, but that was most likely during the time we were having issues with RabbitMQ. I believe it was mostly fixed later on, but either way, we found a new pain point in our system we can now work on.
Surprised you're using RabbitMQ. It's one of those things which work great until they don't (clustering is particularly bad), and then you have almost zero insight into the issue, and have to resort to the Pivotal mailing list.
Have you looked at NATS at all? We're using it as a message bus for one app and it's been fantastic. It is, however, an in-memory queue, and the current version cannot replace Rabbit for queues that require durability.
i've been using rabbitmq heavily (as in, the whole infrastructure is based on two rabbitmq servers) for a long time and i've never seen it fail.
tbh, i never used clustering (because it's one of the shittiest clustering implementations i've ever seen) but we do use two servers (publishers connect to one randomly and consumers connect to both) and it seems to handle millions of messages without any issues.
of all servers i've ever used, rabbitmq is by far the most stable (together with ejabberd).
RabbitMQ is decent if you don't use clustering (which, I agree, is shitty). I have some quibbles with the non-clustered parts, but nothing big.
Right now, the main annoyance is that it's impossible, as far as I understand, to limit its memory usage. You can set a "VM high watermark" and some other things, but beyond that, it will — much like, say, Elasticsearch — use a large amount of mysterious memory that you have no control over. You can't just say "use 1GB and nothing more", which is problematic on Kubernetes where you want to pack things a bit tightly. This happens even if all the queues are marked as durable.
yeah we have dedicated machines to rabbitmq because it's basically memory hungry. but i like it that way because it's only going to crash if the machine crashes.
Note that NATS is currently pub/sub, which is a "if a tree falls in the forest" situation. Messages don't go anywhere if nobody is subscribing.
So it's awesome for realtime firehose-type use cases where a websocket client connects, receives messages (every client gets all the messages, although NATS also supports load-balanced fanout) for a while, then eventually disconnects.
NATS is ridiculously fast [1], too.
There's an add-on currently in beta, NATS Streaming [1], which [2] has durability, acking/redelivery and replay, so covers most of what you get from both RabbitMQ and Kafka. It looks very promising.
What a fantastic writeup. I had some vague ideas regarding the challenges involved to build an application of such scale, but the article really makes it clear for everyone the amount of decision points encountered as well as why certain solutions were selected.
I also like the way the article is broken down into the backend, API, frontend and mobile. This isolated approach really highlights the different struggles each aspects of the product has, while dealing with what is essentially a shared concern: performance.
What I also found interesting is the fact that they were able to come up with a pretty accurate guess in terms of the expected traffic.
> "We experienced a maximum tile placement rate of almost 200/s. This was below our calculated maximum rate of 333/s (average of 100,000 users placing a tile every 5 minutes)."
Their guess ended up being a good amount above the actual maximum usage, but it was probably padded against the worst case scenario. The company that I work for consistently fails to come up with accurate guesses even with our very rigid user base, so it's pretty impressive that Reddit could accommodate the unpredictable user base that is the entire Reddit community.
I really like the "Big Data in Real-Time at Twitter" slides at https://www.slideshare.net/nkallen/q-con-3770885. They explain their original implementation and why it didn't scale, possible new implementations and their current one (it's a bit old though). It's clear and easy to understand.
Documentation always takes me as long or longer than designing, coding.
Most recently, when I released a novel layout manager, the docs, examples, screenshots, etc took roughly twice as much effort as everything else combined.
Why use Redis and multiple machines instead of keeping it in RAM on a single machine? I'm not claiming the Reddit people did anything wrong; they have a lot more experience than me here obviously. I'm just trying to figure out why they couldn't do something simpler. 333 updates/sec to a 500kB packed array, coupled with cooldown logic, should have a negligible performance cost and can easily be done on a single thread. That thread could interact via atomic channels with the CDN (make a copy of the array 33 times a second and send it away, no problem) and websockets (send updates out via a broadcast channel, other cores re-broadcast to the 100K websockets). Again, I'm not saying this is actually a better idea, this is just what I would do naively and I'm curious where it would fall apart.
I agree that machines go down, but there are sane (and safe!) ways to build this sort of thing without adding in cassandra and Redis. Additionally, the max placement rate of 333/s is reaaaaally slow! Maybe that's due to the websocket frontends, not the DB, but, that doesn't mean that's the most obvious way to build it.
The crux of the problem is that they need to mutate a relatively tiny amount of memory and have a rolling log of events for which only the last 5 minutes needs fast access. Also, if you can put all your state on one machine its far less likely that the one machine will die, than it is that at least one will die in a cluster of machines. Given the nature of the problem keeping all state on one machine seems pretty rational to me, so long as you have the ability to switch to a hot spare within a few minutes or so.
If I were to architect this for speed I would have two tiers: a websocket tier, and secondly a 'database' tier. The database would be a custom program that would:
0. Provide a simple Websocket API that would receive a write request and return either success if the user's write timer allowed it to write or failure if it didn't. This would also broadcast the state + deltas.
1. Keep the image in memory as a bitmap
2. Use rocksdb for tracking last user writes to enforce the 5m constraint. You could use an in memory map, but the nice thing about rocksdb is that it shouldn't blow up your heap.
3. Periodically flush the bitmap out to disk to timestamped files for snapshots
4. Keep the hashmap size small by evicting any keys past their time limit
5. Write rotating log files rotated every 5m or so to record the history of events for DR and also later analysis
Backing this sort of thing up is very simple. You just replicate the files using rsync or something like it. You may have some corruption on files that are partially written, but since we're opening and closing new files often you can choose how much data-loss you want to tolerate.
Restoration is as simple as re-reading the bitmap and reading the log files in reverse up to 5 minutes ago to see who still isn't allowed to write yet (thus reconstituting the hashmap). Let's remember, redis replication is async, so this has the same tradeoffs.
> The database would be a custom program that would:
Creating a "custom database program" is not a small task.
We like to use boring technologies that we know work well. We were already using Cassandra, had some experience with Redis, and had a lot of confidence in our CDN.
Well, in your article you mentioned that you tried to use Cassandra for one task and had to jettison it because of unexpected performance problems. You had to re-approach the problem with a whole other DB. I would say contradicts the point you're making.
I'm not arguing that most problems need a custom database, only a minority do. I'd say that this problem is borderline on which direction to go.
Databases are very leaky abstractions as you all discovered. The nice thing about custom code is that you don't have leaky abstractions. The bad thing about custom code is that you have a large new untested surface area.
In the case of your application the requirements are so minimal, a bitfield plus a log, I'd say its a wash.
Programmers today forget that things like flat files exist and are useful. It's a shame, because you wind up with situations where people just assume they need a giant distributed datastore for everything.
What you're doing in that case is trading architectural complexity for code complexity. Now, if its the case that all data in your org goes in one data store to keep things consistent, great, that makes sense. But for a one off app I just don't buy it.
> 500kB packed array, coupled with cooldown logic, should have a negligible performance cost and can easily be done on a single thread. That thread could interact via atomic channels with the CDN
That's not simpler.
We used tools that we're already using heavily in production and are comfortable with.
With respect to your experience in the matter, I strongly disagree. What I described is complicated to say, easy to implement. What the OP describes ("use redis") is easy to say, complicated to implement. Not just in terms of human work time (setting up the redis machine and instance, connecting everything together), but also in terms of number of moving parts (more machines, more programs, etc.).
> We used tools that we're already using heavily in production and are comfortable with.
That's entirely fair, and what I figured was the most likely explanation.
And there's only half a meg of data! Serving the readers is a much more interesting problem than managing the writes, and tbh I'd just keep a rolling "pixels that have changed in the last 10 seconds" diff going, pushed out every 100ms, compressed and cached, and have clients poll for it. Easy peasy, websockets just complicate life.
Our initial approach was to store the full board in a single row in Cassandra and each request for the full board would read that entire row.
This is the epitome of an anti-pattern .I sincerely hope that this approach was floated by somebody who had never used Cassandra before.
Even if individual requests were reasonably fast, you are sticking all of your data in a single partition, creating the hottest of hot spots and failing to leverage the scale out nature of your database.
This entire project is just an elaborate hack day project. There's no reason to fault them for trying new and interesting hacks to get it off the ground. They realized it wasn't the right method and moved on. End of story.
This year? I'm thinking more like this decade. It's gotta be up in the top 10 of ever. On so many levels, /r/place was fascinating; and I didn't even come across it until after it had finished!
This is awesome but man, reading the canvas portion was a bit distressing. I wonder why they didn't use a game engine to do this? All the work they did has been implemented already in several JS game engines, such as the one I help maintain (it's free and OSS), https://excaliburjs.com. We support all the features they needed including mobile & touch support. They could have also used Phaser (http://phaser.io) too I bet... that has WebGL support for even faster rendering on supported devices.
...it's not like you have write assembly to get it done, the native canvas API is fairly straightforward. A game engine is a bit of an overkill if all you want to do is place pixels on a canvas.
But they wanted a lot more than that. Engines like Phaser work hard to take care of browser quirks for things like PointerEvents vs. TouchEvents vs. MouseEvents or supporting mobile devices. Sure, it seems simple at first until you run into those kinds of problems and reinvent the wheel... learning an engine isn't terribly complicated but I understand the sentiment for a one-time project. It just seems like they did so much other planning but didn't want to plan the UI implementation to the same degree?
Like you said, it was a one-time project that wasn't incredibly complex and just needed a one time deployment. And they had UI guys who generally knew what they wanted to and how to do it. I think it would probably have taken them more time to research suitable engines they could rely on than to build the functionality themselves (or use whatever libraries they were already very familiar with.) All engines/libraries end up having quirks that you really only learn through experience.
Also they were kind of time constrained. WebGL would have been definitely more performant but it has all sorts of hardware issues at times in different devices. I've done plenty of WebGL over the years and seen random GPU crashes where you have to restart the entire machine to unlock your self out.
The canvas trick with typed arrays is brilliant. Using requestAnimationFrame is what any front end dev who knows perf would do. Its like the front end version of cdn with 1 second time out trick.
Also using a layer of library whose code you don't understand in a perf critical application is quite risky. Its better to stick closer to the native browser APIs which you are familiar with. We once had to throw away a library and rewrite code from scratch because their assumptions failed when pushed to the limits. The rewritten code was 100x smaller in size and 10x more performant.
I would have loved to work on something like this but it sucks reddit doesn't have any presence in Seattle.
What is the learning curve on a game engine for not game engine developers?
They used tools they knew and knew how to scale. Almost always the tool you know is better than the perfect tool. They know redis and websockets, and they made it work. Beats using some engine know one on staff has ever touched?
I guess it depends on the engine, or maybe that was a rhetorical question. It doesn't take a month, or even a week, though--maybe to master them but not to learn the API. We've worked hard on our little project to design our engine for non-game developers or veterans, it's only a few lines of code to move a square, or draw an image, for example. But I understand the sentiment, especially for a one-time project.
I don't know, they had several well defined constraints and you don't know what a library is doing under the covers without spending some time with it. A proof of concept engine exploration is different than an app with 100,000 simultaneous users. I wonder how many business days they spent on this thing.
Hi, I wrote the majority of that part of the project (canvas stuff) & that section of the article – the simple answer is that I have a lot of experience working with the canvas API directly, but little to no experience using any of the popular JS game engines out there (I played around with Phaser years ago, but not very much). I don't think it would've saved me any time to be honest.
This is amazing and I got so many ideas on how to tackle the scaling issues I have with my own multiplayer drawing website. In the aftermath of r/Place I went into some of the factions' Discord servers and posted my site, getting 50-100 concurrent users which caused a meltdown on my server. It was a good stress test but also a wake-up call.
254 comments
[ 4.5 ms ] story [ 251 ms ] threadThis is why you use a proper database.
I'd probably add a Postgres table to record all user activity, and use that to lock out users for 5 minutes as an initial filter. Have triggers on updates to then feed the rest of the application.
Like people decide to use them from the get-go and then come up with a justification.
All we needed to do here was add some simple locking and we would have been fine.
Ideally, you would have also used redis to limit the per-user activity without having to hit Cassandra. Also not sure why you hit Cassandra instead of redis for the single-pixel fetch endpoint (redis GETBIT operation rather than a database hit); if you already conceded to not-quite-atomic operations across the entire map, a GETBIT would have rarely returned a stale data point. But these are minor nice-to-have criticisms that would have pushed the scaling capabilities even further beyond your expected requirements. All in all, again I highly commend your results. You had one minor snafu, and managed to overcome it. Well done!
Aside: my brain is spinning as to how I would provide a 100% guaranteed atomic version of /r/place - without any point of failure such as a redis server not failing/restarting, or a single-server in-memory nodejs data structure. Really tough to do so without any point of failure or concession to atomicity. :)
Second aside: more than anything, I am surprised you have a CDN that allows 1-second expiries. While perfect for this kind of project, too many CDNs find a 1-second expiry as a risk to permit, as they tend to expect too much abuse/churn. ie: How is a CDN supposed to trust you enough to use a 1-second expiry for reasonably high traffic, rather than cycling so much caching effort for something that could have used a 5 minute expiration? I can't imagine being the developer of a CDN that trusts its users to use a 1-second expiry that wastes an insane number of CPU cycles for an origin that is not legitimately sustainable.
tldr (still long, but on point): You guys did an amazing job for something that lasted, what was it, 3 days? Great job! Many of your critical audience members would not have managed any better, let alone being viable and functional. I would submit my résumé to work for you, but I fear my personality is far too... um... abrasive... to get along with the organisation as a whole. In any case, your team as a cohesive unit - design, backend, and frontend (especially the mobile support) - did an incredible job. +1 to the Reddit team here, you should be immensely proud of yourselves for pulling this off.
We don't have a normal CDN, we have Fastly. They are really incredible at what they do, and this would not have been possible with our previous CDN partners.
I lean towards just using the ratelimiting stuff we already have in place (via memcached, which we talked about in a previous post). We just overlooked it.
No, just using it to store the update log.
But I don't know if there's any obvious problem with querying a handful of megabytes once per second either.
The simple fact of introducing a one-million-row read for the latest data of each "pixel cell" is fairly insane. You must have a cache for such data. "I'd still have have Redis cache, though" is not even debatable. It doesn't have to be Redis, but is definitely has to be a cache of one kind or another.
I don't think you understand how fast Postgres is on modern hardware. What took a large cluster 5 years ago can be done on a single system with a fast NVMe drive today. We really might not even need Redis in this situation.
And, yes, I have to deal with viral content, so this is right up my alley.
I will say that it was an implementation bug which doesn't warrant the swapping out of entire data storage layers.
In 64ms.
Without caching.
Using PHP.
It's definitely doable, but you'll need to heavily fine-tune your queries. My first one was at over 2 hours for the same.
Misrepresentation; then it's not actually over 120 million rows. You're basically encoding which subset to actually search in the query, rather than building a proper overall schema that trivializes queries.
I mean stuff like using aggregation functions to let the database build a bitset out of them, and reading from every row a value into that bitset.
I mean stuff like CLUSTER table ON (pixel_y_index, pixel, x_index) to change the order in which they are stored.
Do those two optimizations alone and you improve speed massively.
You're completely ignoring, or completely oblivious of the fact, that the entire 1000x1000 grid must be provided to every connected client. You're not going to read out one million aggregated rows by most recent timestamp per cell, from a billion rows of history, in a scalable amount of time.
Please post your GitHub link that proves your solution as superior, or even viable. Make sure it includes database triggers, for which you don't explain how they would help scale the app whatsoever. Are you going to have a denormalized table containing each of the one million cells' most recent rows? All you are doing is eliminating a GROUP BY on the indexed cell+timestamp columns. It's still a million rows returned per query. Please explain how that scales. Eagerly awaiting your proven solution that defies common sense scaling logic.
https://www.reddit.com/place?webview=true
I've exported it to imgur for you.
And for those interested, here's some additional stats:
- The original announcement about /r/place: https://www.reddit.com/r/announcements/comments/62mesr/place...
- Full timelapse of the canvas over the course all 72 hours: https://www.youtube.com/watch?v=XnRCZK3KjUY
- Heatmap of all activity on the canvas over the full 72 hours: https://i.redd.it/20mghgkfwppy.png by /u/mustafaihssan
- Timelapse heatmap of activity on the canvas: https://i.imgur.com/a95XXDz.gifv by /u/jampekka
- Entropy map of the canvas over the full 72 hours: https://i.imgur.com/NnjFoHt.jpg by /u/howaboot (explanation: https://www.reddit.com/r/dataisbeautiful/comments/63kuy6/oc_...)
- Map of all white pixels that were never touched throughout the event: https://i.imgur.com/SEHaUSJ.png by /u/alternateme
- Most common color of each pixel over the last...
- Average color of each pixel over the course of the experiment: https://i.imgur.com/IkPOwIh.png- Atlas of the Final Image: https://draemm.li/various/place-atlas/ by /r/placeAtlas/ (source code: https://github.com/RolandR/place-atlas)
- Torrents of various canvas snapshots and image data: https://www.reddit.com/r/place/comments/6396u5/rplace_archiv...
- The post announcing the end of /r/place: https://www.reddit.com/r/place/comments/6382bb/place_has_end...
It took a while for members of the community to realize what was happening and start recording snapshots of the canvas, so there are a few time periods early on that got skipped
It only takes a couple of outliers to bring everything down. I'm not exactly well-versed in defining specs for large scale backend apps (not a back-end engineer) but it seems to me that preparing for the average would not be a wise decision?
For example, designing with an average of a million requests per day in mind would probably fail, since you get most of that traffic during daytime and far more less at the nightly hours.
Could anyone more experienced shed some light?
I know they deal with insane scale yadayada but it's simply not ready.
That and the horrific dark pattern on the "We want you to have the best, massive red/orange button marked continue that takes you to the app store and the tiny weeny little "continue to mobile site" underneath".
I don't want your damn app, stop asking me.
If I was cynical I'd think they didn't care about the mobile site been awful as it drives people to the app.
>We should support at least 100,000 simultaneous users.
This line makes me think that this is what they expected the peak (or near peak) to be.
>Users can place one tile every 5 minutes, so we must support an average update rate of 100,000 tiles per 5 minutes (333 updates/s).
So assuming that they mean that 100k is the peak and that clients are limited to 1 update per 5 minutes, they can expect 333 updates per second on average. The "average" is taken over this 5 minute period. This average represents the number of queries per second they will get if everyone's 5 minute cooldown is spread out evenly over each 5 minute period.
It is possible, for example, for half of the peak population's cooldown to expire at 1300 and the other half to expire at 1305. In this case the average updates/s over the 5 minute period from 1300-1305 would still be 333 updates/s even though there were really 2 bursts of 50k a second at 1300 and 1305. It's far more likely that cooldowns are not excessively stacked in this way, so you prepare for the average and hope for the best.
I didn't follow /r/place that much, but I haven't read any complaints about latency or failures so it looks like they did just fine.
Edit: you're an sre, you probably have more experience planning these things than I ever will. I just can't help but think about what would happen if some trolls realized they could synchronize their updates and bring down the service. (Although based on the infrastructure it doesn't seem possible to cause lasting damage.)
It's not an average: Reddit controlled the 5 minute user cool-down period, a.k.a. request throttling. 333 updates/s was the capacity. As alluded to in the article, the 5 minutes was dynamically configurable: if more than 100,000 had users showed up, they would have increased the cool-down period to a value that would yield 333 updates per second at most.
> For example, designing with an average of a million requests per day in mind would probably fail, since you get most of that traffic during daytime and far more less at the nightly hours.
That depends. If you're talking about a public website, then yes. But this is just a single API endpoint with a very fixed time-based rate limit.
And soon you get exactly what /r/place was.
As others have said subcommunities quickly formed or some subreddits themselves had a orga-thread to paint an iconic logo relevant to their niche.
[0] - https://github.com/reddit/reddit-plugin-place-opensource/com...
From a reddit "expert", so I guess that answers that ;)
Also, reminds be of the million dollar front page [1].
[1] https://en.wikipedia.org/wiki/The_Million_Dollar_Homepage
If it reached 5$, he'd have made 25,000$
>>> total = 0
>>> for i in range(5, 500, 5):
... total += i
>>> total
24750
[0] https://www.formgraph.com
[1] https://medium.com/@JohnWatson/real-time-collaboration-with-...
I remember lueshi
It was quite interesting for a little while.
I was trying to draw something, one pixel at a time, and all of a sudden, after a bunch of pixels, it stopped rate-limiting me! I could place as many as I wanted! So I just figured that they periodically gave people short bursts where they can do anything. This was backed up by my boss, who was also playing with /r/place, saying that the same thing happened to him not long before that (yes, my whole team at work was preoccupied with /r/place that Friday). So I quickly rushed to finish my drawing.
And then I reloaded my browser... and it wasn't there. Turns out that what I thought was a short burst of no rate limiting was just my client totally desyncing from Reddit's servers. Nothing was submitted at all.
Not too long after that, another guy on my team got hit by the same bug. But I told him what happened with me, so he didn't get his hopes up.
Like
timestamp, x, y, color, username
Please explain.
https://www.reddit.com/r/place/comments/6396u5/rplace_archiv...
Complete?
I've been working with that.
Myself, I just get so frustrated about the idiocy.
It's still there: https://www.reddit.com/r/place/
They have may have fixed one or two scrolling issues since, but the main issue is that if you
a) press LMB
b) move the mouse, and move outside of the pixelized area
c) release LMB
.. it does weird things.
How big was the team? How long did it take to complete this project? Is the code going to be open sourced?
I used /r/place from a few different browsers with a few different accounts, and they all seemed to have slightly different view of the same pixels. Was I the only one who experienced this problem?
When /r/place experiment was still going, I assumed that they grouped updates in some sort of batches, but now it seems like they intended all users to receive all updates more or less immediately.
BTW, thanks for the great post, it was a very interesting read.
Have you looked at NATS at all? We're using it as a message bus for one app and it's been fantastic. It is, however, an in-memory queue, and the current version cannot replace Rabbit for queues that require durability.
tbh, i never used clustering (because it's one of the shittiest clustering implementations i've ever seen) but we do use two servers (publishers connect to one randomly and consumers connect to both) and it seems to handle millions of messages without any issues.
of all servers i've ever used, rabbitmq is by far the most stable (together with ejabberd).
Right now, the main annoyance is that it's impossible, as far as I understand, to limit its memory usage. You can set a "VM high watermark" and some other things, but beyond that, it will — much like, say, Elasticsearch — use a large amount of mysterious memory that you have no control over. You can't just say "use 1GB and nothing more", which is problematic on Kubernetes where you want to pack things a bit tightly. This happens even if all the queues are marked as durable.
So it's awesome for realtime firehose-type use cases where a websocket client connects, receives messages (every client gets all the messages, although NATS also supports load-balanced fanout) for a while, then eventually disconnects.
NATS is ridiculously fast [1], too.
There's an add-on currently in beta, NATS Streaming [1], which [2] has durability, acking/redelivery and replay, so covers most of what you get from both RabbitMQ and Kafka. It looks very promising.
[1] http://bravenewgeek.com/tag/nats/
[2] https://nats.io/documentation/streaming/nats-streaming-intro...
You're already on AWS, why not use SQS instead?
If you already have a good Redis infrastructure then you can just use the pub/sub features built into it for your websockets communication.
https://news.ycombinator.com/item?id=14110094
I also like the way the article is broken down into the backend, API, frontend and mobile. This isolated approach really highlights the different struggles each aspects of the product has, while dealing with what is essentially a shared concern: performance.
What I also found interesting is the fact that they were able to come up with a pretty accurate guess in terms of the expected traffic.
> "We experienced a maximum tile placement rate of almost 200/s. This was below our calculated maximum rate of 333/s (average of 100,000 users placing a tile every 5 minutes)."
Their guess ended up being a good amount above the actual maximum usage, but it was probably padded against the worst case scenario. The company that I work for consistently fails to come up with accurate guesses even with our very rigid user base, so it's pretty impressive that Reddit could accommodate the unpredictable user base that is the entire Reddit community.
http://highscalability.com/blog/2016/4/20/how-twitter-handle...
https://redditblog.com/2017/1/17/caching-at-reddit/
https://blog.twitter.com/2017/the-infrastructure-behind-twit...
https://www.netlify.com/blog/2017/03/16/smashing-magazine-ju...
https://nickcraver.com/blog/2016/02/03/stack-overflow-a-tech...
https://engineering.linkedin.com/blog/2016/10/instant-messag...
http://techblog.netflix.com/2016/08/building-fastcom.html
http://highscalability.com/blog/2016/9/28/how-uber-manages-a...
Or a recent writeup on a challenge building IMDB's forums in 2001(!) https://www.beatworm.co.uk/blog/internet/imdb-boards-no-more .. fun and scary in equal measures.
(I'm plucking these from things were popular recently in our http://webopsweekly.com/ :-))
Edit: why am I getting down voted for praising a write-up?
I've done a fair amount of tech writing.
Documentation always takes me as long or longer than designing, coding.
Most recently, when I released a novel layout manager, the docs, examples, screenshots, etc took roughly twice as much effort as everything else combined.
Because machines go down. If you don't expect your hardware to fail at the most inopportune time, you'll be screwed when (not if) it happens.
The crux of the problem is that they need to mutate a relatively tiny amount of memory and have a rolling log of events for which only the last 5 minutes needs fast access. Also, if you can put all your state on one machine its far less likely that the one machine will die, than it is that at least one will die in a cluster of machines. Given the nature of the problem keeping all state on one machine seems pretty rational to me, so long as you have the ability to switch to a hot spare within a few minutes or so.
If I were to architect this for speed I would have two tiers: a websocket tier, and secondly a 'database' tier. The database would be a custom program that would:
0. Provide a simple Websocket API that would receive a write request and return either success if the user's write timer allowed it to write or failure if it didn't. This would also broadcast the state + deltas. 1. Keep the image in memory as a bitmap 2. Use rocksdb for tracking last user writes to enforce the 5m constraint. You could use an in memory map, but the nice thing about rocksdb is that it shouldn't blow up your heap. 3. Periodically flush the bitmap out to disk to timestamped files for snapshots 4. Keep the hashmap size small by evicting any keys past their time limit 5. Write rotating log files rotated every 5m or so to record the history of events for DR and also later analysis
Backing this sort of thing up is very simple. You just replicate the files using rsync or something like it. You may have some corruption on files that are partially written, but since we're opening and closing new files often you can choose how much data-loss you want to tolerate.
Restoration is as simple as re-reading the bitmap and reading the log files in reverse up to 5 minutes ago to see who still isn't allowed to write yet (thus reconstituting the hashmap). Let's remember, redis replication is async, so this has the same tradeoffs.
Creating a "custom database program" is not a small task.
We like to use boring technologies that we know work well. We were already using Cassandra, had some experience with Redis, and had a lot of confidence in our CDN.
I'm not arguing that most problems need a custom database, only a minority do. I'd say that this problem is borderline on which direction to go.
Databases are very leaky abstractions as you all discovered. The nice thing about custom code is that you don't have leaky abstractions. The bad thing about custom code is that you have a large new untested surface area.
In the case of your application the requirements are so minimal, a bitfield plus a log, I'd say its a wash.
Programmers today forget that things like flat files exist and are useful. It's a shame, because you wind up with situations where people just assume they need a giant distributed datastore for everything.
What you're doing in that case is trading architectural complexity for code complexity. Now, if its the case that all data in your org goes in one data store to keep things consistent, great, that makes sense. But for a one off app I just don't buy it.
> 500kB packed array, coupled with cooldown logic, should have a negligible performance cost and can easily be done on a single thread. That thread could interact via atomic channels with the CDN
That's not simpler.
We used tools that we're already using heavily in production and are comfortable with.
With respect to your experience in the matter, I strongly disagree. What I described is complicated to say, easy to implement. What the OP describes ("use redis") is easy to say, complicated to implement. Not just in terms of human work time (setting up the redis machine and instance, connecting everything together), but also in terms of number of moving parts (more machines, more programs, etc.).
> We used tools that we're already using heavily in production and are comfortable with.
That's entirely fair, and what I figured was the most likely explanation.
This is the epitome of an anti-pattern .I sincerely hope that this approach was floated by somebody who had never used Cassandra before.
Even if individual requests were reasonably fast, you are sticking all of your data in a single partition, creating the hottest of hot spots and failing to leverage the scale out nature of your database.
The canvas trick with typed arrays is brilliant. Using requestAnimationFrame is what any front end dev who knows perf would do. Its like the front end version of cdn with 1 second time out trick.
Also using a layer of library whose code you don't understand in a perf critical application is quite risky. Its better to stick closer to the native browser APIs which you are familiar with. We once had to throw away a library and rewrite code from scratch because their assumptions failed when pushed to the limits. The rewritten code was 100x smaller in size and 10x more performant.
I would have loved to work on something like this but it sucks reddit doesn't have any presence in Seattle.
They used tools they knew and knew how to scale. Almost always the tool you know is better than the perfect tool. They know redis and websockets, and they made it work. Beats using some engine know one on staff has ever touched?
Again, amazing write-up. Thank you!