Add a filesystem based persistent events store

This event store is currently very simplistic, and it is only safe to
use from a single node (not multi-master safe) at a time.  It relies on
java synchronized methods for synchronization which only works within
the same process.

The file system layout of this store is fairly simple, it uses
individual files to store the uuid, head, tail, and each event.  The
events are sharded in an extensible way that can scale to the full size
of a java long, with at most 1000 entries per directory.  It is
envisioned that a similar layout will eventually be used with additional
directories for transactions in a multi-master safe way.

Change-Id: I73e3a74ddce10ebf956e473d4bce7119c42d79a7
diff --git a/pom.xml b/pom.xml
index 26238ea..3207839 100644
--- a/pom.xml
+++ b/pom.xml
@@ -79,6 +79,13 @@
       <version>${Gerrit-ApiVersion}</version>
       <scope>provided</scope>
     </dependency>
+
+    <dependency>
+      <groupId>junit</groupId>
+      <artifactId>junit</artifactId>
+      <version>4.8.1</version>
+      <scope>test</scope>
+    </dependency>
   </dependencies>
 
   <repositories>
diff --git a/src/main/java/com/googlesource/gerrit/plugins/events/MemStore.java b/src/main/java/com/googlesource/gerrit/plugins/events/MemStore.java
deleted file mode 100644
index e658f7c..0000000
--- a/src/main/java/com/googlesource/gerrit/plugins/events/MemStore.java
+++ /dev/null
@@ -1,70 +0,0 @@
-// Copyright (C) 2016 The Android Open Source Project
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-
-package com.googlesource.gerrit.plugins.events;
-
-import java.util.Map;
-import java.util.UUID;
-import java.util.concurrent.ConcurrentHashMap;
-import javax.inject.Singleton;
-
-@Singleton
-public class MemStore implements EventStore {
-  protected final Map<Long, String> eventsByIndex = new ConcurrentHashMap<Long, String>();
-  protected final UUID uuid;
-
-  protected long head = 0;
-  protected long tail = 1;
-
-  public MemStore() {
-    uuid = UUID.randomUUID();
-  }
-
-  @Override
-  public UUID getUuid() {
-    return uuid;
-  }
-
-  @Override
-  public synchronized void add(String event) {
-    eventsByIndex.put(head + 1, event);
-    head++;
-  }
-
-  @Override
-  public String get(long n) {
-    return eventsByIndex.get(n);
-  }
-
-  @Override
-  public long getHead() {
-    return head;
-  }
-
-  @Override
-  public long getTail() {
-    return head == 0 ? 0 : tail;
-  }
-
-  @Override
-  public void trim(long trim) {
-    if (trim >= head) {
-      trim = head - 1;
-    }
-    for (long i = tail; i <= trim; i++) {
-      tail++;
-      eventsByIndex.remove(i);
-    }
-  }
-}
diff --git a/src/main/java/com/googlesource/gerrit/plugins/events/Module.java b/src/main/java/com/googlesource/gerrit/plugins/events/Module.java
index 3c9d6cf..3a36a65 100644
--- a/src/main/java/com/googlesource/gerrit/plugins/events/Module.java
+++ b/src/main/java/com/googlesource/gerrit/plugins/events/Module.java
@@ -17,12 +17,13 @@
 import com.google.gerrit.common.ChangeListener;
 import com.google.gerrit.extensions.registration.DynamicSet;
 import com.google.inject.AbstractModule;
+import com.googlesource.gerrit.plugins.events.fsstore.FsStore;
 
 public class Module extends AbstractModule {
   @Override
   protected void configure() {
     DynamicSet.setOf(binder(), StreamEventListener.class);
-    bind(EventStore.class).to(MemStore.class);
+    bind(EventStore.class).to(FsStore.class);
     DynamicSet.bind(binder(), ChangeListener.class).to(CoreListener.class);
   }
 }
