Merge branch 'master' of ssh://gnunet.org/gnunet

12 files changed, 1329 insertions, 960 deletions

diff --git a/src/datastore/gnunet-datastore.c b/src/datastore/gnunet-datastore.c
index 9e0ee205e..891343e17 100644
--- a/src/datastore/gnunet-datastore.c
+++ b/src/datastore/gnunet-datastore.c
@@ -23,101 +23,136 @@
  * @brief tool to manipulate datastores
  * @author Christian Grothoff
  */
+#include <inttypes.h>
 #include "platform.h"
 #include "gnunet_util_lib.h"
 #include "gnunet_datastore_service.h"
 
+GNUNET_NETWORK_STRUCT_BEGIN
+
+struct DataRecord
+{
+  /**
+   * Number of bytes in the item (NBO).
+   */
+  uint32_t size GNUNET_PACKED;
+
+  /**
+   * Type of the item (NBO) (actually an enum GNUNET_BLOCK_Type)
+   */
+  uint32_t type GNUNET_PACKED;
+
+  /**
+   * Priority of the item (NBO).
+   */
+  uint32_t priority GNUNET_PACKED;
+
+  /**
+   * Desired anonymity level (NBO).
+   */
+  uint32_t anonymity GNUNET_PACKED;
+
+  /**
+   * Desired replication level (NBO).
+   */
+  uint32_t replication GNUNET_PACKED;
+
+  /**
+   * Expiration time (NBO).
+   */
+  struct GNUNET_TIME_AbsoluteNBO expiration;
+
+  /**
+   * Key under which the item can be found.
+   */
+  struct GNUNET_HashCode key;
+
+};
+GNUNET_NETWORK_STRUCT_END
+
 
 /**
- * Name of the second configuration file.
+ * Length of our magic header.
  */
-static char *alternative_cfg;
+static const size_t MAGIC_LEN = 16;
 
 /**
- * Global return value.
+ * Magic header bytes.
  */
-static int ret;
+static const uint8_t MAGIC_BYTES[16] = "GNUNETDATASTORE1";
+
+/**
+ * Dump the database.
+ */
+static int dump;
 
 /**
- * Our offset on 'get'.
+ * Insert into the database.
  */
-static uint64_t offset;
+static int insert;
 
 /**
- * First UID ever returned.
+ * Dump file name.
  */
-static uint64_t first_uid;
+static char *file_name;
 
 /**
- * Configuration for the source database.
+ * Dump file handle.
  */
-static struct GNUNET_CONFIGURATION_Handle *scfg;
+static struct GNUNET_DISK_FileHandle *file_handle;
 
 /**
- * Handle for database source.
+ * Global return value.
  */
-static struct GNUNET_DATASTORE_Handle *db_src;
+static int ret;
 
 /**
- * Handle for database destination.
+ * Handle for datastore.
  */
-static struct GNUNET_DATASTORE_Handle *db_dst;
+static struct GNUNET_DATASTORE_Handle *datastore;
 
 /**
  * Current operation.
  */
 static struct GNUNET_DATASTORE_QueueEntry *qe;
 
+/**
+ * Record count.
+ */
+static uint64_t record_count;
+
 
 static void
 do_shutdown (void *cls)
 {
   if (NULL != qe)
     GNUNET_DATASTORE_cancel (qe);
-  GNUNET_DATASTORE_disconnect (db_src, GNUNET_NO);
-  GNUNET_DATASTORE_disconnect (db_dst, GNUNET_NO);
-  GNUNET_CONFIGURATION_destroy (scfg);
+  if (NULL != datastore)
+    GNUNET_DATASTORE_disconnect (datastore, GNUNET_NO);
+  if (NULL != file_handle)
+    GNUNET_DISK_file_close (file_handle);
 }
 
 
 /**
- * Perform next GET operation.
+ * Begin dumping the database.
  */
 static void
-do_get (void);
+start_dump (void);
 
 
 /**
- * Continuation called to notify client about result of the
- * operation.
- *
- * @param cls closure
- * @param success GNUNET_SYSERR on failure (including timeout/queue drop)
- *                GNUNET_NO if content was already there
- *                GNUNET_YES (or other positive value) on success
- * @param min_expiration minimum expiration time required for 0-priority content to be stored
- *                by the datacache at this time, zero for unknown, forever if we have no
- *                space for 0-priority content
- * @param msg NULL on success, otherwise an error message
+ * Begin inserting into the database.
  */
 static void
-do_finish (void *cls,
-           int32_t success,
-           struct GNUNET_TIME_Absolute min_expiration,
-           const char *msg)
-{
-  qe = NULL;
-  if (GNUNET_SYSERR == success)
-  {
-    fprintf (stderr,
-             _("Failed to store item: %s, aborting\n"),
-             msg);
-    ret = 1;
-    GNUNET_SCHEDULER_shutdown ();
-    return;
-  }
-  do_get ();
-}
+start_insert (void);
+
+
+/**
+ * Perform next GET operation.
+ */
+static void
+do_get (const uint64_t next_uid);
 
 
 /**
@@ -136,7 +171,7 @@ do_finish (void *cls,
  *        maybe 0 if no unique identifier is available
  */
 static void
