diff --git a/common/fake_prefs.cc b/common/fake_prefs.cc
index c446e06..73559c5 100644
--- a/common/fake_prefs.cc
+++ b/common/fake_prefs.cc
@@ -21,6 +21,7 @@
 #include <gtest/gtest.h>
 
 using std::string;
+using std::vector;
 
 using chromeos_update_engine::FakePrefs;
 
@@ -105,6 +106,13 @@
   return true;
 }
 
+bool FakePrefs::GetSubKeys(const string& ns, vector<string>* keys) const {
+  for (const auto& pr : values_)
+    if (pr.first.compare(0, ns.length(), ns) == 0)
+      keys->push_back(pr.first);
+  return true;
+}
+
 string FakePrefs::GetTypeName(PrefType type) {
   switch (type) {
     case PrefType::kString:
diff --git a/common/fake_prefs.h b/common/fake_prefs.h
index b1c5b71..b24ff4d 100644
--- a/common/fake_prefs.h
+++ b/common/fake_prefs.h
@@ -49,6 +49,9 @@
   bool Exists(const std::string& key) const override;
   bool Delete(const std::string& key) override;
 
+  bool GetSubKeys(const std::string& ns,
+                  std::vector<std::string>* keys) const override;
+
   void AddObserver(const std::string& key,
                    ObserverInterface* observer) override;
   void RemoveObserver(const std::string& key,
diff --git a/common/mock_prefs.h b/common/mock_prefs.h
index 2582e19..62417a8 100644
--- a/common/mock_prefs.h
+++ b/common/mock_prefs.h
@@ -18,6 +18,7 @@
 #define UPDATE_ENGINE_COMMON_MOCK_PREFS_H_
 
 #include <string>
+#include <vector>
 
 #include <gmock/gmock.h>
 
@@ -41,6 +42,9 @@
   MOCK_CONST_METHOD1(Exists, bool(const std::string& key));
   MOCK_METHOD1(Delete, bool(const std::string& key));
 
+  MOCK_CONST_METHOD2(GetSubKeys,
+                     bool(const std::string&, std::vector<std::string>*));
+
   MOCK_METHOD2(AddObserver, void(const std::string& key, ObserverInterface*));
   MOCK_METHOD2(RemoveObserver,
                void(const std::string& key, ObserverInterface*));
diff --git a/common/prefs.cc b/common/prefs.cc
index 6db01b7..615014f 100644
--- a/common/prefs.cc
+++ b/common/prefs.cc
@@ -32,10 +32,10 @@
 
 namespace chromeos_update_engine {
 
-const char kKeySeparator = '/';
-
 namespace {
 
+const char kKeySeparator = '/';
+
 void DeleteEmptyDirectories(const base::FilePath& path) {
   base::FileEnumerator path_enum(
       path, false /* recursive */, base::FileEnumerator::DIRECTORIES);
@@ -112,6 +112,10 @@
   return true;
 }
 
+bool PrefsBase::GetSubKeys(const string& ns, vector<string>* keys) const {
+  return storage_->GetSubKeys(ns, keys);
+}
+
 void PrefsBase::AddObserver(const string& key, ObserverInterface* observer) {
   observers_[key].push_back(observer);
 }
@@ -150,6 +154,24 @@
   return true;
 }
 
+bool Prefs::FileStorage::GetSubKeys(const string& ns,
+                                    vector<string>* keys) const {
+  base::FilePath filename;
+  TEST_AND_RETURN_FALSE(GetFileNameForKey(ns, &filename));
+  base::FileEnumerator namespace_enum(
+      prefs_dir_, true, base::FileEnumerator::FILES);
+  for (base::FilePath f = namespace_enum.Next(); !f.empty();
+       f = namespace_enum.Next()) {
+    auto filename_str = filename.value();
+    if (f.value().compare(0, filename_str.length(), filename_str) == 0) {
+      // Only return the key portion excluding the |prefs_dir_| with slash.
+      keys->push_back(f.value().substr(
+          prefs_dir_.AsEndingWithSeparator().value().length()));
+    }
+  }
+  return true;
+}
+
 bool Prefs::FileStorage::SetKey(const string& key, const string& value) {
   base::FilePath filename;
   TEST_AND_RETURN_FALSE(GetFileNameForKey(key, &filename));
@@ -172,19 +194,17 @@
 bool Prefs::FileStorage::DeleteKey(const string& key) {
   base::FilePath filename;
   TEST_AND_RETURN_FALSE(GetFileNameForKey(key, &filename));
-  TEST_AND_RETURN_FALSE(base::DeleteFile(filename, true));
+  TEST_AND_RETURN_FALSE(base::DeleteFile(filename, false));
   return true;
 }
 
 bool Prefs::FileStorage::GetFileNameForKey(const string& key,
                                            base::FilePath* filename) const {
-  // Allows only non-empty keys containing [A-Za-z0-9_-].
+  // Allows only non-empty keys containing [A-Za-z0-9_-/].
   TEST_AND_RETURN_FALSE(!key.empty());
-  for (size_t i = 0; i < key.size(); ++i) {
-    char c = key.at(i);
+  for (char c : key)
     TEST_AND_RETURN_FALSE(base::IsAsciiAlpha(c) || base::IsAsciiDigit(c) ||
                           c == '_' || c == '-' || c == kKeySeparator);
-  }
   *filename = prefs_dir_.Append(key);
   return true;
 }
@@ -200,6 +220,24 @@
   return true;
 }
 
+bool MemoryPrefs::MemoryStorage::GetSubKeys(const string& ns,
+                                            vector<string>* keys) const {
+  using value_type = decltype(values_)::value_type;
+  using key_type = decltype(values_)::key_type;
+  auto lower_comp = [](const value_type& pr, const key_type& ns) {
+    return pr.first.substr(0, ns.length()) < ns;
+  };
+  auto upper_comp = [](const key_type& ns, const value_type& pr) {
+    return ns < pr.first.substr(0, ns.length());
+  };
+  auto lower_it =
+      std::lower_bound(begin(values_), end(values_), ns, lower_comp);
+  auto upper_it = std::upper_bound(lower_it, end(values_), ns, upper_comp);
+  while (lower_it != upper_it)
+    keys->push_back((lower_it++)->first);
+  return true;
+}
+
 bool MemoryPrefs::MemoryStorage::SetKey(const string& key,
                                         const string& value) {
   values_[key] = value;
diff --git a/common/prefs.h b/common/prefs.h
index 0116454..3fc1d89 100644
--- a/common/prefs.h
+++ b/common/prefs.h
@@ -42,6 +42,11 @@
     // Returns whether the operation succeeded.
     virtual bool GetKey(const std::string& key, std::string* value) const = 0;
 
+    // Get the keys stored within the namespace. If there are no keys in the
+    // namespace, |keys| will be empty. Returns whether the operation succeeded.
+    virtual bool GetSubKeys(const std::string& ns,
+                            std::vector<std::string>* keys) const = 0;
+
     // Set the value of the key named |key| to |value| regardless of the
     // previous value. Returns whether the operation succeeded.
     virtual bool SetKey(const std::string& key, const std::string& value) = 0;
@@ -70,6 +75,9 @@
   bool Exists(const std::string& key) const override;
   bool Delete(const std::string& key) override;
 
+  bool GetSubKeys(const std::string& ns,
+                  std::vector<std::string>* keys) const override;
+
   void AddObserver(const std::string& key,
                    ObserverInterface* observer) override;
   void RemoveObserver(const std::string& key,
@@ -111,6 +119,8 @@
 
     // PrefsBase::StorageInterface overrides.
     bool GetKey(const std::string& key, std::string* value) const override;
+    bool GetSubKeys(const std::string& ns,
+                    std::vector<std::string>* keys) const override;
     bool SetKey(const std::string& key, const std::string& value) override;
     bool KeyExists(const std::string& key) const override;
     bool DeleteKey(const std::string& key) override;
@@ -149,6 +159,8 @@
 
     // PrefsBase::StorageInterface overrides.
     bool GetKey(const std::string& key, std::string* value) const override;
+    bool GetSubKeys(const std::string& ns,
+                    std::vector<std::string>* keys) const override;
     bool SetKey(const std::string& key, const std::string& value) override;
     bool KeyExists(const std::string& key) const override;
     bool DeleteKey(const std::string& key) override;
diff --git a/common/prefs_interface.h b/common/prefs_interface.h
index 3aad480..1311cb4 100644
--- a/common/prefs_interface.h
+++ b/common/prefs_interface.h
@@ -83,6 +83,10 @@
   // Creates a key which is part of a sub preference.
   static std::string CreateSubKey(const std::vector<std::string>& ns_with_key);
 
+  // Returns a list of keys within the namespace.
+  virtual bool GetSubKeys(const std::string& ns,
+                          std::vector<std::string>* keys) const = 0;
+
   // Add an observer to watch whenever the given |key| is modified. The
   // OnPrefSet() and OnPrefDelete() methods will be called whenever any of the
   // Set*() methods or the Delete() method are called on the given key,
diff --git a/common/prefs_unittest.cc b/common/prefs_unittest.cc
index 24a62b5..6dd26c0 100644
--- a/common/prefs_unittest.cc
+++ b/common/prefs_unittest.cc
@@ -20,6 +20,7 @@
 
 #include <limits>
 #include <string>
+#include <vector>
 
 #include <base/files/file_util.h>
 #include <base/files/scoped_temp_dir.h>
@@ -30,9 +31,11 @@
 #include <gtest/gtest.h>
 
 using std::string;
+using std::vector;
 using testing::_;
 using testing::ElementsAre;
 using testing::Eq;
+using testing::UnorderedElementsAre;
 
 namespace {
 // Test key used along the tests.
@@ -41,12 +44,92 @@
 
 namespace chromeos_update_engine {
 
-class PrefsTest : public ::testing::Test {
+class BasePrefsTest : public ::testing::Test {
+ protected:
+  void MultiNamespaceKeyTest() {
+    ASSERT_TRUE(common_prefs_);
+    auto key0 = common_prefs_->CreateSubKey({"ns1", "key"});
+    // Corner case for "ns1".
+    auto key0corner = common_prefs_->CreateSubKey({"ns11", "key"});
+    auto key1A = common_prefs_->CreateSubKey({"ns1", "nsA", "keyA"});
+    auto key1B = common_prefs_->CreateSubKey({"ns1", "nsA", "keyB"});
+    auto key2 = common_prefs_->CreateSubKey({"ns1", "nsB", "key"});
+    // Corner case for "ns1/nsB".
+    auto key2corner = common_prefs_->CreateSubKey({"ns1", "nsB1", "key"});
+    EXPECT_FALSE(common_prefs_->Exists(key0));
+    EXPECT_FALSE(common_prefs_->Exists(key1A));
+    EXPECT_FALSE(common_prefs_->Exists(key1B));
+    EXPECT_FALSE(common_prefs_->Exists(key2));
+
+    EXPECT_TRUE(common_prefs_->SetString(key0, ""));
+    EXPECT_TRUE(common_prefs_->SetString(key0corner, ""));
+    EXPECT_TRUE(common_prefs_->SetString(key1A, ""));
+    EXPECT_TRUE(common_prefs_->SetString(key1B, ""));
+    EXPECT_TRUE(common_prefs_->SetString(key2, ""));
+    EXPECT_TRUE(common_prefs_->SetString(key2corner, ""));
+
+    EXPECT_TRUE(common_prefs_->Exists(key0));
+    EXPECT_TRUE(common_prefs_->Exists(key0corner));
+    EXPECT_TRUE(common_prefs_->Exists(key1A));
+    EXPECT_TRUE(common_prefs_->Exists(key1B));
+    EXPECT_TRUE(common_prefs_->Exists(key2));
+    EXPECT_TRUE(common_prefs_->Exists(key2corner));
+
+    vector<string> keys2;
+    EXPECT_TRUE(common_prefs_->GetSubKeys("ns1/nsB/", &keys2));
+    EXPECT_THAT(keys2, ElementsAre(key2));
+    for (const auto& key : keys2)
+      EXPECT_TRUE(common_prefs_->Delete(key));
+    EXPECT_TRUE(common_prefs_->Exists(key0));
+    EXPECT_TRUE(common_prefs_->Exists(key0corner));
+    EXPECT_TRUE(common_prefs_->Exists(key1A));
+    EXPECT_TRUE(common_prefs_->Exists(key1B));
+    EXPECT_FALSE(common_prefs_->Exists(key2));
+    EXPECT_TRUE(common_prefs_->Exists(key2corner));
+
+    vector<string> keys2corner;
+    EXPECT_TRUE(common_prefs_->GetSubKeys("ns1/nsB", &keys2corner));
+    EXPECT_THAT(keys2corner, ElementsAre(key2corner));
+    for (const auto& key : keys2corner)
+      EXPECT_TRUE(common_prefs_->Delete(key));
+    EXPECT_FALSE(common_prefs_->Exists(key2corner));
+
+    vector<string> keys1;
+    EXPECT_TRUE(common_prefs_->GetSubKeys("ns1/nsA/", &keys1));
+    EXPECT_THAT(keys1, UnorderedElementsAre(key1A, key1B));
+    for (const auto& key : keys1)
+      EXPECT_TRUE(common_prefs_->Delete(key));
+    EXPECT_TRUE(common_prefs_->Exists(key0));
+    EXPECT_TRUE(common_prefs_->Exists(key0corner));
+    EXPECT_FALSE(common_prefs_->Exists(key1A));
+    EXPECT_FALSE(common_prefs_->Exists(key1B));
+
+    vector<string> keys0;
+    EXPECT_TRUE(common_prefs_->GetSubKeys("ns1/", &keys0));
+    EXPECT_THAT(keys0, ElementsAre(key0));
+    for (const auto& key : keys0)
+      EXPECT_TRUE(common_prefs_->Delete(key));
+    EXPECT_FALSE(common_prefs_->Exists(key0));
+    EXPECT_TRUE(common_prefs_->Exists(key0corner));
+
+    vector<string> keys0corner;
+    EXPECT_TRUE(common_prefs_->GetSubKeys("ns1", &keys0corner));
+    EXPECT_THAT(keys0corner, ElementsAre(key0corner));
+    for (const auto& key : keys0corner)
+      EXPECT_TRUE(common_prefs_->Delete(key));
+    EXPECT_FALSE(common_prefs_->Exists(key0corner));
+  }
+
+  PrefsInterface* common_prefs_;
+};
+
+class PrefsTest : public BasePrefsTest {
  protected:
   void SetUp() override {
     ASSERT_TRUE(temp_dir_.CreateUniqueTempDir());
     prefs_dir_ = temp_dir_.GetPath();
     ASSERT_TRUE(prefs_.Init(prefs_dir_));
+    common_prefs_ = &prefs_;
   }
 
   bool SetValue(const string& key, const string& value) {
@@ -415,8 +498,14 @@
   prefs_.RemoveObserver(kInvalidKey, &mock_obserser);
 }
 
-class MemoryPrefsTest : public ::testing::Test {
+TEST_F(PrefsTest, MultiNamespaceKeyTest) {
+  MultiNamespaceKeyTest();
+}
+
+class MemoryPrefsTest : public BasePrefsTest {
  protected:
+  void SetUp() override { common_prefs_ = &prefs_; }
+
   MemoryPrefs prefs_;
 };
 
@@ -440,4 +529,8 @@
   EXPECT_TRUE(prefs_.Delete(kKey));
 }
 
+TEST_F(MemoryPrefsTest, MultiNamespaceKeyTest) {
+  MultiNamespaceKeyTest();
+}
+
 }  // namespace chromeos_update_engine