A computer-based system and method for verifying integrity of data in a key-value database, including assigning each key that is supported by the key-value database to a bucket in a keys database. Upon storing a pair of a value and a key in the key-value database, storing in the bucket assigned to the key a presence indicator indicative of a presence of the key in the key-value database. A bucket is assigned to a key by applying a predetermined function on the key. When reading a value from the key-value database, if the response is empty: getting from the keys database the bucket associated with the key and searching the bucket for the presence indicator associated with the key. If the presence indicator associated with the key is found in the bucket determining that the key-value database is not complete.