diff --git a/src/ca-storage-detail/ca-memory.cpp b/src/ca-storage-detail/ca-memory.cpp
index 827f36c..5adaa21 100644
--- a/src/ca-storage-detail/ca-memory.cpp
+++ b/src/ca-storage-detail/ca-memory.cpp
@@ -43,24 +43,23 @@
 void
 CaMemory::addRequest(const CaState& request)
 {
-  for (auto& entry : m_requests) {
-    const auto& existingRequest = entry.second;
-    if (existingRequest.m_cert.getKeyName() == request.m_cert.getKeyName()) {
-      BOOST_THROW_EXCEPTION(Error("Request for " + request.m_cert.getKeyName().toUri() + " already exists"));
-      return;
+    auto keyNameTLV = request.m_cert.getKeyName();
+    if (request.m_requestType == RequestType::NEW) {
+      if (m_requestKeyIndex.find(keyNameTLV) != m_requestKeyIndex.end()
+            && !m_requestKeyIndex.find(keyNameTLV)->second.empty()){
+        BOOST_THROW_EXCEPTION(Error("Request for " + keyNameTLV.toUri() + " already exists"));
+        return;
+      }
+      if (m_certsKeyIndex.find(keyNameTLV) != m_certsKeyIndex.end()) {
+        BOOST_THROW_EXCEPTION(Error("Cert for " + keyNameTLV.toUri() + " already exists"));
+        return;
+      }
     }
-  }
-  for (auto& entry : m_issuedCerts) {
-    const auto& cert = entry.second;
-    if (cert.getKeyName() == request.m_cert.getKeyName()) {
-      BOOST_THROW_EXCEPTION(Error("Cert for " + request.m_cert.getKeyName().toUri() + " already exists"));
-      return;
-    }
-  }
 
   auto search = m_requests.find(request.m_requestId);
   if (search == m_requests.end()) {
     m_requests[request.m_requestId] = request;
+    m_requestKeyIndex[keyNameTLV].insert(request.m_requestId);
   }
   else {
     BOOST_THROW_EXCEPTION(Error("Request " + request.m_requestId + " already exists"));
@@ -70,14 +69,18 @@
 void
 CaMemory::updateRequest(const CaState& request)
 {
-  m_requests[request.m_requestId] = request;
+  m_requests[request.m_requestId].m_status = request.m_status;
+  m_requests[request.m_requestId].m_challengeState = request.m_challengeState;
 }
 
 void
 CaMemory::deleteRequest(const std::string& requestId)
 {
   auto search = m_requests.find(requestId);
+  auto keyName = search->second.m_cert.getKeyName();
   if (search != m_requests.end()) {
+    m_requestKeyIndex.find(keyName)->second.erase(requestId);
+    if (m_requestKeyIndex.find(keyName)->second.empty()) m_requestKeyIndex.erase(keyName);
     m_requests.erase(search);
   }
 }
@@ -121,6 +124,7 @@
   auto search = m_issuedCerts.find(certId);
   if (search == m_issuedCerts.end()) {
     m_issuedCerts[certId] = cert;
+    m_certsKeyIndex[cert.getKeyName()] = certId;
   }
   else {
     BOOST_THROW_EXCEPTION(Error("Certificate " + cert.getName().toUri() + " already exists"));
@@ -138,6 +142,7 @@
 {
   auto search = m_issuedCerts.find(certId);
   if (search != m_issuedCerts.end()) {
+    m_certsKeyIndex.erase(search->second.getKeyName());
     m_issuedCerts.erase(search);
   }
 }
diff --git a/src/ca-storage-detail/ca-memory.hpp b/src/ca-storage-detail/ca-memory.hpp
index 63fded7..25b2e25 100644
--- a/src/ca-storage-detail/ca-memory.hpp
+++ b/src/ca-storage-detail/ca-memory.hpp
@@ -73,6 +73,8 @@
 private:
   std::map<std::string, CaState> m_requests;
   std::map<std::string, security::v2::Certificate> m_issuedCerts;
+  std::map<Name, std::set<std::string>> m_requestKeyIndex;
+  std::map<Name, std::string> m_certsKeyIndex;
 };
 
 } // namespace ndncert
diff --git a/src/ca-storage-detail/ca-sqlite.cpp b/src/ca-storage-detail/ca-sqlite.cpp
index a3ff327..a658c43 100644
--- a/src/ca-storage-detail/ca-sqlite.cpp
+++ b/src/ca-storage-detail/ca-sqlite.cpp
@@ -55,7 +55,7 @@
   );
 CREATE UNIQUE INDEX IF NOT EXISTS
   CaStateIdIndex ON CaStates(request_id);
-CREATE UNIQUE INDEX IF NOT EXISTS
+CREATE INDEX IF NOT EXISTS
   CaStateKeyNameIndex ON CaStates(cert_key_name);
 
 CREATE TABLE IF NOT EXISTS
@@ -158,19 +158,21 @@
 
   // check whether request is there already
   auto keyNameTlv = request.m_cert.getKeyName().wireEncode();
-  Sqlite3Statement statement1(m_database,
-          R"_SQLTEXT_(SELECT 1 FROM CaStates where cert_key_name = ?)_SQLTEXT_");
-  statement1.bind(1, keyNameTlv, SQLITE_TRANSIENT);
-  if (statement1.step() == SQLITE_ROW) {
-    BOOST_THROW_EXCEPTION(Error("Request for " + request.m_cert.getKeyName().toUri() + " already exists"));
-  }
+  if (request.m_requestType == RequestType::NEW) {
+    Sqlite3Statement statement1(m_database,
+                                R"_SQLTEXT_(SELECT 1 FROM CaStates where cert_key_name = ?)_SQLTEXT_");
+    statement1.bind(1, keyNameTlv, SQLITE_TRANSIENT);
+    if (statement1.step() == SQLITE_ROW) {
+      BOOST_THROW_EXCEPTION(Error("Request for " + request.m_cert.getKeyName().toUri() + " already exists"));
+    }
 
-  // check whether certificate is already issued
-  Sqlite3Statement statement2(m_database,
-                              R"_SQLTEXT_(SELECT 1 FROM IssuedCerts where cert_key_name = ?)_SQLTEXT_");
-  statement2.bind(1, keyNameTlv, SQLITE_TRANSIENT);
-  if (statement2.step() == SQLITE_ROW) {
-    BOOST_THROW_EXCEPTION(Error("Cert for " + request.m_cert.getKeyName().toUri() + " already exists"));
+    // check whether certificate is already issued
+    Sqlite3Statement statement2(m_database,
+                                R"_SQLTEXT_(SELECT 1 FROM IssuedCerts where cert_key_name = ?)_SQLTEXT_");
+    statement2.bind(1, keyNameTlv, SQLITE_TRANSIENT);
+    if (statement2.step() == SQLITE_ROW) {
+      BOOST_THROW_EXCEPTION(Error("Cert for " + request.m_cert.getKeyName().toUri() + " already exists"));
+    }
   }
 
   Sqlite3Statement statement(