--- a/mobile/android/base/java/org/mozilla/gecko/telemetry/stores/TelemetryJSONFilePingStore.java
+++ b/mobile/android/base/java/org/mozilla/gecko/telemetry/stores/TelemetryJSONFilePingStore.java
@@ -11,160 +11,132 @@ import android.os.Parcelable;
 import android.support.annotation.VisibleForTesting;
 import android.util.Log;
 import org.json.JSONException;
 import org.json.JSONObject;
 import org.mozilla.gecko.sync.ExtendedJSONObject;
 import org.mozilla.gecko.sync.NonObjectJSONException;
 import org.mozilla.gecko.telemetry.TelemetryPing;
 import org.mozilla.gecko.util.FileUtils;
+import org.mozilla.gecko.util.FileUtils.FileLastModifiedComparator;
+import org.mozilla.gecko.util.FileUtils.FilenameRegexFilter;
+import org.mozilla.gecko.util.FileUtils.FilenameWhitelistFilter;
 import org.mozilla.gecko.util.StringUtils;
+import org.mozilla.gecko.util.UUIDUtil;
 
 import java.io.File;
 import java.io.FileInputStream;
 import java.io.FileNotFoundException;
 import java.io.FileOutputStream;
 import java.io.FilenameFilter;
 import java.io.IOException;
 import java.nio.channels.FileLock;
 import java.util.ArrayList;
+import java.util.Arrays;
 import java.util.Iterator;
-import java.util.Locale;
 import java.util.Set;
 import java.util.SortedSet;
 import java.util.TreeSet;
