2008年10月10日星期五

YouTube Architecture

Update: YouTube: The Platform. YouTube adds a new rich set of APIs in order to become your video platform leader--all for free. Upload, edit, watch, search, and comment on video from your own site without visiting YouTube. Compose your site internally from APIs because you'll need to expose them later anyway.

YouTube grew incredibly fast, to over 100 million video views per day, with only a handful of people responsible for scaling the site. How did they manage to deliver all that video to all those users? And how have they evolved since being acquired by Google?

Information Sources

# Google Video

Platform

# Apache
# Python
# Linux (SuSe)
# MySQL
# psyco, a dynamic python->C compiler
# lighttpd for video instead of Apache

What's Inside?

The Stats

# Supports the delivery of over 100 million videos per day.
# Founded 2/2005
# 3/2006 30 million video views/day
# 7/2006 100 million video views/day
# 2 sysadmins, 2 scalability software architects
# 2 feature developers, 2 network engineers, 1 DBA

Recipe for handling rapid growth


while (true)
{
identify_and_fix_bottlenecks();
drink();
sleep();
notice_new_bottleneck();
}

This loop runs many times a day.

Web Servers

# NetScalar is used for load balancing and caching static content.
# Run Apache with mod_fast_cgi.
# Requests are routed for handling by a Python application server.
# Application server talks to various databases and other informations sources to get all the data and formats the html page.
# Can usually scale web tier by adding more machines.
# The Python web code is usually NOT the bottleneck, it spends most of its time blocked on RPCs.
# Python allows rapid flexible development and deployment. This is critical given the competition they face.
# Usually less than 100 ms page service times.
# Use psyco, a dynamic python->C compiler that uses a JIT compiler approach to optimize inner loops.
# For high CPU intensive activities like encryption, they use C extensions.
# Some pre-generated cached HTML for expensive to render blocks.
# Row level caching in the database.
# Fully formed Python objects are cached.
# Some data are calculated and sent to each application so the values are cached in local memory. This is an underused strategy. The fastest cache is in your application server and it doesn't take much time to send precalculated data to all your servers. Just have an agent that watches for changes, precalculates, and sends.

Video Serving

# Costs include bandwidth, hardware, and power consumption.
# Each video hosted by a mini-cluster. Each video is served by more than one machine.
# Using a a cluster means:
- More disks serving content which means more speed.
- Headroom. If a machine goes down others can take over.
- There are online backups.
# Servers use the lighttpd web server for video:
- Apache had too much overhead.
- Uses epoll to wait on multiple fds.
- Switched from single process to multiple process configuration to handle more connections.
# Most popular content is moved to a CDN (content delivery network):
- CDNs replicate content in multiple places. There's a better chance of content being closer to the user, with fewer hops, and content will run over a more friendly network.
- CDN machines mostly serve out of memory because the content is so popular there's little thrashing of content into and out of memory.
# Less popular content (1-20 views per day) uses YouTube servers in various colo sites.
- There's a long tail effect. A video may have a few plays, but lots of videos are being played. Random disks blocks are being accessed.
- Caching doesn't do a lot of good in this scenario, so spending money on more cache may not make sense. This is a very interesting point. If you have a long tail product caching won't always be your performance savior.
- Tune RAID controller and pay attention to other lower level issues to help.
- Tune memory on each machine so there's not too much and not too little.

Serving Video Key Points

# Keep it simple and cheap.
# Keep a simple network path. Not too many devices between content and users. Routers, switches, and other appliances may not be able to keep up with so much load.
# Use commodity hardware. More expensive hardware gets the more expensive everything else gets too (support contracts). You are also less likely find help on the net.
# Use simple common tools. They use most tools build into Linux and layer on top of those.
# Handle random seeks well (SATA, tweaks).

Serving Thumbnails

# Surprisingly difficult to do efficiently.
# There are a like 4 thumbnails for each video so there are a lot more thumbnails than videos.
# Thumbnails are hosted on just a few machines.
# Saw problems associated with serving a lot of small objects:
- Lots of disk seeks and problems with inode caches and page caches at OS level.
- Ran into per directory file limit. Ext3 in particular. Moved to a more hierarchical structure. Recent improvements in the 2.6 kernel may improve Ext3 large directory handling up to 100 times, yet storing lots of files in a file system is still not a good idea.
- A high number of requests/sec as web pages can display 60 thumbnails on page.
- Under such high loads Apache performed badly.
- Used squid (reverse proxy) in front of Apache. This worked for a while, but as load increased performance eventually decreased. Went from 300 requests/second to 20.
- Tried using lighttpd but with a single threaded it stalled. Run into problems with multiprocesses mode because they would each keep a separate cache.
- With so many images setting up a new machine took over 24 hours.
- Rebooting machine took 6-10 hours for cache to warm up to not go to disk.
# To solve all their problems they started using Google's BigTable, a distributed data store:
- Avoids small file problem because it clumps files together.
- Fast, fault tolerant. Assumes its working on a unreliable network.
- Lower latency because it uses a distributed multilevel cache. This cache works across different collocation sites.
- For more information on BigTable take a look at Google Architecture, GoogleTalk Architecture, and BigTable.

