45 ms·

How We Built r/Place

1152 points by dkasper 9y ago

mozumder 9y ago
> 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.
- 77pt77 9y ago
  These no-SQL solutions seem shoehorned many times. Like people decide to use them from the get-go and then come up with a justification.
  - gooeyblob 9y ago
    We've been using Cassandra for 7 years since 0.7.
- bsimpson63 9y ago
  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.
  - fidget 9y ago
    Are you suggesting that you had a concurrency bug that was solvable without changing your entire storage layer? Heresy..
  - developer2 9y ago
    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.
- d23 9y ago
  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.
  - Dylan16807 9y ago
    > And to query the whole canvas you'd query a million rows on every read? 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.
  - mozumder 9y ago
    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.
    - developer2 9y ago
      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.
      - mozumder 9y ago
        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.
- hashhar 9y ago
  And what about adding a million rows to the RDBMS and querying it in under 100ms (which Redis allowed them to do). I will say that it was an implementation bug which doesn't warrant the swapping out of entire data storage layers.
  - kuschku 9y ago
    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.
    - nebabyte 9y ago
      > 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.
      - kuschku 9y ago
        No. 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.
- Thaxll 9y ago
  Well PostgreSQL is a single master for writes so it doesn't scale well to say the least.
  - mozumder 9y ago
    333 writes per second really is nothing in a world with modern NVMe drives.
- jdmichal 9y ago
  Or use bog-standard token bucket rate limiting algorithms with atomic decrement-and-get operations.
- corford 9y ago
  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.
- thinkmoore 9y ago
  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.
- developer2 9y ago
  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.
- Can_Not 9y ago
  Don't even need postgre, Lua scripts are transaction safe on redis clusters.
huangc10 9y ago
Can someone link to the full resolution final image? Been trying to find it. Thanks!
- noxToken 9y ago
  If you ever want to revisit, it's linked in the right side of the sub. https://www.reddit.com/place?webview=true https://www.reddit.com/place?webview=true
  - huangc10 9y ago
    For some reason it leads to 403...weird
    - dan1234 9y ago
      http://i.imgur.com/dYdHDYe.png http://i.imgur.com/dYdHDYe.png I've exported it to imgur for you.
- deleted 9y ago
  [deleted]
- LeoPanthera 9y ago
  This is the final bitmap. http://i.imgur.com/ajWiAYi.png http://i.imgur.com/ajWiAYi.png
- Ajedi32 9y ago
  Here you go: https://i.imgur.com/ajWiAYi.png https://i.imgur.com/ajWiAYi.png. And for those interested, here's some additional stats: - The original announcement about /r/place: https://www.reddit.com/r/announcements/comments/62mesr/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 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 https://i.redd.it/20mghgkfwppy.png by /u/mustafaihssan - Timelapse heatmap of activity on the canvas: https://i.imgur.com/a95XXDz.gifv 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 https://i.imgur.com/NnjFoHt.jpg by /u/howaboot (explanation: https://www.reddit.com/r/dataisbeautiful/comments/63kuy6/oc_heatmap_of_the_most_pixels_changes_happend_on/dfv3n83/ 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 https://i.imgur.com/SEHaUSJ.png by /u/alternateme - Most common color of each pixel over the last... - 72 hours**: https://i.imgur.com/C5jOtl1.png by /u/howaboot - 24 Hours: http://aperiodic.net/phil/tmp/place-mode-24h.png by /u/phil_g - 12 Hours: http://aperiodic.net/phil/tmp/place-mode-12h.png by /u/phil_g - 6 Hours: http://aperiodic.net/phil/tmp/place-mode-6h.png by /u/phil_g - 2 Hours: http://aperiodic.net/phil/tmp/place-mode-2h.png by /u/phil_g - Average color of each pixel over the course of the experiment: https://i.imgur.com/IkPOwIh.png https://i.imgur.com/IkPOwIh.png - Atlas of the Final Image: https://draemm.li/various/place-atlas/ https://draemm.li/various/place-atlas/ by /r/placeAtlas/ (source code: https://github.com/RolandR/place-atlas https://github.com/RolandR/place-atlas) - Torrents of various canvas snapshots and image data: https://www.reddit.com/r/place/comments/6396u5/rplace_archive_update/** 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_ended/ 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