diff --git a/src/main/java/com/googlesource/gerrit/plugins/events/fsstore/DynamicRangeSharder.java b/src/main/java/com/googlesource/gerrit/plugins/events/fsstore/DynamicRangeSharder.java
new file mode 100644
index 0000000..2a15167
--- /dev/null
+++ b/src/main/java/com/googlesource/gerrit/plugins/events/fsstore/DynamicRangeSharder.java
@@ -0,0 +1,113 @@
+// Copyright (C) 2017 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package com.googlesource.gerrit.plugins.events.fsstore;
+
+import java.nio.file.Path;
+
+/**
+ * A dynamic range Path sharder for 'long' numbers.
+ *
+ * <p>This Path sharder splits large collections of filesystem entries (files or directories) into
+ * directory based blocks using the numeric value of the name of the entries. Unlike a traditional
+ * sharder which attempts to distribute entries across many blocks, this sharder attempts to keep
+ * numerically close values together in the same blocks, all while still, for perfromance reasons,
+ * attempting to limit the size of each block. This layout targets large sequences and attempts to
+ * minimize the amount of blocks needed all while being flexible over time as the ranges of the
+ * sequences might shift.
+ *
+ * <p>This sharder will vary the number of "sharding" levels based on the numeric value of entries.
+ * The size of each level is configurable based on how many oders of magnitude are desired per
+ * level. For example, an order of 3 will result in 1,000 entries per level. Entries with different
+ * depths will be stored in different subtrees of the root. Each subtree starts with a prefix
+ * indicating the depth of the subtree by the number of "dotted" sections in the prefix, and the
+ * order of magnitudes in each level of the subtree by the number in each "dotted" section of the
+ * prefix. So a subtree of depth 3 with 2 orders of magnitude per level will start with "2.2.2/" and
+ * an entry of 1,234,567 would end up as "2.2.2/01/23/45/67" in that subtree. Whereas with 3 orders
+ * per level, the same entry 1,234,567 would end up instead in subtree "3.3", which only has 2
+ * levels, as "3.3/001/234/567".
+ */
+public class DynamicRangeSharder {
+  public static final int DEFAULT_ORDERS = 3; // most filesystem can handle 1K
+  protected final Path base;
+  protected final int orders;
+  protected final String order;
+  protected final long entriesPerLevel;
+
+  public DynamicRangeSharder(Path base) {
+    this(base, DEFAULT_ORDERS);
+  }
+
+  public DynamicRangeSharder(Path base, int orders) {
+    this.base = base;
+    this.orders = orders;
+    this.entriesPerLevel = (long) Math.pow(10, orders);
+    order = Long.toString(orders);
+  }
+
+  /** Get the Path of the block that `i` should be stored in. */
+  public Path dir(long i) {
+    Path dir = base.resolve(subtreeName(i));
+    for (int level = levels(i) - 1; level > 0; level--) {
+      long sizeOfLevel = sizeOfLevel(level);
+      long sub = i / sizeOfLevel;
+      dir = dir.resolve(padToOrder(sub));
+      i = i - (sub * sizeOfLevel);
+    }
+    return dir;
+  }
+
+  /** Determine whether a number is the last entry in its dir */
+  public boolean isLastDirEntry(long i) {
+    return !dir(i).equals(dir(i + 1));
+  }
+
+  protected String subtreeName(long i) {
+    String subtree = order;
+    for (int l = levels(i) - 1; l > 0; l--) {
+      subtree += "." + order;
+    }
+    return subtree;
+  }
+
+  /** pad a number to our order. */
+  protected String padToOrder(long i) {
+    return String.format("%0" + order + "d", i);
+  }
+
+  /** how many order levels is number */
+  protected int levels(long i) {
+    if (i == 0) {
+      return 1;
+    }
+    int l = 0;
+    for (; i > 0; l++) {
+      i = i / entriesPerLevel;
+    }
+    return l;
+  }
+
+  /**
+   * Get the aggregate size of a level given our order
+   *
+   * <p>i.e. order 3 and level 2 -> 1,000,000 order 2 and level 2 -> 10,000
+   */
+  protected long sizeOfLevel(int level) {
+    long x = 1;
+    for (; level > 0; level--) {
+      x *= entriesPerLevel;
+    }
+    return x;
+  }
+}
diff --git a/src/main/java/com/googlesource/gerrit/plugins/events/fsstore/Fs.java b/src/main/java/com/googlesource/gerrit/plugins/events/fsstore/Fs.java
new file mode 100644
index 0000000..6c586b8
--- /dev/null
+++ b/src/main/java/com/googlesource/gerrit/plugins/events/fsstore/Fs.java
@@ -0,0 +1,101 @@
+// Copyright (C) 2017 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package com.googlesource.gerrit.plugins.events.fsstore;
+
+import java.io.File;
+import java.io.IOException;
+import java.nio.charset.StandardCharsets;
+import java.nio.file.FileAlreadyExistsException;
+import java.nio.file.FileVisitResult;
+import java.nio.file.Files;
+import java.nio.file.Path;
+import java.nio.file.SimpleFileVisitor;
+import java.nio.file.attribute.BasicFileAttributes;
+
+/** Some Filesystem utilities */
+public class Fs {
+  /** Try to recursively delete a dir. Do NOT throw IOExceptions. */
+  public static void tryRecursiveDelete(Path dir) {
+    try {
+      Files.walkFileTree(
+          dir,
+          new SimpleFileVisitor<Path>() {
+            @Override
+            public FileVisitResult visitFile(Path file, BasicFileAttributes attrs)
+                throws IOException {
+              tryDelete(file);
+              return FileVisitResult.CONTINUE;
+            }
+
+            @Override
+            public FileVisitResult postVisitDirectory(Path dir, IOException e) throws IOException {
+              tryDelete(dir);
+              return FileVisitResult.CONTINUE;
+            }
+          });
+    } catch (IOException e) { // Intent of 'try' function is to ignore these.
+    }
+  }
+
+  /** Try to delete a path. Do NOT throw IOExceptions. */
+  public static void tryDelete(Path path) {
+    try {
+      Files.delete(path);
+    } catch (IOException e) { // Intent of 'try' function is to ignore these.
+    }
+  }
+
+  /** Try to delete a dir and it parents (like rmdir -p). Do NOT throw IOExceptions. */
+  public static void unsafeRecursiveRmdir(File dir) {
+    try {
+      while (unsafeRmdir(dir)) {
+        dir = dir.getParentFile();
+      }
+    } catch (IOException e) { // Intent of 'try' function is to ignore these.
+    }
+  }
+
+  /**
+   * Try to delete a dir and it parents (like rmdir -p). Do NOT throw IOExceptions. Unsafe since the
+   * directory check and removal are not atomic.
+   */
+  public static boolean unsafeRmdir(File dir) throws IOException {
+    if (!dir.isDirectory()) {
+      throw new IOException(dir + " not a directory");
+    }
+    return dir.delete();
+  }
+
+  /** Read the contents of a UTF_8 encoded file as a String */
+  public static String readFile(Path file) throws IOException {
+    StringBuffer buffer = new StringBuffer();
+    for (String line : Files.readAllLines(file, StandardCharsets.UTF_8)) {
+      buffer.append(line);
+    }
+    return buffer.toString();
+  }
+
+  /**
+   * A drop in replacement for Files.createDirectories that works even when the tail of `path` is a
+   * link.
+   */
+  public static Path createDirectories(Path path) throws IOException {
+    try {
+      return Files.createDirectories(path);
+    } catch (FileAlreadyExistsException e) {
+      return Files.createDirectories(Files.readSymbolicLink(path));
+    }
+  }
+}
diff --git a/src/main/java/com/googlesource/gerrit/plugins/events/fsstore/FsStore.java b/src/main/java/com/googlesource/gerrit/plugins/events/fsstore/FsStore.java
new file mode 100644
index 0000000..25264a6
--- /dev/null
+++ b/src/main/java/com/googlesource/gerrit/plugins/events/fsstore/FsStore.java
@@ -0,0 +1,207 @@
+// Copyright (C) 2017 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package com.googlesource.gerrit.plugins.events.fsstore;
+
+import com.google.gerrit.server.config.SitePaths;
+import com.google.inject.Inject;
+import com.googlesource.gerrit.plugins.events.EventStore;
+import java.io.IOException;
+import java.nio.file.Files;
+import java.nio.file.NoSuchFileException;
+import java.nio.file.Path;
+import java.util.UUID;
+import javax.inject.Singleton;
+
+/** This class is only Thread, but not process (Multi-Master) safe */
+@Singleton
+public class FsStore implements EventStore {
+  public abstract static class FsValue<T> {
+    protected final Path path;
+
+    public FsValue(Path path) {
+      this.path = path;
+    }
+
+    /** Only Thread safe, but not process (Multi-Master) safe */
+    public synchronized void initFs(T value) throws IOException {
+      if (!Files.isRegularFile(path)) {
+        Fs.createDirectories(path.getParent());
+        set(value);
+      }
+    }
+
+    protected abstract void set(T value) throws IOException;
+
+    protected synchronized String load() throws IOException {
+      return Fs.readFile(path);
+    }
+
+    /** Only Thread, but not process (Multi-Master) safe */
+    protected synchronized void store(String value) throws IOException {
+      Files.write(path, value.getBytes());
+    }
+  }
+
+  public static class StringFsValue extends FsValue<String> {
+    public StringFsValue(Path path) {
+      super(path);
+    }
+
+    public String get() throws IOException {
+      return load();
+    }
+
+    public void set(String value) throws IOException {
+      store(value + "\n");
+    }
+  }
+
+  public static class FsSequence extends FsValue<Long> {
+    public FsSequence(Path path) {
+      super(path);
+    }
+
+    public Long get() throws IOException {
+      return Long.parseLong(load());
+    }
+
+    protected void set(Long value) throws IOException {
+      store("" + value + "\n");
+    }
+
+    /** Only Thread safe, but not process (Multi-Master) safe */
+    public synchronized Long increment() throws IOException {
+      Long next = get() + 1;
+      set(next);
+      return next;
+    }
+  }
+
+  protected static class BasePaths {
+    final Path base;
+    final Path uuid;
+    final Path head;
+    final Path tail;
+    final DynamicRangeSharder events;
+
+    public BasePaths(Path base) {
+      this.base = base;
+      uuid = base.resolve("uuid");
+      events = new DynamicRangeSharder(base.resolve("events"));
+      head = base.resolve("head");
+      tail = base.resolve("tail");
+    }
+
+    public Path event(long event) {
+      return events.dir(event).resolve(Long.toString(event));
+    }
+
+    public boolean isEventLastDirEntry(long event) {
+      return events.isLastDirEntry(event);
+    }
+  }
+
+  protected static class Stores {
+    final StringFsValue uuid;
+    final FsSequence head;
+    final FsSequence tail;
+
+    public Stores(BasePaths bases) {
+      uuid = new StringFsValue(bases.uuid);
+      head = new FsSequence(bases.head);
+      tail = new FsSequence(bases.tail);
+    }
+
+    public void initFs() throws IOException {
+      uuid.initFs(UUID.randomUUID().toString());
+      head.initFs((long) 0);
+      tail.initFs((long) 1);
+    }
+  }
+
+  protected final BasePaths paths;
+  protected final Stores stores;
+  protected final UUID uuid;
+
+  @Inject
+  public FsStore(SitePaths site) throws IOException {
+    this(site.data_dir.toPath().resolve("plugin").resolve("events").resolve("fstore-v1"));
+  }
+
+  public FsStore(Path base) throws IOException {
+    paths = new BasePaths(base);
+    stores = new Stores(paths);
+    stores.initFs();
+    uuid = UUID.fromString(stores.uuid.get());
+  }
+
+  @Override
+  public UUID getUuid() throws IOException {
+    return uuid;
+  }
+
+  /** Only Thread, but not process (Multi-Master) safe */
+  @Override
+  public synchronized void add(String event) throws IOException {
+    long next = getHead() + 1;
+    Path epath = paths.event(next);
+    Fs.createDirectories(epath.getParent());
+    Files.write(epath, (event + "\n").getBytes());
+    stores.head.increment();
+  }
+
+  @Override
+  public long getHead() throws IOException {
+    return stores.head.get();
+  }
+
+  @Override
+  public String get(long num) throws IOException {
+    if (getTail() <= num && num <= getHead()) {
+      try {
+        return Fs.readFile(paths.event(num));
+      } catch (NoSuchFileException e) {
+      }
+    }
+    return null;
+  }
+
+  @Override
+  public long getTail() throws IOException {
+    if (getHead() == 0) {
+      return 0;
+    }
+    long tail = stores.tail.get();
+    return tail < 1 ? 1 : tail;
+  }
+
+  @Override
+  public synchronized void trim(long trim) throws IOException {
+    long head = getHead();
+    if (trim >= head) {
+      trim = head - 1;
+    }
+    if (trim > 0) {
+      for (long i = getTail(); i <= trim; i++) {
+        stores.tail.increment();
+        Path event = paths.event(i);
+        Fs.tryRecursiveDelete(event);
+        if (paths.isEventLastDirEntry(i)) {
+          Fs.unsafeRecursiveRmdir(event.getParent().toFile());
+        }
+      }
+    }
+  }
+}
diff --git a/src/main/resources/Documentation/about.md b/src/main/resources/Documentation/about.md
new file mode 100644
index 0000000..f0639f5
--- /dev/null
+++ b/src/main/resources/Documentation/about.md
@@ -0,0 +1,13 @@
+@PLUGIN@
+========
+
+The @PLUGIN@ plugin provides a mechanism to store events.
+
+<a id="storage"/>
+@PLUGIN@ Storage
+----------------
+
+The events plugin stores events using a standard filesystem.  Events
+are stored under "<site_dir>/data/plugin/events".  Events do not use
+significant disk space, however it might still make sense to regularly
+trim them with a cron job.
diff --git a/src/test/java/com/googlesource/gerrit/plugins/events/fsstore/DynamicRangeSharderTest.java b/src/test/java/com/googlesource/gerrit/plugins/events/fsstore/DynamicRangeSharderTest.java
new file mode 100644
index 0000000..9bd5382
--- /dev/null
+++ b/src/test/java/com/googlesource/gerrit/plugins/events/fsstore/DynamicRangeSharderTest.java
@@ -0,0 +1,121 @@
+// Copyright (C) 2017 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package com.googlesource.gerrit.plugins.events.fsstore;
+
+import java.nio.file.Path;
+import junit.framework.TestCase;
+import org.junit.Test;
+
+public class DynamicRangeSharderTest extends TestCase {
+  DynamicRangeSharder sharder2;
+  DynamicRangeSharder sharder3;
+
+  @Override
+  protected void setUp() throws Exception {
+    super.setUp();
+    sharder2 = new DynamicRangeSharder(java.nio.file.Paths.get("base"), 2);
+    sharder3 = new DynamicRangeSharder(java.nio.file.Paths.get("base"), 3);
+  }
+
+  @Test
+  public void testEntriesPerLevel() {
+    assertEquals(100, sharder2.entriesPerLevel);
+    assertEquals(1000, sharder3.entriesPerLevel);
+  }
+
+  @Test
+  public void testLevels() {
+    assertEquals(1, sharder2.levels(0));
+    assertEquals(1, sharder2.levels(1));
+    assertEquals(1, sharder2.levels(10));
+    assertEquals(2, sharder2.levels(100));
+    assertEquals(2, sharder2.levels(1000));
+    assertEquals(3, sharder2.levels(100000));
+    assertEquals(4, sharder2.levels(1000000));
+    assertEquals(5, sharder2.levels(100000000));
+    assertEquals(5, sharder2.levels(1000000000));
+
+    assertEquals(1, sharder3.levels(0));
+    assertEquals(1, sharder3.levels(1));
+    assertEquals(1, sharder3.levels(10));
+    assertEquals(1, sharder3.levels(100));
+    assertEquals(2, sharder3.levels(1000));
+    assertEquals(2, sharder3.levels(100000));
+    assertEquals(3, sharder3.levels(1000000));
+    assertEquals(3, sharder3.levels(100000000));
+    assertEquals(4, sharder3.levels(1000000000));
+  }
+
+  @Test
+  public void testSizeOfLevel() {
+    assertEquals(1, sharder2.sizeOfLevel(0));
+    assertEquals(100, sharder2.sizeOfLevel(1));
+    assertEquals(10000, sharder2.sizeOfLevel(2));
+
+    assertEquals(1, sharder3.sizeOfLevel(0));
+    assertEquals(1000, sharder3.sizeOfLevel(1));
+    assertEquals(1000000, sharder3.sizeOfLevel(2));
+  }
+
+  @Test
+  public void testPadToOrder() {
+    assertEquals("01", sharder2.padToOrder(1));
+    assertEquals("10", sharder2.padToOrder(10));
+
+    assertEquals("001", sharder3.padToOrder(1));
+    assertEquals("010", sharder3.padToOrder(10));
+    assertEquals("100", sharder3.padToOrder(100));
+  }
+
+  @Test
+  public void testDir() {
+    assertPathEquals("base/2", sharder2.dir(1));
+    assertPathEquals("base/2", sharder2.dir(10));
+    assertPathEquals("base/2.2/01", sharder2.dir(100));
+    assertPathEquals("base/2.2/10", sharder2.dir(1000));
+    assertPathEquals("base/2.2.2/01/00", sharder2.dir(10000));
+    assertPathEquals("base/2.2.2/10/00", sharder2.dir(100000));
+    assertPathEquals("base/2.2.2.2/01/00/00", sharder2.dir(1000000));
+    assertPathEquals("base/2.2.2.2/01/00/10", sharder2.dir(1001000));
+    assertPathEquals("base/2.2.2.2.2/01/00/00/00", sharder2.dir(100000000));
+    assertPathEquals("base/2.2.2.2.2/10/00/00/00", sharder2.dir(1000000000));
+
+    assertPathEquals("base/3", sharder3.dir(1));
+    assertPathEquals("base/3", sharder3.dir(10));
+    assertPathEquals("base/3", sharder3.dir(100));
+    assertPathEquals("base/3.3/001", sharder3.dir(1000));
+    assertPathEquals("base/3.3/010", sharder3.dir(10000));
+    assertPathEquals("base/3.3/100", sharder3.dir(100000));
+    assertPathEquals("base/3.3.3/001/000", sharder3.dir(1000000));
+    assertPathEquals("base/3.3.3/001/001", sharder3.dir(1001000));
+    assertPathEquals("base/3.3.3/100/000", sharder3.dir(100000000));
+    assertPathEquals("base/3.3.3.3/001/000/000", sharder3.dir(1000000000));
+  }
+
+  @Test
+  public void testIsLastDirEntry() {
+    assertEquals(true, sharder2.isLastDirEntry(99));
+    assertEquals(false, sharder2.isLastDirEntry(100));
+    assertEquals(false, sharder2.isLastDirEntry(1000));
+
+    assertEquals(true, sharder3.isLastDirEntry(999));
+    assertEquals(false, sharder3.isLastDirEntry(1000));
+    assertEquals(false, sharder3.isLastDirEntry(10001));
+  }
+
+  public static void assertPathEquals(String a, Path b) {
+    assertEquals(a, b.toString());
+  }
+}
diff --git a/src/test/java/com/googlesource/gerrit/plugins/events/fsstore/FsStoreTest.java b/src/test/java/com/googlesource/gerrit/plugins/events/fsstore/FsStoreTest.java
new file mode 100644
index 0000000..8da8fba
--- /dev/null
+++ b/src/test/java/com/googlesource/gerrit/plugins/events/fsstore/FsStoreTest.java
@@ -0,0 +1,236 @@
+// Copyright (C) 2017 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package com.googlesource.gerrit.plugins.events.fsstore;
+
+import java.io.IOException;
+import java.nio.file.Files;
+import java.nio.file.Path;
+import java.nio.file.Paths;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.Set;
+import java.util.UUID;
+import junit.framework.TestCase;
+import org.junit.After;
+import org.junit.Before;
+import org.junit.Test;
+
+public class FsStoreTest extends TestCase {
+  private static String dir = "events-FsStore";
+  private static Path base;
+  private Path myBase;
+  private FsStore store;
+  private String submitMarker = "";
+
+  private long count = 1000;
+  Map<String, Long> reported = new HashMap<String, Long>();
+
+  @Override
+  @Before
+  public void setUp() throws Exception {
+    myBase = base;
+    if (myBase == null) {
+      myBase = Files.createTempDirectory(dir);
+    }
+    store = new FsStore(myBase);
+  }
+
+  @After
+  public void tearDown() throws Exception {
+    Fs.tryRecursiveDelete(myBase);
+  }
+
+  @Test
+  public void testUUIDInit() throws IOException {
+    UUID uuid = store.getUuid();
+    FsStore store2 = new FsStore(myBase);
+    assertEquals(uuid, store2.getUuid());
+  }
+
+  @Test
+  public void testHeadInit() throws IOException {
+    assertEquals(0, store.getHead());
+    FsStore store2 = new FsStore(myBase);
+    assertEquals(0, store2.getHead());
+  }
+
+  @Test
+  public void testTailInit() throws IOException {
+    assertEquals(0, store.getTail());
+    FsStore store2 = new FsStore(myBase);
+    assertEquals(0, store2.getTail());
+  }
+
+  @Test
+  public void testGetInit() throws IOException {
+    assertEquals(null, store.get(1));
+  }
+
+  @Test
+  public void testAdd() throws IOException {
+    add();
+  }
+
+  public void add() throws IOException {
+    long next = store.getHead() + 1;
+    assertEquals(0, get(next));
+
+    add(next);
+    assertEquals(next, get(next));
+    assertEquals(next, store.getHead());
+    assertEquals(1, store.getTail());
+
+    FsStore store2 = new FsStore(myBase);
+    assertEquals(next, store2.getHead());
+    assertEquals(1, store2.getTail());
+  }
+
+  private void add(long l) throws IOException {
+    store.add("" + l);
+  }
+
+  private long get(long i) throws IOException {
+    String g = store.get(i);
+    return g == null ? 0 : Long.parseLong(g);
+  }
+
+  @Test
+  public void testAddAgain() throws IOException {
+    add();
+    add();
+    add();
+  }
+
+  @Test
+  public void testTrim() throws IOException {
+    add();
+    add();
+    add();
+
+    assertEquals(1, store.getTail());
+    store.trim(1);
+    assertEquals(2, store.getTail());
+    assertEquals(0, get(1)); // just deleted
+    assertEquals(2, get(2)); // beyond deleted
+
+    store.trim(2);
+    assertEquals(3, store.getTail());
+    assertEquals(0, get(2)); // just deleted
+    assertEquals(3, get(3)); // beyond deleted
+
+    store.trim(3);
+    assertEquals(3, store.getTail());
+    assertEquals(3, get(3)); // cannot delete head
+  }
+
+  @Test
+  public void testCount() throws Exception {
+    for (long i = 0; i < count; i++) {
+      add();
+    }
+  }
+
+  public void count(String id) throws Exception {
+    for (long i = 1; i <= count; i++) {
+      store.add(id + " " + i);
+      System.out.print(submitMarker);
+    }
+  }
+
+  public void verify(String id, long head) throws Exception {
+    Set<Long> found = new HashSet<Long>();
+    long stop = store.getHead();
+    long mine = 1;
+
+    for (long i = head + 1; i <= stop; i++) {
+      String event = store.get(i);
+      if (event != null) {
+        String split[] = event.split(" ");
+        if (split != null && id.equals(split[0])) {
+          long n = Long.parseLong(split[1]);
+          if (!found.add(n)) {
+            report("duplicate", n, i);
+          }
+          if (mine != n) {
+            report("ouf of order", n, i);
+          }
+          mine++;
+        }
+      } else {
+        report("gap", mine, i);
+      }
+    }
+    for (long i = 1; i <= count; i++) {
+      if (!found.contains(i)) {
+        report("missing", i, -1);
+      }
+    }
+    reportTotal("duplicate");
+    reportTotal("out of order");
+    reportTotal("missing");
+    reportTotal("gap");
+  }
+
+  private void report(String type, long n, long i) {
+    Long cnt = reported.get(type);
+    if (cnt == null) {
+      System.out.println("First " + type + ": " + n + " pos(" + i + ")");
+      cnt = (long) 0;
+    }
+    reported.put(type, ++cnt);
+  }
+
+  private void reportTotal(String type) {
+    Long cnt = reported.get(type);
+    if (cnt != null) {
+      System.out.println("Total " + type + "s: " + cnt);
+    }
+  }
+
+  /**
+   * First, make the junit jar easily available
+   *
+   * <p>ln -s ~/.m2/repository/junit/junit/4.8.1/junit-4.8.1.jar target
+   *
+   * <p>To run type:
+   *
+   * <p>java -cp target/classes:target/test-classes:target/junit-4.8.1.jar \
+   * com.googlesource.gerrit.plugins.events.fsstore.FsStoreTest \ [dir [count [store-id]]]
+   *
+   * <p>Note: if you do not specify <dir>, it will create a directory under /tmp
+   */
+  public static void main(String[] argv) throws Exception {
+    if (argv.length > 0) {
+      base = Paths.get(argv[0]);
+    }
+    FsStoreTest t = new FsStoreTest();
+    if (argv.length > 1) {
+      t.count = Long.parseLong(argv[1]);
+    }
+
+    String id = UUID.randomUUID().toString();
+    t.submitMarker = ".";
+    if (argv.length > 2) {
+      id = argv[2];
+      t.submitMarker += id + ".";
+    }
+
+    t.setUp();
+    long head = t.store.getHead();
+    t.count(id);
+    t.verify(id, head);
+  }
+}