-do_put (void *cls,
+get_cb (void *cls,
         const struct GNUNET_HashCode *key,
         size_t size,
         const void *data,
@@ -144,33 +179,63 @@ do_put (void *cls,
         uint32_t priority,
         uint32_t anonymity,
         uint32_t replication,
-        struct GNUNET_TIME_Absolute
-        expiration,
+        struct GNUNET_TIME_Absolute expiration,
         uint64_t uid)
 {
   qe = NULL;
-  if ( (0 != offset) &&
-       (uid == first_uid) )
+  if (NULL == key)
   {
+    FPRINTF (stderr,
+             _("Dumped %" PRIu64 " records\n"),
+             record_count);
+    GNUNET_DISK_file_close (file_handle);
+    file_handle = NULL;
+    if (insert)
+      start_insert();
+    else
+    {
+      ret = 0;
+      GNUNET_SCHEDULER_shutdown ();
+    }
+    return;
+  }
+
+  struct DataRecord dr;
+  dr.size = htonl ((uint32_t) size);
+  dr.type = htonl (type);
+  dr.priority = htonl (priority);
+  dr.anonymity = htonl (anonymity);
+  dr.replication = htonl (replication);
+  dr.expiration = GNUNET_TIME_absolute_hton (expiration);
+  dr.key = *key;
+
+  ssize_t len;
+  len = GNUNET_DISK_file_write (file_handle, &dr, sizeof (dr));
+  if (sizeof (dr) != len)
+  {
+    FPRINTF (stderr,
+             _("Short write to file: %zd bytes expecting %zd\n"),
+             len,
+             sizeof (dr));
+    ret = 1;
     GNUNET_SCHEDULER_shutdown ();
     return;
   }
-  if (0 == offset)
-    first_uid = uid;
-  qe = GNUNET_DATASTORE_put (db_dst,
-                             0,
-                             key,
-                             size,
-                             data,
-                             type,
-                             priority,
-                             anonymity,
-                             replication,
-                             expiration,
-                             0,
-                             1,
-                             &do_finish,
-                             NULL);
+
+  len = GNUNET_DISK_file_write (file_handle, data, size);
+  if (size != len)
+  {
+    FPRINTF (stderr,
+             _("Short write to file: %zd bytes expecting %zd\n"),
+             len,
+             size);
+    ret = 1;
+    GNUNET_SCHEDULER_shutdown ();
+    return;
+  }
+
+  record_count++;
+  do_get(uid + 1);
 }
 
 
@@ -178,64 +243,236 @@ do_put (void *cls,
  * Perform next GET operation.
  */
 static void
-do_get ()
+do_get (const uint64_t next_uid)
 {
-  qe = GNUNET_DATASTORE_get_key (db_src,
-                                 0, false,
-                                 NULL, GNUNET_BLOCK_TYPE_ANY,
-                                 0, 1,
-                                 &do_put, NULL);
+  GNUNET_assert (NULL == qe);
+  qe = GNUNET_DATASTORE_get_key (datastore,
+                                 next_uid,
+                                 false /* random */,
+                                 NULL /* key */,
+                                 GNUNET_BLOCK_TYPE_ANY,
+                                 0 /* queue_priority */,
+                                 1 /* max_queue_size */,
+                                 &get_cb,
+                                 NULL /* proc_cls */);
+  if (NULL == qe)
+  {
+    FPRINTF (stderr,
+             _("Error queueing datastore GET operation\n"));
+    ret = 1;
+    GNUNET_SCHEDULER_shutdown ();
+  }
 }
 
 
+/**
+ * Begin dumping the database.
+ */
+static void
+start_dump ()
+{
+  record_count = 0;
+
+  if (NULL != file_name)
+  {
+    file_handle = GNUNET_DISK_file_open (file_name,
+                                         GNUNET_DISK_OPEN_WRITE |
+                                         GNUNET_DISK_OPEN_TRUNCATE |
+                                         GNUNET_DISK_OPEN_CREATE,
+                                         GNUNET_DISK_PERM_USER_READ |
+                                         GNUNET_DISK_PERM_USER_WRITE);
+    if (NULL == file_handle)
+    {
+      FPRINTF (stderr,
+               _("Unable to open dump file: %s\n"),
+               file_name);
+      ret = 1;
+      GNUNET_SCHEDULER_shutdown ();
+      return;
+    }
+  }
+  else
+  {
+    file_handle = GNUNET_DISK_get_handle_from_int_fd (STDOUT_FILENO);
+  }
+  GNUNET_DISK_file_write (file_handle, MAGIC_BYTES, MAGIC_LEN);
+  do_get(0);
+}
+
 
 /**
- * Main function that will be run by the scheduler.
+ * Continuation called to notify client about result of the
+ * operation.
  *
  * @param cls closure
- * @param args remaining command-line arguments
- * @param cfgfile name of the configuration file used
- * @param cfg configuration -- for destination datastore
+ * @param success GNUNET_SYSERR on failure (including timeout/queue drop)
+ *                GNUNET_NO if content was already there
+ *                GNUNET_YES (or other positive value) on success
+ * @param min_expiration minimum expiration time required for 0-priority content to be stored
+ *                by the datacache at this time, zero for unknown, forever if we have no
+ *                space for 0-priority content
+ * @param msg NULL on success, otherwise an error message
  */
 static void
-run (void *cls, char *const *args, const char *cfgfile,
-     const struct GNUNET_CONFIGURATION_Handle *cfg)
+put_cb (void *cls,
+        int32_t success,
+        struct GNUNET_TIME_Absolute min_expiration,
+        const char *msg)
 {
-  if (NULL == alternative_cfg)
-    return; /* nothing to be done */
-  if (0 == strcmp (cfgfile, alternative_cfg))
+  qe = NULL;
+  if (GNUNET_SYSERR == success)
   {
-    fprintf (stderr,
-             _("Cannot use the same configuration for source and destination\n"));
+    FPRINTF (stderr,
+             _("Failed to store item: %s, aborting\n"),
+             msg);
     ret = 1;
+    GNUNET_SCHEDULER_shutdown ();
     return;
   }
-  scfg = GNUNET_CONFIGURATION_create ();
-  if (GNUNET_OK !=
-      GNUNET_CONFIGURATION_load (scfg,
-                                 alternative_cfg))
+
+  struct DataRecord dr;
+  ssize_t len;
+
+  len = GNUNET_DISK_file_read (file_handle, &dr, sizeof (dr));
+  if (0 == len)
+  {
+    FPRINTF (stderr,
+             _("Inserted %" PRIu64 " records\n"),
+             record_count);
+    ret = 0;
+    GNUNET_SCHEDULER_shutdown ();
+    return;
+  }
+  else if (sizeof (dr) != len)
   {
-    GNUNET_CONFIGURATION_destroy (scfg);
+    FPRINTF (stderr,
+             _("Short read from file: %zd bytes expecting %zd\n"),
+             len,
+             sizeof (dr));
     ret = 1;
+    GNUNET_SCHEDULER_shutdown ();
     return;
   }
-  db_src = GNUNET_DATASTORE_connect (scfg);
-  if (NULL == db_src)
+
+  const size_t size = ntohl (dr.size);
+  uint8_t data[size];
+  len = GNUNET_DISK_file_read (file_handle, data, size);
+  if (size != len)
   {
-    GNUNET_CONFIGURATION_destroy (scfg);
+    FPRINTF (stderr,
+             _("Short read from file: %zd bytes expecting %zd\n"),
+             len,
+             size);
     ret = 1;
+    GNUNET_SCHEDULER_shutdown ();
     return;
   }
-  db_dst = GNUNET_DATASTORE_connect (cfg);
-  if (NULL == db_dst)
+
+  record_count++;
+  qe = GNUNET_DATASTORE_put (datastore,
+                             0,
+                             &dr.key,
+                             size,
+                             data,
+                             ntohl (dr.type),
+                             ntohl (dr.priority),
+                             ntohl (dr.anonymity),
+                             ntohl (dr.replication),
+                             GNUNET_TIME_absolute_ntoh (dr.expiration),
+                             0,
+                             1,
+                             &put_cb,
+                             NULL);
+  if (NULL == qe)
   {
-    GNUNET_DATASTORE_disconnect (db_src, GNUNET_NO);
-    GNUNET_CONFIGURATION_destroy (scfg);
+    FPRINTF (stderr,
+             _("Error queueing datastore PUT operation\n"));
     ret = 1;
+    GNUNET_SCHEDULER_shutdown ();
+  }
+}
+
+
+/**
+ * Begin inserting into the database.
+ */
+static void
+start_insert ()
+{
+  record_count = 0;
+
+  if (NULL != file_name)
+  {
+    file_handle = GNUNET_DISK_file_open (file_name,
+                                         GNUNET_DISK_OPEN_READ,
+                                         GNUNET_DISK_PERM_NONE);
+    if (NULL == file_handle)
+    {
+      FPRINTF (stderr,
+               _("Unable to open dump file: %s\n"),
+               file_name);
+      ret = 1;
+      GNUNET_SCHEDULER_shutdown ();
+      return;
+    }
+  }
+  else
+  {
+    file_handle = GNUNET_DISK_get_handle_from_int_fd (STDIN_FILENO);
+  }
+
+  uint8_t buf[MAGIC_LEN];
+  ssize_t len;
+
+  len = GNUNET_DISK_file_read (file_handle, buf, MAGIC_LEN);
+  if (len != MAGIC_LEN ||
+      0 != memcmp (buf, MAGIC_BYTES, MAGIC_LEN))
+  {
+    FPRINTF (stderr,
+             _("Input file is not of a supported format\n"));
     return;
   }
+  put_cb (NULL, GNUNET_YES, GNUNET_TIME_UNIT_ZERO_ABS, NULL);
+}
+
+
+/**
+ * Main function that will be run by the scheduler.
+ *
+ * @param cls closure
+ * @param args remaining command-line arguments
+ * @param cfgfile name of the configuration file used
+ * @param cfg configuration
+ */
+static void
+run (void *cls,
+     char *const *args,
+     const char *cfgfile,
+     const struct GNUNET_CONFIGURATION_Handle *cfg)
+{
   GNUNET_SCHEDULER_add_shutdown (&do_shutdown, NULL);
-  do_get ();
+  datastore = GNUNET_DATASTORE_connect (cfg);
+  if (NULL == datastore)
+  {
+    FPRINTF (stderr,
+             _("Failed connecting to the datastore.\n"));
+    ret = 1;
+    GNUNET_SCHEDULER_shutdown ();
+    return;
+  }
+  if (dump)
+    start_dump();
+  else if (insert)
+    start_insert();
+  else
+  {
+    FPRINTF (stderr,
+             _("Please choose at least one operation: %s, %s\n"),
+             "dump",
+             "insert");
+    ret = 1;
+    GNUNET_SCHEDULER_shutdown ();
+  }
 }
 
 
@@ -247,14 +484,23 @@ run (void *cls, char *const *args, const char *cfgfile,
  * @return 0 ok, 1 on error
  */
 int
-main (int argc, char *const *argv)
+main (int argc,
+      char *const *argv)
 {
   struct GNUNET_GETOPT_CommandLineOption options[] = {
-    GNUNET_GETOPT_option_filename ('s',
-                                   "sourcecfg",
+    GNUNET_GETOPT_option_flag ('d',
+                               "dump",
+                               gettext_noop ("Dump all records from the datastore"),
+                               &dump),
+    GNUNET_GETOPT_option_flag ('i',
+                               "insert",
+                               gettext_noop ("Insert records into the datastore"),
+                               &insert),
+    GNUNET_GETOPT_option_filename ('f',
+                                   "file",
                                    "FILENAME",
-                                   gettext_noop ("specifies the configuration to use to access an alternative datastore; will merge that datastore into our current datastore"),
-                                       &alternative_cfg),
+                                   gettext_noop ("File to dump or insert"),
+                                   &file_name),
     GNUNET_GETOPT_OPTION_END
   };
   if (GNUNET_OK != GNUNET_STRINGS_get_utf8_args (argc, argv, &argc, &argv))
diff --git a/src/datastore/gnunet-service-datastore.c b/src/datastore/gnunet-service-datastore.c
index 277530843..53ba858e4 100644
--- a/src/datastore/gnunet-service-datastore.c
+++ b/src/datastore/gnunet-service-datastore.c
@@ -733,41 +733,23 @@ check_data (const struct DataMessage *dm)
 
 
 /**
- * Context for a PUT request used to see if the content is
- * already present.
- */
-struct PutContext
-{
-  /**
-   * Client to notify on completion.
-   */
-  struct GNUNET_SERVICE_Client *client;
-
-#if ! HAVE_UNALIGNED_64_ACCESS
-  void *reserved;
-#endif
-
-  /* followed by the 'struct DataMessage' */
-};
-
-
-/**
  * Put continuation.
  *
  * @param cls closure
  * @param key key for the item stored
  * @param size size of the item stored
- * @param status #GNUNET_OK or #GNUNET_SYSERROR
+ * @param status #GNUNET_OK if inserted, #GNUNET_NO if updated,
+ *        or #GNUNET_SYSERROR if error
  * @param msg error message on error
  */
 static void
 put_continuation (void *cls,
-                  const struct GNUNET_HashCode *key,
-                  uint32_t size,
+                  const struct GNUNET_HashCode *key,
+                  uint32_t size,
                   int status,
-                  const char *msg)
+                  const char *msg)
 {
-  struct PutContext *pc = cls;
+  struct GNUNET_SERVICE_Client *client = cls;
 
   if (GNUNET_OK == status)
   {
@@ -782,10 +764,9 @@ put_continuation (void *cls,
                 size,
                 GNUNET_h2s (key));
   }
-  transmit_status (pc->client,
-                   status,
+  transmit_status (client,
+                   GNUNET_SYSERR == status ? GNUNET_SYSERR : GNUNET_OK,
                    msg);
-  GNUNET_free (pc);
   if (quota - reserved - cache_size < payload)
   {
     GNUNET_log (GNUNET_ERROR_TYPE_INFO,
@@ -799,125 +780,6 @@ put_continuation (void *cls,
 
 
 /**
- * Actually put the data message.
- *
- * @param pc put context
- */
-static void
-execute_put (struct PutContext *pc)
-{
-  const struct DataMessage *dm;
-
-  dm = (const struct DataMessage *) &pc[1];
-  plugin->api->put (plugin->api->cls,
-                    &dm->key,
-                    ntohl (dm->size),
-                    &dm[1],
-                    ntohl (dm->type),
-                    ntohl (dm->priority),
-                    ntohl (dm->anonymity),
-                    ntohl (dm->replication),
-                    GNUNET_TIME_absolute_ntoh (dm->expiration),
-                    &put_continuation,
-                    pc);
-}
-
-
-/**
- *
- * @param cls closure
- * @param status #GNUNET_OK or #GNUNET_SYSERR
- * @param msg error message on error
- */
-static void
-check_present_continuation (void *cls,
-                            int status,
-                            const char *msg)
-{
-  struct GNUNET_SERVICE_Client *client = cls;
-
-  transmit_status (client,
-                   GNUNET_NO,
-                   NULL);
-}
-
-
-/**
- * Function that will check if the given datastore entry
- * matches the put and if none match executes the put.
- *
- * @param cls closure, pointer to the client (of type `struct PutContext`).
- * @param key key for the content
- * @param size number of bytes in data
- * @param data content stored
- * @param type type of the content
- * @param priority priority of the content
- * @param anonymity anonymity-level for the content
- * @param replication replication-level for the content
- * @param expiration expiration time for the content
- * @param uid unique identifier for the datum;
- *        maybe 0 if no unique identifier is available
- * @return #GNUNET_OK usually
- *         #GNUNET_NO to delete the item
- */
-static int
-check_present (void *cls,
-               const struct GNUNET_HashCode *key,
-               uint32_t size,
-               const void *data,
-               enum GNUNET_BLOCK_Type type,
-               uint32_t priority,
-               uint32_t anonymity,
-               uint32_t replication,
-               struct GNUNET_TIME_Absolute expiration,
-               uint64_t uid)
-{
-  struct PutContext *pc = cls;
-  const struct DataMessage *dm;
-
-  dm = (const struct DataMessage *) &pc[1];
-  if (key == NULL)
-  {
-    execute_put (pc);
-    return GNUNET_OK;
-  }
-  if ( (GNUNET_BLOCK_TYPE_FS_DBLOCK == type) ||
-       (GNUNET_BLOCK_TYPE_FS_IBLOCK == type) ||
-       ( (size == ntohl (dm->size)) &&
-         (0 == memcmp (&dm[1],
-                       data,
-                       size)) ) )
-  {
-    GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
-                "Result already present in datastore\n");
-    if ( (ntohl (dm->priority) > 0) ||
-         (ntohl (dm->replication) > 0) ||
-         (GNUNET_TIME_absolute_ntoh (dm->expiration).abs_value_us >
-          expiration.abs_value_us) )
-      plugin->api->update (plugin->api->cls,
-                           uid,
-                           ntohl (dm->priority),
-                           ntohl (dm->replication),
-                           GNUNET_TIME_absolute_ntoh (dm->expiration),
-                           &check_present_continuation,
-                           pc->client);
-    else
-    {
-      transmit_status (pc->client,
-                       GNUNET_NO,
-                       NULL);
-    }
-    GNUNET_free (pc);
-  }
-  else
-  {
-    execute_put (pc);
-  }
-  return GNUNET_OK;
-}
-
-
-/**
  * Verify PUT-message.
  *
  * @param cls identification of the client
@@ -950,8 +812,6 @@ handle_put (void *cls,
   struct GNUNET_SERVICE_Client *client = cls;
   int rid;
   struct ReservationList *pos;
-  struct PutContext *pc;
-  struct GNUNET_HashCode vhash;
   uint32_t size;
 
   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
@@ -979,30 +839,20 @@ handle_put (void *cls,
                              GNUNET_NO);
     }
   }
-  pc = GNUNET_malloc (sizeof (struct PutContext) + size +
-                      sizeof (struct DataMessage));
-  pc->client = client;
-  GNUNET_memcpy (&pc[1],
-                 dm,
-                 size + sizeof (struct DataMessage));
-  if (GNUNET_YES == GNUNET_CONTAINER_bloomfilter_test (filter,
-                                                       &dm->key))
-  {
-    GNUNET_CRYPTO_hash (&dm[1],
-                        size,
-                        &vhash);
-    plugin->api->get_key (plugin->api->cls,
-                          0,
-                          false,
-                          &dm->key,
-                          &vhash,
-                          ntohl (dm->type),
-                          &check_present,
-                          pc);
-    GNUNET_SERVICE_client_continue (client);
-    return;
-  }
-  execute_put (pc);
+  bool absent = GNUNET_NO == GNUNET_CONTAINER_bloomfilter_test (filter,
+                                                                &dm->key);
+  plugin->api->put (plugin->api->cls,
+                    &dm->key,
+                    absent,
+                    ntohl (dm->size),
+                    &dm[1],
+                    ntohl (dm->type),
+                    ntohl (dm->priority),
+                    ntohl (dm->anonymity),
+                    ntohl (dm->replication),
+                    GNUNET_TIME_absolute_ntoh (dm->expiration),
+                    &put_continuation,
+                    client);
   GNUNET_SERVICE_client_continue (client);
 }
 
@@ -1030,7 +880,6 @@ handle_get (void *cls,
                         GNUNET_ntohll (msg->next_uid),
                         msg->random,
                         NULL,
-                        NULL,
                         ntohl (msg->type),
                         &transmit_item,
                         client);
@@ -1082,7 +931,6 @@ handle_get_key (void *cls,
                         GNUNET_ntohll (msg->next_uid),
                         msg->random,
                         &msg->key,
-                        NULL,
                         ntohl (msg->type),
                         &transmit_item,
                         client);
@@ -1151,50 +999,46 @@ handle_get_zero_anonymity (void *cls,
 
 
 /**
- * Callback function that will cause the item that is passed
- * in to be deleted (by returning #GNUNET_NO).
+ * Remove continuation.
  *
  * @param cls closure
  * @param key key for the content
  * @param size number of bytes in data
- * @param data content stored
- * @param type type of the content
- * @param priority priority of the content
- * @param anonymity anonymity-level for the content
- * @param replication replication-level for the content
- * @param expiration expiration time for the content
- * @param uid unique identifier for the datum
- * @return #GNUNET_OK to keep the item
- *         #GNUNET_NO to delete the item
+ * @param status #GNUNET_OK if removed, #GNUNET_NO if not found,
+ *        or #GNUNET_SYSERROR if error
+ * @param msg error message on error
  */
-static int
-remove_callback (void *cls,
-                 const struct GNUNET_HashCode *key,
-                 uint32_t size,
-                 const void *data,
-                 enum GNUNET_BLOCK_Type type,
-                 uint32_t priority,
-                 uint32_t anonymity,
-                 uint32_t replication,
-                 struct GNUNET_TIME_Absolute expiration,
-                 uint64_t uid)
+static void
+remove_continuation (void *cls,
+                     const struct GNUNET_HashCode *key,
+                     uint32_t size,
+                     int status,
+                     const char *msg)
 {
   struct GNUNET_SERVICE_Client *client = cls;
 
-  if (NULL == key)
+  if (GNUNET_SYSERR == status)
+  {
+    GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
+                "REMOVE request failed: %s.\n",
+                msg);
+    transmit_status (client,
+                     GNUNET_NO,
+                     msg);
+    return;
+  }
+  if (GNUNET_NO == status)
   {
     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
-                "No further matches for REMOVE request.\n");
+                "Content not found for REMOVE request.\n");
     transmit_status (client,
                      GNUNET_NO,
                      _("Content not found"));
-    return GNUNET_OK;           /* last item */
+    return;
   }
   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
-              "Item %llu matches REMOVE request for key `%s' and type %u.\n",
-              (unsigned long long) uid,
-              GNUNET_h2s (key),
-              type);
+              "Item matches REMOVE request for key `%s'.\n",
+              GNUNET_h2s (key));
   GNUNET_STATISTICS_update (stats,
                             gettext_noop ("# bytes removed (explicit request)"),
                             size,
@@ -1204,7 +1048,6 @@ remove_callback (void *cls,
   transmit_status (client,
                    GNUNET_OK,
                    NULL);
-  return GNUNET_NO;
 }
 
 
@@ -1240,26 +1083,19 @@ handle_remove (void *cls,
                const struct DataMessage *dm)
 {
   struct GNUNET_SERVICE_Client *client = cls;
-  struct GNUNET_HashCode vhash;
 
   GNUNET_STATISTICS_update (stats,
                             gettext_noop ("# REMOVE requests received"),
                             1, GNUNET_NO);
-  GNUNET_CRYPTO_hash (&dm[1],
-                      ntohl (dm->size),
-                      &vhash);
   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
-              "Processing REMOVE request for `%s' of type %u\n",
-              GNUNET_h2s (&dm->key),
-              (uint32_t) ntohl (dm->type));
-  plugin->api->get_key (plugin->api->cls,
-                        0,
-                        false,
-                        &dm->key,
-                        &vhash,
-                        (enum GNUNET_BLOCK_Type) ntohl (dm->type),
-                        &remove_callback,
-                        client);
+              "Processing REMOVE request for `%s'\n",
+              GNUNET_h2s (&dm->key));
+  plugin->api->remove_key (plugin->api->cls,
+                           &dm->key,
+                           ntohl (dm->size),
+                           &dm[1],
+                           &remove_continuation,
+                           client);
   GNUNET_SERVICE_client_continue (client);
 }
 
diff --git a/src/datastore/perf_plugin_datastore.c b/src/datastore/perf_plugin_datastore.c
index 2f9502989..d6f44bf9f 100644
--- a/src/datastore/perf_plugin_datastore.c
+++ b/src/datastore/perf_plugin_datastore.c
@@ -181,8 +181,14 @@ do_put (struct CpsRunContext *crc)
   value[0] = crc->i;
   GNUNET_memcpy (&value[4], &i, sizeof (i));
   prio = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, 100);
-  crc->api->put (crc->api->cls, &key, size, value, 1 + i % 4 /* type */ ,
-                 prio, i % 4 /* anonymity */ ,
+  crc->api->put (crc->api->cls,
+                 &key,
+                 false /* absent */,
+                 size,
+                 value,
+                 1 + i % 4 /* type */ ,
+                 prio,
+                 i % 4 /* anonymity */ ,
                  0 /* replication */ ,
                  GNUNET_TIME_relative_to_absolute
                  (GNUNET_TIME_relative_multiply
@@ -190,7 +196,8 @@ do_put (struct CpsRunContext *crc)
                     60 * 60 * 60 * 1000 +
                     GNUNET_CRYPTO_random_u32
                       (GNUNET_CRYPTO_QUALITY_WEAK, 1000))),
-                 put_continuation, crc);
+                 put_continuation,
+                 crc);
   i++;
 }
 