vmasto 9y ago
> 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. Could anyone more experienced shed some light?
- deleted 9y ago
  [deleted]
- andoon 9y ago
  The entire reddit website goes down every night, especially during weekends, sport matches, etc, so there you have your answer.
  - celticninja 9y ago
    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.
    - andoon 9y ago
      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.
      - rhizome 9y ago
        This isn't my experience.
writeslowly 9y ago
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.
- gramstrong 9y ago
  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..
  - kuschku 9y ago
    Oh it is very easy. You just need subreddits with lots of very loyal people who even do frequent meetups, and lots of those subreddits. And soon you get exactly what /r/place was.
  - saulrh 9y ago
    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.
  - jobigoud 9y ago
    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.
  - ralfd 9y ago
    But reddit itself is a tool to bring cohesion out of a million random strangers. As others have said subcommunities quickly formed or some subreddits themselves had a orga-thread to paint an iconic logo relevant to their niche.
archagon 9y ago
Thank you for the fascinating writeup! How long did the whole thing take to put together?
- tyrust 9y ago
  First commit was on Jan 20 [0], so that provides a lower-bound for how long they spent on it. [0] - https://github.com/reddit/reddit-plugin-place-opensource/commit/68498bab9300f43ae4273dd4719dcecb081126f7 https://github.com/reddit/reddit-plugin-place-opensource/com...
- maaaats 9y ago
  > seems to be pretty simple, I feel like it shouldn't take more than a day to code From a reddit "expert", so I guess that answers that ;)
maaaats 9y ago
Interesting how big the Norwegian and Swedish flags got, given our small populations.
- 77pt77 9y ago
  Very easy flags to maintain and extend from a smaller model.
- stevekemp 9y ago
  I thought the exact same thing, about the Finnish flag - complete with Moomins.
  - pimeys 9y ago
    And the almost a dictator of a president Urho Kekkonen. I kind of understand this, I was born in that country...
  - nerfhammer 9y ago
    I also notice some kind of Finland-Brazil-Argentina alliance
- kzrdude 9y ago
  Populations are not so small in reddit terms. Sweden probably has an equal population to Italy or even more, on reddit.
pitaj 9y ago
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.
- kzrdude 9y ago
  Full time? I haven't heard that anywhere.
ag_47 9y ago
Now I'm curious, Are there any websites that do something similar to /r/place? (hackathon idea?) Also, reminds be of the million dollar front page [1]. [1] https://en.wikipedia.org/wiki/The_Million_Dollar_Homepage https://en.wikipedia.org/wiki/The_Million_Dollar_Homepage
- criley2 9y ago
  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
- splintercell 9y ago
  http://8192px.co/ http://8192px.co/
  - caspervonb 9y ago
    <shameless-plug> Also available on GitHub (https://github.com/8192px/8192px https://github.com/8192px/8192px) ;-] </shameless-plug>
- DanHulton 9y ago
  A long time ago, I built http://www.ipaidthemost.com/ 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.
  - jacquesm 9y ago
    Hilarious. That's got to be the most direct monetization strategy since tmdhp.
    - deleted 9y ago
      [deleted]
  - Twirrim 9y ago
    Does that actually make money?
amyjess 9y ago
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.
- johansch 9y ago
  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.
77pt77 9y ago
Now where can we get a dump of all the data. Like timestamp, x, y, color, username
- Paul_S 9y ago
  You can't have it because it would show the extent of moderation.
  - 77pt77 9y ago
    I don't get it. Please explain.
- calosa 9y ago
  One of the reddit data scientists dumped it here... https://data.world/justintbassett/place-events https://data.world/justintbassett/place-events
  - aw3c2 9y ago
    > Oops! We can't find that page.
    - justintbassett 9y ago
      my fault :). I have to get a few things ready for a public release of more data
      - calosa 9y ago
        Oops. Sorry about that. Look forward to it being back up :)
      - 77pt77 9y ago
        Is this data: https://www.reddit.com/r/place/comments/6396u5/rplace_archive_update/ https://www.reddit.com/r/place/comments/6396u5/rplace_archiv... Complete? I've been working with that.
