MizanGraph Processing System - 网络与信息系统.ppt

Mizan:Graph Processing System,xuejilonggmail.com,topics,Brief introduction on PregelEuroSys'13 paper: MizanOur ideas,Pregel,A System for Large-Scale Graph ProcessingMapreduce v.s. PregelHadoop v.s. Hama,Giraph.,Inside Pregel,Graph partitioning,Graph data,Worker1,Worker2,Workern,Pregel,output,Communication costLoad balance,Inside Pregel,Problems of Pregel,Worker1,Worker2,Workern,Worker1,Worker2,Workern,Computation,Communication,Mizan,A system for Dynamic Load Balancing in Large-scale Graph Processing,Load balance,Current method for load balance:Hash partition, Giraph, PregelRange partition, Min-cut partition(Metis) Sophisticated partitioning tech.,Mizan goal,building a system that is:AdaptiveAgnostic to the graph structurerequires no a priori knowledge of algorithm behavior,Graph algorithms,Stationary Graph Algorithms:matrix-vector multiplicationPageRankfinding weakly connected componentsNon-stationary Graph Algorithms:DMST: distributed minimal spanning treegraph queriesadvertisement propagation,Mizan,MonitoringMigration planning,Monitoring,Outgoing messageIncoming messageResponse time,Migration Planning,Five-step migration planning:Identify the source of imbalanceSelect the migration objectivePair over-utilized workers with under-utilized onesSelect vertices to migrateMigrate vertices,Step 1,Step 2,Select the migration objectiveOutgoing msg, incoming msg, response timeCompute correlation between:Outgoing msg and response timeIncoming msg and response timeDefault response time,Step 3,Step 4,Step 5,Migrate verticeswhen all workers arriving at migration barrierMigrated data:vertex IDStateedge information (friends list) the received messages it will process,Mizan,Mizan implementation,Mizan implementation,Challenge 1: Vertex Ownershiphuge dataFrequent vertex migrationTechs:Each vertex has a home_workerHDT maintain home_worker location,Mizan implementation,Challenge 2: Large Message Size,Evaluation,Experiments:Implemented Mizan using C+ and MPI12 machines with i5 processor 16GB RAM,Evaluation,Benchmarks:Static: disables any dynamic migrationWork Stealing (WS): Pregel versionMizan.,Evaluation,Static Mizan vs. Giraph:,Evaluation,PageRank on three system:,Evaluation,Migration costs:,Evaluation,Un-stationary algorithm:,Evaluation,Migration overhead:,Really?,Some arguable parts of Mizan:Cost: migration planning, multi global information synchronization(S1,S2,S3)Especially in S3, global order maintainingLarge data transferred in migrationMigration will lead more cross-communicationCentralized management bad than decentralized?Not friendly to graph mutation ,