共计 4576 个字符，预计需要花费 12 分钟才能阅读完成。
最近在做一个跟网络存储有关的项目涉及到 CDC，目前比较主流的算法除了前几年新提出的 FastCDC 以外就是基于拉宾卡普算法的 Rabin CDC，其基本思想是计算拉宾指纹并根据滚动哈希进行分块。目前比较典型的成熟应用就是海文的 Seafile，它的后端使用的是 Rabin CDC 并且网络上有很多针对其源代码的分析，例如：
[1] http://www.ilovecpp.com/2019/02/03/cdc/
[2] https://blog.csdn.net/cyk0620/article/details/120813255
我也找到了一个 Github 仓库基本上是把 Seafile 的分块部分单独拿出来做了个主程序的实现：
https://github.com/baixiangcpp/FileCDC
目前遇到的问题是，当我尝试将分块后的文件块再重新合并成一个文件，但发现这个文件跟原来的哈希不一致。具体来说，我使用 ubuntu 官网的 22.04 amd64 的系统镜像 iso 进行测试，源文件的 SHA256 哈希：
$ sha256sum ubuntu.iso
a435f6f393dda581172490eda9f683c32e495158a780b5a1de422ee77d98e909 ubuntu.iso
这与 Ubuntu 官网提供的 SHA256 校验值是一致的。但我尝试将分块后的块按照顺序重新合并后，得到的文件虽然大小与源文件相同，但 SHA256 哈希却变了:
$ sha256sum merged.iso
04a917c75a2d7733e0aabe6a5dbd0bbc875e8d3e63622c8d3c78b9058b92abd3 merged.iso
我自己用 C# 另外实现了一遍，也是针对同一个 iso 源文件，但合并出来的文件哈希也不一样，甚至分块结果（也就是分了多少块，每一块的 SHA1）和 C 语言的实现也不一样。
我用小黄鸭调试法检查了几遍也没能发现逻辑上的错误和问题，初步的断点调试和单元测发现拉宾指纹的计算部分 C# 的运算结果和 C 语言的运算结果没有区别，但文件分块出来不一样，合并起来也不一样，完全没有排查的思路。毕竟一个大文件会分出 500+ 块，也很难通过断点一个个查到底是哪里出了问题。
所以现在出现的现象包括：
1. 分块后合并导致哈希不一致（C 语言实现和 C# 实现都存在，但两种实现合并后的文件哈希也互不一致）
2. C# 的实现和 C 语言实现两种实现计算 Rabin 指纹的结果一致，但分块结果不完全一致，具体来说，有些 C# 分出来的块在 C 语言实现的结果中不存在，C 语言实现的结果一些块在 C# 结果中也没有，分出来的块数也不一样。但有一些块是一样的，SHA1 和大小都一致。
所以想问问大佬们：
1. 以上出现的两种情况是正常的吗？
2. 如果不正常，是由于什么原因造成的？
3. 如何调试这样的问题？打断点一步步调试？找拉宾指纹的分割点可是一个个字节找的，这恐怕不太现实
附：
1. C 语言的完整代码是基于 https://github.com/baixiangcpp/FileCDC，但改动了两个地方
一个是写块的函数，我把写在当前工作目录改成了卸载 chunks 文件夹中：
```c
int do_write_chunk (const unsigned char *checksum, const char *buf, int len)
{char chksum_str[41];
int fd;
int n;
rawdata_to_hex (checksum, chksum_str, 20);
/* Don't write if the block already exists. */
if (g_access (chksum_str, F_OK) == 0)
return 0;
// Make path "/workspace/chunks/{chksum_str}"
char path[100];
sprintf(path, "/workspaces/FileCDC-master/chunks/%s", chksum_str);
fd = open (path, O_WRONLY|O_CREAT,0666);
if (fd == -1) {printf ("Failed to open block %s.n", path);
return -1;
}
n = write (fd, buf, len);
if (n < 0) {printf ("Failed to write chunk %s.n", chksum_str);
close (fd);
return -1;
}
close(fd);
return 0;
}
```
另一个是我自己加的，合并分块的函数:
```c
void file_merge_cdc(CDCFileDescriptor* file_desc)
{
int i;
int fd;
char path[100];
char *buf = malloc(file_desc->block_max_sz);
int merged_file = open("merged.iso", O_WRONLY | O_APPEND, 0666);
if(merged_file == -1)
{printf("Failed to open merged file.n");
return;
}
for(i = 0; i < file_desc->block_nr; i++)
{char chksum_str[41];
rawdata_to_hex(file_desc->blk_sha1s + i * CHECKSUM_LENGTH, chksum_str, 20);
sprintf(path, "/workspaces/FileCDC-master/chunks/%s", chksum_str);
fd = open(path, O_RDONLY);
if(fd == -1)
{printf("Failed to open block %s.n", path);
return;
}
read(fd, buf, file_desc->block_max_sz);
close(fd);
write(merged_file, buf, file_desc->block_max_sz);
}
close(merged_file);
free(buf);
}
```
2. C# 的分块实现
```c#
public class RabingCDC
{private RabinChecksum rabinChecksum = new RabinChecksum();
private readonly int MinChunkSize = 1024 * 1024 * 6; // 6MB
private readonly int MaxChunkSize = 1024 * 1024 * 10; // 10MB
private readonly int AvarageChunkSize = 1024 * 1024 * 8; // 8MB
private LinkedList fileHashed = new LinkedList();
public async Task FileChunkCDC(Stream file)
{byte[] buffer = new byte[MaxChunkSize];
int cursor = MinChunkSize - 1;
int bufferDataTail = 0;
while (true)
{
int readSize = 4096; // 4KB
if (bufferDataTail < MinChunkSize)
{readSize = MinChunkSize - bufferDataTail + 4096;}
else if (MaxChunkSize - bufferDataTail < 4096)
{readSize = MaxChunkSize - bufferDataTail;}
int readed = await file.ReadAsync(buffer, bufferDataTail, readSize);
bufferDataTail += readed;
if (bufferDataTail < MinChunkSize || cursor>= bufferDataTail)
{
// The file is less than minimum chunk size
// Write the entire file as a block
WriteBlock(buffer.Take(readed).ToArray());
bufferDataTail = 0;
cursor = MinChunkSize - 1;
break;
}
uint fingerprint = 0;
while (cursor < bufferDataTail)
{if (cursor == MinChunkSize - 1)
{fingerprint = rabinChecksum.GetRabingChecksum(buffer.Skip(cursor).Take(48).ToArray());
}
else
{fingerprint = rabinChecksum.RabinRollingChecksum(fingerprint, 48, buffer[cursor - 48], buffer[cursor]);
}
if ((fingerprint & (AvarageChunkSize - 1)) == (0x0013 & (AvarageChunkSize - 1)) || cursor + 1 >= MaxChunkSize)
{WriteBlock(buffer.Take(cursor + 1).ToArray());
// Move the rest of the buffer to the beginning
Array.Copy(buffer, cursor, buffer, 0, bufferDataTail - cursor-1);
bufferDataTail -= cursor + 1;
cursor = MinChunkSize - 1;
break;
}
else
{cursor++;}
}
}
}
public void WriteBlock(byte[] block)
{
var path = "D:\Code\temp\cdc";
// Write block as a new file under the path, the file name is the SHA1 of the block
// Calcualte SHA1 of the block
byte[] sha1 = SHA1.Create().ComputeHash(block);
string fileName = BitConverter.ToString(sha1).Replace("-", "").ToLower();
fileHashed.AddLast(fileName);
File.WriteAllBytes(Path.Combine(path, fileName), block);
}
public async Task FileMergeCDC(string chunksFolderPath , string resultFilePath)
{var fileStream = File.OpenWrite(resultFilePath);
foreach (var file in fileHashed)
{var buffer = File.ReadAllBytes(Path.Combine(chunksFolderPath, file));
await fileStream.WriteAsync(buffer, 0, buffer.Length);
}
fileStream.Close();}
}
