Smallest lithium battery backup?
CR2032 (20mm x 3.2mm) is the cheap standard for coin cells, if you want smaller there are several other CRxxyy type cells (e.g. CR1220) that are meant for this sort of thing.

The crudest design could just be a diode-OR with the power supply, before or after the regulator depending on the voltages/regulator type, otherwise you could implement something like in this article.