Maximize number of backups that fit on backup drive

Question

This is an intrinsically "practical" question, but it leads to a well-defined mathematical problem. Let me start with the practical part:

I regularly back up my data. My backup strategy are differential backups, where the first backup is a full backup containing all files and subsequent backups are either full backups or differential backups, containing only data that has been added/changed since the last full backup.¹

My backup storage is limited to $C$. I use the term "snapshot" to refer to the data from either a full backup or a differential backup.

Question: After how many differential backups should I make a new full backup to maximize the number of snapshots I can squeeze in the storage capacity $C$?

Intuition: A full backup takes up more space than a differential backup, but the more data has been added since the last full backup, the larger becomes each additional differential backup. Therefore, there is a trade-off between an additional large full backup vs. many larger differential backups.

---

I tried to formalize my problem as follows:

Denote data that is newly added between $t-1$ and $t$ as $s(t)$ and let $s(0) = d_0$ (some constant, size of initial data). Ignore deletes, i.e. total data at time $\tilde{t}$ is $f(\tilde{t})=\sum_{t=0}^{\tilde{t}} s(t)$, which equals the size of a full backup at this time. The size of a differential backup ($d$) at time $\tilde{t}$ depends on the time of the last full backup $b$: $d(\tilde{t},b) = \sum_{t=b+1}^{\tilde{t}} s(t)$.

With 1 full backup and only differential backups afterwards, I am not running out of storage capacity $C$ as long as $T$ is small enough² such that $$f(0) + \sum_{\tilde{t}=1}^T d(\tilde{t}, 0) \leq C.$$

With 2 full backups, each followed by differential backups, $T_1$ must be small enough such that $$f(0) + \sum_{\tilde{t}=1}^{T_0} \Big[ d(\tilde{t}, 0) \Big] + f(T_0+1) + \sum_{\tilde{t}=T_0+2}^{T_1} d(\tilde{t}, T_0+1) \leq C.$$

I think the pattern becomes clear now:³ with $N$ full backups, $T_{N-1}$ must be small enough such that $$f(0) + \sum_{\tilde{t}=1}^{T_0} \Big[ d(\tilde{t}, 0) \Big] + \sum_{n=1}^{N-1} \Big[ f(T_{n-1}+1) + \sum_{\tilde{t}=T_{n-1}+2}^{T_n} d(\tilde{t}, T_{n-1}+1) \Big] \leq C. \tag{1} \label{eq:cond}$$

This leads to the ultimate question:

Which $N$ maximizes the largest $T_{N-1}$ for which equation $(\ref{eq:cond})$ holds?

I am not sure how to approach a solution to this problem, nor am I sure if further assumptions are needed to make progress. Maybe it is helpful to assume that the amount of new data in each period $s(t)$ is constant ($s(t) = \bar{s} ~ \forall ~ t$)?

Plugging my definitions of $f(\tilde{t})$ and $d(\tilde{t}, b)$ into equation $(\ref{eq:cond})$ yields: $$d_0 + \Big[ \sum_{\tilde{t}=1}^{T_0} \sum_{t=1}^{\tilde{t}} s(t) \Big] + \sum_{n=1}^{N-1} \Bigg[ \Big[ \sum_{t=0}^{T_{n-1}+1} s(t) \Big] + \Big[ \sum_{\tilde{t}=T_{n-1}+2}^{T_n} \sum_{t=T_{n-1}+2}^{\tilde{t}} s(t) \Big] \Bigg] \leq C, \tag{1'} \label{eq:cond-plugged-in}$$ but I do not know how to proceed from here.

Any help, either on tackling equation $(\ref{eq:cond-plugged-in})$ or completely different strategies to solve the problem are highly appreciated!

---

¹ Note that I am not referring to incremental backups, where each backup contains only the data since the previous incremental backup. Differential backups always contain all data since the last full backup.

² I assume that $C$ is large enough for at least 1 full and 1 differential backup.

³ To be more explicit, the conditions for 3 and 4 full backups are $$f(0) + \sum_{\tilde{t}=1}^{T_0} d(\tilde{t}, 0) + f(T_0+1) + \sum_{\tilde{t}=T_0+2}^{T_1} d(\tilde{t}, T_0+1) + f(T_1+1) + \sum_{\tilde{t}=T_1+2}^{T_2} d(\tilde{t}, T_1+1) \leq C,$$

$$f(0) + \sum_{\tilde{t}=1}^{T_0} d(\tilde{t}, 0) + f(T_0+1) + \sum_{\tilde{t}=T_0+2}^{T_1} d(\tilde{t}, T_0+1) + f(T_1+1) + \sum_{\tilde{t}=T_1+2}^{T_2} d(\tilde{t}, T_1+1) + f(T_2+1) + \sum_{\tilde{t}=T_2+2}^{T_3} d(\tilde{t}, T_2+1) \leq C.$$

Answer 1

Here is an easy dynamic programming solution which runs in $O(n^2)$ time, where $n$ is the number of updates to the data.

Create an array of partial sums $p$ of size $n$, such that $p[j]=\sum_{i=0}^{j}s(i)$ for all $0\leq j \leq n-1$.

For $0\leq k \leq t \leq n$ let $m[k][t]$ denote the minimum amount of storage required to store the first $k+1$ snapshots, knowing that the last full backup happened at snapshot $t$.

We have:

• $m[0][0] = s(0)$
• $m[i][i] = \min_{0\leq t \leq i-1}\{m[i-1][t]\}+p[i]$ for all $0<i\leq n-1$
• $m[i][t] = m[i-1][t] + (p[i]-p[t])$ for all $0\leq t<i \leq n-1$

These relations let you compute the whole matrix $m$ in $O(n^2)$ time. If you then let $m'[i] = \min_{0\leq t \leq i}\{m[i][t]\}$ denote the minimum amount of storage required to store the first $i+1$ snapshots for all $0\leq i \leq n-1$, the maximum number of snapshots you can store is one more than the maximum $i$ such that $m'[i]\leq C$.

Note that you can also compute $m'$ as you are computing $m$ and stop whenever you find that $m'[i] > C$. You can also easily adapt this approach to handle deletes.

---

Now to actually find out when you should do a full backup and when you should do a differential backup, there are two main approaches (essentially doing the same thing). One involves storing some additional information while computing $m'$, the other a sort of backtracking to figure out which choices led to the values of $m$ and $m'$ we end up with.

I prefer the former, and it goes like this:

• Let $q[i]$ denote the last time before $i$ we have to do a full backup in order to do store the first $i+1$ backups using $m'[i]$ storage. In other words, $q[i]=t$, where $0\leq t \leq i$ is the value which minimizes $m[i][t]$. You can compute $q$ while computing $m'$.
• To store the $i+1$ first snapshots with the least amount of storage, you need to do your last full backup at time $t=q[i]$ and minimize the storage required for the first $t$ snapshots. To minimize the storage of the first $t$ snapshots you need to do your last full backup at time $t'=q[t-1]$ and minimize the storage required for the first $t'$ snapshots. To minimize the storage of the first $t'$ snapshots you need to do your last full backup at time $t''=q[t'-1]$... And so on until you reach $0$, where you have no choice but to do a full backup.

The values $t,t',t'',t'''\ldots$ you will reach in this process tell you exactly when you have to do a full backup in order to store the first $i+1$ snapshots using $m'[i]$ storage (which is the minimum possible).