nitwit005 9y ago
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.
- bsimpson63 9y ago
  You're basically describing how we used redis for this project.
  - nitwit005 9y ago
    I suppose so, but then what did you gain from the extra hop to redis?
    - bsimpson63 9y ago
      Not having to implement redis ourselves.
- foota 9y ago
  That was my thought as well.
- Matheus28 9y ago
  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.
- nullbyte 9y ago
  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.
  - nitwit005 9y ago
    Perhaps, rather than posting an insult, you should consider the possibility that you misinterpreted my comment?
johansch 9y ago
The front-end UX for scrolling that bitmap was quite frankly horribly badly designed.
- bsimpson63 9y ago
  What was wrong with it?
  - lima 9y ago
    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.
    - johansch 9y ago
      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.
      - zodiakzz 9y ago
        Reddit has a place for everyone, you might find yourself at home on https://reddit.com/r/iamverysmart https://reddit.com/r/iamverysmart
        deleted 9y ago
        [deleted]
        johansch 9y ago
        Oh please just go back to reddit.
  - johansch 9y ago
    Did you try to use it? It's still there: https://www.reddit.com/r/place/ 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.
antoniuschan99 9y ago
Looks impressive! How big was the team? How long did it take to complete this project? Is the code going to be open sourced?
- aw3c2 9y ago
  https://github.com/reddit/reddit-plugin-place-opensource https://github.com/reddit/reddit-plugin-place-opensource
eatitraw 9y ago
> 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.
- programbreeding 9y ago
  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.
- d23 9y ago
  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.
  - eatitraw 9y ago
    Ah okay then! BTW, thanks for the great post, it was a very interesting read.
  - atombender 9y ago
    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.
    - 9y ago
calosa 9y ago
If any data science-y folks want to work with the raw data, you can find it here... https://data.world/justintbassett/place-events https://data.world/justintbassett/place-events
- Ajedi32 9y ago
  "Oops! We can't find that page."
  - calosa 9y ago
    Looks like the owner changed it to be private :/ Hopefully they'll open it up again.
    - ReverseCold 9y ago
      Did anyone download it already? Reshare?
      - deleted 9y ago
        [deleted]
  - Viper007Bond 9y ago
    > my fault :). I have to get a few things ready for a public release of more data https://news.ycombinator.com/item?id=14110094 https://news.ycombinator.com/item?id=14110094
seankimdesign 9y ago
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.
- eblanshey 9y ago
  Agreed, great write-up. Anyone have other recommended links to write-ups about specific challenges and how to make them scale?
  - rajathagasthya 9y ago
    I really like the "Big Data in Real-Time at Twitter" slides at https://www.slideshare.net/nkallen/q-con-3770885 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.
  - josephg 9y ago
    http://highscalability.com/ http://highscalability.com/ frequently features content like this. The archives are a treasure trove of practical software architecture wisdom.
  - petercooper 9y ago
GrumpyNl 9y ago
Same was done in Holland several years ago. The one million pixels site. Each pixel was sold for a dollar. All was sold.
- frandroid 9y ago
  In real time though?
wyager 9y ago
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.
- eric_h 9y ago
  > Why use Redis and multiple machines instead of keeping it in RAM on a single machine? 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.
  - andrewvc 9y ago
    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.
tupshin 9y ago
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.
- spyspy 9y ago
  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.
- er8h 9y ago
  They're using (timestamp, user) as their compound key, which would partition rows by timestamp, no?
_hamilton 9y ago
/r/place is probably the coolest project that happened this year so far.
- taftster 9y ago
  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!
