在过去的几周中，开放式工程团队一直在建立我们称之为披萨烤箱的服务。该服务索引索引在定制的git存储库中，可用于基于这些服务来生成洞察力提交。这一切都使我们能够围绕开源项目速度，合并的时间，撰稿人的谁等等创建有趣的指标；通过索引和解析git提交！我们一直在尝试许多不同的模型，并为提高服务的性能和可用性创建了一个有趣的解决方案。

最初，作为概念证明，为了索引单个在git仓库中的索引，披萨烤箱将做最基本的事情：直接克隆仓库，并在其所有提交中分析，将新的承诺插入配置的数据库。

服务器上的热路径将包括此GO代码，该代码将Git Repo直接克隆到内存中：

inMemRepo, err := git.Clone(memory.NewStorage(), nil, &git.CloneOptions{
   URL:         URL,
   SingleBranch: true,
})

但是，显而易见的性能瓶颈：git克隆储物库可能非常慢。一个大的Git存储库可以包含数万个需要从远程源获取并未压缩的对象，甚至数千个（即使不是数十万个）。此外，每次从服务中询问GIT回购的重新封闭和重新分配是对计算资源的详尽浪费，尤其是如果已经存在索引的现有承诺。最后，需要通过具有大量昂贵的波动内存的计算实例来支持这项服务，以便同时克服许多不同的存储库。

必须有更好的方法！

输入LRU缓存：一种有效的方法，可以使经常查询的项目容易处理，而无需始终重建内存数据结构。 LRU缓存是一个最近使用的缓存，它驱逐尚未处理过或命中的项目。

您可以将其视为优先级的队列，在召唤时，队列成员会撞到线的正面。但是，落在线后面的队列成员最终会根据某些限制被驱逐出境。对于一个非常基本的示例，如果LRU缓存只能长10个成员，则每当有新的条目到达时，就会立即将其放在队列的前面，如果尺寸现在超过10。

实际上，通过两个常见的数据结构实现了LRU缓存：双重链接列表和一个哈希图。 hashmap在缓存中保持键 /值对的快速记录，并且双重链接的列表跟踪缓存中每个项目的定位。使用这两者，您可以有效地创建一个系统，其中可以快速检索哈希图中的项目，并由双链接列表的前后确定定位。

在GO中，我们可以使用标准库列表。列表作为双重链接列表，通常是hashmap：

type GitRepoLRUCache struct {
    // a doubly linked list to support the LRU cache behavior
    dll *list.List

    // a hashmap to support the LRU cache behavior
    hm map[string]*list.Element
}

在此实现LRU缓存中，“元素”确实可以是您想要的任何东西。在我们的情况下，我们决定在已经克隆的磁盘上跟踪GIT存储库。这围绕着通过克隆直接进入内存的大量内存的限制。相反，我们可以随着请求进来的磁盘或克隆新索引。

为此，我们创建了GitRepoFilePath struct，该结构表示一个键/值对，该键对指向磁盘上的filepath，其中存储库已经被克隆。

type GitRepoFilePath struct {
    // The key for the GitRepoFilePath key/value pair
    // generally, is the remote URL for the git 
    // repository
    key string

    // path is the value in the GitRepoFilePath
    // key/value and denotes the filepath
    // on-disk to the cloned git repository
    path string
}

使用LRU缓存，其数据结构和GitRepoFilePath作为缓存中的“元素”，在磁盘上经常使用的GIT存储库可以轻松，清洁，有效地更新，而无需重新粘结它们。

通常，有两种方法构成了lru cache的api：for and to。两者都可能很明显，但是根据其键从缓存中返回成员，将返回项目返回到双链接列表的前面。如果不存在缓存中的查询键，则获得零元素：

