Cool to read. Looks very familiar. I started an Easter Egg Hunt Facebook game out of my dorm room in 2008 called Hatchlings. We actually had them beat in the engineers to users ratio. When we had 5 million users and more pageviews/mo than the NY Times it was still just me (and I had hired my mom and sister part time to do customer support). It was running on a LAMP stack + memcached (first at DreamHost, then Joyent, and finally AWS).
This article sparked in my mind a bit-twiddling hack I implemented to get a ton more scale out of our single giant MySQL box that survives in their code base to this day, much to every one of their dev’s chagrin (crazy to think that 15 years later the weekend project I launched still has tens of thousands of monthly subscribers).
At Hatchlings, we had several hundred collections of Easter Eggs (usually 7-12 unique eggs in each collection). Each user would “open” and then hunt for a few collections at a time until they “finished” them. New collections would come out every week (to ensure there was new content daily).
As we scaled both in users and number of collections I realized that the “normal” SQL layout you’d use to represent this (a users table, a collections table keyed on user_id, collection_id, and an eggs table keyed on user_id, collection_id, egg_id) was growing rapidly (each user was adding new rows every day) and needed multiple joins in our “hot” routes (when a user searches for an egg we need to know which collections they have access to, and when a user clicks an egg we need to know if it was new for them and if it newly completed that collection) which were being hit tens of thousands of times per second during peak times. Additionally, every egg collected increased the user’s score.
So I implemented an optimization: store the collection unlocked and completed info compactly in the users table in bit fields. These were several 64 bit integers where eg collections_unlocked_1 being equal to 4 (binary 100) meant that the collection with ID 2 was unlocked. (collections_unlocked_2 equaling 1 would mean collection 64 was unlocked since there were 64 bits in 1). Your “active” collections were the bits that were 1 in an unlocked bit field but 0 in the parallel completed bit field.
This did a few things:
* Reduced the rows per user from total_collectionstotal_eggs to ~collections_in_progress (just in-flight collections) — about a 100x reduction in our total DB size
* Reduced joins to 0
* Since all the “common” egg collections were already completed by all the most active users we didn’t have to check the eggs table for the vast majority of finds because if a collection was marked finished we knew you already had all the eggs in it
* Made everything needed for the hot route compactly storable in a single memcached entry (which allowed us to greatly reduce writes because we would read scores and collections from memcached in the hot route and only write changes to the DB once/minute)
It was a great speed and scaling optimization… But it was really tricky to deal with and reason about… and a binary arithmetic error could completely nuke months of game progress for people. And we also had to remember to add more columns to the users table every year or two or we’d run out of space for collections in our bit fields (we forgot about this a couple of times and it lead to downtime which tended to happen during the most peak times where we had hyped that we were going to release a ton of new content all at once).
This article sparked in my mind a bit-twiddling hack I implemented to get a ton more scale out of our single giant MySQL box that survives in their code base to this day, much to every one of their dev’s chagrin (crazy to think that 15 years later the weekend project I launched still has tens of thousands of monthly subscribers).
At Hatchlings, we had several hundred collections of Easter Eggs (usually 7-12 unique eggs in each collection). Each user would “open” and then hunt for a few collections at a time until they “finished” them. New collections would come out every week (to ensure there was new content daily).
As we scaled both in users and number of collections I realized that the “normal” SQL layout you’d use to represent this (a users table, a collections table keyed on user_id, collection_id, and an eggs table keyed on user_id, collection_id, egg_id) was growing rapidly (each user was adding new rows every day) and needed multiple joins in our “hot” routes (when a user searches for an egg we need to know which collections they have access to, and when a user clicks an egg we need to know if it was new for them and if it newly completed that collection) which were being hit tens of thousands of times per second during peak times. Additionally, every egg collected increased the user’s score.
So I implemented an optimization: store the collection unlocked and completed info compactly in the users table in bit fields. These were several 64 bit integers where eg collections_unlocked_1 being equal to 4 (binary 100) meant that the collection with ID 2 was unlocked. (collections_unlocked_2 equaling 1 would mean collection 64 was unlocked since there were 64 bits in 1). Your “active” collections were the bits that were 1 in an unlocked bit field but 0 in the parallel completed bit field.
This did a few things:
* Reduced the rows per user from total_collectionstotal_eggs to ~collections_in_progress (just in-flight collections) — about a 100x reduction in our total DB size
* Reduced joins to 0
* Since all the “common” egg collections were already completed by all the most active users we didn’t have to check the eggs table for the vast majority of finds because if a collection was marked finished we knew you already had all the eggs in it
* Made everything needed for the hot route compactly storable in a single memcached entry (which allowed us to greatly reduce writes because we would read scores and collections from memcached in the hot route and only write changes to the DB once/minute)
It was a great speed and scaling optimization… But it was really tricky to deal with and reason about… and a binary arithmetic error could completely nuke months of game progress for people. And we also had to remember to add more columns to the users table every year or two or we’d run out of space for collections in our bit fields (we forgot about this a couple of times and it lead to downtime which tended to happen during the most peak times where we had hyped that we were going to release a ton of new content all at once).