For the actual Video-On-Demand (VOD) service environment, we implement a cluster-based VOD server composed of general PCs and adopt the parallel processing for MPEG movies. For the implemented VOD server, a video block recovery mechanism is designed on the RAID-3 and the RAID-4 algorithms. However, without considering the architecture of cluster-based VOD server, the application of these basic RAID techniques causes the performance bottleneck of the internal network for recovery. To solve these problems, the new failure recovery mechanism based on the pipeline computing concept is proposed. The proposed method distributes the network traffics invoked by recovery operations and utilizes the available CPU computing power of cluster nodes.