Databases

# The Early Years
- Use MySQL to store meta data like users, tags, and descriptions.
- Served data off a monolithic RAID 10 Volume with 10 disks.
- Living off credit cards so they leased hardware. When they needed more hardware to handle load it took a few days to order and get delivered.
- They went through a common evolution: single server, went to a single master with multiple read slaves, then partitioned the database, and then settled on a sharding approach.
- Suffered from replica lag. The master is multi-threaded and runs on a large machine so it can handle a lot of work. Slaves are single threaded and usually run on lesser machines and replication is asynchronous, so the slaves can lag significantly behind the master.
- Updates cause cache misses which goes to disk where slow I/O causes slow replication.
- Using a replicating architecture you need to spend a lot of money for incremental bits of write performance.
- One of their solutions was prioritize traffic by splitting the data into two clusters: a video watch pool and a general cluster. The idea is that people want to watch video so that function should get the most resources. The social networking features of YouTube are less important so they can be routed to a less capable cluster.
# The later years:
- Went to database partitioning.
- Split into shards with users assigned to different shards.
- Spreads writes and reads.
- Much better cache locality which means less IO.
- Resulted in a 30% hardware reduction.
- Reduced replica lag to 0.
- Can now scale database almost arbitrarily.

Data Center Strategy

# Used manage hosting providers at first. Living off credit cards so it was the only way.
# Managed hosting can't scale with you. You can't control hardware or make favorable networking agreements.
# So they went to a colocation arrangement. Now they can customize everything and negotiate their own contracts.
# Use 5 or 6 data centers plus the CDN.
# Videos come out of any data center. Not closest match or anything. If a video is popular enough it will move into the CDN.
# Video bandwidth dependent, not really latency dependent. Can come from any colo.
# For images latency matters, especially when you have 60 images on a page.
# Images are replicated to different data centers using BigTable. Code
looks at different metrics to know who is closest.

Lessons Learned

# Stall for time. Creative and risky tricks can help you cope in the short term while you work out longer term solutions.

# Prioritize. Know what's essential to your service and prioritize your resources and efforts around those priorities.

# Pick your battles. Don't be afraid to outsource some essential services. YouTube uses a CDN to distribute their most popular content. Creating their own network would have taken too long and cost too much. You may have similar opportunities in your system. Take a look at Software as a Service for more ideas.

# Keep it simple! Simplicity allows you to rearchitect more quickly so you can respond to problems. It's true that nobody really knows what simplicity is, but if you aren't afraid to make changes then that's a good sign simplicity is happening.

# Shard. Sharding helps to isolate and constrain storage, CPU, memory, and IO. It's not just about getting more writes performance.

# Constant iteration on bottlenecks:
- Software: DB, caching
- OS: disk I/O
- Hardware: memory, RAID

# You succeed as a team. Have a good cross discipline team that understands the whole system and what's underneath the system. People who can set up printers, machines, install networks, and so on. With a good team all things are possible.

Flickr Architecture

Update: Flickr hits 2 Billion photos served. That's a lot of hamburgers.

Flickr is both my favorite bird and the web's leading photo sharing site. Flickr has an amazing challenge, they must handle a vast sea of ever expanding new content, ever increasing legions of users, and a constant stream of new features, all while providing excellent performance. How do they do it?

Site: http://www.flickr.com/

Information Sources

# Flickr and PHP (an early document)
# Capacity Planning for LAMP
# Federation at Flickr: Doing Billions of Queries a Day by Dathan Pattishall.
# Building Scalable Web Sites by Cal Henderson from Flickr.
# Database War Stories #3: Flickr by Tim O'Reilly
# Cal Henderson's Talks. A lot of useful PowerPoint presentations.

Platform

