Update 2:: How Digg Works and How Digg Really Works (wear ear plugs). Brought to you straight from Digg's blog. A very succinct explanation of the major elements of the Digg architecture while tracing a request through the system. I've updated this profile with the new information.
Update: Digg now receives 230 million plus page views per month and 26 million unique visitors - traffic that necessitated major internal upgrades.
Traffic generated by Digg's over 22 million famously info-hungry users and 230 million page views can crash an unsuspecting website head-on into its CPU, memory, and bandwidth limits. How does Digg handle billions of requests a month?
Site: http://digg.com
Information Sources
# How Digg Works by Digg
# How Digg.com uses the LAMP stack to scale upward
# Digg PHP's Scalability and Performance
Platform
# MySQL
# Linux
# PHP
# Lucene
# Python
# APC PHP Accelerator
# MCache
# Gearman - job scheduling system
# MogileFS - open source distributed filesystem
# Apache
# Memcached
The Stats
# Started in late 2004 with a single Linux server running Apache 1.3, PHP 4, and MySQL. 4.0 using the default MyISAM storage engine
# Over 22 million users.
# 230 million plus page views per month
# 26 million unique visitors per month
# Several billion page views per month
# None of the scaling challenges faced had anything to do with PHP. The biggest issues faced were database related.
# Dozens of web servers.
# Dozens of DB servers.
# Six specialized graph database servers to run the Recommendation Engine.
# Six to ten machines that serve files from MogileFS.
What's Inside
# Specialized load balancer appliances monitor the application servers, handle failover, constantly adjust the cluster according to health, balance incoming requests and caching JavaScript, CSS and images. If you don't have the fancy load balancers take a look at Linux Virtual Server and Squid as a replacement.
# Requests are passed to the Application Server cluster. Application servers consist of: Apache+PHP, Memcached, Gearman and other daemons. They are responsible for making coordinating access to different services (DB, MogileFS, etc) and creating the response sent to the browser.
# Uses a MySQL master-slave setup.
- Four master databases are partitioned by functionality: promotion, profiles, comments, main. Many slave databases hang off each master.
- Writes go to the masters and reads go to the slaves.
- Transaction-heavy servers use the InnoDB storage engine.
- OLAP-heavy servers use the MyISAM storage engine.
- They did not notice a performance degradation moving from MySQL 4.1 to version 5.
- The schema is denormalized more than "your average database design."
- Sharding is used to break the database into several smaller ones.
# Digg's usage pattern makes it easier for them to scale. Most people just view the front page and leave. Thus 98% of Digg's database accesses are reads. With this balance of operations they don't have to worry about the complex work of architecting for writes, which makes it a lot easier for them to scale.
# They had problems with their storage system telling them writes were on disk when they really weren't. Controllers do this to improve the appearance of their performance. But what it does is leave a giant data integrity whole in failure scenarios. This is really a pretty common problem and can be hard to fix, depending on your hardware setup.
# To lighten their database load they used the APC PHP accelerator MCache.
# Memcached is used for caching and memcached servers seemed to be spread across their database and application servers. A specialized daemon monitors connections and kills connections that have been open too long.
# You can configure PHP not parse and compile on each load using a combination of Apache 2’s worker threads, FastCGI, and a PHP accelerator. On a page's first load the PHP code is compiles so any subsequent page loads are very fast.
# MogileFS, a distributed file system, serves story icons, user icons, and stores copies of each story’s source. A distributed file system spreads and replicates files across a lot of disks which supports fast and scalable file access.
# A specialized Recommendation Engine service was built to act as their distributed graph database. Relational databases are not well structured for generating recommendations so a separate service was created. LinkedIn did something similar for their graph.
Lessons Learned
# The number of machines isn't as important what the pieces are and how they fit together.
# Don't treat the database as a hammer. Recommendations didn't fit will with the relational model so they made a specialized service.
# Tune MySQL through your database engine selection. Use InnoDB when you need transactions and MyISAM when you don't. For example, transactional tables on the master can use MyISAM for read-only slaves.
# At some point in their growth curve they were unable to grow by adding RAM so had to grow through architecture.
# People often complain Digg is slow. This is perhaps due to their large javascript libraries rather than their backend architecture.
# One way they scale is by being careful of which application they deploy on their system. They are careful not to release applications which use too much CPU. Clearly Digg has a pretty standard LAMP architecture, but I thought this was an interesting point. Engineers often have a bunch of cool features they want to release, but those features can kill an infrastructure if that infrastructure doesn't grow along with the features. So push back until your system can handle the new features. This goes to capacity planning, something the Flickr emphasizes in their scaling process.
# You have to wonder if by limiting new features to match their infrastructure might Digg lose ground to other faster moving social bookmarking services? Perhaps if the infrastructure was more easily scaled they could add features faster which would help them compete better? On the other hand, just adding features because you can doesn't make a lot of sense either.
# The data layer is where most scaling and performance problems are to be found and these are language specific. You'll hit them using Java, PHP, Ruby, or insert your favorite language here.
2008年10月10日星期五
Google Architecture
Update: Greg Linden points to a new Google article MapReduce: simplified data processing on large clusters. Some interesting stats: 100k MapReduce jobs are executed each day; more than 20 petabytes of data are processed per day; more than 10k MapReduce programs have been implemented; machines are dual processor with gigabit ethernet and 4-8 GB of memory.
Google is the King of scalability. Everyone knows Google for their large, sophisticated, and fast searching, but they don't just shine in search. Their platform approach to building scalable applications allows them to roll out internet scale applications at an alarmingly high competition crushing rate. Their goal is always to build a higher performing higher scaling infrastructure to support their products. How do they do that?
Information Sources
# Video: Building Large Systems at Google
# Google Lab: The Google File System
# Google Lab: MapReduce: Simplified Data Processing on Large Clusters
# Google Lab: BigTable.
# Video: BigTable: A Distributed Structured Storage System.
# Google Lab: The Chubby Lock Service for Loosely-Coupled Distributed Systems.
# How Google Works by David Carr in Baseline Magazine.
# Google Lab: Interpreting the Data: Parallel Analysis with Sawzall.
# Dare Obasonjo's Notes on the scalability conference.
Platform
# Linux
# A large diversity of languages: Python, Java, C++
What's Inside?
The Stats
# Estimated 450,000 low-cost commodity servers in 2006
# In 2005 Google indexed 8 billion web pages. By now, who knows?
# Currently there over 200 GFS clusters at Google. A cluster can have 1000 or even 5000 machines. Pools of tens of thousands of machines retrieve data from GFS clusters that run as large as 5 petabytes of storage. Aggregate read/write throughput can be as high as 40 gigabytes/second across the cluster.
# Currently there are 6000 MapReduce applications at Google and hundreds of new applications are being written each month.
# BigTable scales to store billions of URLs, hundreds of terabytes of satellite imagery, and preferences for hundreds of millions of users.
The Stack
Google visualizes their infrastructure as a three layer stack:
# Products: search, advertising, email, maps, video, chat, blogger
# Distributed Systems Infrastructure: GFS, MapReduce, and BigTable.
# Computing Platforms: a bunch of machines in a bunch of different data centers
# Make sure easy for folks in the company to deploy at a low cost.
# Look at price performance data on a per application basis. Spend more money on hardware to not lose log data, but spend less on other types of data. Having said that, they don't lose data.
Reliable Storage Mechanism with GFS (Google File System)
# Reliable scalable storage is a core need of any application. GFS is their core storage platform.
# Google File System - large distributed log structured file system in which they throw in a lot of data.
# Why build it instead of using something off the shelf? Because they control everything and it's the platform that distinguishes them from everyone else. They required:
- high reliability across data centers
- scalability to thousands of network nodes
- huge read/write bandwidth requirements
- support for large blocks of data which are gigabytes in size.
- efficient distribution of operations across nodes to reduce bottlenecks
# System has master and chunk servers.
- Master servers keep metadata on the various data files. Data are stored in the file system in 64MB chunks. Clients talk to the master servers to perform metadata operations on files and to locate the chunk server that contains the needed they need on disk.
- Chunk servers store the actual data on disk. Each chunk is replicated across three different chunk servers to create redundancy in case of server crashes. Once directed by a master server, a client application retrieves files directly from chunk servers.
# A new application coming on line can use an existing GFS cluster or they can make your own. It would be interesting to understand the provisioning process they use across their data centers.
# Key is enough infrastructure to make sure people have choices for their application. GFS can be tuned to fit individual application needs.
Do Something With the Data Using MapReduce
# Now that you have a good storage system, how do you do anything with so much data? Let's say you have many TBs of data stored across a 1000 machines. Databases don't scale or cost effectively scale to those levels. That's where MapReduce comes in.
# MapReduce is a programming model and an associated implementation for processing and generating large data sets. Users specify a map function that processes a key/value pair to generate a set of intermediate key/value pairs, and a reduce function that merges all intermediate values associated with the same intermediate key. Many real world tasks are expressible in this model. Programs written in this functional style are automatically parallelized and executed on a large cluster of commodity machines. The run-time system takes care of the details of partitioning the input data, scheduling the program's execution across a set of machines, handling machine failures, and managing the required inter-machine communication. This allows programmers without any experience with parallel and distributed systems to easily utilize the resources of a large distributed system.
# Why use MapReduce?
- Nice way to partition tasks across lots of machines.
- Handle machine failure.
- Works across different application types, like search and ads. Almost every application has map reduce type operations. You can precompute useful data, find word counts, sort TBs of data, etc.
- Computation can automatically move closer to the IO source.
# The MapReduce system has three different types of servers.
- The Master server assigns user tasks to map and reduce servers. It also tracks the state of the tasks.
- The Map servers accept user input and performs map operations on them. The results are written to intermediate files
- The Reduce servers accepts intermediate files produced by map servers and performs reduce operation on them.
# For example, you want to count the number of words in all web pages. You would feed all the pages stored on GFS into MapReduce. This would all be happening on 1000s of machines simultaneously and all the coordination, job scheduling, failure handling, and data transport would be done automatically.
- The steps look like: GFS -> Map -> Shuffle -> Reduction -> Store Results back into GFS.
- In MapReduce a map maps one view of data to another, producing a key value pair, which in our example is word and count.
- Shuffling aggregates key types.
- The reductions sums up all the key value pairs and produces the final answer.
# The Google indexing pipeline has about 20 different map reductions. A pipeline looks at data with a whole bunch of records and aggregating keys. A second map-reduce comes a long, takes that result and does something else. And so on.
# Programs can be very small. As little as 20 to 50 lines of code.
# One problem is stragglers. A straggler is a computation that is going slower than others which holds up everyone. Stragglers may happen because of slow IO (say a bad controller) or from a temporary CPU spike. The solution is to run multiple of the same computations and when one is done kill all the rest.
# Data transferred between map and reduce servers is compressed. The idea is that because servers aren't CPU bound it makes sense to spend on data compression and decompression in order to save on bandwidth and I/O.
Storing Structured Data in BigTable
# BigTable is a large scale, fault tolerant, self managing system that includes terabytes of memory and petabytes of storage. It can handle millions of reads/writes per second.
# BigTable is a distributed hash mechanism built on top of GFS. It is not a relational database. It doesn't support joins or SQL type queries.
# It provides lookup mechanism to access structured data by key. GFS stores opaque data and many applications needs has data with structure.
# Commercial databases simply don't scale to this level and they don't work across 1000s machines.
# By controlling their own low level storage system Google gets more control and leverage to improve their system. For example, if they want features that make cross data center operations easier, they can build it in.
# Machines can be added and deleted while the system is running and the whole system just works.
# Each data item is stored in a cell which can be accessed using a row key, column key, or timestamp.
# Each row is stored in one or more tablets. A tablet is a sequence of 64KB blocks in a data format called SSTable.
# BigTable has three different types of servers:
- The Master servers assign tablets to tablet servers. They track where tablets are located and redistributes tasks as needed.
- The Tablet servers process read/write requests for tablets. They split tablets when they exceed size limits (usually 100MB - 200MB). When a tablet server fails, then a 100 tablet servers each pickup 1 new tablet and the system recovers.
- The Lock servers form a distributed lock service. Operations like opening a tablet for writing, Master aribtration, and access control checking require mutual exclusion.
# A locality group can be used to physically store related bits of data together for better locality of reference.
# Tablets are cached in RAM as much as possible.
Hardware
# When you have a lot of machines how do you build them to be cost efficient and use power efficiently?
# Use ultra cheap commodity hardware and built software on top to handle their death.
# A 1,000-fold computer power increase can be had for a 33 times lower cost if you you use a failure-prone infrastructure rather than an infrastructure built on highly reliable components. You must build reliability on top of unreliability for this strategy to work.
# Linux, in-house rack design, PC class mother boards, low end storage.
# Price per wattage on performance basis isn't getting better. Have huge power and cooling issues.
# Use a mix of collocation and their own data centers.
Misc
# Push changes out quickly rather than wait for QA.
# Libraries are the predominant way of building programs.
# Some are applications are provided as services, like crawling.
# An infrastructure handles versioning of applications so they can be release without a fear of breaking things.
Future Directions for Google
# Support geo-distributed clusters.
# Create a single global namespace for all data. Currently data is segregated by cluster.
# More and better automated migration of data and computation.
# Solve consistency issues that happen when you couple wide area replication with network partitioning (e.g. keeping services up even if a cluster goes offline for maintenance or due to some sort of outage).
Lessons Learned
# Infrastructure can be a competitive advantage. It certainly is for Google. They can roll out new internet services faster, cheaper, and at scale at few others can compete with. Many companies take a completely different approach. Many companies treat infrastructure as an expense. Each group will use completely different technologies and their will be little planning and commonality of how to build systems. Google thinks of themselves as a systems engineering company, which is a very refreshing way to look at building software.
# Spanning multiple data centers is still an unsolved problem. Most websites are in one and at most two data centers. How to fully distribute a website across a set of data centers is, shall we say, tricky.
# Take a look at Hadoop (product) if you don't have the time to rebuild all this infrastructure from scratch yourself. Hadoop is an open source implementation of many of the same ideas presented here.
# An under appreciated advantage of a platform approach is junior developers can quickly and confidently create robust applications on top of the platform. If every project needs to create the same distributed infrastructure wheel you'll run into difficulty because the people who know how to do this are relatively rare.
# Synergy isn't always crap. By making all parts of a system work together an improvement in one helps them all. Improve the file system and everyone benefits immediately and transparently. If every project uses a different file system then there's no continual incremental improvement across the entire stack.
# Build self-managing systems that work without having to take the system down. This allows you to more easily rebalance resources across servers, add more capacity dynamically, bring machines off line, and gracefully handle upgrades.
# Create a Darwinian infrastructure. Perform time consuming operation in parallel and take the winner.
# Don't ignore the Academy. Academia has a lot of good ideas that don't get translated into production environments. Most of what Google has done has prior art, just not prior large scale deployment.
# Consider compression. Compression is a good option when you have a lot of CPU to throw around and limited IO.
Google is the King of scalability. Everyone knows Google for their large, sophisticated, and fast searching, but they don't just shine in search. Their platform approach to building scalable applications allows them to roll out internet scale applications at an alarmingly high competition crushing rate. Their goal is always to build a higher performing higher scaling infrastructure to support their products. How do they do that?
Information Sources
# Video: Building Large Systems at Google
# Google Lab: The Google File System
# Google Lab: MapReduce: Simplified Data Processing on Large Clusters
# Google Lab: BigTable.
# Video: BigTable: A Distributed Structured Storage System.
# Google Lab: The Chubby Lock Service for Loosely-Coupled Distributed Systems.
# How Google Works by David Carr in Baseline Magazine.
# Google Lab: Interpreting the Data: Parallel Analysis with Sawzall.
# Dare Obasonjo's Notes on the scalability conference.
Platform
# Linux
# A large diversity of languages: Python, Java, C++
What's Inside?
The Stats
# Estimated 450,000 low-cost commodity servers in 2006
# In 2005 Google indexed 8 billion web pages. By now, who knows?
# Currently there over 200 GFS clusters at Google. A cluster can have 1000 or even 5000 machines. Pools of tens of thousands of machines retrieve data from GFS clusters that run as large as 5 petabytes of storage. Aggregate read/write throughput can be as high as 40 gigabytes/second across the cluster.
# Currently there are 6000 MapReduce applications at Google and hundreds of new applications are being written each month.
# BigTable scales to store billions of URLs, hundreds of terabytes of satellite imagery, and preferences for hundreds of millions of users.
The Stack
Google visualizes their infrastructure as a three layer stack:
# Products: search, advertising, email, maps, video, chat, blogger
# Distributed Systems Infrastructure: GFS, MapReduce, and BigTable.
# Computing Platforms: a bunch of machines in a bunch of different data centers
# Make sure easy for folks in the company to deploy at a low cost.
# Look at price performance data on a per application basis. Spend more money on hardware to not lose log data, but spend less on other types of data. Having said that, they don't lose data.
Reliable Storage Mechanism with GFS (Google File System)
# Reliable scalable storage is a core need of any application. GFS is their core storage platform.
# Google File System - large distributed log structured file system in which they throw in a lot of data.
# Why build it instead of using something off the shelf? Because they control everything and it's the platform that distinguishes them from everyone else. They required:
- high reliability across data centers
- scalability to thousands of network nodes
- huge read/write bandwidth requirements
- support for large blocks of data which are gigabytes in size.
- efficient distribution of operations across nodes to reduce bottlenecks
# System has master and chunk servers.
- Master servers keep metadata on the various data files. Data are stored in the file system in 64MB chunks. Clients talk to the master servers to perform metadata operations on files and to locate the chunk server that contains the needed they need on disk.
- Chunk servers store the actual data on disk. Each chunk is replicated across three different chunk servers to create redundancy in case of server crashes. Once directed by a master server, a client application retrieves files directly from chunk servers.
# A new application coming on line can use an existing GFS cluster or they can make your own. It would be interesting to understand the provisioning process they use across their data centers.
# Key is enough infrastructure to make sure people have choices for their application. GFS can be tuned to fit individual application needs.
Do Something With the Data Using MapReduce
# Now that you have a good storage system, how do you do anything with so much data? Let's say you have many TBs of data stored across a 1000 machines. Databases don't scale or cost effectively scale to those levels. That's where MapReduce comes in.
# MapReduce is a programming model and an associated implementation for processing and generating large data sets. Users specify a map function that processes a key/value pair to generate a set of intermediate key/value pairs, and a reduce function that merges all intermediate values associated with the same intermediate key. Many real world tasks are expressible in this model. Programs written in this functional style are automatically parallelized and executed on a large cluster of commodity machines. The run-time system takes care of the details of partitioning the input data, scheduling the program's execution across a set of machines, handling machine failures, and managing the required inter-machine communication. This allows programmers without any experience with parallel and distributed systems to easily utilize the resources of a large distributed system.
# Why use MapReduce?
- Nice way to partition tasks across lots of machines.
- Handle machine failure.
- Works across different application types, like search and ads. Almost every application has map reduce type operations. You can precompute useful data, find word counts, sort TBs of data, etc.
- Computation can automatically move closer to the IO source.
# The MapReduce system has three different types of servers.
- The Master server assigns user tasks to map and reduce servers. It also tracks the state of the tasks.
- The Map servers accept user input and performs map operations on them. The results are written to intermediate files
- The Reduce servers accepts intermediate files produced by map servers and performs reduce operation on them.
# For example, you want to count the number of words in all web pages. You would feed all the pages stored on GFS into MapReduce. This would all be happening on 1000s of machines simultaneously and all the coordination, job scheduling, failure handling, and data transport would be done automatically.
- The steps look like: GFS -> Map -> Shuffle -> Reduction -> Store Results back into GFS.
- In MapReduce a map maps one view of data to another, producing a key value pair, which in our example is word and count.
- Shuffling aggregates key types.
- The reductions sums up all the key value pairs and produces the final answer.
# The Google indexing pipeline has about 20 different map reductions. A pipeline looks at data with a whole bunch of records and aggregating keys. A second map-reduce comes a long, takes that result and does something else. And so on.
# Programs can be very small. As little as 20 to 50 lines of code.
# One problem is stragglers. A straggler is a computation that is going slower than others which holds up everyone. Stragglers may happen because of slow IO (say a bad controller) or from a temporary CPU spike. The solution is to run multiple of the same computations and when one is done kill all the rest.
# Data transferred between map and reduce servers is compressed. The idea is that because servers aren't CPU bound it makes sense to spend on data compression and decompression in order to save on bandwidth and I/O.
Storing Structured Data in BigTable
# BigTable is a large scale, fault tolerant, self managing system that includes terabytes of memory and petabytes of storage. It can handle millions of reads/writes per second.
# BigTable is a distributed hash mechanism built on top of GFS. It is not a relational database. It doesn't support joins or SQL type queries.
# It provides lookup mechanism to access structured data by key. GFS stores opaque data and many applications needs has data with structure.
# Commercial databases simply don't scale to this level and they don't work across 1000s machines.
# By controlling their own low level storage system Google gets more control and leverage to improve their system. For example, if they want features that make cross data center operations easier, they can build it in.
# Machines can be added and deleted while the system is running and the whole system just works.
# Each data item is stored in a cell which can be accessed using a row key, column key, or timestamp.
# Each row is stored in one or more tablets. A tablet is a sequence of 64KB blocks in a data format called SSTable.
# BigTable has three different types of servers:
- The Master servers assign tablets to tablet servers. They track where tablets are located and redistributes tasks as needed.
- The Tablet servers process read/write requests for tablets. They split tablets when they exceed size limits (usually 100MB - 200MB). When a tablet server fails, then a 100 tablet servers each pickup 1 new tablet and the system recovers.
- The Lock servers form a distributed lock service. Operations like opening a tablet for writing, Master aribtration, and access control checking require mutual exclusion.
# A locality group can be used to physically store related bits of data together for better locality of reference.
# Tablets are cached in RAM as much as possible.
Hardware
# When you have a lot of machines how do you build them to be cost efficient and use power efficiently?
# Use ultra cheap commodity hardware and built software on top to handle their death.
# A 1,000-fold computer power increase can be had for a 33 times lower cost if you you use a failure-prone infrastructure rather than an infrastructure built on highly reliable components. You must build reliability on top of unreliability for this strategy to work.
# Linux, in-house rack design, PC class mother boards, low end storage.
# Price per wattage on performance basis isn't getting better. Have huge power and cooling issues.
# Use a mix of collocation and their own data centers.
Misc
# Push changes out quickly rather than wait for QA.
# Libraries are the predominant way of building programs.
# Some are applications are provided as services, like crawling.
# An infrastructure handles versioning of applications so they can be release without a fear of breaking things.
Future Directions for Google
# Support geo-distributed clusters.
# Create a single global namespace for all data. Currently data is segregated by cluster.
# More and better automated migration of data and computation.
# Solve consistency issues that happen when you couple wide area replication with network partitioning (e.g. keeping services up even if a cluster goes offline for maintenance or due to some sort of outage).
Lessons Learned
# Infrastructure can be a competitive advantage. It certainly is for Google. They can roll out new internet services faster, cheaper, and at scale at few others can compete with. Many companies take a completely different approach. Many companies treat infrastructure as an expense. Each group will use completely different technologies and their will be little planning and commonality of how to build systems. Google thinks of themselves as a systems engineering company, which is a very refreshing way to look at building software.
# Spanning multiple data centers is still an unsolved problem. Most websites are in one and at most two data centers. How to fully distribute a website across a set of data centers is, shall we say, tricky.
# Take a look at Hadoop (product) if you don't have the time to rebuild all this infrastructure from scratch yourself. Hadoop is an open source implementation of many of the same ideas presented here.
# An under appreciated advantage of a platform approach is junior developers can quickly and confidently create robust applications on top of the platform. If every project needs to create the same distributed infrastructure wheel you'll run into difficulty because the people who know how to do this are relatively rare.
# Synergy isn't always crap. By making all parts of a system work together an improvement in one helps them all. Improve the file system and everyone benefits immediately and transparently. If every project uses a different file system then there's no continual incremental improvement across the entire stack.
# Build self-managing systems that work without having to take the system down. This allows you to more easily rebalance resources across servers, add more capacity dynamically, bring machines off line, and gracefully handle upgrades.
# Create a Darwinian infrastructure. Perform time consuming operation in parallel and take the winner.
# Don't ignore the Academy. Academia has a lot of good ideas that don't get translated into production environments. Most of what Google has done has prior art, just not prior large scale deployment.
# Consider compression. Compression is a good option when you have a lot of CPU to throw around and limited IO.
订阅：
博文 (Atom)
博文
