数据存储架构与技术：第五章

键值存储

• key-value Store 是以键值为基本单位进行数据存储、索引与查找的存储系统
• 基本操作包括put,get,delete
• 在实现上可大致分为存储模块和索引模块两部分，存储模块决定了记录的存放位置和写入格式，索引模块提供键记录于存储设备上的位置信息；键值索引有：
• 散列表Hash table
• B+树
• LSM（log structure merge）树
• 数据更新时有两种可选方式：in-place update, out-of-place update
• in-place update好处：无需更新索引，无需垃圾回收；不足：若块不足以容纳更新后的数据则无法进行（因为更新途中如果崩溃会导致数据不一致）
• 日志结构是out-of-place update的常用实现。所有插入，删除，更新操作都以日至记录的形式顺序写入存储介质；索引结构指向最新且有效的日志项；日志结构的数据会定期执行垃圾回收算法来回收无效日志所占据的空间。
• 崩溃一致性是指系统崩溃时仍然保持一致性（原子性，持久性）的特性，实现方法有：
• WAL：通过两次写操作实现，先写到别的存储位置上，以保证在任意时刻至少存在一个正确的版本。
• CoW: 影子页避免对任何块进行元帝更新。当需要对块进行更新时，总是分配新块写入，而后系统采用原子方法让新块代替旧块；