Rust中的缓存

22-06-17 banq

在这篇文章中,我将描述如何在 Rust 中实现缓存。它的灵感来自我最近在 nearcore 上进行的两个重构(nearcore#6549,nearcore#6811)。根据这个经验,似乎错误地实现缓存是相当容易的,并且在那里犯错有“溢出”的风险,并且有点破坏应用程序的整体架构

让我们从一个带有一些配置和数据库的应用程序的假想设置开始:

struct App {
  config: Config,
  db: Db,
}

数据库是一个无类型的键值存储:

impl Db {
  pub fn load(&self, key: &[u8]) -> io::Result<Option<Vec<u8>>> {
    ...
  }
}

并且App封装数据库并提供对特定域的类型访问Widget:


#[derive(serde::Serialize, serde::Deserialize)]
struct Widget {
  title: String,
}

impl App {
  pub fn get_widget(
    &self,
    id: u32,
  ) -> io::Result<Option<Widget>> {
    let key = id.to_be_bytes();
    let value = match self.db.load(&key)? {
      None => return Ok(None),
      Some(it) => it,
    };

    let widget: Widget =
      bincode::deserialize(&value).map_err(|it| {
        io::Error::new(io::ErrorKind::InvalidData, it)
      })?;

    Ok(Some(widget))
  }
}

现在,为了争论,我们假设数据库访问和后续的反序列化成本很高,并且我们想在数据库前面添加一个 Widget 缓存。面向数据的思维会迫使我们摆脱反序列化步骤,但这次我们不会追求这个想法。

我们将使用一个简单HashMap的缓存:

struct App {
  config: Config,
  db: Db,
  cache: HashMap<u32, Widget>,
}

我们需要修改get_widget方法以从缓存中返回值,如果有的话:

impl App {
  pub fn get_widget(
    &mut self,
    id: u32,
  ) -> io::Result<Option<&Widget>> {

    if self.cache.contains_key(&id) {
      let widget = self.cache.get(&id).unwrap();
      return Ok(Some(widget));
    }

    let key = id.to_be_bytes();
    let value = match self.db.load(&key)? {
      None => return Ok(None),
      Some(it) => it,
    };
    let widget: Widget =
      bincode::deserialize(&value).map_err(|it| {
        io::Error::new(io::ErrorKind::InvalidData, it)
      })?;

    self.cache.insert(id, widget);
    let widget = self.cache.get(&id).unwrap();

    Ok(Some(widget))
  }
}

最大的变化是&mut self. 即使在阅读小部件时,我们也需要修改cache,而获得该功能的最简单方法是要求独占引用。

我想争辩说,这条阻力最小的道路不会通向一个好地方。以下形状的方法存在许多问题:

fn get(&mut self) -> &Widget

首先,这些方法相互冲突。例如,以下代码将不起作用,因为我们将尝试以独占方式借用该应用两次。

let app: &mut App = ...;
let w1 = app.get_widget(1)?;
let w2 = app.get_widget(2)?;


第二,&mut方法与方法相冲突&。天真地,看起来,当get_widget 返回一个共享引用时,我们应该能够调用&方法。所以,人们可以期待这样的事情:

let w: &Widget = app.get_widget(1)?.unwrap();
let c: &Color = &app.config.main_color;


不幸的是,它并没有。Rust借贷检查器并不区分突变和非突变的寿命(有一个很好的理由:那样做是不健全的)。所以,虽然w只是&Widget,但它的生命周期与&mut的自我相同,所以在widget存在的时候,应用程序仍然是可被借用的。

第三,也许是最重要的一点,&mut自我变成了病毒--程序中的大多数函数开始需要&mut,你失去了类型系统对只读和读写操作的区分。在 "这个函数只能修改缓存 "和 "这个函数可以修改字面上的一切 "之间没有区别。

最后,即使实现get_widget也是不愉快的。经验丰富的Rustaceans可能会因为无谓的重复hashmap查找而抽搐。但是,试图在入口API的帮助下摆脱这些,就会遇到当前借贷检查器的限制。

让我们来看看如何才能更好地解决这个问题

这类问题的总体思路是思考所有权和借贷情况应该是怎样的,并努力实现这一目标,而不是仅仅遵循编译器的建议。也就是说,大多数时候,按照编译器的指导使用&mut和&是一条成功的道路,因为事实证明,大多数的代码都自然地遵循简单的别名规则。但是也有例外,重要的是要认识到它们的存在,并利用内部可变性来实现有意义的别名结构。

让我们从一个简化的案例开始。假设只有一个Widget需要处理。在这种情况下,我们会想要这样的东西。

struct App {
  ...
  cache: Option<Widget>,
}

impl App {
  fn get_widget(&self) -> &Widget {
    if let Some(widget) = &self.cache {
      return widget;
    }
    self.cache = Some(create_widget());
    self.cache.as_ref().unwrap()
  }
}

这不是按原样工作的——修改我们非常希望避免的cache需求。&mut然而,考虑到这种模式,感觉它应该是有效的——我们在运行时强制执行cache永远不会覆盖的内容。也就是说,我们实际上在运行时对高亮行上的缓存具有独占访问权,我们只是无法向类型系统解释这一点。但我们可以为此伸出援手unsafe。更重要的是,Rust 的类型系统足够强大,可以将 unsafe 的使用封装到一个安全且通常可重用的 API 中。once_cell所以让我们为此拉箱子:

struct App {
  ...
  cache: once_cell::sync::OnceCell<Widget>,
}

impl App {
  fn get_widget(&self) -> &Widget {
    self.cache.get_or_init(create_widget)
  }
}

回到最初的 hash-map 示例,我们可以在这里应用相同的逻辑:只要我们从不覆盖、删除或移动值,我们就可以安全地返回对它们的引用。这是由elsa板条箱处理的:

struct App {
  config: Config,
  db: Db,
  cache: elsa::map::FrozenMap<u32, Box<Widget>>,
}

impl App {
  pub fn get_widget(
    &self,
    id: u32,
  ) -> io::Result<Option<&Widget>> {
    if let Some(widget) = self.cache.get(&id) {
      return Ok(Some(widget));
    }

    let key = id.to_be_bytes();
    let value = match self.db.load(&key)? {
      None => return Ok(None),
      Some(it) => it,
    };
    let widget: Widget =
      bincode::deserialize(&value).map_err(|it| {
        io::Error::new(io::ErrorKind::InvalidData, it)
      })?;

    let widget = self.cache.insert(id, Box::new(widget));

    Ok(Some(widget))
  }
}

第三种情况是有边界的缓冲区。如果你需要驱逐值,那么上面的推理就不适用了。如果缓存的用户得到一个&T,而相应的条目被驱逐,那么这个引用就会悬空。在这种情况下,我们希望缓存的客户能够共同拥有这个值。这很容易通过Rc来处理。

struct App {
  config: Config,
  db: Db,
  cache: RefCell<lru::LruCache<u32, Rc<Widget>>>,
}

impl App {
  pub fn get_widget(
    &self,
    id: u32,
  ) -> io::Result<Option<Rc<Widget>>> {
    {
      let mut cache = self.cache.borrow_mut();
      if let Some(widget) = cache.get(&id) {
        return Ok(Some(Rc::clone(widget)));
      }
    }

    let key = id.to_be_bytes();
    let value = match self.db.load(&key)? {
      None => return Ok(None),
      Some(it) => it,
    };
    let widget: Widget =
      bincode::deserialize(&value).map_err(|it| {
        io::Error::new(io::ErrorKind::InvalidData, it)
      })?;

    let widget = Rc::new(widget);
    {
      let mut cache = self.cache.borrow_mut();
      cache.put(id, Rc::clone(&widget));
    }

    Ok(Some(widget))
  }
}

总结一下:在实现缓存时,阻力最小的路径是拿出这样的签名:

fn get(&mut self) -> &T

这通常会导致问题发生。通常最好使用一些内部可变性并获得其中任何一个:

fn get(&self) -> &T
fn get(&self) -> T


这是更普遍的效果的一个例子:尽管有 "可变性 "的术语,Rust引用跟踪的不是可变性,而是别名。可变性和独占访问是相关的,但不是完美的。识别需要采用内部可变性的实例是很重要的,通常它们在架构上是有趣的。

猜你喜欢