Hacker News Reader

Comment by mozumder | Hacker News Reader

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

View on HN

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.

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

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.

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.

Are you suggesting that you had a concurrency bug that was solvable without changing your entire storage layer? Heresy..

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.

Thanks for the support!

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.

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.

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.

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.

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.

We've been using Cassandra for 7 years since 0.7.

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.

Well PostgreSQL is a single master for writes so it doesn't scale well to say the least.

333 writes per second really is nothing in a world with modern NVMe drives.

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.

Or use bog-standard token bucket rate limiting algorithms with atomic decrement-and-get operations.

Don't even need postgre, Lua scripts are transaction safe on redis clusters.

Reply on news.ycombinator.com