func (c *GitRepoLRUCache) Get(key string) *GitRepoFilePath {

put更加复杂，是魔术的大量发生的地方：当键/值对被放在缓存到缓存时，首先，缓存必须根据其成员驱逐成员标准。

但是，哪种驱逐标准对于git存储库的缓存有意义？好吧，借助将git存储库缓存到磁盘上的服务，显然要跟踪的指标是“自由空间”。部署此服务的人可以配置他们预期的免费磁盘量，他们期望始终需要可用，也可以配置配置他们想用作系统上的缓存的特定目录。这提供了一个很好的缓冲区，以防止磁盘完全填充并可能引起自己的问题。

在“ put”中，克隆新的存储库并将其放入缓存时，如果使用的磁盘的量超过了配置的“ Free Disk”空间，则LRU缓存将驱逐存储库并将其从磁盘中删除。此过程一直持续到配置的“ Free Disk”小于指定的高速缓存路径上的实际自由磁盘空间的数量。

在GO代码中，这是函数签名最终的外观：

func (c *GitRepoLRUCache) Put(key string) (*GitRepoFilePath, error)

这一切都可以在单个螺纹模型中效果很好，但是当您需要同时提供许多不同的请求时，它们会崩溃。同一请求同时提出请求时会发生什么？缓存如何同时处理多个请求？

有了几次调整和修改，我们可以使此缓存实现线程安全！

首先，我们需要使缓存操作成为原子。我们可以通过在缓存本身中添加互斥锁来做到这一点：

type GitRepoLRUCache struct {
    // A locking mutex for atomic operations
    lock sync.Mutex

    // a doubly linked list to support the LRU cache behavior
    dll *list.List

    // a hashmap to support the LRU cache behavior
    hm map[string]*list.Element
}

然后可以在原子缓存操作期间锁定缓存和解锁此静音。

让我们看一下所有这些方法的“获取”方法。当称为“ get”时，缓存的静音被锁定，允许操作继续。这个呼吁“ C.lock.lock（）”将阻塞，直到穆特克斯处于解锁状态，该状态指示其他线程在缓存上运行：

func (c *GitRepoLRUCache) Get(key string) *GitRepoFilePath {
    // Lock (and unlock when done) the cache's mutex
    c.lock.Lock()
    defer c.lock.Unlock()

    if element, ok := c.hm[key]; ok {
     // Cache hit
     c.dll.MoveToFront(element)
     return element.Value.(*GitRepoFilePath)
    }

    // Cache miss
    return nil
}

defer c.lock.Unlock()是确保在此功能范围关闭之前始终解锁互斥X的好方法。最糟糕的事情可能是如果发生挂钩，线程永远不会解锁缓存的静音，而其他线程则无法在缓存上操作，则在调用c.lock.Lock()时悬挂。

这确保了缓存本身是安全的，但是缓存中的各个元素呢？如果缓存操作本身真的很快，难道是否有可能在其GIT操作完成之前驱逐元素？在处理GIT委员会处理过程中对元素的驱逐真的很糟糕，因为这需要完全从磁盘中删除GIT回购，这完全会导致索引提交的无法恢复的状态。

一种解决方案是将高速缓存的静音延伸到未解锁，直到对单个元素进行处理。但是，敏锐的并发程序员将看到这将返回缓存到单个螺纹数据结构，而无需进行任何并行操作。

相反，单个的GitRepoFilePath元素也可以具有锁定的sutex：

type GitRepoFilePath struct {
    // Locking mutex for atomic file operations
    lock sync.Mutex

    // The key for the GitRepoFilePath key/value pair
    // generally, is the remote URL for the git 
    // repository
    key string

    // path is the value in the GitRepoFilePath
    // key/value and denotes the filepath
    // on-disk to the cloned git repository
    path string
}

现在，当从缓存操作中返回元素时，它们本身可以锁定以防止僵局或拆除，然后再完成处理。让我们再次查看“获取”方法，以查看在发生缓存命中时如何锁定单个元素的工作方式：

func (c *GitRepoLRUCache) Get(key string) *GitRepoFilePath {
    // Lock (and unlock when done) the cache's mutex
    c.lock.Lock()
    defer c.lock.Unlock()

    if element, ok := c.hm[key]; ok {
     // Cache hit
     c.dll.MoveToFront(element)

        // Lock the git repo filepath element
     element.Value.(*GitRepoFilePath).lock.Lock()
     return element.Value.(*GitRepoFilePath)
    }

    // Cache miss
    return nil
}

请注意，查询元素在返回之前已锁定。然后，后者，在呼叫者完成返回的GitRepoFilePath处理后，他们可以调用Done方法。这是一个简单，稀薄的包装器，围绕解锁互斥品，但确保任何GitRepoFilePath的消费者都可以清理他们的状态。

func (g *GitRepoFilePath) Done() {
    g.lock.Unlock()
}

在“ put”中和在驱逐过程中解锁这些静音的类似结构，都可以一起工作，可以安全地进行缓存及其元素。

在大规模上，使用这种LRU缓存方法，我们可以防止重新克服经常查询的Git存储库并大幅度加快服务的加速。确保查看此服务的开源代码以及此实现LRU CACHE的所有详细信息！

保持狡猾！ ð