-import java.util.regex.Matcher;
-import java.util.regex.Pattern;
 
 /**
  * An implementation of TelemetryPingStore that is backed by JSON files.
  *
- * This implementation seeks simplicity. Each ping to upload is stored in its own file with a
- * name patterned after {@link #FILENAME}. The file name includes the ping's unique id - these are used to
- * both remove pings and prune pings. During prune, the pings with the smallest ids will be removed first
- * so these ping ids should be strictly increasing as new pings are stored; consider using data already contained
- * in the ping, such as a sequence number.
+ * This implementation seeks simplicity. Each ping to upload is stored in its own file with its doc ID
+ * as the filename. The doc ID is sent with a ping to be uploaded and is expected to be returned with
+ * {@link #onUploadAttemptComplete(Set)} so the associated file can be removed.
+ *
+ * During prune, the pings with the oldest modified time will be removed first.
  *
  * Using separate files for this store allows for less restrictive concurrency:
  *   * requires locking: {@link #storePing(TelemetryPing)} writes a new file
  *   * requires locking: {@link #getAllPings()} reads all files, including those potentially being written,
  * hence locking
  *   * no locking: {@link #maybePrunePings()} deletes the least recently written pings, none of which should
  * be currently written
  *   * no locking: {@link #onUploadAttemptComplete(Set)} deletes the given pings, none of which should be
  * currently written
  */
 public class TelemetryJSONFilePingStore implements TelemetryPingStore {
     private static final String LOGTAG = StringUtils.safeSubstring(
             "Gecko" + TelemetryJSONFilePingStore.class.getSimpleName(), 0, 23);
 
     @VisibleForTesting static final int MAX_PING_COUNT = 40; // TODO: value.
 
-    private static final String FILENAME = "ping-%s.json";
-    private static final Pattern FILENAME_PATTERN = Pattern.compile("ping-([0-9]+)\\.json");
-
     // We keep the key names short to reduce storage size impact.
     @VisibleForTesting static final String KEY_PAYLOAD = "p";
     @VisibleForTesting static final String KEY_URL_PATH = "u";
 
     private final File storeDir;
+    private final FilenameFilter uuidFilenameFilter;
 
     public TelemetryJSONFilePingStore(final File storeDir) {
         this.storeDir = storeDir;
         this.storeDir.mkdirs();
-    }
-
-    @VisibleForTesting File getPingFile(final long id) {
-        final String filename = String.format(Locale.US, FILENAME, id);
-        return new File(storeDir, filename);
+        uuidFilenameFilter = new FilenameRegexFilter(UUIDUtil.UUID_PATTERN);
     }
 
-    /**
-     * @return the ID from the filename or -1 if the id does not exist.
-     */
-    @VisibleForTesting static int getIDFromFilename(final String filename) {
-        final Matcher matcher = FILENAME_PATTERN.matcher(filename);
-        if (!matcher.matches()) { // Matcher.matches has the side effect of starting the match - needed to call Matcher.group
-            return -1;
-        }
-        return Integer.parseInt(matcher.group(1));
+    @VisibleForTesting File getPingFile(final String docID) {
+        return new File(storeDir, docID);
     }
 
     @Override
     public void storePing(final TelemetryPing ping) throws IOException {
         final String output;
         try {
             output = new JSONObject()
                     .put(KEY_PAYLOAD, ping.getPayload())
                     .put(KEY_URL_PATH, ping.getURLPath())
                     .toString();
         } catch (final JSONException e) {
             // Do not log the exception to avoid leaking personal data.
             throw new IOException("Unable to create JSON to store to disk");
         }
 
-        final FileOutputStream outputStream = new FileOutputStream(getPingFile(ping.getUniqueID()), false);
+        final FileOutputStream outputStream = new FileOutputStream(getPingFile(ping.getDocID()), false);
         blockForLockAndWriteFileAndCloseStream(outputStream, output);
     }
 
     @Override
     public void maybePrunePings() {
-        final File[] files = storeDir.listFiles(new PingFileFilter());
+        final File[] files = storeDir.listFiles(uuidFilenameFilter);
         if (files.length < MAX_PING_COUNT) {
             return;
         }
 
-        final SortedSet<Integer> ids = getIDsFromFileList(files);
-        removeFilesWithSmallestIDs(ids, files.length - MAX_PING_COUNT);
+        final SortedSet<File> sortedFiles = new TreeSet<>(new FileLastModifiedComparator());
+        sortedFiles.addAll(Arrays.asList(files));
+        deleteSmallestFiles(sortedFiles, files.length - MAX_PING_COUNT);
     }
 
-    private static SortedSet<Integer> getIDsFromFileList(final File[] files) {
-        // Since we get the ids from a file list which is probably sorted, I assume a TreeSet will get unbalanced
-        // and could be inefficient. However, it sounds less complex and more efficient than the alternative: the
-        // ConcurrentSkipListSet. In any case, our data is relatively small.
-        final SortedSet<Integer> out = new TreeSet<>();
-        for (final File file : files) {
-            final int id = getIDFromFilename(file.getName());
-            if (id >= 0) {
-                out.add(id);
-            }
-        }
-        return out;
-    }
-
-    private void removeFilesWithSmallestIDs(final SortedSet<Integer> ids, final int numFilesToRemove) {
-        final Iterator<Integer> it = ids.iterator();
+    private void deleteSmallestFiles(final SortedSet<File> files, final int numFilesToRemove) {
+        final Iterator<File> it = files.iterator();
         int i = 0;
-        while (i < numFilesToRemove) { // Sorted set so these are ascending values.
+        while (i < numFilesToRemove) {
             i += 1;
-            final Integer id = it.next(); // file count > files to remove so this should not throw.
-            getPingFile(id).delete();
+            // Sorted set so we're iterating over ascending files.
+            final File file = it.next(); // file count > files to remove so this should not throw.
+            file.delete();
         }
     }
 
     @Override
     public ArrayList<TelemetryPing> getAllPings() {
-        final File[] files = storeDir.listFiles(new PingFileFilter());
+        final File[] files = storeDir.listFiles(uuidFilenameFilter);
         final ArrayList<TelemetryPing> out = new ArrayList<>(files.length);
         for (final File file : files) {
             final JSONObject obj = lockAndReadJSONFromFile(file);
             if (obj == null) {
                 // We log in the method to get the JSONObject if we return null.
                 continue;
             }
 
             try {
                 final String url = obj.getString(KEY_URL_PATH);
                 final ExtendedJSONObject payload = new ExtendedJSONObject(obj.getString(KEY_PAYLOAD));
-                final int id = getIDFromFilename(file.getName());
-                if (id < 0) {
-                    throw new IllegalStateException("These files are already filtered - did not expect to see " +
-                            "an invalid ID in these files");
-                }
-                out.add(new TelemetryPing(url, payload, id));
+                out.add(new TelemetryPing(url, payload, file.getName()));
             } catch (final IOException | JSONException | NonObjectJSONException e) {
                 Log.w(LOGTAG, "Bad json in ping. Ignoring.");
                 continue;
             }
         }
         return out;
     }
 
@@ -194,22 +166,22 @@ public class TelemetryJSONFilePingStore 
 
         if (obj == null) {
             Log.d(LOGTAG, "Could not read given file: " + file.getName() + " File is locked. Ignoring");
         }
         return obj;
     }
 
     @Override
-    public void onUploadAttemptComplete(final Set<Integer> successfulRemoveIDs) {
+    public void onUploadAttemptComplete(final Set<String> successfulRemoveIDs) {
         if (successfulRemoveIDs.isEmpty()) {
             return;
         }
 
-        final File[] files = storeDir.listFiles(new PingFileFilter(successfulRemoveIDs));
+        final File[] files = storeDir.listFiles(new FilenameWhitelistFilter(successfulRemoveIDs));
         for (final File file : files) {
             file.delete();
         }
     }
 
     /**
      * Locks the given {@link FileOutputStream} and writes the given String. This method will close the given stream.
      *
@@ -246,37 +218,16 @@ public class TelemetryJSONFilePingStore 
             // a ClosedChannelException. To be safe, we could catch that every time but there is a performance
             // hit to exception handling so instead we assume the file lock will be closed.
             return new JSONObject(FileUtils.readStringFromInputStreamAndCloseStream(inputStream, fileSize));
         } finally {
             inputStream.close(); // redundant: closed when the stream is closed, but let's be safe.
         }
     }
 
-    private static class PingFileFilter implements FilenameFilter {
-        private final Set<Integer> idsToFilter;
-
-        public PingFileFilter() {
-            this(null);
-        }
-
-        public PingFileFilter(final Set<Integer> idsToFilter) {
-            this.idsToFilter = idsToFilter;
-        }
-
-        @Override
-        public boolean accept(final File dir, final String filename) {
-            if (idsToFilter == null) {
-                return FILENAME_PATTERN.matcher(filename).matches();
-            }
-
-            return idsToFilter.contains(getIDFromFilename(filename));
-        }
-    }
-
     public static final Parcelable.Creator<TelemetryJSONFilePingStore> CREATOR = new Parcelable.Creator<TelemetryJSONFilePingStore>() {
         @Override
         public TelemetryJSONFilePingStore createFromParcel(final Parcel source) {
             final String storeDirPath = source.readString();
             return new TelemetryJSONFilePingStore(new File(storeDirPath));
         }
 
         @Override

--- a/mobile/android/base/java/org/mozilla/gecko/telemetry/stores/TelemetryPingStore.java
+++ b/mobile/android/base/java/org/mozilla/gecko/telemetry/stores/TelemetryPingStore.java
@@ -39,13 +39,12 @@ public interface TelemetryPingStore exte
      * Removes telemetry pings from the store if there are too many pings or they take up too much space.
      */
     void maybePrunePings();
 
     /**
      * Removes the successfully uploaded pings from the database and performs another other actions necessary
      * for when upload is completed.
      *
-     * @param successfulRemoveIDs unique ids of pings passed to {@link #storePing(TelemetryPing)} that were
-     *                            successfully uploaded
+     * @param successfulRemoveIDs doc ids of pings that were successfully uploaded
      */
-    void onUploadAttemptComplete(Set<Integer> successfulRemoveIDs);
+    void onUploadAttemptComplete(Set<String> successfulRemoveIDs);
 }

--- a/mobile/android/tests/background/junit4/src/org/mozilla/gecko/telemetry/stores/TestTelemetryJSONFilePingStore.java
+++ b/mobile/android/tests/background/junit4/src/org/mozilla/gecko/telemetry/stores/TestTelemetryJSONFilePingStore.java
@@ -15,31 +15,29 @@ import org.junit.runner.RunWith;
 import org.mozilla.gecko.background.testhelpers.TestRunner;
 import org.mozilla.gecko.sync.ExtendedJSONObject;
 import org.mozilla.gecko.telemetry.TelemetryPing;
 import org.mozilla.gecko.util.FileUtils;
 
 import java.io.File;
 import java.io.FileOutputStream;
 import java.util.ArrayList;
-import java.util.Arrays;
 import java.util.HashSet;
-import java.util.regex.Matcher;
-import java.util.regex.Pattern;
+import java.util.List;
+import java.util.Set;
+import java.util.UUID;
 
 import static org.junit.Assert.*;
 
 /**
  * Unit test methods of the {@link TelemetryJSONFilePingStore} class.
  */
 @RunWith(TestRunner.class)
 public class TestTelemetryJSONFilePingStore {
 
-    private final Pattern ID_PATTERN = Pattern.compile("[^0-9]*([0-9]+)[^0-9]*");
-
     @Rule
     public TemporaryFolder tempDir = new TemporaryFolder();
     private File testDir;
     private TelemetryJSONFilePingStore testStore;
 
     @Before
     public void setUp() throws Exception {
         testDir = tempDir.newFolder();
@@ -70,41 +68,41 @@ public class TestTelemetryJSONFilePingSt
         assertTrue("Store dir exists", testDir.exists());
         assertEquals("Temp dir contains one dir (the store dir)", 1, tempDir.getRoot().list().length);
     }
 
     @Test
     public void testStorePingStoresCorrectData() throws Exception {
         assertStoreFileCount(0);
 
-        final int expectedID = 48679;
+        final String expectedID = getDocID();
         final TelemetryPing expectedPing = new TelemetryPing("a/server/url", generateTelemetryPayload(), expectedID);
         testStore.storePing(expectedPing);
 
         assertStoreFileCount(1);
         final String filename = testDir.list()[0];
-        assertTrue("Filename contains expected ID", filename.contains(Integer.toString(expectedID)));
+        assertTrue("Filename contains expected ID", filename.equals(expectedID));
         final JSONObject actual = FileUtils.readJSONObjectFromFile(new File(testDir, filename));
         assertEquals("Ping url paths are equal", expectedPing.getURLPath(), actual.getString(TelemetryJSONFilePingStore.KEY_URL_PATH));
         assertIsGeneratedPayload(new ExtendedJSONObject(actual.getString(TelemetryJSONFilePingStore.KEY_PAYLOAD)));
     }
 
     @Test
     public void testStorePingMultiplePingsStoreSeparateFiles() throws Exception {
         assertStoreFileCount(0);
         for (int i = 1; i < 10; ++i) {
-            testStore.storePing(new TelemetryPing("server " + i, generateTelemetryPayload(), i));
+            testStore.storePing(new TelemetryPing("server", generateTelemetryPayload(), getDocID()));
             assertStoreFileCount(i);
         }
     }
 
     @Test
     public void testStorePingReleasesFileLock() throws Exception {
         assertStoreFileCount(0);
-        testStore.storePing(new TelemetryPing("server", generateTelemetryPayload(), 0));
+        testStore.storePing(new TelemetryPing("server", generateTelemetryPayload(), getDocID()));
         assertStoreFileCount(1);
         final File file = new File(testDir, testDir.list()[0]);
         final FileOutputStream stream = new FileOutputStream(file);
         try {
             assertNotNull("File lock is released after store write", stream.getChannel().tryLock());
         } finally {
             stream.close(); // releases lock
         }
@@ -112,18 +110,17 @@ public class TestTelemetryJSONFilePingSt
 
     @Test
     public void testGetAllPings() throws Exception {
         final String urlPrefix = "url";
         writeTestPingsToStore(3, urlPrefix);
 
         final ArrayList<TelemetryPing> pings = testStore.getAllPings();
         for (final TelemetryPing ping : pings) {
-            final int id = ping.getUniqueID(); // we use ID as a key for specific pings and check against the url values.
-            assertEquals("Expected url path value received", urlPrefix + id, ping.getURLPath());
+            assertEquals("Expected url path value received", urlPrefix + ping.getDocID(), ping.getURLPath());
             assertIsGeneratedPayload(ping.getPayload());
         }
     }
 
     @Test
     public void testMaybePrunePingsDoesNothingIfAtMax() throws Exception {
         final int pingCount = TelemetryJSONFilePingStore.MAX_PING_COUNT;
         writeTestPingsToStore(pingCount, "whatever");
@@ -135,68 +132,66 @@ public class TestTelemetryJSONFilePingSt
     @Test
     public void testMaybePrunePingsPrunesIfAboveMax() throws Exception {
         final int pingCount = TelemetryJSONFilePingStore.MAX_PING_COUNT + 1;
         writeTestPingsToStore(pingCount, "whatever");
         assertStoreFileCount(pingCount);
         testStore.maybePrunePings();
         assertStoreFileCount(TelemetryJSONFilePingStore.MAX_PING_COUNT);
 
-        final HashSet<Integer> existingIDs = new HashSet<>(TelemetryJSONFilePingStore.MAX_PING_COUNT);
+        final HashSet<String> existingIDs = new HashSet<>(TelemetryJSONFilePingStore.MAX_PING_COUNT);
         for (final String filename : testDir.list()) {
-            existingIDs.add(getIDFromFilename(filename));
+            existingIDs.add(filename);
         }
         assertFalse("Smallest ID was removed", existingIDs.contains(1));
     }
 
     @Test
     public void testOnUploadAttemptCompleted() throws Exception {
-        writeTestPingsToStore(10, "url");
-        final HashSet<Integer> unuploadedPingIDs = new HashSet<>(Arrays.asList(1, 3, 5, 7, 9));
-        final HashSet<Integer> removedPingIDs = new HashSet<>(Arrays.asList(2, 4, 6, 8, 10));
+        final List<String> savedDocIDs = writeTestPingsToStore(10, "url");
+        final int halfSize = savedDocIDs.size() / 2;
+        final Set<String> unuploadedPingIDs = new HashSet<>(savedDocIDs.subList(0, halfSize));
+        final Set<String> removedPingIDs = new HashSet<>(savedDocIDs.subList(halfSize, savedDocIDs.size()));
         testStore.onUploadAttemptComplete(removedPingIDs);
 
-        for (final String unuploadedFilePath : testDir.list()) {
-            final int unuploadedID = getIDFromFilename(unuploadedFilePath);
-            assertFalse("Unuploaded ID is not in removed ping IDs", removedPingIDs.contains(unuploadedID));
-            assertTrue("Unuploaded ID is in unuploaded ping IDs", unuploadedPingIDs.contains(unuploadedID));
-            unuploadedPingIDs.remove(unuploadedID);
+        for (final String unuploadedDocID : testDir.list()) {
+            assertFalse("Unuploaded ID is not in removed ping IDs", removedPingIDs.contains(unuploadedDocID));
+            assertTrue("Unuploaded ID is in unuploaded ping IDs", unuploadedPingIDs.contains(unuploadedDocID));
+            unuploadedPingIDs.remove(unuploadedDocID);
         }
         assertTrue("All non-successful-upload ping IDs were matched", unuploadedPingIDs.isEmpty());
     }
 
     @Test
-    public void testGetPingFileContainsID() throws Exception {
-        final int expected = 1234567890;
-        final File file = testStore.getPingFile(expected);
-        assertTrue("Ping filename contains ID", file.getName().contains(Integer.toString(expected)));
-    }
-
-    @Test // assumes {@link TelemetryJSONFilePingStore.getPingFile(String)} is working.
-    public void testGetIDFromFilename() throws Exception {
-        final int expectedID = 465739201;
-        final File file = testStore.getPingFile(expectedID);
-        assertEquals("Retrieved ID from filename", expectedID, TelemetryJSONFilePingStore.getIDFromFilename(file.getName()));
-    }
-
-    private int getIDFromFilename(final String filename) {
-        final Matcher matcher = ID_PATTERN.matcher(filename);
-        assertTrue("Filename contains ID", matcher.matches());
-        return Integer.parseInt(matcher.group(1));
+    public void testGetPingFileIsDocID() throws Exception {
+        final String docID = getDocID();
+        final File file = testStore.getPingFile(docID);
+        assertTrue("Ping filename contains ID", file.getName().equals(docID));
     }
 
     /**
      * Writes pings to store without using store API with:
-     *   id = 1 to count (inclusive)
-     *   server = urlPrefix + id
+     *   server = urlPrefix + docID
      *   payload = generated payload
      *
-     * Note: assumes {@link TelemetryJSONFilePingStore#getPingFile(long)} works.
+     * The docID is stored as the filename.
+     *
+     * Note: assumes {@link TelemetryJSONFilePingStore#getPingFile(String)} works.
+     *
+     * @return a list of doc IDs saved to disk
      */
-    private void writeTestPingsToStore(final int count, final String urlPrefix) throws Exception {
+    private List<String> writeTestPingsToStore(final int count, final String urlPrefix) throws Exception {
+        final List<String> savedDocIDs = new ArrayList<>(count);
         for (int i = 1; i <= count; ++i) {
+            final String docID = getDocID();
             final JSONObject obj = new JSONObject()
-                    .put(TelemetryJSONFilePingStore.KEY_URL_PATH, urlPrefix + i)
+                    .put(TelemetryJSONFilePingStore.KEY_URL_PATH, urlPrefix + docID)
                     .put(TelemetryJSONFilePingStore.KEY_PAYLOAD, generateTelemetryPayload());
-            FileUtils.writeJSONObjectToFile(testStore.getPingFile(i), obj);
+            FileUtils.writeJSONObjectToFile(testStore.getPingFile(docID), obj);
+            savedDocIDs.add(docID);
         }
+        return savedDocIDs;
+    }
+
+    private String getDocID() {
+        return UUID.randomUUID().toString();
     }
 }