subkamran 9y ago
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 https://excaliburjs.com. We support all the features they needed including mobile & touch support. They could have also used Phaser (http://phaser.io http://phaser.io) too I bet... that has WebGL support for even faster rendering on supported devices.
- Mahn 9y ago
  ...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.
  - subkamran 9y ago
    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?
    - emorse 9y ago
      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.
      - 9y ago
look_lookatme 9y ago
This is all great, but your search never works, still. It has been like that forever.
brilliantcode 9y ago
This reminds me of http://www.milliondollarhomepage.com/ http://www.milliondollarhomepage.com/
webdwarf 9y ago
It's awesome project!
hopfog 9y ago
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. Again, amazing write-up. Thank you!
ChicagoBoy11 9y ago
I love write-ups like this because they are such a nice contrast to the too-common comments on Reddit and HN where people claim that they could rebuild FB or Uber as a side project. Something as superficially trivial as the r/Place requires a tremendous amount of effort to run smoothly and there are countless gotchas and issues that you'd never even begin to consider unless you really tried to implement it yourself. Big thanks to Reddit for the fun experiment and for sharing with us some of the engineering lessons behind it.
- deleted 9y ago
  [deleted]
- dstroot 9y ago
  I came to write exactly what you wrote. Here's an upvote brother from another mother.
  - JTrilogy 9y ago
    I'm I'm I' are] can you 3a1 we 3e 2 2 I'm/e in to in3/'maw3
- deleted 9y ago
  [deleted]
- soup10 9y ago
  To me it seems a little over-engineered but it held up so props to them.
  - joezydeco 9y ago
    I have this hunch that Reddit engineers know what they're up against when they launch something like this. It can get out of control extremely fast when something catches on.
  - dmihal 9y ago
    Reddit is like the 7th most popular website, features like this need to be able to handle significant load
ThomPete 9y ago
This is why experimentation is so important and why I always love when people do things just to do them. It's literally like exploring the digital universe and reporting on some of your findings. Great writeup!
biot 9y ago
> At the peak of r/place the websocket service was > transmitting over 4 gbps (150 Mbps per instance > and 24 instances). What does Reddit use for serving up this much websocket traffic? Something open source, or is it custom built?
- dkasper 9y ago
  It's open source and custom built. https://github.com/reddit/reddit-service-websockets https://github.com/reddit/reddit-service-websockets
- deleted 9y ago
  [deleted]
replface 9y ago
Similar to this? https://www.youtube.com/watch?v=9_uX5yXSOwU https://www.youtube.com/watch?v=9_uX5yXSOwU
Cofike 9y ago
As someone looking to expand their knowledge of big systems and building at scale this kind of resource is invaluable!
ziikutv 9y ago
Startup tech writers, take note. This write up has been more helpful than many in the past. Thank you very much Reddit developers
rohankshir 9y ago
anyone know what framework they used to do visualizations?
- bsimpson63 9y ago
  https://grafana.com/ https://grafana.com/ for the graphs and https://www.draw.io/ https://www.draw.io/ and http://www.fiftythree.com/ http://www.fiftythree.com/ for the diagrams.
the_arun 9y ago
Good article. One security issue I see is - showing Nginx version in error page - nginx/1.8.0. No need to show details of webserver or its version!
disque71 9y ago
Why?
blurrywh 9y ago
FULL 72h (90fps) TIMELAPSE: https://www.youtube.com/watch?v=XnRCZK3KjUY https://www.youtube.com/watch?v=XnRCZK3KjUY
nathan_f77 9y ago
This is fantastic. I learned a lot, and it seems like they nailed everything. I really enjoyed the part about TypedArray and ArrayBuffer. And this might be a common thing to do, but I've never thought about using a CDN with an expiry time of 1 second, just to buffer lots of requests while still being close to real-time. That's brilliant.
a_bonobo 9y ago
Weird question - why does that bash script use absolute paths for standard tools like awk and grep (/usr/bin/awk instead of just awk)? Is this some best practice I know nothing about?
svarrall 9y ago
Anyone with any insight into how much something like this 'cost' Reddit, resource wise. Is the main outlay in time and the server costs already covered by their infrastructure or does the high traffic add enough to make a difference?

