Data to be backed up in a backup system

A backup system comprising:

• an acquisition engine to acquire, with a network interface device, a target data portion and other data portions to be backed up in the backup system;
• a target engine to determine a target insertion point in a fingerprint-based directed acyclic graph (DAG) for a target leaf node representing the target data portion, the DAG comprising non-leaf nodes and other leaf nodes representing, in a sorted order, the other data portions;
• a breakpoint engine to determine whether a hash of the target data portion is one of a plurality of predefined breakpoint values;
• a determine engine to, in response to determinations that the hash is one of the breakpoint values and that the target insertion point is between two of the other leaf nodes having a common non-leaf node parent, to split the common non-leaf node regardless of whether the common non-leaf node is full;
• an update engine to update the DAG, comprising inserting the target leaf node under one of the non-leaf nodes resulting from the split;
• and
• a store engine to store, in persistent storage of the backup system, each of the target and other data portions determined not to be previously stored in the backup system based on a comparison of the updated DAG, with or without further updates, with a previously stored DAG.

A method comprising:

• determining, by a client computing device, a target data portion and other data portions of the client computing device to be backed up in a remote backup system;
• determining a target insertion point in a hash tree for a target leaf node representing the target data portion, the hash tree comprising non-leaf nodes and other leaf nodes representing, in a sorted order, the other data portions;
• determining a target hash of the target data portion;
• in response to determinations that the target hash is one of a plurality of predefined breakpoint values and that the target insertion point is between two of the other leaf nodes having a common non-leaf node parent, splitting the common non-leaf node parent, regardless of whether the common non-leaf node is full;
• updating the hash tree, comprising inserting the target leaf node under a non-leaf node resulting from the split;
• iteratively providing one or more representative hashes of nodes of the hash tree, with or without further updates, to the remote backup system via a network interface device;
• and
• providing one or more of the target and other data portions to the remote backup system for storage based on comparison results received in response to the provided representative hash values.