文章插图
读操作 1 徒劳地等待读操作 3 和读操作 2 填充感兴趣的缓存键时 ， 会经历一段荒谬的延迟 。
在冗长的写操作过程中 ， 可能会出现一种病态的情况 ， 读操作最终会轮流获得租约 ， 并查询记录系统 ， 结果却被一个写操作清除了 。 实际上 ， 这会序列化来自真实源的读取 ， 但不会消除重复数据 ， 最终会导致过高的读延迟和超时 ， 因为读需要等待轮流从真实源中获取所需的值 。
我们在 Box 的分布式关系数据服务中遇到了这个问题 ， 并想出了一些与之相关的解决方案 。 我们最终采用的方法是基于这样一种观点：任何正在等待租约的读操作都可以安全地使用持有租约的读操作检索到的值 ， 即使租约最终被写操作清除 ， 并且atomic_check_and_set失败 。 实际上 ， 如果某个读操作遇到了另一个读操作的租约 ， 则该读操作必须在写操作清除缓存值之前到达 ， 因此在确认写操作之前 ， 这两个读操作都可以返回由租约持有者检索到的值 ， 而不会牺牲读写（read-after-write）一致性 。 为了利用这一观点 ， 除了执行atomic_check_and_set尝试将根据真实源计算出来的值存储到缓存中之外 ， 获得租约的读操作还需将该值存储在缓存的其他位置 ， 从而可以被等待租约的读操作发现 。
使用流程图来说明该算法会变得复杂且难以阅读 ， 但下面是执行该算法的代码片段 。 该代码片段是用 Java 过程编写的 ， 旨在使高级方法更加清晰明了 ， 而没有考虑错误处理、编译时的安全性、可维护性等 。
public class LookasideCache {private CacheCluster cacheCluster;private LeaseUtils leaseUtils;/*** 使用 lookaside 缓存读取某个值** @param key 要返回谁的值* @param sourceOfTruthComputation 如果有必要的话 ，*用于从真实源中获取值的函数 。*计算被认为是昂贵的*并且会加大真实数据存储源的负载 。** @return a byte[] 表示与查找 key 相关联的值 。*/public byte[] read(byte[] key, Function sourceOfTruthComputation) {return read(key, sourceOfTruthComputation, Collections.EMPTY_SET);}/*** 用于上述 read 方法的私用辅助方法 ， 允许我们在堆栈上携带之前看到的租约集 **/private byte[] read(byte[] key,Function sourceOfTruthComputation,Set previouslySeenLeases) {// 首先查找所提供的 key 以及以前看到的所有租约 。List cacheKeysToLookUp = new ArrayList<>();cacheKeysToLookUp.add(key);for (Lease previouslySeenLease : previouslySeenLeases) {cacheKeysToLookUp.add(previouslySeenLease.getNonce());}List valuesFromCacheServer = cacheCluster.get(cacheKeysToLookUp);byte[] valueForKey = valuesFromCacheServer.remove(0);// 检查该值是否隐藏在我们前面看到的某个租约的后面 。for (byte[] valueForPreviouslySeenLease : valuesFromCacheServer) {if (valueForPreviouslySeenLease != null) {return valueForPreviouslySeenLease;}}if (valueForKey == null) {// 我们试着获取该 key 的租约 。Lease newLease = leaseUtils.createNew();boolean leaseAddSucceeded = cacheCluster.atomicAdd(key, newLease.getNonce());if (leaseAddSucceeded) {// 我们设法获取该 key 的租约 ， 这意味着需要我们去寻找真实源 ，// 然后用真实源里的值填充缓存 。byte[] valueFromSourceOfTruth = sourceOfTruthComputation.apply(key);boolean checkAndSetSuccceeded = cacheCluster.atomicCheckAndSet(key,newLease.getNonce(),valueFromSourceOfTruth);// 让我们使用租约的 nonce 作为 key ，并将我们计算的值与之关联 。cacheCluster.set(newLease.getNonce(), valueFromSourceOfTruth);return valueFromSourceOfTruth;} else {// 另一个请求比我们先获得了租约 。 让我们重试 。return read(key, sourceOfTruthComputation, previouslySeenLeases);}} else if (leaseUtils.isCacheValueLease(valueForKey)) {// 另一个缓存请求持有该 key 的租约 ，// 让我们给它一些时间来填满混存 ， 然后再重试 。sleep(100);previouslySeenLeases.add(leaseUtils.fromCacheValue(valueForKey));return read(key, sourceOfTruthComputation, previouslySeenLeases);} else {// 从缓存服务中获取值 ， 然后返回 。return valueForKey;}}private void sleep(int millis) {try {Thread.sleep(millis);} catch (InterruptedException e) {System.err.println("Sleep interrupted.");e.printStackTrace();}}}interface CacheCluster {/*** 从缓存集群获取键的列表 。* @param keys 要从缓存集群中获取键* @return byte[] 列表表示与提供的键相关联的值*返回的列表将与提供的键列表并行 ，* 换句话说 ， 与某个键关联的值在返回列表中的位置与键在键列表中的位置相同 。* 返回列表中的空值表示缓存未命中 。* 虽然这不是一个好的设计 API 的方法* 但对于这个算法的高层演示 ， 它能很好的运行 。*/List get(List keys);/*** 设置值与缓存集群中所提供的键的关联关系*/void set(byte[] key, byte[] value);/*** 当且仅当键尚未被设置时 ， 为该键设置所提供的值 。* 否则 ， 操作失败 。* @return 如果操作成功且设置了值 ， 则返回 true ， 否则返回 false 。*/boolean atomicAdd(byte[] key, byte[] value);/*** 当且仅当键刚好与 expectedValue 相关关联时 ， 为所提供的键设置 valueToSet 。* @return 如果操作成功且设置了值 ， 则返回 true ， 否则返回 false 。*/boolean atomicCheckAndSet(byte[] key, byte[] expectedValue, byte[] valueToSet);}interface Lease {byte[] getNonce();}interface LeaseUtils {Lease createNew();Lease fromCacheValue(byte[] nonce);boolean isCacheValueLease(byte[] value);}