1152 points by dkasper 9y ago

> 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.

77pt77 9y ago
These no-SQL solutions seem shoehorned many times. Like people decide to use them from the get-go and then come up with a justification.
- gooeyblob 9y ago
  We've been using Cassandra for 7 years since 0.7.
bsimpson63 9y ago
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.
- fidget 9y ago
  Are you suggesting that you had a concurrency bug that was solvable without changing your entire storage layer? Heresy..
- developer2 9y ago
  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.
d23 9y ago
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.
- Dylan16807 9y ago
  > And to query the whole canvas you'd query a million rows on every read? 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.
- mozumder 9y ago
  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.
  - developer2 9y ago
    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.
    - mozumder 9y ago
      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.
hashhar 9y ago
And what about adding a million rows to the RDBMS and querying it in under 100ms (which Redis allowed them to do). I will say that it was an implementation bug which doesn't warrant the swapping out of entire data storage layers.
- kuschku 9y ago
  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.
  - nebabyte 9y ago
    > 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.
    - kuschku 9y ago
      No. 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.
Thaxll 9y ago
Well PostgreSQL is a single master for writes so it doesn't scale well to say the least.
- mozumder 9y ago
  333 writes per second really is nothing in a world with modern NVMe drives.
jdmichal 9y ago
Or use bog-standard token bucket rate limiting algorithms with atomic decrement-and-get operations.
corford 9y ago
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.
thinkmoore 9y ago
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.
developer2 9y ago
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.
Can_Not 9y ago
Don't even need postgre, Lua scripts are transaction safe on redis clusters.

huangc10 9y ago

Can someone link to the full resolution final image? Been trying to find it. Thanks!

noxToken 9y ago
If you ever want to revisit, it's linked in the right side of the sub. https://www.reddit.com/place?webview=true https://www.reddit.com/place?webview=true
- huangc10 9y ago
  For some reason it leads to 403...weird
  - dan1234 9y ago
    http://i.imgur.com/dYdHDYe.png http://i.imgur.com/dYdHDYe.png I've exported it to imgur for you.
deleted 9y ago
[deleted]
LeoPanthera 9y ago
This is the final bitmap. http://i.imgur.com/ajWiAYi.png http://i.imgur.com/ajWiAYi.png
Ajedi32 9y ago
Here you go: https://i.imgur.com/ajWiAYi.png https://i.imgur.com/ajWiAYi.png. And for those interested, here's some additional stats: - The original announcement about /r/place: https://www.reddit.com/r/announcements/comments/62mesr/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 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 https://i.redd.it/20mghgkfwppy.png by /u/mustafaihssan - Timelapse heatmap of activity on the canvas: https://i.imgur.com/a95XXDz.gifv 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 https://i.imgur.com/NnjFoHt.jpg by /u/howaboot (explanation: https://www.reddit.com/r/dataisbeautiful/comments/63kuy6/oc_heatmap_of_the_most_pixels_changes_happend_on/dfv3n83/ 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 https://i.imgur.com/SEHaUSJ.png by /u/alternateme - Most common color of each pixel over the last... - 72 hours**: https://i.imgur.com/C5jOtl1.png by /u/howaboot - 24 Hours: http://aperiodic.net/phil/tmp/place-mode-24h.png by /u/phil_g - 12 Hours: http://aperiodic.net/phil/tmp/place-mode-12h.png by /u/phil_g - 6 Hours: http://aperiodic.net/phil/tmp/place-mode-6h.png by /u/phil_g - 2 Hours: http://aperiodic.net/phil/tmp/place-mode-2h.png by /u/phil_g - Average color of each pixel over the course of the experiment: https://i.imgur.com/IkPOwIh.png https://i.imgur.com/IkPOwIh.png - Atlas of the Final Image: https://draemm.li/various/place-atlas/ https://draemm.li/various/place-atlas/ by /r/placeAtlas/ (source code: https://github.com/RolandR/place-atlas https://github.com/RolandR/place-atlas) - Torrents of various canvas snapshots and image data: https://www.reddit.com/r/place/comments/6396u5/rplace_archive_update/** 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_ended/ 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

