Originally the foot-soldiers who ran shouting before an official's horse to clear the road. Han Yu contrasted their misery with the comfort of ministers in 《
符读书城南》: '
一为马前卒,
鞭背生虫蛆;
一为公与相,
潭潭府中居.' The figurative 'pawn running errands for a bigger power' is the sense that stuck.