这是一个创建于 275 天前的主题，其中的信息可能已经有所发展或是发生改变。
最近在做一个跟网络存储有关的项目涉及到 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<string> fileHashed = new LinkedList<string>();
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();
}
}
目前尚无回复
Select Language