//---------------------------------------------------------- -*- Mode: C++ -*-// $Id: LayoutManager.h 214 2008-11-05 22:15:43Z sriramsrao $ //// Created 2006/06/06// Author: Sriram Rao//// Copyright 2008 Quantcast Corp.// Copyright 2006-2008 Kosmix Corp.//// This file is part of Kosmos File System (KFS).//// Licensed under the Apache License, Version 2.0// (the "License"); you may not use this file except in compliance with// the License. You may obtain a copy of the License at//// http://www.apache.org/licenses/LICENSE-2.0//// Unless required by applicable law or agreed to in writing, software// distributed under the License is distributed on an "AS IS" BASIS,// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or// implied. See the License for the specific language governing// permissions and limitations under the License.//// \file LayoutManager.h// \brief Layout manager is responsible for laying out chunks on chunk// servers.  Model is that, when a chunkserver connects to the meta// server, the layout manager gets notified; the layout manager then// uses the chunk server for data placement.////----------------------------------------------------------------------------#ifndef META_LAYOUTMANAGER_H#define META_LAYOUTMANAGER_H#include <map>#include <tr1/unordered_map>#include <vector>#include <set>#include <sstream>#include "kfstypes.h"#include "meta.h"#include "queue.h"#include "ChunkServer.h"#include "LeaseCleaner.h"#include "ChunkReplicator.h"#include "libkfsIO/Counter.h"namespace KFS{	///	/// For disk space utilization balancing, we say that a server	/// is "under utilized" if is below XXX% full; we say that a server	/// is "over utilized" if it is above YYY% full.  For rebalancing, we	/// move data from servers that are over-utilized to servers that are	/// under-utilized.  These #'s are intentionally set conservatively; we	/// don't want the system to constantly move stuff between nodes when	/// there isn't much to be gained by it.	///	const float MIN_SERVER_SPACE_UTIL_THRESHOLD = 0.3;	const float MAX_SERVER_SPACE_UTIL_THRESHOLD = 0.9;	/// Model for leases: metaserver assigns write leases to chunkservers;	/// clients/chunkservers can grab read lease on a chunk at any time.	/// The server will typically renew unexpired leases whenever asked.	/// As long as the lease is valid, server promises not to chnage	/// the lease's version # (also, chunk won't disappear as long as	/// lease is valid).	struct LeaseInfo {		LeaseInfo(LeaseType t, int64_t i): leaseType(t), leaseId(i)		{			time(&expires);			// default lease time of 1 min			expires += LEASE_INTERVAL_SECS;		}		LeaseInfo(LeaseType t, int64_t i, ChunkServerPtr &c):			leaseType(t), leaseId(i), chunkServer(c)		{			time(&expires);			// default lease time of 1 min			expires += LEASE_INTERVAL_SECS;		}		static bool IsValidLease(const LeaseInfo &l)		{			time_t now = time(0);			return now <= l.expires;		}		static bool IsValidWriteLease(const LeaseInfo &l)		{			return (l.leaseType == WRITE_LEASE) &&				IsValidLease(l);		}		LeaseType leaseType;		int64_t leaseId;		// set for a write lease		ChunkServerPtr chunkServer;		time_t expires;	};	// Given a chunk-id, where is stored and who has the lease(s)	struct ChunkPlacementInfo {		ChunkPlacementInfo() :			fid(-1), ongoingReplications(0) { }		// For cross-validation, we store the fid here.  This		// is also useful during re-replication: given a chunk, we		// can get its fid and from all the attributes of the file		fid_t fid;		/// is this chunk being (re) replicated now?  if so, how many		int ongoingReplications;		std::vector<ChunkServerPtr> chunkServers;		std::vector<LeaseInfo> chunkLeases;	};	// To support rack-aware placement, we need an estimate of how much	// space is available on each given rack.  Once the set of candidate	// racks are ordered, we walk down the sorted list to pick the	// desired # of servers.  For ordering purposes, we track how much space	// each machine on the rack exports and how much space we have parceled	// out; this gives us an estimate of availble space (we are	// over-counting because the space we parcel out may not be fully used).	class RackInfo {		uint32_t mRackId;		uint64_t mTotalSpace;		uint64_t mAllocSpace;		// set of servers on this rack		std::vector<ChunkServerPtr> mServers;	public:		RackInfo(int id) : mRackId(id), mTotalSpace(0), mAllocSpace(0) { }		inline uint32_t id() const {			return mRackId;		}		void clear() {			mTotalSpace = mAllocSpace = 0;		}		void addServer(ChunkServerPtr &s) {			mTotalSpace += s->GetTotalSpace();			mAllocSpace += s->GetUsedSpace();			mServers.push_back(s);		}		void removeServer(ChunkServer *server) {			std::vector <ChunkServerPtr>::iterator iter;			iter = find_if(mServers.begin(), mServers.end(),					ChunkServerMatcher(server));			if (iter == mServers.end())				return;			mTotalSpace -= server->GetTotalSpace();			mAllocSpace -= server->GetUsedSpace();			mServers.erase(iter);		}		void computeSpace() {			clear();			for(std::vector<ChunkServerPtr>::iterator iter = mServers.begin();				iter != mServers.end(); iter++) {				ChunkServerPtr s = *iter;				mTotalSpace += s->GetTotalSpace();				mAllocSpace += s->GetUsedSpace();			}		}		const std::vector<ChunkServerPtr> &getServers() {			return mServers;		}		uint64_t availableSpace() const {			if (mTotalSpace < mAllocSpace)				// paranoia...				return 0;			return mTotalSpace - mAllocSpace;		}		// want to sort in decreasing order so that racks with more		// space are at the head of list (and so, a node from them will		// get chosen).		bool operator < (const RackInfo &other) const {			uint64_t mine;			mine = availableSpace();			if (mine == 0)				return false;			return mine < other.availableSpace();		}	};	// Functor to enable matching of a rack-id with a RackInfo	class RackMatcher {		uint32_t id;	public:		RackMatcher(uint32_t rackId) : id(rackId) { }		bool operator()(const RackInfo &rack) const {			return rack.id() == id;		}	};	// chunkid to server(s) map	typedef std::map <chunkId_t, ChunkPlacementInfo > CSMap;	typedef std::map <chunkId_t, ChunkPlacementInfo >::const_iterator CSMapConstIter;	typedef std::map <chunkId_t, ChunkPlacementInfo >::iterator CSMapIter;#if 0	typedef std::tr1::unordered_map <chunkId_t, ChunkPlacementInfo > CSMap;	typedef std::tr1::unordered_map <chunkId_t, ChunkPlacementInfo >::const_iterator CSMapConstIter;	typedef std::tr1::unordered_map <chunkId_t, ChunkPlacementInfo >::iterator CSMapIter;#endif	// candidate set of chunks whose replication needs checking	typedef std::set <chunkId_t> CRCandidateSet;	typedef std::set <chunkId_t>::iterator CRCandidateSetIter;	//	// For maintenance reasons, we'd like to schedule downtime for a server.	// When the server is taken down, a promise is made---the server will go	// down now and come back up by a specified time. During this window, we	// are willing to tolerate reduced # of copies for a block.  Now, if the	// server doesn't come up by the promised time, the metaserver will	// initiate re-replication of blocks on that node.  This ability allows	// us to schedule downtime on a node without having to incur the	// overhead of re-replication.	//	struct HibernatingServerInfo_t {		// the server we put in hibernation		ServerLocation location;		// the blocks on this server		CRCandidateSet blocks;		// when is it likely to wake up		time_t sleepEndTime;	};        ///        /// LayoutManager is responsible for write allocation:        /// it determines where to place a chunk based on metrics such as,        /// which server has the most space, etc.  Will eventually be        /// extend this model to include replication.        ///        /// Allocating space for a chunk is a 3-way communication:        ///  1. Client sends a request to the meta server for        /// allocation        ///  2. Meta server picks a chunkserver to hold the chunk and        /// then sends an RPC to that chunkserver to create a chunk.        ///  3. The chunkserver creates a chunk and replies to the        /// meta server's RPC.        ///  4. Finally, the metaserver logs the allocation request        /// and then replies to the client.        ///        /// In this model, the layout manager picks the chunkserver        /// location and queues the RPC to the chunkserver.  All the        /// communication is handled by a thread in NetDispatcher        /// which picks up the RPC request and sends it on its merry way.        ///	class LayoutManager {	public:		LayoutManager();		virtual ~LayoutManager() { }                /// A new chunk server has joined and sent a HELLO message.                /// Use it to configure information about that server                /// @param[in] r  The MetaHello request sent by the                /// new chunk server.		void AddNewServer(MetaHello *r);                /// Our connection to a chunkserver went down.  So,                /// for all chunks hosted on this server, update the                /// mapping table to indicate that we can't                /// get to the data.                /// @param[in] server  The server that is down		void ServerDown(ChunkServer *server);		/// A server is being taken down: if downtime is > 0, it is a		/// value in seconds that specifies the time interval within		/// which the server will connect back.  If it doesn't connect		/// within that interval, the server is assumed to be down and		/// re-replication will start.		int RetireServer(const ServerLocation &loc, int downtime);                /// Allocate space to hold a chunk on some                /// chunkserver.                /// @param[in] r The request associated with the                /// write-allocation call.                /// @retval 0 on success; -1 on failure		int AllocateChunk(MetaAllocate *r);		/// A chunkid has been previously allocated.  The caller		/// is trying to grab the write lease on the chunk. If a valid		/// lease exists, we return it; otherwise, we assign a new lease,		/// bump the version # for the chunk and notify the caller.		///                /// @param[in] r The request associated with the                /// write-allocation call.		/// @param[out] isNewLease  True if a new lease has been		/// issued, which tells the caller that a version # bump		/// for the chunk has been done.                /// @retval status code		int GetChunkWriteLease(MetaAllocate *r, bool &isNewLease);                /// Delete a chunk on the server that holds it.                /// @param[in] chunkId The id of the chunk being deleted		void DeleteChunk(chunkId_t chunkId);                /// A chunkserver is notifying us that a chunk it has is		/// corrupt; so update our tables to reflect that the chunk isn't		/// hosted on that chunkserver any more; re-replication will take		/// care of recovering that chunk.                /// @param[in] r  The request that describes the corrupted chunk		void ChunkCorrupt(MetaChunkCorrupt *r);                /// Truncate a chunk to the desired size on the server that holds it.                /// @param[in] chunkId The id of the chunk being                /// truncated		/// @param[in] sz    The size to which the should be                /// truncated to.		void TruncateChunk(chunkId_t chunkId, off_t sz);		/// Handlers to acquire and renew leases.  Unexpired leases		/// will typically be renewed.		int GetChunkReadLease(MetaLeaseAcquire *r);		int LeaseRenew(MetaLeaseRenew *r);		/// Handler to let a lease owner relinquish a lease.		int LeaseRelinquish(MetaLeaseRelinquish *r);		/// Is a valid lease issued on any of the chunks in the		/// vector of MetaChunkInfo's?		bool IsValidLeaseIssued(const std::vector <MetaChunkInfo *> &c);                /// Add a mapping from chunkId -> server.                /// @param[in] chunkId  chunkId that has been stored                /// on server c                /// @param[in] fid  fileId associated with this chunk.                /// @param[in] c   server that stores chunk chunkId.                ///   If c == NULL, then, we update the table to                /// reflect chunk allocation; whenever chunk servers                /// start up and tell us what chunks they have, we                /// line things up and see which chunk is stored where.		void AddChunkToServerMapping(chunkId_t chunkId, fid_t fid, ChunkServer *c);		/// Remove the mappings for a chunk.                /// @param[in] chunkId  chunkId for which mapping needs to be nuked.		void RemoveChunkToServerMapping(chunkId_t chunkId);