vmasto 9y ago

> 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. Could anyone more experienced shed some light?

deleted 9y ago
[deleted]
andoon 9y ago
The entire reddit website goes down every night, especially during weekends, sport matches, etc, so there you have your answer.
- celticninja 9y ago
  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.
  - andoon 9y ago
    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.
    - rhizome 9y ago
      This isn't my experience.

writeslowly 9y ago

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.

gramstrong 9y ago
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..
- kuschku 9y ago
  Oh it is very easy. You just need subreddits with lots of very loyal people who even do frequent meetups, and lots of those subreddits. And soon you get exactly what /r/place was.
- saulrh 9y ago
  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.
- jobigoud 9y ago
  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.
- ralfd 9y ago
  But reddit itself is a tool to bring cohesion out of a million random strangers. As others have said subcommunities quickly formed or some subreddits themselves had a orga-thread to paint an iconic logo relevant to their niche.

archagon 9y ago

Thank you for the fascinating writeup! How long did the whole thing take to put together?

tyrust 9y ago
First commit was on Jan 20 [0], so that provides a lower-bound for how long they spent on it. [0] - https://github.com/reddit/reddit-plugin-place-opensource/commit/68498bab9300f43ae4273dd4719dcecb081126f7 https://github.com/reddit/reddit-plugin-place-opensource/com...
maaaats 9y ago
> seems to be pretty simple, I feel like it shouldn't take more than a day to code From a reddit "expert", so I guess that answers that ;)

maaaats 9y ago

Interesting how big the Norwegian and Swedish flags got, given our small populations.

77pt77 9y ago
Very easy flags to maintain and extend from a smaller model.
stevekemp 9y ago
I thought the exact same thing, about the Finnish flag - complete with Moomins.
- pimeys 9y ago
  And the almost a dictator of a president Urho Kekkonen. I kind of understand this, I was born in that country...
- nerfhammer 9y ago
  I also notice some kind of Finland-Brazil-Argentina alliance
kzrdude 9y ago
Populations are not so small in reddit terms. Sweden probably has an equal population to Italy or even more, on reddit.

pitaj 9y ago

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.

kzrdude 9y ago
Full time? I haven't heard that anywhere.

ag_47 9y ago

Now I'm curious, Are there any websites that do something similar to /r/place? (hackathon idea?) Also, reminds be of the million dollar front page [1]. [1] https://en.wikipedia.org/wiki/The_Million_Dollar_Homepage https://en.wikipedia.org/wiki/The_Million_Dollar_Homepage

criley2 9y ago
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
splintercell 9y ago
http://8192px.co/ http://8192px.co/
- caspervonb 9y ago
  <shameless-plug> Also available on GitHub (https://github.com/8192px/8192px https://github.com/8192px/8192px) ;-] </shameless-plug>
DanHulton 9y ago
A long time ago, I built http://www.ipaidthemost.com/ 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.
- jacquesm 9y ago
  Hilarious. That's got to be the most direct monetization strategy since tmdhp.
  - deleted 9y ago
    [deleted]
- Twirrim 9y ago
  Does that actually make money?

amyjess 9y ago

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.

johansch 9y ago
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.

77pt77 9y ago

Now where can we get a dump of all the data. Like timestamp, x, y, color, username

Paul_S 9y ago
You can't have it because it would show the extent of moderation.
- 77pt77 9y ago
  I don't get it. Please explain.
calosa 9y ago
One of the reddit data scientists dumped it here... https://data.world/justintbassett/place-events https://data.world/justintbassett/place-events
- aw3c2 9y ago
  > Oops! We can't find that page.
  - justintbassett 9y ago
    my fault :). I have to get a few things ready for a public release of more data
    - calosa 9y ago
      Oops. Sorry about that. Look forward to it being back up :)
    - 77pt77 9y ago
      Is this data: https://www.reddit.com/r/place/comments/6396u5/rplace_archive_update/ https://www.reddit.com/r/place/comments/6396u5/rplace_archiv... Complete? I've been working with that.

