O rsync em geral será mais rápido que o cp ou o tar, porque o rsync somente transfere os arquivos que foram alterados, e com --partial ele somente transfere as partes de um arquivo que foi alterado.
Dito isto, o rsync funciona muito melhor se você sabe o que está fazendo backup e pode organizar as coisas para que o rsync não precise fazer tanto trabalho. Por exemplo, arquivos de log girados em / var / log funcionam muito melhor se você os rotaciona para um nome de arquivo com uma data, em vez de .0, .1, .2, etc.
Mais uma observação: Na sua pergunta você menciona / var / lib / mysql. Usando rsync para backup que é uma idéia muito ruim, use o mysqldump para obter um backup confiável. Se esse backup for muito grande para ser transferido com freqüência, use a replicação e o backup do mysql de um escravo. (Você ainda deve fazer um backup completo no master periodicamente, embora a replicação também possa falhar).