ISP Server FarmBetter Surfing Through CachingJason Goggin, Erik Nordlander, Daniel Loreto, and Adam OlinerApril 1, 20041 IntroductionThe Internet places heavy demands on servers to provide a continuous, reliable, and efficient service toclients. Servers s hould be resilient to failures, able to handle very large numbers of requests, and able toanswer those requests quickly. A common way to provide these features is by having multiple networkedservers share their resources for the benefit of all. These servers are usually all housed in a single locationand are commonly called a server farm.Of particular interest to us are ISPs: client requests come through ISP routers and must be handled ap-propriately. The service provider is responsible for maintaining the connection to the Internet, and managingthe infrastructure that guarantees fast, reliable access. The ISP can achieve this, in part, through caching.The aim of this project is to provide the following deliverables for an ISP system:1. A specification for the system.2. High-level code im plementation of the system, emphasizing the tricky and novel parts of the system.3. The abstraction function and key invariants for the correctness of the code.4. Proofs of correctness for the code whenever appropriate.Among the different aspects we will consider in the design of our system are:• Scaling: How easy is it for our system to grow? Can we add new servers easily? How many serverscan we support?• Initialization: How is the system brought to its starting state? If a server needs to be restarted, howdo we initialize it so that it is in agreement with the rest of the system?• Partitioning of Data: How will the data in our farm be divided? Is data to be distributed amongseveral servers, or will each server be used for a specific type of data? Which servers will hold whatinformation?• Replication for Availability: If there is very important data for which we must guarantee availability,should we replicate it? How and where should we do that?• Persistent Caching: Should frequently requested data be “cached” on multiple servers to increaseperformance? Where do we place copies of the data in order to avoid bottlenecks and balance theload?• System Failures: How can our system fail? How can we recover from failed system components? Whatare the consequences of a failure?• Automation: The system should perform with minimal manual intervention. In particular when itcomes to load balancing and handling failures.In the next section, we describe our technical approach to the problem and discuss some basic ideasbehind our design.12 Technical ApproachThe system can be viewed as consisting of four components: routers, management servers, caching servers,and persistent content servers. This section describes each component. An overview of the system is shownin Figure 1.2.1 Router LevelThe router level is composed of the routers and network connections that bridge between the exterior networkand the caching servers. The routers forward incoming requests for data to the appropriate caching s ervers.Some such requests are sent around the caching servers and directly to the content servers. Their routingtables can be changed dynamically and are controlled by a set of management servers.2.2 Caching LevelThe cache level is the heart of our system. It consists of a number of stateless servers that cache datarequested by clients. These servers receive requests from the router level and determine, using time stamps,whether they should return their locally cached copy of the data to the client or retrieve a fresh copy fromthe server. Multiple caching servers may contain the same data, and some content servers may not have anycaching server assigned to them.There are a variety of replacement policies, but one ultimate goal of the strategy should be to minimizea cost function; most likely, this will relate to latency or bandwidth costs. The caching servers will cachedata in their persistent storage, as well, because disk latencies may b e exceeded by network latencies.2.3 Content LevelThis level consists only of the persistent servers. The job of each of these servers is simply to store the dataon a stable medium and serve material back to c lients and cache servers. These machines are not nec ess arilyunder our control, and some may be web servers across the world. Indeed, those are the kinds of machinesfor which our system will be most beneficial.2.4 Management LevelThe management servers control aspects of the routers and caching servers. The management servers samplerequests as they are sent to the routers. The goal of the management servers is to manage routing tables toensure that the caching servers are not overloaded, and that the appropriate data is c ached. Periodically, themanagement servers update routing tables and instruct the caching servers to move data among themselves.The management server is aware of what caching servers are responsible for what storage servers.Each management server is mirrored by a number of hot backup servers that process all incoming requestsalongside the primary server. Therefore, these backups always contain the current state of the system. Inthe event of a failure, the system can fail over quickly to another backup management server. When amanagement server is restored, it can copy the current state over from one of the active backups. Thesystem will not be able to function optimally for very long without any management servers, but will stillfunction.In a more geographically disperse system, there can be a number of management servers active at thesame time. For e xample, an ISP with locations in New York and Boston may wish to have cache serversactive in each location, which could each be controlled by their own collection of management servers.2InternetPersistent ServersServerServerServerServerServerServerPrimary & Back-upLoad BalancersStateless Cache MachinesRoutersRequests for UncachedDocumentsRequests for CachedDocumentsRequests from ClientsRouting TablesCaching InstructionsFiles Returned toClientsFiles returned toClientsFigure 1: An overview of the network architecture. The system is composed of three main components: therouters, the stateless cache machines, and the load balancers that manage the other two. Requests are madeby clients of the ISP. The persistent servers may either be local to the ISP or may be arbitrarily far away.The distant servers are the ones for which caching is most