nitwit005 9y ago

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.

bsimpson63 9y ago
You're basically describing how we used redis for this project.
- nitwit005 9y ago
  I suppose so, but then what did you gain from the extra hop to redis?
  - bsimpson63 9y ago
    Not having to implement redis ourselves.
foota 9y ago
That was my thought as well.
Matheus28 9y ago
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.
nullbyte 9y ago
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.
- nitwit005 9y ago
  Perhaps, rather than posting an insult, you should consider the possibility that you misinterpreted my comment?

johansch 9y ago

The front-end UX for scrolling that bitmap was quite frankly horribly badly designed.

bsimpson63 9y ago
What was wrong with it?
- lima 9y ago
  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.
  - johansch 9y ago
    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.
    - zodiakzz 9y ago
      Reddit has a place for everyone, you might find yourself at home on https://reddit.com/r/iamverysmart https://reddit.com/r/iamverysmart
      - deleted 9y ago
        [deleted]
      - johansch 9y ago
        Oh please just go back to reddit.
- johansch 9y ago
  Did you try to use it? It's still there: https://www.reddit.com/r/place/ 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.

antoniuschan99 9y ago

Looks impressive! How big was the team? How long did it take to complete this project? Is the code going to be open sourced?

aw3c2 9y ago
https://github.com/reddit/reddit-plugin-place-opensource https://github.com/reddit/reddit-plugin-place-opensource

eatitraw 9y ago

> 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.

programbreeding 9y ago
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.
d23 9y ago
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.
- eatitraw 9y ago
  Ah okay then! BTW, thanks for the great post, it was a very interesting read.
- atombender 9y ago
  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.
  - 9y ago

calosa 9y ago

If any data science-y folks want to work with the raw data, you can find it here... https://data.world/justintbassett/place-events https://data.world/justintbassett/place-events

Ajedi32 9y ago
"Oops! We can't find that page."
- calosa 9y ago
  Looks like the owner changed it to be private :/ Hopefully they'll open it up again.
  - ReverseCold 9y ago
    Did anyone download it already? Reshare?
    - deleted 9y ago
      [deleted]
- Viper007Bond 9y ago
  > my fault :). I have to get a few things ready for a public release of more data https://news.ycombinator.com/item?id=14110094 https://news.ycombinator.com/item?id=14110094

seankimdesign 9y ago

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.

eblanshey 9y ago
Agreed, great write-up. Anyone have other recommended links to write-ups about specific challenges and how to make them scale?
- rajathagasthya 9y ago
  I really like the "Big Data in Real-Time at Twitter" slides at https://www.slideshare.net/nkallen/q-con-3770885 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.
- josephg 9y ago
  http://highscalability.com/ http://highscalability.com/ frequently features content like this. The archives are a treasure trove of practical software architecture wisdom.
- petercooper 9y ago

GrumpyNl 9y ago

Same was done in Holland several years ago. The one million pixels site. Each pixel was sold for a dollar. All was sold.

frandroid 9y ago
In real time though?

wyager 9y ago

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.

eric_h 9y ago
> Why use Redis and multiple machines instead of keeping it in RAM on a single machine? 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.
- andrewvc 9y ago
  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.

tupshin 9y ago

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.

spyspy 9y ago
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.
er8h 9y ago
They're using (timestamp, user) as their compound key, which would partition rows by timestamp, no?

_hamilton 9y ago

/r/place is probably the coolest project that happened this year so far.

taftster 9y ago
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!

subkamran 9y ago

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 https://excaliburjs.com. We support all the features they needed including mobile & touch support. They could have also used Phaser (http://phaser.io http://phaser.io) too I bet... that has WebGL support for even faster rendering on supported devices.