diff --git a/src/datastore/plugin_datastore_heap.c b/src/datastore/plugin_datastore_heap.c
index d04c1cf60..9950f7ab2 100644
--- a/src/datastore/plugin_datastore_heap.c
+++ b/src/datastore/plugin_datastore_heap.c
@@ -195,10 +195,89 @@ heap_plugin_estimate_size (void *cls, unsigned long long *estimate)
 
 
 /**
+ * Closure for iterator for updating.
+ */
+struct UpdateContext
+{
+  /**
+   * Number of bytes in 'data'.
+   */
+  uint32_t size;
+
+  /**
+   * Pointer to the data.
+   */
+  const void *data;
+
+  /**
+   * Priority of the value.
+   */
+  uint32_t priority;
+
+  /**
+   * Replication level for the value.
+   */
+  uint32_t replication;
+
+  /**
+   * Expiration time for this value.
+   */
+  struct GNUNET_TIME_Absolute expiration;
+
+  /**
+   * True if the value was found and updated.
+   */
+  bool updated;
+};
+
+
+/**
+ * Update the matching value.
+ *
+ * @param cls the 'struct UpdateContext'
+ * @param key unused
+ * @param val the 'struct Value'
+ * @return GNUNET_YES (continue iteration), GNUNET_NO if value was found
+ */
+static int
+update_iterator (void *cls,
+                 const struct GNUNET_HashCode *key,
+                 void *val)
+{
+  struct UpdateContext *uc = cls;
+  struct Value *value = val;
+
+  if (value->size != uc->size)
+    return GNUNET_YES;
+  if (0 != memcmp (value->data, uc->data, uc->size))
+    return GNUNET_YES;
+  uc->expiration = GNUNET_TIME_absolute_max (value->expiration,
+                                             uc->expiration);
+  if (value->expiration.abs_value_us != uc->expiration.abs_value_us)
+  {
+    value->expiration = uc->expiration;
+    GNUNET_CONTAINER_heap_update_cost (value->expire_heap,
+                                       value->expiration.abs_value_us);
+  }
+  /* Saturating adds, don't overflow */
+  if (value->priority > UINT32_MAX - uc->priority)
+    value->priority = UINT32_MAX;
+  else
+    value->priority += uc->priority;
+  if (value->replication > UINT32_MAX - uc->replication)
+    value->replication = UINT32_MAX;
+  else
+    value->replication += uc->replication;
+  uc->updated = true;
+  return GNUNET_NO;
+}
+
+/**
  * Store an item in the datastore.
  *
  * @param cls closure
  * @param key key for the item
+ * @param absent true if the key was not found in the bloom filter
  * @param size number of bytes in data
  * @param data content stored
  * @param type type of the content
@@ -211,19 +290,40 @@ heap_plugin_estimate_size (void *cls, unsigned long long *estimate)
  */
 static void
 heap_plugin_put (void *cls,
-                 const struct GNUNET_HashCode * key,
-                 uint32_t size,
-                 const void *data,
-                 enum GNUNET_BLOCK_Type type,
-                 uint32_t priority, uint32_t anonymity,
-                 uint32_t replication,
-                 struct GNUNET_TIME_Absolute expiration,
-                 PluginPutCont cont,
-                 void *cont_cls)
+                 const struct GNUNET_HashCode *key,
+                 bool absent,
+                 uint32_t size,
+                 const void *data,
+                 enum GNUNET_BLOCK_Type type,
+                 uint32_t priority,
+                 uint32_t anonymity,
+                 uint32_t replication,
+                 struct GNUNET_TIME_Absolute expiration,
+                 PluginPutCont cont,
+                 void *cont_cls)
 {
   struct Plugin *plugin = cls;
   struct Value *value;
 
+  if (!absent) {
+    struct UpdateContext uc;
+
+    uc.size = size;
+    uc.data = data;
+    uc.priority = priority;
+    uc.replication = replication;
+    uc.expiration = expiration;
+    uc.updated = false;
+    GNUNET_CONTAINER_multihashmap_get_multiple (plugin->keyvalue,
+                                                key,
+                                                &update_iterator,
+                                                &uc);
+    if (uc.updated)
+    {
+      cont (cont_cls, key, size, GNUNET_NO, NULL);
+      return;
+    }
+  }
   value = GNUNET_malloc (sizeof (struct Value) + size);
   value->key = *key;
   value->data = &value[1];
@@ -333,11 +433,6 @@ struct GetContext
   struct Value *value;
 
   /**
-   * Requested value hash.
-   */
-  const struct GNUNET_HashCode *vhash;
-
-  /**
    * Requested type.
    */
   enum GNUNET_BLOCK_Type type;
@@ -365,17 +460,10 @@ get_iterator (void *cls,
 {
   struct GetContext *gc = cls;
   struct Value *value = val;
-  struct GNUNET_HashCode vh;
 
   if ( (gc->type != GNUNET_BLOCK_TYPE_ANY) &&
        (gc->type != value->type) )
     return GNUNET_OK;
-  if (NULL != gc->vhash)
-  {
-    GNUNET_CRYPTO_hash (&value[1], value->size, &vh);
-    if (0 != memcmp (&vh, gc->vhash, sizeof (struct GNUNET_HashCode)))
-      return GNUNET_OK;
-  }
   if (gc->random)
   {
     gc->value = value;
@@ -398,23 +486,20 @@ get_iterator (void *cls,
  * @param next_uid return the result with lowest uid >= next_uid
  * @param random if true, return a random result instead of using next_uid
  * @param key maybe NULL (to match all entries)
- * @param vhash hash of the value, maybe NULL (to
- *        match all values that have the right key).
- *        Note that for DBlocks there is no difference
- *        betwen key and vhash, but for other blocks
- *        there may be!
  * @param type entries of which type are relevant?
  *     Use 0 for any type.
- * @param proc function to call on each matching value;
+ * @param proc function to call on the matching value;
  *        will be called with NULL if nothing matches
- * @param proc_cls closure for proc
+ * @param proc_cls closure for @a proc
  */
 static void
-heap_plugin_get_key (void *cls, uint64_t next_uid, bool random,
-                     const struct GNUNET_HashCode *key,
-                     const struct GNUNET_HashCode *vhash,
-                     enum GNUNET_BLOCK_Type type, PluginDatumProcessor proc,
-                     void *proc_cls)
+heap_plugin_get_key (void *cls,
+                     uint64_t next_uid,
+                     bool random,
+                     const struct GNUNET_HashCode *key,
+                     enum GNUNET_BLOCK_Type type,
+                     PluginDatumProcessor proc,
+                     void *proc_cls)
 {
   struct Plugin *plugin = cls;
   struct GetContext gc;
@@ -422,7 +507,6 @@ heap_plugin_get_key (void *cls, uint64_t next_uid, bool random,
   gc.value = NULL;
   gc.next_uid = next_uid;
   gc.random = random;
-  gc.vhash = vhash;
   gc.type = type;
   if (NULL == key)
   {
@@ -442,20 +526,17 @@ heap_plugin_get_key (void *cls, uint64_t next_uid, bool random,
     proc (proc_cls, NULL, 0, NULL, 0, 0, 0, 0, GNUNET_TIME_UNIT_ZERO_ABS, 0);
     return;
   }
-  if (GNUNET_NO ==
-      proc (proc_cls,
-            &gc.value->key,
-            gc.value->size,
-            &gc.value[1],
-            gc.value->type,
-            gc.value->priority,
-            gc.value->anonymity,
-            gc.value->replication,
-            gc.value->expiration,
-            (uint64_t) (intptr_t) gc.value))
-  {
-    delete_value (plugin, gc.value);
-  }
+  GNUNET_assert (GNUNET_OK ==
+                 proc (proc_cls,
+                       &gc.value->key,
+                       gc.value->size,
+                       &gc.value[1],
+                       gc.value->type,
+                       gc.value->priority,
+                       gc.value->anonymity,
+                       gc.value->replication,
+                       gc.value->expiration,
+                       (uint64_t) (intptr_t) gc.value));
 }
 
 
@@ -499,18 +580,17 @@ heap_plugin_get_replication (void *cls,
                                                             value->replication);
     value = GNUNET_CONTAINER_heap_walk_get_next (plugin->by_replication);
   }
-  if (GNUNET_NO ==
-      proc (proc_cls,
-            &value->key,
-            value->size,
-            &value[1],
-            value->type,
-            value->priority,
-            value->anonymity,
-            value->replication,
-            value->expiration,
-            (uint64_t) (intptr_t) value))
-    delete_value (plugin, value);
+  GNUNET_assert (GNUNET_OK ==
+                 proc (proc_cls,
+                       &value->key,
+                       value->size,
+                       &value[1],
+                       value->type,
+                       value->priority,
+                       value->anonymity,
+                       value->replication,
+                       value->expiration,
+                       (uint64_t) (intptr_t) value));
 }
 
 
@@ -551,57 +631,6 @@ heap_plugin_get_expiration (void *cls, PluginDatumProcessor proc,
 
 
 /**
- * Update the priority, replication and expiration for a particular
- * unique ID in the datastore.  If the expiration time in value is
- * different than the time found in the datastore, the higher value
- * should be kept.  The specified priority and replication is added
- * to the existing value.
- *
- * @param cls our `struct Plugin *`
- * @param uid unique identifier of the datum
- * @param priority by how much should the priority
- *     change?
- * @param replication by how much should the replication
- *     change?
- * @param expire new expiration time should be the
- *     MAX of any existing expiration time and
- *     this value
- * @param cont continuation called with success or failure status
- * @param cons_cls continuation closure
- */
-static void
-heap_plugin_update (void *cls,
-                    uint64_t uid,
-                    uint32_t priority,
-                    uint32_t replication,
-                    struct GNUNET_TIME_Absolute expire,
-                    PluginUpdateCont cont,
-                    void *cont_cls)
-{
-  struct Value *value;
-
-  value = (struct Value*) (intptr_t) uid;
-  GNUNET_assert (NULL != value);
-  if (value->expiration.abs_value_us != expire.abs_value_us)
-  {
-    value->expiration = expire;
-    GNUNET_CONTAINER_heap_update_cost (value->expire_heap,
-                                       expire.abs_value_us);
-  }
-  /* Saturating adds, don't overflow */
-  if (value->priority > UINT32_MAX - priority)
-    value->priority = UINT32_MAX;
-  else
-    value->priority += priority;
-  if (value->replication > UINT32_MAX - replication)
-    value->replication = UINT32_MAX;
-  else
-    value->replication += replication;
-  cont (cont_cls, GNUNET_OK, NULL);
-}
-
-
-/**
  * Call the given processor on an item with zero anonymity.
  *
  * @param cls our "struct Plugin*"
@@ -641,18 +670,17 @@ heap_plugin_get_zero_anonymity (void *cls, uint64_t next_uid,
     proc (proc_cls, NULL, 0, NULL, 0, 0, 0, 0, GNUNET_TIME_UNIT_ZERO_ABS, 0);
     return;
   }
-  if (GNUNET_NO ==
-      proc (proc_cls,
-            &value->key,
-            value->size,
-            &value[1],
-            value->type,
-            value->priority,
-            value->anonymity,
-            value->replication,
-            value->expiration,
-            (uint64_t) (intptr_t) value))
-    delete_value (plugin, value);
+  GNUNET_assert (GNUNET_OK ==
+                 proc (proc_cls,
+                       &value->key,
+                       value->size,
+                       &value[1],
+                       value->type,
+                       value->priority,
+                       value->anonymity,
+                       value->replication,
+                       value->expiration,
+                       (uint64_t) (intptr_t) value));
 }
 
 
@@ -730,6 +758,102 @@ heap_get_keys (void *cls,
 
 
 /**
+ * Closure for iterator called during 'remove_key'.
+ */
+struct RemoveContext
+{
+
+  /**
+   * Value found.
+   */
+  struct Value *value;
+
+  /**
+   * Size of data.
+   */
+  uint32_t size;
+
+  /**
+   * Data to remove.
+   */
+  const void *data;
+
+};
+
+
+/**
+ * Obtain the matching value with the lowest uid >= next_uid.
+ *
+ * @param cls the 'struct GetContext'
+ * @param key unused
+ * @param val the 'struct Value'
+ * @return GNUNET_YES (continue iteration), GNUNET_NO if result was found
+ */
+static int
+remove_iterator (void *cls,
+                 const struct GNUNET_HashCode *key,
+                 void *val)
+{
+  struct RemoveContext *rc = cls;
+  struct Value *value = val;
+
+  if (value->size != rc->size)
+    return GNUNET_YES;
+  if (0 != memcmp (value->data, rc->data, rc->size))
+    return GNUNET_YES;
+  rc->value = value;
+  return GNUNET_NO;
+}
+
+
+/**
+ * Remove a particular key in the datastore.
+ *
+ * @param cls closure
+ * @param key key for the content
+ * @param size number of bytes in data
+ * @param data content stored
+ * @param cont continuation called with success or failure status
+ * @param cont_cls continuation closure for @a cont
+ */
+static void
+heap_plugin_remove_key (void *cls,
+                        const struct GNUNET_HashCode *key,
+                        uint32_t size,
+                        const void *data,
+                        PluginRemoveCont cont,
+                        void *cont_cls)
+{
+  struct Plugin *plugin = cls;
+  struct RemoveContext rc;
+
+  rc.value = NULL;
+  rc.size = size;
+  rc.data = data;
+  GNUNET_CONTAINER_multihashmap_get_multiple (plugin->keyvalue,
+                                              key,
+                                              &remove_iterator,
+                                              &rc);
+  if (NULL == rc.value)
+  {
+    cont (cont_cls,
+          key,
+          size,
+          GNUNET_NO,
+          NULL);
+    return;
+  }
+  delete_value (plugin,
+                rc.value);
+  cont (cont_cls,
+        key,
+        size,
+        GNUNET_OK,
+        NULL);
+}
+
+
+/**
  * Entry point for the plugin.
  *
  * @param cls the "struct GNUNET_DATASTORE_PluginEnvironment*"
@@ -758,13 +882,13 @@ libgnunet_plugin_datastore_heap_init (void *cls)
   api->cls = plugin;
   api->estimate_size = &heap_plugin_estimate_size;
   api->put = &heap_plugin_put;
-  api->update = &heap_plugin_update;
   api->get_key = &heap_plugin_get_key;
   api->get_replication = &heap_plugin_get_replication;
   api->get_expiration = &heap_plugin_get_expiration;
   api->get_zero_anonymity = &heap_plugin_get_zero_anonymity;
   api->drop = &heap_plugin_drop;
   api->get_keys = &heap_get_keys;
+  api->remove_key = &heap_plugin_remove_key;
   GNUNET_log_from (GNUNET_ERROR_TYPE_INFO, "heap",
                    _("Heap database running\n"));
   return api;
diff --git a/src/datastore/plugin_datastore_mysql.c b/src/datastore/plugin_datastore_mysql.c
index 6f2a76499..708e35860 100644
--- a/src/datastore/plugin_datastore_mysql.c
+++ b/src/datastore/plugin_datastore_mysql.c
@@ -150,6 +150,12 @@ struct Plugin
 #define DELETE_ENTRY_BY_UID "DELETE FROM gn090 WHERE uid=?"
   struct GNUNET_MYSQL_StatementHandle *delete_entry_by_uid;
 
+#define DELETE_ENTRY_BY_HASH_VALUE "DELETE FROM gn090 "\
+  "WHERE hash = ? AND "\
+  "value = ? "\
+  "LIMIT 1"
+  struct GNUNET_MYSQL_StatementHandle *delete_entry_by_hash_value;
+
 #define RESULT_COLUMNS "repl, type, prio, anonLevel, expire, hash, value, uid"
 
 #define SELECT_ENTRY "SELECT " RESULT_COLUMNS " FROM gn090 "\
@@ -159,22 +165,13 @@ struct Plugin
   struct GNUNET_MYSQL_StatementHandle *select_entry;
 
 #define SELECT_ENTRY_BY_HASH "SELECT " RESULT_COLUMNS " FROM gn090 "\
-  "FORCE INDEX (idx_hash) "\
+  "FORCE INDEX (idx_hash_type_uid) "\
   "WHERE hash=? AND "\
   "uid >= ? AND "\
   "(rvalue >= ? OR 0 = ?) "\
   "ORDER BY uid LIMIT 1"
   struct GNUNET_MYSQL_StatementHandle *select_entry_by_hash;
 
-#define SELECT_ENTRY_BY_HASH_AND_VHASH "SELECT " RESULT_COLUMNS " FROM gn090 "\
-  "FORCE INDEX (idx_hash_vhash) "\
-  "WHERE hash = ? AND "\
-  "vhash = ? AND "\
-  "uid >= ? AND "\
-  "(rvalue >= ? OR 0 = ?) "\
-  "ORDER BY uid LIMIT 1"
-  struct GNUNET_MYSQL_StatementHandle *select_entry_by_hash_and_vhash;
-
 #define SELECT_ENTRY_BY_HASH_AND_TYPE "SELECT " RESULT_COLUMNS " FROM gn090 "\
   "FORCE INDEX (idx_hash_type_uid) "\
   "WHERE hash = ? AND "\
@@ -184,22 +181,11 @@ struct Plugin
   "ORDER BY uid LIMIT 1"
   struct GNUNET_MYSQL_StatementHandle *select_entry_by_hash_and_type;
 
-#define SELECT_ENTRY_BY_HASH_VHASH_AND_TYPE "SELECT " RESULT_COLUMNS " "\
-  "FROM gn090 "\
-  "FORCE INDEX (idx_hash_vhash) "\
-  "WHERE hash = ? AND "\
-  "vhash = ? AND "\
-  "type = ? AND "\
-  "uid >= ? AND "\
-  "(rvalue >= ? OR 0 = ?) "\
-  "ORDER BY uid LIMIT 1"
-  struct GNUNET_MYSQL_StatementHandle *select_entry_by_hash_vhash_and_type;
-
 #define UPDATE_ENTRY "UPDATE gn090 SET "\
   "prio = prio + ?, "\
   "repl = repl + ?, "\
-  "expire = IF(expire >= ?, expire, ?) "\
-  "WHERE uid = ?"
+  "expire = GREATEST(expire, ?) "\
+  "WHERE hash = ? AND vhash = ?"
   struct GNUNET_MYSQL_StatementHandle *update_entry;
 
 #define DEC_REPL "UPDATE gn090 SET repl=GREATEST (1, repl) - 1 WHERE uid=?"
@@ -330,6 +316,7 @@ mysql_plugin_estimate_size (void *cls,
  *
  * @param cls closure
  * @param key key for the item
+ * @param absent true if the key was not found in the bloom filter
  * @param size number of bytes in @a data
  * @param data content stored
  * @param type type of the content
@@ -343,6 +330,7 @@ mysql_plugin_estimate_size (void *cls,
 static void
 mysql_plugin_put (void *cls,
                   const struct GNUNET_HashCode *key,
+                  bool absent,
                   uint32_t size,
                   const void *data,
                   enum GNUNET_BLOCK_Type type,
@@ -355,9 +343,54 @@ mysql_plugin_put (void *cls,
 {
   struct Plugin *plugin = cls;
   uint64_t lexpiration = expiration.abs_value_us;
+  struct GNUNET_HashCode vhash;
+
+  GNUNET_CRYPTO_hash (data,
+                      size,
+                      &vhash);
+  if (!absent)
+  {
+    struct GNUNET_MY_QueryParam params_update[] = {
+      GNUNET_MY_query_param_uint32 (&priority),
+      GNUNET_MY_query_param_uint32 (&replication),
+      GNUNET_MY_query_param_uint64 (&lexpiration),
+      GNUNET_MY_query_param_auto_from_type (key),
+      GNUNET_MY_query_param_auto_from_type (&vhash),
+      GNUNET_MY_query_param_end
+    };
+
+    if (GNUNET_OK !=
+        GNUNET_MY_exec_prepared (plugin->mc,
+                                 plugin->update_entry,
+                                 params_update))
+    {
+      cont (cont_cls,
+            key,
+            size,
+            GNUNET_SYSERR,
+            _("MySQL statement run failure"));
+      return;
+    }
+
+    MYSQL_STMT *stmt = GNUNET_MYSQL_statement_get_stmt (plugin->update_entry);
+    my_ulonglong rows = mysql_stmt_affected_rows (stmt);
+
+    GNUNET_break (GNUNET_NO ==
+                  GNUNET_MY_extract_result (plugin->update_entry,
+                                            NULL));
+    if (0 != rows)
+    {
+      cont (cont_cls,
+            key,
+            size,
+            GNUNET_NO,
+            NULL);
+      return;
+    }
+  }
+
   uint64_t lrvalue = GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
                                                UINT64_MAX);
-  struct GNUNET_HashCode vhash;
   struct GNUNET_MY_QueryParam params_insert[] = {
     GNUNET_MY_query_param_uint32 (&replication),
     GNUNET_MY_query_param_uint32 (&type),
@@ -377,9 +410,6 @@ mysql_plugin_put (void *cls,
     cont (cont_cls, key, size, GNUNET_SYSERR, _("Data too large"));
     return;
   }
-  GNUNET_CRYPTO_hash (data,
-                      size,
-                      &vhash);
 
   if (GNUNET_OK !=
       GNUNET_MY_exec_prepared (plugin->mc,
@@ -412,76 +442,6 @@ mysql_plugin_put (void *cls,
 
 
 /**
- * Update the priority, replication and expiration for a particular
- * unique ID in the datastore.  If the expiration time in value is
- * different than the time found in the datastore, the higher value
- * should be kept.  The specified priority and replication is added
- * to the existing value.
- *
- * @param cls our "struct Plugin*"
- * @param uid unique identifier of the datum
- * @param priority by how much should the priority
- *     change?
- * @param replication by how much should the replication
- *     change?
- * @param expire new expiration time should be the
- *     MAX of any existing expiration time and
- *     this value
- * @param cont continuation called with success or failure status
- * @param cons_cls continuation closure
- */
-static void
-mysql_plugin_update (void *cls,
-                     uint64_t uid,
-                     uint32_t priority,
-                     uint32_t replication,
-                     struct GNUNET_TIME_Absolute expire,
-                     PluginUpdateCont cont,
-                     void *cont_cls)
-{
-  struct Plugin *plugin = cls;
-  uint64_t lexpire = expire.abs_value_us;
-  int ret;
-
-  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
-              "Updating value %llu adding %d to priority %d to replication and maxing exp at %s\n",
-              (unsigned long long) uid,
-              priority,
-              replication,
-              GNUNET_STRINGS_absolute_time_to_string (expire));
-
-  struct GNUNET_MY_QueryParam params_update[] = {
-    GNUNET_MY_query_param_uint32 (&priority),
-    GNUNET_MY_query_param_uint32 (&replication),
-    GNUNET_MY_query_param_uint64 (&lexpire),
-    GNUNET_MY_query_param_uint64 (&lexpire),
-    GNUNET_MY_query_param_uint64 (&uid),
-    GNUNET_MY_query_param_end
-  };
-
-  ret = GNUNET_MY_exec_prepared (plugin->mc,
-                                 plugin->update_entry,
-                                 params_update);
-
-  if (GNUNET_OK != ret)
-  {
-    GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
-                "Failed to update value %llu\n",
-                (unsigned long long) uid);
-  }
-  else
-  {
-    GNUNET_break (GNUNET_NO ==
-                  GNUNET_MY_extract_result (plugin->update_entry,
-                                            NULL));
-  }
-  cont (cont_cls,
-        ret,
-        NULL);
-}
-
-
-/**
  * Run the given select statement and call 'proc' on the resulting
  * values (which must be in particular positions).
  *
@@ -578,11 +538,6 @@ execute_select (struct Plugin *plugin,
  * @param next_uid return the result with lowest uid >= next_uid
  * @param random if true, return a random result instead of using next_uid
  * @param key key to match, never NULL
- * @param vhash hash of the value, maybe NULL (to
- *        match all values that have the right key).
- *        Note that for DBlocks there is no difference
- *        betwen key and vhash, but for other blocks
- *        there may be!
  * @param type entries of which type are relevant?
  *     Use 0 for any type.
  * @param proc function to call on the matching value,
@@ -594,7 +549,6 @@ mysql_plugin_get_key (void *cls,
                       uint64_t next_uid,
                       bool random,
                       const struct GNUNET_HashCode *key,
-                      const struct GNUNET_HashCode *vhash,
                       enum GNUNET_BLOCK_Type type,
                       PluginDatumProcessor proc,
                       void *proc_cls)
@@ -628,79 +582,37 @@ mysql_plugin_get_key (void *cls,
   }
   else if (type != GNUNET_BLOCK_TYPE_ANY)
   {
-    if (NULL != vhash)
-    {
-      struct GNUNET_MY_QueryParam params_select[] = {
-        GNUNET_MY_query_param_auto_from_type (key),
-        GNUNET_MY_query_param_auto_from_type (vhash),
-        GNUNET_MY_query_param_uint32 (&type),
-        GNUNET_MY_query_param_uint64 (&next_uid),
-        GNUNET_MY_query_param_uint64 (&rvalue),
-        GNUNET_MY_query_param_uint64 (&rvalue),
-        GNUNET_MY_query_param_end
-      };
-
-      execute_select (plugin,
-                      plugin->select_entry_by_hash_vhash_and_type,
-                      proc,
-                      proc_cls,
-                      params_select);
-    }
-    else
-    {
-      struct GNUNET_MY_QueryParam params_select[] = {
-        GNUNET_MY_query_param_auto_from_type (key),
-        GNUNET_MY_query_param_uint32 (&type),
-        GNUNET_MY_query_param_uint64 (&next_uid),
-        GNUNET_MY_query_param_uint64 (&rvalue),
-        GNUNET_MY_query_param_uint64 (&rvalue),
-        GNUNET_MY_query_param_end
-      };
-
-      execute_select (plugin,
-                      plugin->select_entry_by_hash_and_type,
-                      proc,
-                      proc_cls,
-                      params_select);
-    }
+    struct GNUNET_MY_QueryParam params_select[] = {
+      GNUNET_MY_query_param_auto_from_type (key),
+      GNUNET_MY_query_param_uint32 (&type),
+      GNUNET_MY_query_param_uint64 (&next_uid),
+      GNUNET_MY_query_param_uint64 (&rvalue),
+      GNUNET_MY_query_param_uint64 (&rvalue),
+      GNUNET_MY_query_param_end
+    };
+
+    execute_select (plugin,
+                    plugin->select_entry_by_hash_and_type,
+                    proc,
+                    proc_cls,
+                    params_select);
   }
   else
   {
-    if (NULL != vhash)
-    {
-      struct GNUNET_MY_QueryParam params_select[] = {
-        GNUNET_MY_query_param_auto_from_type (key),
-        GNUNET_MY_query_param_auto_from_type (vhash),
-        GNUNET_MY_query_param_uint64 (&next_uid),
-        GNUNET_MY_query_param_uint64 (&rvalue),
-        GNUNET_MY_query_param_uint64 (&rvalue),
-        GNUNET_MY_query_param_end
-      };
-
-      execute_select (plugin,
-                      plugin->select_entry_by_hash_and_vhash,
-                      proc,
-                      proc_cls,
-                      params_select);
-    }
-    else
-    {
-      struct GNUNET_MY_QueryParam params_select[] = {
-        GNUNET_MY_query_param_auto_from_type (key),
-        GNUNET_MY_query_param_uint64 (&next_uid),
-        GNUNET_MY_query_param_uint64 (&rvalue),
-        GNUNET_MY_query_param_uint64 (&rvalue),
-        GNUNET_MY_query_param_end
-      };
-
-      execute_select (plugin,
-                      plugin->select_entry_by_hash,
-                      proc,
-                      proc_cls,
-                      params_select);
-    }
-  }
+    struct GNUNET_MY_QueryParam params_select[] = {
+      GNUNET_MY_query_param_auto_from_type (key),
+      GNUNET_MY_query_param_uint64 (&next_uid),
+      GNUNET_MY_query_param_uint64 (&rvalue),
+      GNUNET_MY_query_param_uint64 (&rvalue),
+      GNUNET_MY_query_param_end
+    };
 
+    execute_select (plugin,
+                    plugin->select_entry_by_hash,
+                    proc,
+                    proc_cls,
+                    params_select);
+  }
 }
 
 
@@ -1124,6 +1036,69 @@ mysql_plugin_drop (void *cls)
 
 
 /**
+ * Remove a particular key in the datastore.
+ *
+ * @param cls closure
+ * @param key key for the content
+ * @param size number of bytes in data
+ * @param data content stored
+ * @param cont continuation called with success or failure status
+ * @param cont_cls continuation closure for @a cont
+ */
+static void
+mysql_plugin_remove_key (void *cls,
+                         const struct GNUNET_HashCode *key,
+                         uint32_t size,
+                         const void *data,
+                         PluginRemoveCont cont,
+                         void *cont_cls)
+{
+  struct Plugin *plugin = cls;
+  struct GNUNET_MY_QueryParam params_delete[] = {
+    GNUNET_MY_query_param_auto_from_type (key),
+    GNUNET_MY_query_param_fixed_size (data, size),
+    GNUNET_MY_query_param_end
+  };
+
+  if (GNUNET_OK !=
+      GNUNET_MY_exec_prepared (plugin->mc,
+                               plugin->delete_entry_by_hash_value,
+                               params_delete))
+  {
+    GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
+                "Removing key `%s' from gn090 table failed\n",
+                GNUNET_h2s (key));
+    cont (cont_cls,
+          key,
+          size,
+          GNUNET_SYSERR,
+          _("MySQL statement run failure"));
+    return;
+  }
+
+  MYSQL_STMT *stmt = GNUNET_MYSQL_statement_get_stmt (plugin->delete_entry_by_hash_value);
+  my_ulonglong rows = mysql_stmt_affected_rows (stmt);
+
+  if (0 == rows)
+  {
+    cont (cont_cls,
+          key,
+          size,
+          GNUNET_NO,
+          NULL);
+    return;
+  }
+  plugin->env->duc (plugin->env->cls,
+                    -size);
+  cont (cont_cls,
+        key,
+        size,
+        GNUNET_OK,
+        NULL);
+}
+
+
+/**
  * Entry point for the plugin.
  *
  * @param cls the `struct GNUNET_DATASTORE_PluginEnvironment *`
@@ -1158,24 +1133,20 @@ libgnunet_plugin_datastore_mysql_init (void *cls)
        " hash BINARY(64) NOT NULL DEFAULT '',"
        " vhash BINARY(64) NOT NULL DEFAULT '',"
        " value BLOB NOT NULL DEFAULT ''," " uid BIGINT NOT NULL AUTO_INCREMENT,"
-       " PRIMARY KEY (uid)," " INDEX idx_hash (hash(64)),"
-       " INDEX idx_hash_uid (hash(64),uid),"
-       " INDEX idx_hash_vhash (hash(64),vhash(64)),"
+       " PRIMARY KEY (uid),"
        " INDEX idx_hash_type_uid (hash(64),type,rvalue),"
-       " INDEX idx_prio (prio)," " INDEX idx_repl_rvalue (repl,rvalue),"
+       " INDEX idx_prio (prio),"
+       " INDEX idx_repl_rvalue (repl,rvalue),"
        " INDEX idx_expire (expire),"
        " INDEX idx_anonLevel_type_rvalue (anonLevel,type,rvalue)"
        ") ENGINE=InnoDB") || MRUNS ("SET AUTOCOMMIT = 1") ||
       PINIT (plugin->insert_entry, INSERT_ENTRY) ||
       PINIT (plugin->delete_entry_by_uid, DELETE_ENTRY_BY_UID) ||
+      PINIT (plugin->delete_entry_by_hash_value, DELETE_ENTRY_BY_HASH_VALUE) ||
       PINIT (plugin->select_entry, SELECT_ENTRY) ||
       PINIT (plugin->select_entry_by_hash, SELECT_ENTRY_BY_HASH) ||
-      PINIT (plugin->select_entry_by_hash_and_vhash,
-             SELECT_ENTRY_BY_HASH_AND_VHASH) ||
       PINIT (plugin->select_entry_by_hash_and_type,
              SELECT_ENTRY_BY_HASH_AND_TYPE) ||
-      PINIT (plugin->select_entry_by_hash_vhash_and_type,
-             SELECT_ENTRY_BY_HASH_VHASH_AND_TYPE) ||
       PINIT (plugin->get_size, SELECT_SIZE) ||
       PINIT (plugin->update_entry, UPDATE_ENTRY) ||
       PINIT (plugin->dec_repl, DEC_REPL) ||
@@ -1184,7 +1155,8 @@ libgnunet_plugin_datastore_mysql_init (void *cls)
       PINIT (plugin->select_priority, SELECT_IT_PRIORITY) ||
       PINIT (plugin->max_repl, SELECT_MAX_REPL) ||
       PINIT (plugin->get_all_keys, GET_ALL_KEYS) ||
-      PINIT (plugin->select_replication, SELECT_IT_REPLICATION))
+      PINIT (plugin->select_replication, SELECT_IT_REPLICATION) ||
+      false)
   {
     GNUNET_MYSQL_context_destroy (plugin->mc);
     GNUNET_free (plugin);
@@ -1197,13 +1169,13 @@ libgnunet_plugin_datastore_mysql_init (void *cls)
   api->cls = plugin;
   api->estimate_size = &mysql_plugin_estimate_size;
   api->put = &mysql_plugin_put;
-  api->update = &mysql_plugin_update;
   api->get_key = &mysql_plugin_get_key;
   api->get_replication = &mysql_plugin_get_replication;
   api->get_expiration = &mysql_plugin_get_expiration;
   api->get_zero_anonymity = &mysql_plugin_get_zero_anonymity;
   api->get_keys = &mysql_plugin_get_keys;
   api->drop = &mysql_plugin_drop;
+  api->remove_key = &mysql_plugin_remove_key;
   GNUNET_log_from (GNUNET_ERROR_TYPE_INFO, "mysql",
                    _("Mysql database running\n"));
   return api;
diff --git a/src/datastore/plugin_datastore_postgres.c b/src/datastore/plugin_datastore_postgres.c
index 87a7acbdc..b6aeb0be6 100644
--- a/src/datastore/plugin_datastore_postgres.c
+++ b/src/datastore/plugin_datastore_postgres.c
@@ -119,9 +119,6 @@ init_connection (struct Plugin *plugin)
                                "CREATE INDEX IF NOT EXISTS idx_hash ON gn090 (hash)")) ||
         (GNUNET_OK !=
          GNUNET_POSTGRES_exec (plugin->dbh,
-                               "CREATE INDEX IF NOT EXISTS idx_hash_vhash ON gn090 (hash,vhash)")) ||
-        (GNUNET_OK !=
-         GNUNET_POSTGRES_exec (plugin->dbh,
                                "CREATE INDEX IF NOT EXISTS idx_prio ON gn090 (prio)")) ||
         (GNUNET_OK !=
          GNUNET_POSTGRES_exec (plugin->dbh,
@@ -183,9 +180,8 @@ init_connection (struct Plugin *plugin)
                    "WHERE oid >= $1::bigint AND "
                    "(rvalue >= $2 OR 0 = $3::smallint) AND "
                    "(hash = $4 OR 0 = $5::smallint) AND "
-                   "(vhash = $6 OR 0 = $7::smallint) AND "
-                   "(type = $8 OR 0 = $9::smallint) "
-                   "ORDER BY oid ASC LIMIT 1", 9)) ||
+                   "(type = $6 OR 0 = $7::smallint) "
+                   "ORDER BY oid ASC LIMIT 1", 7)) ||
       (GNUNET_OK !=
        GNUNET_POSTGRES_prepare (plugin->dbh, "put",
                    "INSERT INTO gn090 (repl, type, prio, anonLevel, expire, rvalue, hash, vhash, value) "
@@ -195,8 +191,8 @@ init_connection (struct Plugin *plugin)
                    "UPDATE gn090 "
                    "SET prio = prio + $1, "
                    "repl = repl + $2, "
-                   "expire = CASE WHEN expire < $3 THEN $3 ELSE expire END "
-                   "WHERE oid = $4", 4)) ||
+                   "expire = GREATEST(expire, $3) "
+                   "WHERE hash = $4 AND vhash = $5", 5)) ||
       (GNUNET_OK !=
        GNUNET_POSTGRES_prepare (plugin->dbh, "decrepl",
                    "UPDATE gn090 SET repl = GREATEST (repl - 1, 0) "
@@ -223,6 +219,10 @@ init_connection (struct Plugin *plugin)
       (GNUNET_OK !=
        GNUNET_POSTGRES_prepare (plugin->dbh, "delrow", "DELETE FROM gn090 " "WHERE oid=$1", 1)) ||
       (GNUNET_OK !=
+       GNUNET_POSTGRES_prepare (plugin->dbh, "remove", "DELETE FROM gn090 "
+         "WHERE hash = $1 AND "
+         "value = $2", 2)) ||
+      (GNUNET_OK !=
        GNUNET_POSTGRES_prepare (plugin->dbh, "get_keys", "SELECT hash FROM gn090", 0)))
   {
     PQfinish (plugin->dbh);
@@ -288,6 +288,7 @@ postgres_plugin_estimate_size (void *cls, unsigned long long *estimate)
  *
  * @param cls closure with the `struct Plugin`
  * @param key key for the item
+ * @param absent true if the key was not found in the bloom filter
  * @param size number of bytes in data
  * @param data content stored
  * @param type type of the content
@@ -300,23 +301,70 @@ postgres_plugin_estimate_size (void *cls, unsigned long long *estimate)
  */
 static void
 postgres_plugin_put (void *cls,
-                     const struct GNUNET_HashCode *key,
-                     uint32_t size,
+                     const struct GNUNET_HashCode *key,
+                     bool absent,
+                     uint32_t size,
                      const void *data,
-                     enum GNUNET_BLOCK_Type type,
+                     enum GNUNET_BLOCK_Type type,
                      uint32_t priority,
-                     uint32_t anonymity,
+                     uint32_t anonymity,
                      uint32_t replication,
                      struct GNUNET_TIME_Absolute expiration,
-                     PluginPutCont cont,
+                     PluginPutCont cont,
                      void *cont_cls)
 {
   struct Plugin *plugin = cls;
-  uint32_t utype = type;
   struct GNUNET_HashCode vhash;
+  PGresult *ret;
+
+  GNUNET_CRYPTO_hash (data,
+                      size,
+                      &vhash);
+
+  if (!absent)
+  {
+    struct GNUNET_PQ_QueryParam params[] = {
+      GNUNET_PQ_query_param_uint32 (&priority),
+      GNUNET_PQ_query_param_uint32 (&replication),
+      GNUNET_PQ_query_param_absolute_time (&expiration),
+      GNUNET_PQ_query_param_auto_from_type (key),
+      GNUNET_PQ_query_param_auto_from_type (&vhash),
+      GNUNET_PQ_query_param_end
+    };
+    ret = GNUNET_PQ_exec_prepared (plugin->dbh,
+                                   "update",
+                                   params);
+    if (GNUNET_OK !=
+        GNUNET_POSTGRES_check_result (plugin->dbh,
+                                      ret,
+                                      PGRES_COMMAND_OK,
+                                      "PQexecPrepared",
+                                      "update"))
+    {
+      cont (cont_cls,
+            key,
+            size,
+            GNUNET_SYSERR,
+            _("Postgress exec failure"));
+      return;
+    }
+    /* What an awful API, this function really does return a string */
+    bool affected = 0 != strcmp ("0", PQcmdTuples (ret));
+    PQclear (ret);
+    if (affected)
+    {
+      cont (cont_cls,
+            key,
+            size,
+            GNUNET_NO,
+            NULL);
+      return;
+    }
+  }
+
+  uint32_t utype = type;
   uint64_t rvalue = GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
                                               UINT64_MAX);
-  PGresult *ret;
   struct GNUNET_PQ_QueryParam params[] = {
     GNUNET_PQ_query_param_uint32 (&replication),
     GNUNET_PQ_query_param_uint32 (&utype),
@@ -330,7 +378,6 @@ postgres_plugin_put (void *cls,
     GNUNET_PQ_query_param_end
   };
 
-  GNUNET_CRYPTO_hash (data, size, &vhash);
   ret = GNUNET_PQ_exec_prepared (plugin->dbh,
                                  "put",
                                  params);
@@ -489,11 +536,6 @@ process_result (struct Plugin *plugin,
  * @param next_uid return the result with lowest uid >= next_uid
  * @param random if true, return a random result instead of using next_uid
  * @param key maybe NULL (to match all entries)
- * @param vhash hash of the value, maybe NULL (to
- *        match all values that have the right key).
- *        Note that for DBlocks there is no difference
- *        betwen key and vhash, but for other blocks
- *        there may be!
  * @param type entries of which type are relevant?
  *     Use 0 for any type.
  * @param proc function to call on the matching value;
@@ -505,7 +547,6 @@ postgres_plugin_get_key (void *cls,
                          uint64_t next_uid,
                          bool random,
                          const struct GNUNET_HashCode *key,
-                         const struct GNUNET_HashCode *vhash,
                          enum GNUNET_BLOCK_Type type,
                          PluginDatumProcessor proc,
                          void *proc_cls)
@@ -514,7 +555,6 @@ postgres_plugin_get_key (void *cls,
   uint32_t utype = type;
   uint16_t use_rvalue = random;
   uint16_t use_key = NULL != key;
-  uint16_t use_vhash = NULL != vhash;
   uint16_t use_type = GNUNET_BLOCK_TYPE_ANY != type;
   uint64_t rvalue;
   struct GNUNET_PQ_QueryParam params[] = {
@@ -523,8 +563,6 @@ postgres_plugin_get_key (void *cls,
     GNUNET_PQ_query_param_uint16 (&use_rvalue),
     GNUNET_PQ_query_param_auto_from_type (key),
     GNUNET_PQ_query_param_uint16 (&use_key),
-    GNUNET_PQ_query_param_auto_from_type (vhash),
-    GNUNET_PQ_query_param_uint16 (&use_vhash),
     GNUNET_PQ_query_param_uint32 (&utype),
     GNUNET_PQ_query_param_uint16 (&use_type),
     GNUNET_PQ_query_param_end
@@ -750,67 +788,6 @@ postgres_plugin_get_expiration (void *cls,
 
 
 /**
- * Update the priority, replication and expiration for a particular
- * unique ID in the datastore.  If the expiration time in value is
- * different than the time found in the datastore, the higher value
- * should be kept.  The specified priority and replication is added
- * to the existing value.
- *
- * @param cls our `struct Plugin *`
- * @param uid unique identifier of the datum
- * @param priority by how much should the priority
- *     change?
- * @param replication by how much should the replication
- *     change?
- * @param expire new expiration time should be the
- *     MAX of any existing expiration time and
- *     this value
- * @param cont continuation called with success or failure status
- * @param cons_cls continuation closure
- */
-static void
-postgres_plugin_update (void *cls,
-                        uint64_t uid,
-                        uint32_t priority,
-                        uint32_t replication,
-                        struct GNUNET_TIME_Absolute expire,
-                        PluginUpdateCont cont,
-                        void *cont_cls)
-{
-  struct Plugin *plugin = cls;
-  uint32_t oid = (uint32_t) uid;
-  struct GNUNET_PQ_QueryParam params[] = {
-    GNUNET_PQ_query_param_uint32 (&priority),
-    GNUNET_PQ_query_param_uint32 (&replication),
-    GNUNET_PQ_query_param_absolute_time (&expire),
-    GNUNET_PQ_query_param_uint32 (&oid),
-    GNUNET_PQ_query_param_end
-  };
-  PGresult *ret;
-
-  ret = GNUNET_PQ_exec_prepared (plugin->dbh,
-                                 "update",
-                                 params);
-  if (GNUNET_OK !=
-      GNUNET_POSTGRES_check_result (plugin->dbh,
-                                    ret,
-                                    PGRES_COMMAND_OK,
-                                    "PQexecPrepared",
-                                    "update"))
-  {
-    cont (cont_cls,
-          GNUNET_SYSERR,
-          NULL);
-    return;
-  }
-  PQclear (ret);
-  cont (cont_cls,
-        GNUNET_OK,
-        NULL);
-}
-
-
-/**
  * Get all of the keys in the datastore.
  *
  * @param cls closure with the `struct Plugin *`
@@ -868,6 +845,74 @@ postgres_plugin_drop (void *cls)
 
 
 /**
+ * Remove a particular key in the datastore.
+ *
+ * @param cls closure
+ * @param key key for the content
+ * @param size number of bytes in data
+ * @param data content stored
+ * @param cont continuation called with success or failure status
+ * @param cont_cls continuation closure for @a cont
+ */
+static void
+postgres_plugin_remove_key (void *cls,
+                            const struct GNUNET_HashCode *key,
+                            uint32_t size,
+                            const void *data,
+                            PluginRemoveCont cont,
+                            void *cont_cls)
+{
+  struct Plugin *plugin = cls;
+  PGresult *ret;
+  struct GNUNET_PQ_QueryParam params[] = {
+    GNUNET_PQ_query_param_auto_from_type (key),
+    GNUNET_PQ_query_param_fixed_size (data, size),
+    GNUNET_PQ_query_param_end
+  };
+  ret = GNUNET_PQ_exec_prepared (plugin->dbh,
+                                 "remove",
+                                 params);
+  if (GNUNET_OK !=
+      GNUNET_POSTGRES_check_result (plugin->dbh,
+                                    ret,
+                                    PGRES_COMMAND_OK,
+                                    "PQexecPrepared",
+                                    "remove"))
+  {
+    cont (cont_cls,
+          key,
+          size,
+          GNUNET_SYSERR,
+          _("Postgress exec failure"));
+    return;
+  }
+  /* What an awful API, this function really does return a string */
+  bool affected = 0 != strcmp ("0", PQcmdTuples (ret));
+  PQclear (ret);
+  if (!affected)
+  {
+    cont (cont_cls,
+          key,
+          size,
+          GNUNET_NO,
+          NULL);
+    return;
+  }
+  plugin->env->duc (plugin->env->cls,
+                    - (size + GNUNET_DATASTORE_ENTRY_OVERHEAD));
+  GNUNET_log_from (GNUNET_ERROR_TYPE_DEBUG,
+                   "datastore-postgres",
+                   "Deleted %u bytes from database\n",
+                   (unsigned int) size);
+  cont (cont_cls,
+        key,
+        size,
+        GNUNET_OK,
+        NULL);
+}
+
+
+/**
  * Entry point for the plugin.
  *
  * @param cls the `struct GNUNET_DATASTORE_PluginEnvironment*`
@@ -891,13 +936,13 @@ libgnunet_plugin_datastore_postgres_init (void *cls)
   api->cls = plugin;
   api->estimate_size = &postgres_plugin_estimate_size;
   api->put = &postgres_plugin_put;
-  api->update = &postgres_plugin_update;
   api->get_key = &postgres_plugin_get_key;
   api->get_replication = &postgres_plugin_get_replication;
   api->get_expiration = &postgres_plugin_get_expiration;
   api->get_zero_anonymity = &postgres_plugin_get_zero_anonymity;
   api->get_keys = &postgres_plugin_get_keys;
   api->drop = &postgres_plugin_drop;
+  api->remove_key = &postgres_plugin_remove_key;
   GNUNET_log_from (GNUNET_ERROR_TYPE_INFO,
                    "datastore-postgres",
                    _("Postgres database running\n"));
diff --git a/src/datastore/plugin_datastore_sqlite.c b/src/datastore/plugin_datastore_sqlite.c
index 1f874e190..bcaf27d99 100644
--- a/src/datastore/plugin_datastore_sqlite.c
+++ b/src/datastore/plugin_datastore_sqlite.c
@@ -88,6 +88,11 @@ struct Plugin
   sqlite3 *dbh;
 
   /**
+   * Precompiled SQL for remove_key.
+   */
+  sqlite3_stmt *remove;
+
+  /**
    * Precompiled SQL for deletion.
    */
   sqlite3_stmt *delRow;
@@ -95,7 +100,7 @@ struct Plugin
   /**
    * Precompiled SQL for update.
    */
-  sqlite3_stmt *updPrio;
+  sqlite3_stmt *update;
 
   /**
    * Get maximum repl value in database.
@@ -185,10 +190,6 @@ create_indices (sqlite3 * dbh)
                      NULL, NULL, NULL)) ||
       (SQLITE_OK !=
        sqlite3_exec (dbh,
-                     "CREATE INDEX IF NOT EXISTS idx_hash_vhash ON gn090 (hash,vhash)",
-                     NULL, NULL, NULL)) ||
-      (SQLITE_OK !=
-       sqlite3_exec (dbh,
                      "CREATE INDEX IF NOT EXISTS idx_expire_repl ON gn090 (expire ASC,repl DESC)",
                      NULL, NULL, NULL)) ||
       (SQLITE_OK !=
@@ -356,8 +357,8 @@ database_setup (const struct GNUNET_CONFIGURATION_Handle *cfg,
                     "SET prio = prio + ?, "
                     "repl = repl + ?, "
                     "expire = MAX(expire, ?) "
-                    "WHERE _ROWID_ = ?",
-                    &plugin->updPrio)) ||
+                    "WHERE hash = ? AND vhash = ?",
+                    &plugin->update)) ||
        (SQLITE_OK !=
         sq_prepare (plugin->dbh,
                     "UPDATE gn090 " "SET repl = MAX (0, repl - 1) WHERE _ROWID_ = ?",
@@ -415,15 +416,21 @@ database_setup (const struct GNUNET_CONFIGURATION_Handle *cfg,
                     "WHERE _ROWID_ >= ? AND "
                     "(rvalue >= ? OR 0 = ?) AND "
                     "(hash = ? OR 0 = ?) AND "
-                    "(vhash = ? OR 0 = ?) AND "
                     "(type = ? OR 0 = ?) "
                     "ORDER BY _ROWID_ ASC LIMIT 1",
                     &plugin->get)) ||
        (SQLITE_OK !=
         sq_prepare (plugin->dbh,
                     "DELETE FROM gn090 WHERE _ROWID_ = ?",
-                    &plugin->delRow))
-       )
+                    &plugin->delRow)) ||
+       (SQLITE_OK !=
+        sq_prepare (plugin->dbh,
+                    "DELETE FROM gn090 "
+                    "WHERE hash = ? AND "
+                    "value = ? "
+                    "LIMIT 1",
+                    &plugin->remove)) ||
+       false)
   {
     LOG_SQLITE (plugin,
                 GNUNET_ERROR_TYPE_ERROR,
@@ -448,10 +455,12 @@ database_shutdown (struct Plugin *plugin)
   sqlite3_stmt *stmt;
 #endif
 
+  if (NULL != plugin->remove)
+    sqlite3_finalize (plugin->remove);
   if (NULL != plugin->delRow)
     sqlite3_finalize (plugin->delRow);
-  if (NULL != plugin->updPrio)
-    sqlite3_finalize (plugin->updPrio);
+  if (NULL != plugin->update)
+    sqlite3_finalize (plugin->update);
   if (NULL != plugin->updRepl)
     sqlite3_finalize (plugin->updRepl);
   if (NULL != plugin->selRepl)
@@ -541,6 +550,7 @@ delete_by_rowid (struct Plugin *plugin,
  *
  * @param cls closure
  * @param key key for the item
+ * @param absent true if the key was not found in the bloom filter
  * @param size number of bytes in @a data
  * @param data content stored
  * @param type type of the content
@@ -554,6 +564,7 @@ delete_by_rowid (struct Plugin *plugin,
 static void
 sqlite_plugin_put (void *cls,
                    const struct GNUNET_HashCode *key,
+                   bool absent,
                    uint32_t size,
                    const void *data,
                    enum GNUNET_BLOCK_Type type,
@@ -564,8 +575,63 @@ sqlite_plugin_put (void *cls,
                    PluginPutCont cont,
                    void *cont_cls)
 {
-  uint64_t rvalue;
+  struct Plugin *plugin = cls;
   struct GNUNET_HashCode vhash;
+  char *msg = NULL;
+
+  GNUNET_CRYPTO_hash (data,
+                      size,
+                      &vhash);
+
+  if (!absent)
+  {
+    struct GNUNET_SQ_QueryParam params[] = {
+      GNUNET_SQ_query_param_uint32 (&priority),
+      GNUNET_SQ_query_param_uint32 (&replication),
+      GNUNET_SQ_query_param_absolute_time (&expiration),
+      GNUNET_SQ_query_param_auto_from_type (key),
+      GNUNET_SQ_query_param_auto_from_type (&vhash),
+      GNUNET_SQ_query_param_end
+    };
+
+    if (GNUNET_OK !=
+        GNUNET_SQ_bind (plugin->update,
+                        params))
+    {
+      cont (cont_cls,
+            key,
+            size,
+            GNUNET_SYSERR,
+            _("sqlite bind failure"));
+      return;
+    }
+    if (SQLITE_DONE != sqlite3_step (plugin->update))
+    {
+      LOG_SQLITE_MSG (plugin, &msg, GNUNET_ERROR_TYPE_ERROR | GNUNET_ERROR_TYPE_BULK,
+                      "sqlite3_step");
+      cont (cont_cls,
+            key,
+            size,
+            GNUNET_SYSERR,
+            msg);
+      GNUNET_free_non_null (msg);
+      return;
+    }
+    int changes = sqlite3_changes (plugin->dbh);
+    GNUNET_SQ_reset (plugin->dbh,
+                     plugin->update);
+    if (0 != changes)
+    {
+      cont (cont_cls,
+            key,
+            size,
+            GNUNET_NO,
+            NULL);
+      return;
+    }
+  }
+
+  uint64_t rvalue;
   uint32_t type32 = (uint32_t) type;
   struct GNUNET_SQ_QueryParam params[] = {
     GNUNET_SQ_query_param_uint32 (&replication),
@@ -579,11 +645,9 @@ sqlite_plugin_put (void *cls,
     GNUNET_SQ_query_param_fixed_size (data, size),
     GNUNET_SQ_query_param_end
   };
-  struct Plugin *plugin = cls;
   int n;
   int ret;
   sqlite3_stmt *stmt;
-  char *msg = NULL;
 
   if (size > MAX_ITEM_SIZE)
   {
@@ -598,15 +662,13 @@ sqlite_plugin_put (void *cls,
                    GNUNET_STRINGS_relative_time_to_string (GNUNET_TIME_absolute_get_remaining (expiration),
                                                            GNUNET_YES),
                    GNUNET_STRINGS_absolute_time_to_string (expiration));
-  GNUNET_CRYPTO_hash (data, size, &vhash);
   stmt = plugin->insertContent;
   rvalue = GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK, UINT64_MAX);
   if (GNUNET_OK !=
       GNUNET_SQ_bind (stmt,
                       params))
   {
-    cont (cont_cls, key, size, GNUNET_SYSERR, msg);
-    GNUNET_free_non_null(msg);
+    cont (cont_cls, key, size, GNUNET_SYSERR, NULL);
     return;
   }
   n = sqlite3_step (stmt);
@@ -646,79 +708,6 @@ sqlite_plugin_put (void *cls,
 
 
 /**
- * Update the priority, replication and expiration for a particular
- * unique ID in the datastore.  If the expiration time in value is
- * different than the time found in the datastore, the higher value
- * should be kept.  The specified priority and replication is added
- * to the existing value.
- *
- * @param cls the plugin context (state for this module)
- * @param uid unique identifier of the datum
- * @param priority by how much should the priority
- *     change?
- * @param replication by how much should the replication
- *     change?
- * @param expire new expiration time should be the
- *     MAX of any existing expiration time and
- *     this value
- * @param cont continuation called with success or failure status
- * @param cons_cls closure for @a cont
- */
-static void
-sqlite_plugin_update (void *cls,
-                      uint64_t uid,
-                      uint32_t priority,
-                      uint32_t replication,
-                      struct GNUNET_TIME_Absolute expire,
-                      PluginUpdateCont cont,
-                      void *cont_cls)
-{
-  struct Plugin *plugin = cls;
-  struct GNUNET_SQ_QueryParam params[] = {
-    GNUNET_SQ_query_param_uint32 (&priority),
-    GNUNET_SQ_query_param_uint32 (&replication),
-    GNUNET_SQ_query_param_absolute_time (&expire),
-    GNUNET_SQ_query_param_uint64 (&uid),
-    GNUNET_SQ_query_param_end
-  };
-  int n;
-  char *msg = NULL;
-
-  if (GNUNET_OK !=
-      GNUNET_SQ_bind (plugin->updPrio,
-                      params))
-  {
-    cont (cont_cls, GNUNET_SYSERR, msg);
-    GNUNET_free_non_null(msg);
-    return;
-  }
-  n = sqlite3_step (plugin->updPrio);
-  GNUNET_SQ_reset (plugin->dbh,
-                   plugin->updPrio);
-  switch (n)
-  {
-  case SQLITE_DONE:
-    GNUNET_log_from (GNUNET_ERROR_TYPE_DEBUG, "sqlite", "Block updated\n");
-    cont (cont_cls, GNUNET_OK, NULL);
-    return;
-  case SQLITE_BUSY:
-    LOG_SQLITE_MSG (plugin, &msg,
-                    GNUNET_ERROR_TYPE_WARNING | GNUNET_ERROR_TYPE_BULK,
-                    "sqlite3_step");
-    cont (cont_cls, GNUNET_NO, msg);
-    GNUNET_free_non_null(msg);
-    return;
-  default:
-    LOG_SQLITE_MSG (plugin, &msg, GNUNET_ERROR_TYPE_ERROR | GNUNET_ERROR_TYPE_BULK,
-                    "sqlite3_step");
-    cont (cont_cls, GNUNET_SYSERR, msg);
-    GNUNET_free_non_null(msg);
-    return;
-  }
-}
-
-
-/**
  * Execute statement that gets a row and call the callback
  * with the result.  Resets the statement afterwards.
  *
@@ -865,15 +854,10 @@ sqlite_plugin_get_zero_anonymity (void *cls,
  * @param next_uid return the result with lowest uid >= next_uid
  * @param random if true, return a random result instead of using next_uid
  * @param key maybe NULL (to match all entries)
- * @param vhash hash of the value, maybe NULL (to
- *        match all values that have the right key).
- *        Note that for DBlocks there is no difference
- *        betwen key and vhash, but for other blocks
- *        there may be!
  * @param type entries of which type are relevant?
  *     Use 0 for any type.
- * @param proc function to call on each matching value;
- *        will be called once with a NULL value at the end
+ * @param proc function to call on the matching value;
+ *        will be called with NULL if nothing matches
  * @param proc_cls closure for @a proc
  */
 static void
@@ -881,7 +865,6 @@ sqlite_plugin_get_key (void *cls,
                        uint64_t next_uid,
                        bool random,
                        const struct GNUNET_HashCode *key,
-                       const struct GNUNET_HashCode *vhash,
                        enum GNUNET_BLOCK_Type type,
                        PluginDatumProcessor proc,
                        void *proc_cls)
@@ -892,15 +875,12 @@ sqlite_plugin_get_key (void *cls,
   uint32_t type32 = (uint32_t) type;
   uint16_t use_type = GNUNET_BLOCK_TYPE_ANY != type;
   uint16_t use_key = NULL != key;
-  uint16_t use_vhash = NULL != vhash;
   struct GNUNET_SQ_QueryParam params[] = {
     GNUNET_SQ_query_param_uint64 (&next_uid),
     GNUNET_SQ_query_param_uint64 (&rvalue),
     GNUNET_SQ_query_param_uint16 (&use_rvalue),
     GNUNET_SQ_query_param_auto_from_type (key),
     GNUNET_SQ_query_param_uint16 (&use_key),
-    GNUNET_SQ_query_param_auto_from_type (vhash),
-    GNUNET_SQ_query_param_uint16 (&use_vhash),
     GNUNET_SQ_query_param_uint32 (&type32),
     GNUNET_SQ_query_param_uint16 (&use_type),
     GNUNET_SQ_query_param_end
@@ -1206,6 +1186,79 @@ sqlite_plugin_drop (void *cls)
 
 
 /**
+ * Remove a particular key in the datastore.
+ *
+ * @param cls closure
+ * @param key key for the content
+ * @param size number of bytes in data
+ * @param data content stored
+ * @param cont continuation called with success or failure status
+ * @param cont_cls continuation closure for @a cont
+ */
+static void
+sqlite_plugin_remove_key (void *cls,
+                          const struct GNUNET_HashCode *key,
+                          uint32_t size,
+                          const void *data,
+                          PluginRemoveCont cont,
+                          void *cont_cls)
+{
+  struct Plugin *plugin = cls;
+  struct GNUNET_SQ_QueryParam params[] = {
+    GNUNET_SQ_query_param_auto_from_type (key),
+    GNUNET_SQ_query_param_fixed_size (data, size),
+    GNUNET_SQ_query_param_end
+  };
+
+  if (GNUNET_OK !=
+      GNUNET_SQ_bind (plugin->remove,
+                      params))
+  {
+    cont (cont_cls,
+          key,
+          size,
+          GNUNET_SYSERR,
+          "bind failed");
+    return;
+  }
+  if (SQLITE_DONE != sqlite3_step (plugin->remove))
+  {
+    LOG_SQLITE (plugin,
+                GNUNET_ERROR_TYPE_ERROR | GNUNET_ERROR_TYPE_BULK,
+                "sqlite3_step");
+    GNUNET_SQ_reset (plugin->dbh,
+                     plugin->remove);
+    cont (cont_cls,
+          key,
+          size,
+          GNUNET_SYSERR,
+          "sqlite3_step failed");
+    return;
+  }
+  int changes = sqlite3_changes (plugin->dbh);
+  GNUNET_SQ_reset (plugin->dbh,
+                   plugin->remove);
+  if (0 == changes)
+  {
+    cont (cont_cls,
+          key,
+          size,
+          GNUNET_NO,
+          NULL);
+    return;
+  }
+  if (NULL != plugin->env->duc)
+    plugin->env->duc (plugin->env->cls,
+                      -(size + GNUNET_DATASTORE_ENTRY_OVERHEAD));
+  cont (cont_cls,
+        key,
+        size,
+        GNUNET_OK,
+        NULL);
+}
+
+
+/**
  * Get an estimate of how much space the database is
  * currently using.
  *
@@ -1300,13 +1353,13 @@ libgnunet_plugin_datastore_sqlite_init (void *cls)
   api->cls = &plugin;
   api->estimate_size = &sqlite_plugin_estimate_size;
   api->put = &sqlite_plugin_put;
-  api->update = &sqlite_plugin_update;
   api->get_key = &sqlite_plugin_get_key;
   api->get_replication = &sqlite_plugin_get_replication;
   api->get_expiration = &sqlite_plugin_get_expiration;
   api->get_zero_anonymity = &sqlite_plugin_get_zero_anonymity;
   api->get_keys = &sqlite_plugin_get_keys;
   api->drop = &sqlite_plugin_drop;
+  api->remove_key = &sqlite_plugin_remove_key;
   GNUNET_log_from (GNUNET_ERROR_TYPE_INFO,
                    "sqlite",
                    _("Sqlite database running\n"));
diff --git a/src/datastore/plugin_datastore_template.c b/src/datastore/plugin_datastore_template.c
index 8e44f020d..16bda45d4 100644
--- a/src/datastore/plugin_datastore_template.c
+++ b/src/datastore/plugin_datastore_template.c
@@ -62,6 +62,7 @@ template_plugin_estimate_size (void *cls, unsigned long long *estimate)
  *
  * @param cls closure
  * @param key key for the item
+ * @param absent true if the key was not found in the bloom filter
  * @param size number of bytes in data
  * @param data content stored
  * @param type type of the content
@@ -73,11 +74,17 @@ template_plugin_estimate_size (void *cls, unsigned long long *estimate)
  * @param cont_cls continuation closure
  */
 static void
-template_plugin_put (void *cls, const struct GNUNET_HashCode * key, uint32_t size,
-                     const void *data, enum GNUNET_BLOCK_Type type,
-                     uint32_t priority, uint32_t anonymity,
+template_plugin_put (void *cls,
+                     const struct GNUNET_HashCode *key,
+                     bool absent,
+                     uint32_t size,
+                     const void *data,
+                     enum GNUNET_BLOCK_Type type,
+                     uint32_t priority,
+                     uint32_t anonymity,
                      uint32_t replication,
-                     struct GNUNET_TIME_Absolute expiration, PluginPutCont cont,
+                     struct GNUNET_TIME_Absolute expiration,
+                     PluginPutCont cont,
                      void *cont_cls)
 {
   GNUNET_break (0);
@@ -92,11 +99,6 @@ template_plugin_put (void *cls, const struct GNUNET_HashCode * key, uint32_t siz
  * @param next_uid return the result with lowest uid >= next_uid
  * @param random if true, return a random result instead of using next_uid
  * @param key maybe NULL (to match all entries)
- * @param vhash hash of the value, maybe NULL (to
- *        match all values that have the right key).
- *        Note that for DBlocks there is no difference
- *        betwen key and vhash, but for other blocks
- *        there may be!
  * @param type entries of which type are relevant?
  *     Use 0 for any type.
  * @param proc function to call on each matching value;
@@ -104,10 +106,12 @@ template_plugin_put (void *cls, const struct GNUNET_HashCode * key, uint32_t siz
  * @param proc_cls closure for proc
  */
 static void
-template_plugin_get_key (void *cls, uint64_t next_uid, bool random,
-                         const struct GNUNET_HashCode * key,
-                         const struct GNUNET_HashCode * vhash,
-                         enum GNUNET_BLOCK_Type type, PluginDatumProcessor proc,
+template_plugin_get_key (void *cls,
+                         uint64_t next_uid,
+                         bool random,
+                         const struct GNUNET_HashCode *key,
+                         enum GNUNET_BLOCK_Type type,
+                         PluginDatumProcessor proc,
                          void *proc_cls)
 {
   GNUNET_break (0);
@@ -151,39 +155,6 @@ template_plugin_get_expiration (void *cls, PluginDatumProcessor proc,
 
 
 /**
- * Update the priority, replication and expiration for a particular
- * unique ID in the datastore.  If the expiration time in value is
- * different than the time found in the datastore, the higher value
- * should be kept.  The specified priority and replication is added
- * to the existing value.
- *
- * @param cls our "struct Plugin*"
- * @param uid unique identifier of the datum
- * @param priority by how much should the priority
- *     change?
- * @param replication by how much should the replication
- *     change?
- * @param expire new expiration time should be the
- *     MAX of any existing expiration time and
- *     this value
- * @param cont continuation called with success or failure status
- * @param cons_cls continuation closure
- */
-static void
-template_plugin_update (void *cls,
-                        uint64_t uid,
-                        uint32_t priority,
-                        uint32_t replication,
-                        struct GNUNET_TIME_Absolute expire,
-                        PluginUpdateCont cont,
-                        void *cont_cls)
-{
-  GNUNET_break (0);
-  cont (cont_cls, GNUNET_SYSERR, "not implemented");
-}
-
-
-/**
  * Call the given processor on an item with zero anonymity.
  *
  * @param cls our "struct Plugin*"
@@ -230,6 +201,29 @@ template_get_keys (void *cls,
 
 
 /**
+ * Remove a particular key in the datastore.
+ *
+ * @param cls closure
+ * @param key key for the content
+ * @param size number of bytes in data
+ * @param data content stored
+ * @param cont continuation called with success or failure status
+ * @param cont_cls continuation closure for @a cont
+ */
+static void
+template_plugin_remove_key (void *cls,
+                            const struct GNUNET_HashCode *key,
+                            uint32_t size,
+                            const void *data,
+                            PluginRemoveCont cont,
+                            void *cont_cls)
+{
+  GNUNET_break (0);
+  cont (cont_cls, key, size, GNUNET_SYSERR, "not implemented");
+}
+
+
+/**
  * Entry point for the plugin.
  *
  * @param cls the "struct GNUNET_DATASTORE_PluginEnvironment*"
@@ -248,13 +242,13 @@ libgnunet_plugin_datastore_template_init (void *cls)
   api->cls = plugin;
   api->estimate_size = &template_plugin_estimate_size;
   api->put = &template_plugin_put;
-  api->update = &template_plugin_update;
   api->get_key = &template_plugin_get_key;
   api->get_replication = &template_plugin_get_replication;
   api->get_expiration = &template_plugin_get_expiration;
   api->get_zero_anonymity = &template_plugin_get_zero_anonymity;
   api->drop = &template_plugin_drop;
   api->get_keys = &template_get_keys;
+  api->remove_key = &template_plugin_remove_key;
   GNUNET_log_from (GNUNET_ERROR_TYPE_INFO, "template",
                    _("Template database running\n"));
   return api;
diff --git a/src/datastore/test_plugin_datastore.c b/src/datastore/test_plugin_datastore.c
index 1867d6755..d460daed7 100644
--- a/src/datastore/test_plugin_datastore.c
+++ b/src/datastore/test_plugin_datastore.c
@@ -49,10 +49,10 @@ enum RunPhase
   RP_ERROR = 0,
   RP_PUT,
   RP_GET,
-  RP_UPDATE,
   RP_ITER_ZERO,
   RP_REPL_GET,
   RP_EXPI_GET,
+  RP_REMOVE,
   RP_DROP
 };
 
@@ -154,7 +154,7 @@ do_put (struct CpsRunContext *crc)
   /* most content is 32k */
   size = 32 * 1024;
 
-  if (GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, 16) == 0)   /* but some of it is less! */
+  if (0 != i && GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, 16) == 0)   /* but some of it is less! */
     size = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, 32 * 1024);
   size = size - (size & 7);     /* always multiple of 8 */
 
@@ -168,8 +168,13 @@ do_put (struct CpsRunContext *crc)
   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
               "putting type %u, anon %u under key %s\n", i + 1, i,
               GNUNET_h2s (&key));
-  crc->api->put (crc->api->cls, &key, size, value, i + 1 /* type */ ,
-                 prio, i /* anonymity */ ,
+  crc->api->put (crc->api->cls,
+                 &key,
+                 false /* absent */,
+                 size,
+                 value, i + 1 /* type */ ,
+                 prio,
+                 i /* anonymity */ ,
                  0 /* replication */ ,
                  GNUNET_TIME_relative_to_absolute
                    (GNUNET_TIME_relative_multiply
@@ -177,7 +182,8 @@ do_put (struct CpsRunContext *crc)
                       60 * 60 * 60 * 1000 +
                       GNUNET_CRYPTO_random_u32
                       (GNUNET_CRYPTO_QUALITY_WEAK, 1000))),
-                 put_continuation, crc);
+                 put_continuation,
+                 crc);
   i++;
 }
 
@@ -215,6 +221,25 @@ iterate_one_shot (void *cls,
 }
 
 
+static void
+remove_continuation (void *cls,
+                     const struct GNUNET_HashCode *key,
+                     uint32_t size,
+                     int status,
+                     const char *msg)
+{
+  struct CpsRunContext *crc = cls;
+
+  GNUNET_assert (NULL != key);
+  GNUNET_assert (32768 == size);
+  GNUNET_assert (GNUNET_OK == status);
+  GNUNET_assert (NULL == msg);
+  crc->phase++;
+  GNUNET_SCHEDULER_add_now (&test,
+                            crc);
+}
+
+
 /**
  * Function called when the service shuts
  * down.  Unloads our datastore plugin.
@@ -264,19 +289,6 @@ cleaning_task (void *cls)
 
 
 static void
-update_continuation (void *cls,
-                     int status,
-                     const char *msg)
-{
-  struct CpsRunContext *crc = cls;
-
-  GNUNET_assert (GNUNET_OK == status);
-  crc->phase++;
-  GNUNET_SCHEDULER_add_now (&test, crc);
-}
-
-
-static void
 test (void *cls)
 {
   struct CpsRunContext *crc = cls;
@@ -311,21 +323,10 @@ test (void *cls)
                        0,
                        false,
                        &key,
-                       NULL,
                        GNUNET_BLOCK_TYPE_ANY,
                        &iterate_one_shot,
                        crc);
     break;
-  case RP_UPDATE:
-    crc->api->update (crc->api->cls,
-                      guid,
-                      1,
-                      1,
-                      GNUNET_TIME_UNIT_ZERO_ABS,
-                      &update_continuation,
-                      crc);
-    break;
-
   case RP_ITER_ZERO:
     if (crc->cnt == 1)
     {
@@ -342,6 +343,23 @@ test (void *cls)
   case RP_EXPI_GET:
     crc->api->get_expiration (crc->api->cls, &iterate_one_shot, crc);
     break;
+  case RP_REMOVE:
+    {
+      struct GNUNET_HashCode key;
+      uint32_t size = 32768;
+      char value[size];
+
+      gen_key (0, &key);
+      memset (value, 0, size);
+      value[0] = crc->i;
+      crc->api->remove_key (crc->api->cls,
+                            &key,
+                            size,
+                            value,
+                            &remove_continuation,
+                            crc);
+      break;
+    }
   case RP_DROP:
     crc->api->drop (crc->api->cls);
     GNUNET_SCHEDULER_add_now (&cleaning_task, crc);
diff --git a/src/include/gnunet_datastore_plugin.h b/src/include/gnunet_datastore_plugin.h
index 516ba525c..36a3fbec2 100644
--- a/src/include/gnunet_datastore_plugin.h
+++ b/src/include/gnunet_datastore_plugin.h
@@ -134,7 +134,8 @@ typedef void
  * @param cls closure
  * @param key key for the item stored
  * @param size size of the item stored
- * @param status #GNUNET_OK or #GNUNET_SYSERROR
+ * @param status #GNUNET_OK if inserted, #GNUNET_NO if updated,
+ *        or #GNUNET_SYSERROR if error
  * @param msg error message on error
  */
 typedef void
@@ -152,6 +153,7 @@ typedef void
  *
  * @param cls closure
  * @param key key for the item
+ * @param absent true if the key was not found in the bloom filter
  * @param size number of bytes in @a data
  * @param data content stored
  * @param type type of the content
@@ -165,15 +167,16 @@ typedef void
 typedef void
 (*PluginPut) (void *cls,
               const struct GNUNET_HashCode *key,
-              uint32_t size,
-              const void *data,
-              enum GNUNET_BLOCK_Type type,
-              uint32_t priority,
-              uint32_t anonymity,
-              uint32_t replication,
-              struct GNUNET_TIME_Absolute expiration,
-              PluginPutCont cont,
-              void *cont_cls);
+              bool absent,
+              uint32_t size,
+              const void *data,
+              enum GNUNET_BLOCK_Type type,
+              uint32_t priority,
+              uint32_t anonymity,
+              uint32_t replication,
+              struct GNUNET_TIME_Absolute expiration,
+              PluginPutCont cont,
+              void *cont_cls);
 
 
 /**
@@ -209,11 +212,6 @@ typedef void
  * @param next_uid return the result with lowest uid >= next_uid
  * @param random if true, return a random result instead of using next_uid
  * @param key maybe NULL (to match all entries)
- * @param vhash hash of the value, maybe NULL (to
- *        match all values that have the right key).
- *        Note that for DBlocks there is no difference
- *        betwen key and vhash, but for other blocks
- *        there may be!
  * @param type entries of which type are relevant?
  *     Use 0 for any type.
  * @param proc function to call on the matching value;
@@ -225,68 +223,62 @@ typedef void
                  uint64_t next_uid,
                  bool random,
                  const struct GNUNET_HashCode *key,
-                 const struct GNUNET_HashCode *vhash,
                  enum GNUNET_BLOCK_Type type,
                  PluginDatumProcessor proc,
                  void *proc_cls);
 
 
 /**
- * Get a random item (additional constraints may apply depending on
- * the specific implementation).  Calls @a proc with all values ZERO or
- * NULL if no item applies, otherwise @a proc is called once and only
- * once with an item.
+ * Remove continuation.
  *
  * @param cls closure
- * @param proc function to call the value (once only).
- * @param proc_cls closure for @a proc
+ * @param key key for the content removed
+ * @param size number of bytes removed
+ * @param status #GNUNET_OK if removed, #GNUNET_NO if not found,
+ *        or #GNUNET_SYSERROR if error
+ * @param msg error message on error
  */
 typedef void
-(*PluginGetRandom) (void *cls,
-                    PluginDatumProcessor proc,
-                    void *proc_cls);
+(*PluginRemoveCont) (void *cls,
+                     const struct GNUNET_HashCode *key,
+                     uint32_t size,
+                     int status,
+                     const char *msg);
 
 
 /**
- * Update continuation.
+ * Remove a particular key in the datastore.
  *
  * @param cls closure
- * @param status #GNUNET_OK or #GNUNET_SYSERR
- * @param msg error message on error
+ * @param key key for the content
+ * @param size number of bytes in data
+ * @param data content stored
+ * @param cont continuation called with success or failure status
+ * @param cont_cls continuation closure for @a cont
  */
 typedef void
-(*PluginUpdateCont) (void *cls,
-                     int status,
-                     const char *msg);
+(*PluginRemoveKey) (void *cls,
+                    const struct GNUNET_HashCode *key,
+                    uint32_t size,
+                    const void *data,
+                    PluginRemoveCont cont,
+                    void *cont_cls);
 
 
 /**
- * Update the priority, replication and expiration for a particular
- * unique ID in the datastore.  If the expiration time in value is
- * different than the time found in the datastore, the higher value
- * should be kept.  The specified priority and replication is added
- * to the existing value.
+ * Get a random item (additional constraints may apply depending on
+ * the specific implementation).  Calls @a proc with all values ZERO or
+ * NULL if no item applies, otherwise @a proc is called once and only
+ * once with an item.
  *
  * @param cls closure
- * @param uid unique identifier of the datum
- * @param priority by how much should the priority
- *     change?
- * @param replication by how much should the replication
- *     change?
- * @param expire new expiration time should be the
- *     MAX of any existing expiration time and
- *     this value
- * @param cont continuation called with success or failure status
- * @param cons_cls continuation closure
+ * @param proc function to call the value (once only).
+ * @param proc_cls closure for @a proc
  */
 typedef void
-(*PluginUpdate) (void *cls,
-                 uint64_t uid,
-                 uint32_t priority,
-                 uint32_t replication,
-                 struct GNUNET_TIME_Absolute expire,
-                 PluginUpdateCont cont,
-                 void *cont_cls);
+(*PluginGetRandom) (void *cls,
+                    PluginDatumProcessor proc,
+                    void *proc_cls);
 
 
 /**
@@ -342,16 +334,6 @@ struct GNUNET_DATASTORE_PluginFunctions
   PluginPut put;
 
   /**
-   * Update the priority for a particular key in the datastore.  If
-   * the expiration time in value is different than the time found in
-   * the datastore, the higher value should be kept.  For the
-   * anonymity level, the lower value is to be used.  The specified
-   * priority should be added to the existing priority, ignoring the
-   * priority in value.
-   */
-  PluginUpdate update;
-
-  /**
    * Get a particular datum matching a given hash from the datastore.
    */
   PluginGetKey get_key;
@@ -388,6 +370,10 @@ struct GNUNET_DATASTORE_PluginFunctions
    */
   PluginGetKeys get_keys;
 
+  /**
+   * Function to remove an item from the database.
+   */
+  PluginRemoveKey remove_key;
 };
 
 #endif
diff --git a/src/include/gnunet_json_lib.h b/src/include/gnunet_json_lib.h
index ce721d8d8..f2682bea7 100644
--- a/src/include/gnunet_json_lib.h
+++ b/src/include/gnunet_json_lib.h
@@ -263,6 +263,17 @@ GNUNET_JSON_spec_absolute_time (const char *name,
 
 
 /**
+ * Absolute time in network byte order.
+ *
+ * @param name name of the JSON field
+ * @param[out] at where to store the absolute time found under @a name
+ */
+struct GNUNET_JSON_Specification
+GNUNET_JSON_spec_absolute_time_nbo (const char *name,
+                                    struct GNUNET_TIME_AbsoluteNBO *at);
+
+
+/**
  * Relative time.
  *
  * @param name name of the JSON field
diff --git a/src/json/json_helper.c b/src/json/json_helper.c
index dca2106aa..194ec5c76 100644
--- a/src/json/json_helper.c
+++ b/src/json/json_helper.c
@@ -610,6 +610,83 @@ GNUNET_JSON_spec_absolute_time (const char *name,
 
 
 /**
+ * Parse given JSON object to absolute time.
+ *
+ * @param cls closure, NULL
+ * @param root the json object representing data
+ * @param[out] spec where to write the data
+ * @return #GNUNET_OK upon successful parsing; #GNUNET_SYSERR upon error
+ */
+static int
+parse_abs_time_nbo (void *cls,
+                    json_t *root,
+                    struct GNUNET_JSON_Specification *spec)
+{
+  struct GNUNET_TIME_AbsoluteNBO *abs = spec->ptr;
+  const char *val;
+  unsigned long long int tval;
+  struct GNUNET_TIME_Absolute a;
+
+  val = json_string_value (root);
+  if (NULL == val)
+  {
+    GNUNET_break_op (0);
+    return GNUNET_SYSERR;
+  }
+  if ( (0 == strcasecmp (val,
+                         "/forever/")) ||
+       (0 == strcasecmp (val,
+                         "/end of time/")) ||
+       (0 == strcasecmp (val,
+                         "/never/")) )
+  {
+    *abs = GNUNET_TIME_absolute_hton (GNUNET_TIME_UNIT_FOREVER_ABS);
+    return GNUNET_OK;
+  }
+  if (1 != sscanf (val,
+                   "/Date(%llu)/",
+                   &tval))
+  {
+    GNUNET_break_op (0);
+    return GNUNET_SYSERR;
+  }
+  /* Time is in seconds in JSON, but in microseconds in GNUNET_TIME_Absolute */
+  a.abs_value_us = tval * 1000LL * 1000LL;
+  if ( (a.abs_value_us) / 1000LL / 1000LL != tval)
+  {
+    /* Integer overflow */
+    GNUNET_break_op (0);
+    return GNUNET_SYSERR;
+  }
+  *abs = GNUNET_TIME_absolute_hton (a);
+  return GNUNET_OK;
+}
+
+
+/**
+ * Absolute time in network byte order.
+ *
+ * @param name name of the JSON field
+ * @param[out] at where to store the absolute time found under @a name
+ */
+struct GNUNET_JSON_Specification
+GNUNET_JSON_spec_absolute_time_nbo (const char *name,
+                                    struct GNUNET_TIME_AbsoluteNBO *at)
+{
+  struct GNUNET_JSON_Specification ret = {
+    .parser = &parse_abs_time_nbo,
+    .cleaner = NULL,
+    .cls = NULL,
+    .field = name,
+    .ptr = at,
+    .ptr_size = sizeof (uint64_t),
+    .size_ptr = NULL
+  };
+  return ret;
+}
+
+
+/**
  * Parse given JSON object to relative time.
  *
  * @param cls closure, NULL