A highly desirable feature in storage video applications is uniform video quality. Variable bit rate (VBR) coding has the potential to produce nearly constant quality throughout an entire movie. This can be defined as a bit allocation problem with a long-term constraint on distortion variation. We consider optimal bit allocation with multiple constraints including disk capacity and distortion bounds on the individual frames. We find the theoretical optimality conditions and propose a practical iterative solution based on Lagrangian methods. While minimizing both average distortion and distortion variation cannot be achieved simultaneously for a given bit budget, the proposed algorithms are able to efficiently trade-off between the two goals. The computational complexity of the exact rate-distortion (<i>R-D</i>) functions for real movies is addressed by a statistical <i>R-D</i> model proposed in this work. The model is formed by a rate-quantization (<i>R-Q</i>) function and the corresponding distortion-quantization (<i>D-Q</i>) function. A novel two-pass MPEG-2 VBR encoder based on the proposed algorithms is developed for coding with long-term nearly constant quality. Experimental results are promising and the encoder effectively achieves the fit-to-disc function and at the same time controls objective quality variation. By incorporating basic subjective coding techniques into the encoder significant visual quality improvement is observed during the preliminary subjective tests.