diff --git a/rust/treedirstate/Cargo.toml b/rust/treedirstate/Cargo.toml
--- a/rust/treedirstate/Cargo.toml
+++ b/rust/treedirstate/Cargo.toml
@@ -10,6 +10,9 @@
 name = "rusttreedirstate"
 crate-type = ["cdylib"]
 
+[dependencies]
+error-chain = "*"
+
 [dev-dependencies]
 itertools = "0.7.2"
 quickcheck = "*"
diff --git a/rust/treedirstate/src/errors.rs b/rust/treedirstate/src/errors.rs
new file mode 100644
--- /dev/null
+++ b/rust/treedirstate/src/errors.rs
@@ -0,0 +1,16 @@
+// Copyright Facebook, Inc. 2017
+//! Errors.
+
+error_chain! {
+    errors {
+        InvalidStoreId(id: usize) {
+            description("invalid store id"),
+            display("invalid store id: {}", id),
+        }
+    }
+    foreign_links {
+        Io(::std::io::Error);
+        Utf8(::std::str::Utf8Error);
+        Utf8String(::std::string::FromUtf8Error);
+    }
+}
diff --git a/rust/treedirstate/src/lib.rs b/rust/treedirstate/src/lib.rs
--- a/rust/treedirstate/src/lib.rs
+++ b/rust/treedirstate/src/lib.rs
@@ -12,6 +12,9 @@
 //! The directory state also stores files that are in the working copy parent manifest but have
 //! been marked as removed.
 
+#[macro_use]
+extern crate error_chain;
+
 #[cfg(test)]
 extern crate itertools;
 
@@ -19,4 +22,8 @@
 #[macro_use]
 extern crate quickcheck;
 
+pub mod errors;
+pub mod store;
 pub mod vecmap;
+
+pub use errors::*;
diff --git a/rust/treedirstate/src/store.rs b/rust/treedirstate/src/store.rs
new file mode 100644
--- /dev/null
+++ b/rust/treedirstate/src/store.rs
@@ -0,0 +1,100 @@
+// Copyright Facebook, Inc. 2017
+//! Trait defining an append-only storage system.
+
+use errors::*;
+use std::borrow::Cow;
+
+pub type BlockId = usize;
+
+/// Append-only storage.  Blocks of data may be stored in an instance of a Store.
+pub trait Store {
+    /// Append a new block of data to the store.  Returns the ID of the block.  Note that blocks
+    /// may be buffered until `flush` is called.
+    fn append(&mut self, data: &[u8]) -> Result<BlockId>;
+
+    /// Flush all appended blocks to the backing store.
+    fn flush(&mut self) -> Result<()>;
+}
+
+/// Read-only view of a store.
+pub trait StoreView {
+    /// Read a block of data from the store.
+    fn read<'a>(&'a self, id: BlockId) -> Result<Cow<'a, [u8]>>;
+}
+
+/// Null implementation of a store.  This cannot be used to store new blocks of data, and returns
+/// an error if any attempts to read are made.
+pub struct NullStore;
+
+impl NullStore {
+    pub fn new() -> NullStore {
+        NullStore
+    }
+}
+
+impl StoreView for NullStore {
+    fn read<'a>(&'a self, id: BlockId) -> Result<Cow<'a, [u8]>> {
+        bail!(ErrorKind::InvalidStoreId(id))
+    }
+}
+
+#[cfg(test)]
+pub mod tests {
+    use std::collections::HashMap;
+    use errors::*;
+    use store::{BlockId, Store, StoreView};
+    use std::borrow::Cow;
+
+    /// Define a Store to be used in tests.  This doesn't store the data on disk, but rather
+    /// keeps it in memory in a hash map.
+    pub struct MapStore {
+        next_id: BlockId,
+        data: HashMap<BlockId, Vec<u8>>,
+    }
+
+    impl MapStore {
+        pub fn new() -> MapStore {
+            // Initial ID is set to 24 to simulate a header.
+            MapStore {
+                next_id: 24,
+                data: HashMap::new(),
+            }
+        }
+    }
+
+    impl Store for MapStore {
+        fn append(&mut self, data: &[u8]) -> Result<BlockId> {
+            let id = self.next_id;
+            self.data.insert(id, data.to_vec());
+            self.next_id += data.len();
+            Ok(id)
+        }
+
+        fn flush(&mut self) -> Result<()> {
+            Ok(())
+        }
+    }
+
+    impl StoreView for MapStore {
+        fn read<'a>(&'a self, id: BlockId) -> Result<Cow<'a, [u8]>> {
+            match self.data.get(&id) {
+                Some(data) => Ok(Cow::from(data.as_slice())),
+                None => bail!(ErrorKind::InvalidStoreId(id)),
+            }
+        }
+    }
+
+    #[test]
+    fn basic_test() {
+        let mut ms = MapStore::new();
+        let key1 = ms.append("12345".as_bytes()).expect("append key1");
+        let key2 = ms.append("67890".as_bytes()).expect("append key2");
+        ms.flush().expect("flush");
+        assert_eq!(ms.read(key2).unwrap(), "67890".as_bytes());
+        assert_eq!(ms.read(key1).unwrap(), "12345".as_bytes());
+        assert_eq!(
+            ms.read(999).unwrap_err().to_string(),
+            "invalid store id: 999"
+        );
+    }
+}