内容寻址存储(Content-Addressed Storage)，简称CAS，是一种基于内容进行信息检索的存储方式，本文将对CAS进行技术简述，并通过具体的实例来解释CAS的原理和使用。
哈希表(hash table)
哈希表可以理解是使用hash作为key来指向具体value的数据结构。key具体可以通过hash的算法(CRC16\SHA256\SHA384\SHA512等)进行计算得到，因此存储具体的值如下：
storage[SHA512(key)] = value
取值也相当简单：
return storage[SHA512(key)]
看到这里你会发现，这不就是javascript\python里的Map \ dict 或Set结构吗，在javascript里更简单的实现就是一个object:
const storeage = {
key1: value1,
key2: value2
}
const value1 = storeage.key1
没错，事实上这就是内容寻址存储的本质，value可以理解是文件的具体内容，通过键值对的方式进行内容寻址，在算法上只需O(1)的时间复杂度就可以完成，效率很高！
传统地址寻址，如果内容位置发生变化或被删除，那就会导致我们通过物理地址访问内容失效，而且如果文件内容发生了改变，在最后查询到的结果是无法感知的。内容寻址存储就可以避免上述问题，因为内容寻址的key是通过内容的hash算法生成，hash key对应的值是具体的文件内容，一旦文件发生任何改变，，内容地址也会发生改变，同时内容地址存储的是文件的具体内容，即使源文件删除，也可以通过CAS找到原内容。
这里总结CAS的优点如下：
- 检索效率高
- 有hash算法的校验保证内容的完整性
- 文件永久存储
- 单例存储，因为文件是基于内容寻址，在整个CAS中，如果文件内容相同，那将会指向同一个内容地址
- 跨平台，CAS是一种文本内容存储方案，因此本质上也离不开文件读写的操作（读者可以从后面的例子感受），因此所有的操作系统都支持这种寻址方式，你可以使用任何你熟悉的技术和编程语言去实现CAS
下面我将通过几个常用的技术工具介绍他们是怎么使用CAS的。
GIT
git实现原理很大程度上依赖了文件内容寻址存储。通过在项目根目录.git文件夹下存储文件内容，实现了代码提交、分支切换、版本回退等一系列复杂功能。git将项目所有受控文件内容、文件的状态通过SHA1算法进行hash、压缩后存储在.git内。例如针对每个阶段的文件，计算其内容的SHA1值，再将SHA1值前两位作为二级目录，余下字符串作为文件名存储在objects文件夹内，文件的具体内容即为源文件内容:
./objects/4a/cde9ab6dd9bf439ff2cbddb47d5e96b1f2e3ad
./objects/61/d7f2fcb4d4aa0c55abb07f0cca6fd6ffa91e00
./objects/2e/c39aec17a9e53d21dcdafd8cdbe3ae7ada8c57
./objects/8b/35c7d4622c1aa11531166e4bd7d1901c9d5d2b
...
实现的核心源码如下:
const commitSha = getSHA1(jsonToString(commitObj));
const commitFilename = workSpace() + '/.gito/objects/' + commitSha.substring(0, 2) + '/' + commitSha.substring(2);
const commitContent = compress(jsonToString(commitObj));
shell.mkdir(workSpace() + '/.gito/objects/' + commitSha.substring(0, 2));
fs.writeFile(commitFilename, commitContent, (err) => {
...
})
objects可以理解是git的数据库，里面存储的每个文件就是数据库的实际数据。git会将每个文件内容、目录树结构都进行内容寻址，在适当的场合就会直接通过内容查找到对应的状态。例如需要将当前git仓库回退到某个版本，git会通过commit号查到对应当时commit的目录树结构，再从目录树结构的文件SHA1地址从objects文件夹内寻找匹配的文件内容，将文件的内容还原到对应的文件中，从而达到”时光穿梭”的效果。
具体实现的源码大致如下：
// 1.读取head
getHead().then(ref => {
// 2. 遍历读取objects文件夹
readfiles(`${workSpace()}/.gito/objects/`, {
// 3.查找commit
commitSearchPath = `${workSpace()}/.gito/objects/${commitData.substring(0, 2)}/${commitData.substring(2)}`;
CommitCon = parseJson(files[commitSearchPath].content);
tree = CommitCon.tree;
// 4.查找tree
treeSearchPath = `${workSpace()}/.gito/objects/${tree.substring(0, 2)}/${tree.substring(2)}`;
// 5.获取blob内容，还原
BlobCon = parseJson(files[blobSearchPath].content);
fs.writeFile(filename, BlobCon.content, (err, data) => {
// ...
})
})
})
关于git的细节原理可以查看我之前写的另一篇文章从零开发一个微型Git
PNPM
pnpm通过将模块统一存放在pnpm/store再将项目内具体使用的依赖通过硬链接的方式引入到项目node_modules中，从而实现了依赖的缓存和共享，提升了npm模块安装的速度和节省了磁盘空间，在pnpm/store也同样使用了CAS技术存储。
使用pnpm store path查看pnpm的存储目录:
$ pnpm store path
/Users/lijiahao/Library/pnpm/store/v3
pnpm/store/v3的目录结构如下：
./files/00/0af4fc03d2ecf7155b911e07941ea071519cc573fc911548cdad0701587a3617d6dc9954610260c3d1c421adc4799ccec5835ec14b994d5fc5baa8a6f83e0a
./files/00/0b3e3b523861e25ab1b971c8ab5960db76fc8ebdb3c8735dadc228fc8ead180111a87864d2c29dc209c3781da5427ed690c7eba5193b5610937dc4fac02e36
./files/0a/1b821be818c3903a3d59166f11b2d292debb93c5d1375a588019bfb29f9b6ed9d111e3087330e3cdf9cbf46768e57de293fab7a80bba50dac4ea9961571e9f
./files/0b/0b25eee67f9ee4949dda96a00f1b42e76d57a13434caf97b67f49db91168a40734e3e3e4673d48703e760591232bd97ebaeecb4221a3a711ca953828fe2de6
可以看到pnpm的store存储和git的objects存储结构很像，也是采用了hash值前两位作为二级目录，余下hash值作为文件名。打开store内的文件，发现pnpm并没有对文件内容做压缩，看到的直接是npm包文件的源码，因此pnpm以store内存储的文件内容进行文件硬链接。
我们来通过pnpm的源码来看下文件名那一长串字符串是怎么来的。pnpm关于CAS的核心代码都集中在@pnpm/cafs模块内，看到生成文件寻址文件的源码如下：
// packages/cafs/src/index.ts
async function addBufferToCafs (
writeBufferToCafs: WriteBufferToCafs,
buffer: Buffer,
mode: number
): Promise<FileWriteResult> {
// 通过ssir生成唯一的索引，类似git的SHA1
const integrity = ssri.fromData(buffer)
console.log('integrity:', integrity)
// Integrity {
// sha512: [
// Hash {
// source: 'sha512-7xeEGq2LfXfO2TCZlf6syJO/KCc1Vj/p08DX8Cj/+X5MH7DNlG42Na8bLscPDjGNo18GWNNP6QGsLgR6+Djaig==',
// digest: '7xeEGq2LfXfO2TCZlf6syJO/KCc1Vj/p08DX8Cj/+X5MH7DNlG42Na8bLscPDjGNo18GWNNP6QGsLgR6+Djaig==',
// algorithm: 'sha512',
// options: []
// }
// ]
// }
// fileDest是最终的索引目录名
// eg: 8f/4513441...
const fileDest = contentPathFromHex(isExecutable ? 'exec' : 'nonexec', integrity.hexDigest())
const checkedAt = await writeBufferToCafs(
buffer,
fileDest,
isExecutable ? 0o755 : undefined,
integrity
)
return { checkedAt, integrity }
})
ssri是实现pnpm strore模块文件内容生成唯一hash key的核心模块。通过计算文件内容的integrity，再将integrity进行base64编码，转换为16进制，就是pnpm strore存储的那一长串文件的文件名。
大家可能会注意到package-lock.json内每个包也有integrity字段，其实这是W3C规定的标准webappsec-subresource-integrity，目的是保证用户下载npm模块的完整性和准确性。
integrity由两部分组成: 加密hash函数-摘要dgest，其中：
dgest=base64(hashfn(content))
ssri的实现如下:
hexDigest () {
return this.digest && Buffer.from(this.digest, 'base64').toString('hex')
}
加密hash函数可以是：sha512/sha384/sha256/sha1，ssri默认使用的是sha512。
pnpm的寻址也很简单，即在下载npm模块时会获得模块(通常是tgz的压缩包)的integrity，再进行解压通过ssri计算里面每个文件的integrity，如果pnpm/store内已经缓存过这个模块，那么将直接通过ssri解析integraty获得文件内容的具体路径，对这个文件进行硬链接，pnpm的解析源码如下：
// packages/cafs/src/getFilePathInCafs.ts
function contentPathFromIntegrity (
integrity: string | IntegrityLike,
fileType: FileType
) {
const sri = ssri.parse(integrity, { single: true })
return contentPathFromHex(fileType, sri.hexDigest())
}
function contentPathFromHex (fileType: FileType, hex: string) {
const p = path.join(hex.slice(0, 2), hex.slice(2))
switch (fileType) {
case 'exec':
return `${p}-exec`
case 'nonexec':
return p
case 'index':
return `${p}-index.json`
}
}
文件共享服务
最后再说一下非开发工具里使用到CAS的场景，那就是我们常见的网盘系统。常见的网盘中通常会放置许多超大文件，如果每个用户都存储一份，那云存储主机是承受不了那么多重复的大文件的，这时候内容寻址存储就排上用场了，比如一个电影、音乐即使名字不一样，但内容也是可能相同的，把内容相同的文件通过hash计算后存储到公共文件寻址区，通过文件内容寻址+硬链接，可以让多个用户重复共享一个文件真实内容(即使文件名不一样)。
总结
本文通过git、pnpm、网盘系统这几个实例介绍内容寻址存储(CAS)在实际场景的使用，希望可以让读者了解CAS的优点和适合场景，在自己的开发中能巧妙利用文件寻址存储提升自己的发开体验。
（完）