# PHP
# MySQL
# Shards
# Memcached for a caching layer.
# Squid in reverse-proxy for html and images.
# Linux (RedHat)
# Smarty for templating
# Perl
# PEAR for XML and Email parsing
# ImageMagick, for image processing
# Java, for the node service
# Apache
# SystemImager for deployment
# Ganglia for distributed system monitoring
# Subcon stores essential system configuration files in a subversion repository for easy deployment to machines in a cluster.
# Cvsup for distributing and updating collections of files across a network.

The Stats

# More than 4 billion queries per day.
# ~35M photos in squid cache (total)
# ~2M photos in squid’s RAM
# ~470M photos, 4 or 5 sizes of each
# 38k req/sec to memcached (12M objects)
# 2 PB raw storage (consumed about ~1.5TB on Sunday
# Over 400,000 photos being added every day

The Architecture

# A pretty picture of Flickr's architecture can be found on this slide . A simple depiction is:
-- Pair of ServerIron's
---- Squid Caches
------ Net App's
---- PHP App Servers
------ Storage Manager
------ Master-master shards
------ Dual Tree Central Database
------ Memcached Cluster
------ Big Search Engine

- The Dual Tree structure is a custom set of changes to MySQL that allows scaling by incrementally adding masters without a ring architecture. This allows cheaper scaling because you need less hardware as compared to master-master setups which always requires double the hardware.
- The central database includes data like the 'users' table, which includes primary user
keys (a few different IDs) and a pointer to which shard a users' data can be found on.

# Use dedicated servers for static content.
# Talks about how to support Unicode.
# Use a share nothing architecture.
# Everything (except photos) are stored in the database.
# Statelessness means they can bounce people around servers and it's easier to make their APIs.
# Scaled at first by replication, but that only helps with reads.
# Create a search farm by replicating the portion of the database they want to search.
# Use horizontal scaling so they just need to add more machines.
# Handle pictures emailed from users by parsing each email is it's delivered in PHP. Email is parsed for any photos.
# Earlier they suffered from Master-Slave lag. Too much load and they had a single point of failure.
# They needed the ability to make live maintenance, repair data, and so forth, without taking the site down.
# Lots of excellent material on capacity planning. Take a look in the Information Sources for more details.
# Went to a federated approach so they can scale far into the future:
- Shards: My data gets stored on my shard, but the record of performing action on your comment, is on your shard. When making a comment on someone else's’ blog
- Global Ring: Its like DNS, you need to know where to go and who controls where you go. Every page view, calculate where your data is, at that moment of time.
- PHP logic to connect to the shards and keep the data consistent (10 lines of code with comments!)
# Shards:
- Slice of the main database
- Active Master-Master Ring Replication: a few drawbacks in MySQL 4.1, as honoring commits in Master-Master. AutoIncrement IDs are automated to keep it Active Active.
- Shard assignments are from a random number for new accounts
- Migration is done from time to time, so you can remove certain power users. Needs to be balanced if you have a lot of photos… 192,000 photos, 700,000 tags, will take about 3-4 minutes. Migration is done manually.
# Clicking a Favorite:
- Pulls the Photo owners Account from Cache, to get the shard location (say on shard-5)
- Pulls my Information from cache, to get my shard location (say on shard-13)
- Starts a “distributed transaction” - to answer the question: Who favorited the photo? What are my favorites?
# Can ask question from any shard, and recover data. Its absolutely redundant.
# To get rid of replication lag…
- every page load, the user is assigned to a bucket
- if host is down, go to next host in the list; if all hosts are down, display an error page. They don’t use persistent connections, they build connections and tear it down. Every page load thus, tests the connection.
# Every users reads and writes are kept in one shard. Notion of replication lag is gone.
# Each server in shard is 50% loaded. Shut down 1/2 the servers in each shard. So 1 server in the shard can take the full load if a server of that shard is down or in maintenance mode. To upgrade you just have to shut down half the shard, upgrade that half, and then repeat the process.
# Periods of time when traffic spikes, they break the 50% rule though. They do something like 6,000-7,000 queries per second. Now, its designed for at most 4,000 queries per second to keep it at 50% load.
# Average queries per page, are 27-35 SQL statements. Favorites counts are real time. API access to the database is all real time. Achieved the real time requirements without any disadvantages.
# Over 36,000 queries per second - running within capacity threshold. Burst of traffic, double 36K/qps.
# Each Shard holds 400K+ users data.
- A lot of data is stored twice. For example, a comment is part of the relation between the commentor and the commentee. Where is the comment stored? How about both places? Transactions are used to prevent out of sync data: open transaction 1, write commands, open transaction 2, write commands, commit 1st transaction if all is well, commit 2nd transaction if 1st committed. but there still a chance for failure when a box goes down during the 1st commit.
# Search:
- Two search back-ends: shards 35k qps on a few shards and Yahoo!’s (proprietary) web search
- Owner’s single tag search or a batch tag change (say, via Organizr) goes to the Shards due to real-time requirements, everything else goes to Yahoo!’s engine (probably about 90% behind the real-time goodness)
- Think of it such that you’ve got Lucene-like search
# Hardware:
- EMT64 w/RHEL4, 16GB RAM
- 6-disk 15K RPM RAID-10.
- Data size is at 12 TB of user metadata (these are not photos, this is just innodb ibdata files - the photos are a lot larger).
- 2U boxes. Each shard has~120GB of data.
# Backup procedure:
- ibbackup on a cron job, that runs across various shards at different times. Hotbackup to a spare.
- Snapshots are taken every night across the entire cluster of databases.
- Writing or deleting several huge backup files at once to a replication filestore can wreck performance on that filestore for the next few hours as it replicates the backup files. Doing this to an in-production photo storage filer is a bad idea.
- However much it costs to keep multiple days of backups of all of your data, it's worth it. Keeping staggered backups is good for when you discover something gone wrong a few days later. something like 1, 2, 10 and 30 day backups.
# Photos are stored on the filer. Upon upload, it processes the photos, gives you different sizes, then its complete. Metadata and points to the filers, are stored in the database.
# Aggregating the data: Very fast, because its a process per shard. Stick it into a table, or recover data from another copy from other users shards.
# max_connections = 400 connections per shard, or 800 connections per server & shard. Plenty of capacity and connections. Thread cache is set to 45, because you don’t have more than 45 users having simultaneous activity.
# Tags:
- Tags do not fit well with traditional normalized RDBMs schema design. Denormalization or heavy caching is the only way to generate a tag cloud in milliseconds for hundreds of millions of tags.
- Some of their data views are calculated offline by dedicated processing clusters which save the results into MySQL because some relationships are so complicated to calculate it would absorb all the database CPU cycles.
# Future Direction:
- Make it faster with real-time BCP, so all data centers can receive writes to the data layer (db, memcache, etc) all at the same time. Everything is active nothing will ever be idle.