Mahn 9y ago
...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.
- subkamran 9y ago
  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?
  - emorse 9y ago
    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.
    - 9y ago

look_lookatme 9y ago

This is all great, but your search never works, still. It has been like that forever.

brilliantcode 9y ago

This reminds me of http://www.milliondollarhomepage.com/ http://www.milliondollarhomepage.com/

webdwarf 9y ago

It's awesome project!

hopfog 9y ago

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. Again, amazing write-up. Thank you!

ChicagoBoy11 9y ago

I love write-ups like this because they are such a nice contrast to the too-common comments on Reddit and HN where people claim that they could rebuild FB or Uber as a side project. Something as superficially trivial as the r/Place requires a tremendous amount of effort to run smoothly and there are countless gotchas and issues that you'd never even begin to consider unless you really tried to implement it yourself. Big thanks to Reddit for the fun experiment and for sharing with us some of the engineering lessons behind it.

deleted 9y ago
[deleted]
dstroot 9y ago
I came to write exactly what you wrote. Here's an upvote brother from another mother.
- JTrilogy 9y ago
  I'm I'm I' are] can you 3a1 we 3e 2 2 I'm/e in to in3/'maw3
deleted 9y ago
[deleted]
soup10 9y ago
To me it seems a little over-engineered but it held up so props to them.
- joezydeco 9y ago
  I have this hunch that Reddit engineers know what they're up against when they launch something like this. It can get out of control extremely fast when something catches on.
- dmihal 9y ago
  Reddit is like the 7th most popular website, features like this need to be able to handle significant load

ThomPete 9y ago

This is why experimentation is so important and why I always love when people do things just to do them. It's literally like exploring the digital universe and reporting on some of your findings. Great writeup!

biot 9y ago

> At the peak of r/place the websocket service was > transmitting over 4 gbps (150 Mbps per instance > and 24 instances). What does Reddit use for serving up this much websocket traffic? Something open source, or is it custom built?

dkasper 9y ago
It's open source and custom built. https://github.com/reddit/reddit-service-websockets https://github.com/reddit/reddit-service-websockets
deleted 9y ago
[deleted]

replface 9y ago

Similar to this? https://www.youtube.com/watch?v=9_uX5yXSOwU https://www.youtube.com/watch?v=9_uX5yXSOwU

Cofike 9y ago

As someone looking to expand their knowledge of big systems and building at scale this kind of resource is invaluable!

ziikutv 9y ago

Startup tech writers, take note. This write up has been more helpful than many in the past. Thank you very much Reddit developers

rohankshir 9y ago

anyone know what framework they used to do visualizations?

bsimpson63 9y ago
https://grafana.com/ https://grafana.com/ for the graphs and https://www.draw.io/ https://www.draw.io/ and http://www.fiftythree.com/ http://www.fiftythree.com/ for the diagrams.

the_arun 9y ago

Good article. One security issue I see is - showing Nginx version in error page - nginx/1.8.0. No need to show details of webserver or its version!

disque71 9y ago

Why?

blurrywh 9y ago

FULL 72h (90fps) TIMELAPSE: https://www.youtube.com/watch?v=XnRCZK3KjUY https://www.youtube.com/watch?v=XnRCZK3KjUY

nathan_f77 9y ago

This is fantastic. I learned a lot, and it seems like they nailed everything. I really enjoyed the part about TypedArray and ArrayBuffer. And this might be a common thing to do, but I've never thought about using a CDN with an expiry time of 1 second, just to buffer lots of requests while still being close to real-time. That's brilliant.

a_bonobo 9y ago

Weird question - why does that bash script use absolute paths for standard tools like awk and grep (/usr/bin/awk instead of just awk)? Is this some best practice I know nothing about?

svarrall 9y ago

Anyone with any insight into how much something like this 'cost' Reddit, resource wise. Is the main outlay in time and the server costs already covered by their infrastructure or does the high traffic add enough to make a difference?