## 2 Content Sharing Graphs
### Sparse Content Sharing Graph (SCSG)  
_SCSG_ graphs are graph structures where vertices represent storage objects (files, blocks, volumes, _etc._) and edges represent content shared between the connected vertices. To have a sparse and scalable graph, we require to use a minimum number of edges to represent sharing of the same content between files, that is, if the same chunk or group of chunks is shared by \(n\) files (vertices) we use \(n-1\) edges. We illustrate below the construction of such graphs. Our primary use of these graphs was in analysis and visualization of deduplication content distribution in storage systems. Figure 1 shows such an _SCSG_ graph representing the files (vertices) and the shared content (edges), for a folder on a Windows XP laptop. Identical files (full file duplicates) are represented only once and singleton files (files that do not share any chunks with other files) are not represented in the graph. From a total of \(8940\) files in the folder, removing the singletons and file duplicates we were left with only \(432\) files (vertices shown in Figure 1) that share some content so are connected by edges. A _component_ in the graph is a maximal subset of the vertices such that there is a path from every vertex in the subset to every other. The graph in Figure 1 has \(103\) components, most of them being small (two or three vertices), but there is a large component where the vertices are densely connected. The total number of edges connecting a vertex with its neighbors is the _degree_ of the vertex. Figure 1: Content sharing graph for a directory on Windows XP. To illustrate the construction of content sharing graphs we use a smaller folder (directory) on Windows XP consisting of 19 files (file IDs 1 to 19) with the content shown in Table 1. The file sizes vary between 20 and 60 bytes and they were created purposely to share content between themselves. To determine the content sharing between the files in a folder (or an entire file system) we first collect a \"trace\" by running a \"file scanner\" program that traverses each file of the folder (file system). The trace contains for each file a sequence of SHA1 content hashes, one hash for each chunk of the file. We use fixed chunk sizes, and for this example the chunk size is 4 bytes (for example, file #1 in Table 1 has 15 chunks and file #11 has 6 chunks, the last chunk in these files has the same content: \"L111\"). Note that in real applications the chunk sizes are much larger: 4 KB, 8 KB or larger. Given the 19 files with the content shown in Table 1 we can build an _SCSG_ graph as follows: each file is represented by a vertex, so we have \(\{v1,v2,v3,\ldots,v19\}\) vertices in our graph. Edges represent sharing of content between vertices and to have a minimum number of edges in the graph, we represent the shared content only once. Each edge has a _weight_ representing the number of bytes shared by connected vertices. Representing the shared content only once provides another important property of the _SCSG_ graphs: the deduplicated size of the folder (file system) is simply the sum of vertex (raw file) sizes minus the sum of connecting edge weights. In Table 1 we see that file #1 to file #10 share chunks 2 to 14 (that is 13 chunks \(\times\) 4 bytes = 52 bytes), and file #11 to file #19 share chunks 2 to 5 (20 bytes). One way to build an _SCSG_ graph with vertices \(\{v1,v2,v3,\ldots,v19\}\) is to connect \(v1\) with each vertex \(v2\) to \(v10\) by edges of weight \(52\) bytes, then to connect \(v11\) with each vertex \(v12\) to \(v19\) by edges of weight \(20\) bytes and finally to make explicit the sharing of the \"brown\" (last chunks in files #1 and #11) and \"yellow\" chunks (last chunks in files #5 and #15) by edges of weight \(4\) bytes. We get the _SCSG_ graph shown in Figure 2. We name this connection topology a STAR because from the \(n\) vertices sharing the same content we selected one (center of the star) to be connected with each other.