Lessons Learned

# Think of your application as more than just a web application. You'll have REST APIs, SOAP APIs, RSS feeds, Atom feeds, etc.

# Go stateless. Statelessness makes for a simpler more robust system that can handle upgrades without flinching.

# Re-architecting your database sucks.

# Capacity plan. Bring capacity planning into the product discussion EARLY. Get buy-in from the $$$ people (and engineering management) that it’s something to watch.

# Start slow. Don’t buy too much equipment just because you’re scared/happy that your site will explode.

# Measure reality. Capacity planning math should be based on real things, not abstract ones.

# Build in logging and metrics. Usage stats are just as important as server stats. Build in custom metrics to measure real-world usage to server-based stats.

# Cache. Caching and RAM is the answer to everything.

# Abstract. Create clear levels of abstraction between database work, business logic, page logic, page mark-up and the presentation layer. This supports quick turn around iterative development.

# Layer. Layering allows developers to create page level logic which designers can use to build the user experience. Designers can ask for page logic as needed. It's a negotiation between the two parties.

# Release frequently. Even every 30 minutes.

# Forget about small efficiencies, about 97% of the time. Premature optimization is the root of all evil.

# Test in production. Build into the architecture mechanisms (config flags, load balancing, etc.) with which you can deploy new hardware easily into (and out of) production.

# Forget benchmarks. Benchmarks are fine for getting a general idea of capabilities, but not for planning. Artificial tests give artificial results, and the time is better used with testing for real.

# Find ceilings.
- What is the maximum something that every server can do ?
- How close are you to that maximum, and how is it trending ?
- MySQL (disk IO ?)
- SQUID (disk IO ? or CPU ?)
- memcached (CPU ? or network ?)

# Be sensitive to the usage patterns for your type of application.
- Do you have event related growth? For example: disaster, news event.
- Flickr gets 20-40% more uploads on first work day of the year than any previous peak the previous year.
- 40-50% more uploads on Sundays than the rest of the week, on average

# Be sensitive to the demands of exponential growth. More users means more content, more content means more connections, more connections mean more usage.

# Plan for peaks. Be able to handle peak loads up and down the stack.