Repository: etcd-io/etcd (language: go)

Issue:
etcdutl Snapshot Status: TotalKey Calculation Inquiry

### Discussed in https://github.com/etcd-io/etcd/discussions/19012

<div type='discussions-op-text'>

<sup>Originally posted by **jxustc** December  5, 2024</sup>
## Problem Description
When using the `etcdutl snapshot status` command, I've observed the following characteristics of TotalKey calculation:
- Current implementation counts keys across all buckets in the bbolt database
- Includes keys beyond visible etcd key-value data
- Key counts in other buckets may vary with different etcd versions

## Case
<img width="978" alt="image" src="https://github.com/user-attachments/assets/dd2093de-1357-476a-87b0-a3d5de2ed21d">

![image](https://github.com/user-attachments/assets/7878cd3a-28ec-4fbf-b586-033beb4d0d3a)


During  testing, I discovered that the TotalKey calculation includes keys from various internal buckets beyond the main key-value store:
### Identified Included Keys
- In `meta` bucket:
  - `term`
  - `scheduledCompactRev`
  - `confState`
  - ...
- In `auth` bucket:
  - `authRevision`
- Keys from other internal buckets


## Specific Questions
1. What is the precise definition of TotalKey?
2. Is the current calculation method appropriate?
3. Should the count be limited to etcd key-value entries?

## Potential Implementation Approach

```golang
func (s *v3Manager) Status(dbPath string) (ds Status, err error) {
	...
	if err = db.View(func(tx *bolt.Tx) error {
		...
		c := tx.Cursor()
		for next, _ := c.First(); next != nil; next, _ = c.Next() {
			b := tx.Bucket(next)
			if b == nil {
				return fmt.Errorf("nil bucket: %q", string(next))
			}
			_, err = h.Write(next)
			if err != nil {
				return fmt.Errorf("cannot hash bucket name: %q err: %w", string(next), err)
			}

			iskeyb := (bytes.Equal(next, schema.Key.Name()))
			if err = b.ForEach(func(k, v []byte) error {
				_, err = h.Write(k)
				if err != nil {
					return fmt.Errorf("cannot hash bucket key: %q err: %w", k, err)
				}
				_, err = h.Write(v)
				if err != nil {
					return fmt.Errorf("cannot hash bucket key: %q value: %q err: %w", k, v, err)
				}
				if iskeyb {
					var rev mvcc.Revision
					rev, err = bytesToRev(k)
					if err != nil {
						return fmt.Errorf("cannot parse revision key: %q err: %w", k, err)
					}
					ds.Revision = rev.Main

					var kv mvccpb.KeyValue
					err = kv.Unmarshal(v)
					if err != nil {
						return fmt.Errorf("cannot unmarshal value, key: %q value: %q err: %w", k, v, err)
					}
                                         // move to here 
                                         ds.TotalKey++
				}
                                 // remove 
				ds.TotalKey++
				return nil
			}); err != nil {
				return fmt.Errorf("error during bucket key iteration, name: %q err: %w", string(next), err)
			}
		}
		return nil
	}); err != nil {
		return ds, err
	}
...
}
```

**Besides this solution, could we possibly add a field to count the number of non-built-in key-value pairs in etcd?**

## Proposed Improvement

If appropriate, I am willing to submit a PR to implement this change. </div>


Discussion / hints:
Expect there is misaligment between definition of `bbolt` key and `etcd` key. As you mentioned it includes meta keys like `scheduledCompactRev` used for internal etcd purpose. I think it makes sense for etcd snapshot command to return keys in the etcd database, excluding the metadata keys. cc @ahrtr 
> I think it makes sense for etcd snapshot command to return keys in the etcd database, excluding the metadata keys. cc [@ahrtr](https://github.com/ahrtr)

YES, I agree. But unfortunately, it would be a breaking change as it has already been included in 3.5 for a long time. But I won't against to make a breaking change in 3.7 if there is no strong objection from users & contributors.

A better way is to run `./bbolt inspect` to get the number of keys in each bucket,
```
$ ./bbolt inspect ../etcd/default.etcd/member/snap/db 
{
    "name": "root",
    "keyN": 0,
    "buckets": [
        {
            "name": "alarm",
            "keyN": 0
        },
        {
            "name": "auth",
            "keyN": 1
        },
        {
            "name": "authRoles",
            "keyN": 0
        },
        {
            "name": "authUsers",
            "keyN": 0
        },
        {
            "name": "cluster",
            "keyN": 1
        },
        {
            "name": "key",
            "keyN": 2
        },
        {
            "name": "lease",
            "keyN": 0
        },
        {
            "name": "members",
            "keyN": 1
        },
        {
            "name": "members_removed",
            "keyN": 0
        },
        {
            "name": "meta",
            "keyN": 4
        }
    ]
}

$ ./bin/etcdutl snapshot status ./default.etcd/member/snap/db 
663fd1f5, 3, 9, 98 kB, 3.6.0
F5WPP69Q7H:etcd wachao$ ./bin/etcdutl snapshot status ./default.etcd/member/snap/db  -w table
+----------+----------+------------+------------+---------+
|   HASH   | REVISION | TOTAL KEYS | TOTAL SIZE | VERSION |
+----------+----------+------------+------------+---------+
| 663fd1f5 |        3 |          9 |      98 kB |   3.6.0 |
+----------+----------+------------+------------+---------+

```
> But unfortunately, it would be a breaking change as it has already been included in 3.5 for a long time

Could you clarify what you mean by breaking change? How you expect users depend on the value? 

For me this is fix in metric value to be more accurate. There are no changes in structure, name or format of the metric that could impact how user interacts with it. 
In theory, users may 
- parse the json output
- or call `(*v3Manager) Status` directly.

Changing the value may break users's expectation.

In practice, I am not sure how many users use/depend on it, might not too many.

Overall, I am not against make this breaking change.
To be clearer, I agree that there is no format/struct change. 

I was saying changing the value is also a breaking change. For example, starting a brand new etcd instance, the default number of key is always 7 even there is no any key/value write. Now we are going to change it to 0. We don't know how it may affect user's test or any expectation.

Again, overall, I am not against to make it more accurate.
Thank you all for the discussion. If there are no objections, I'd like to submit a PR to the main branch to fix this issue by excluding built-in keys from the TotalKey calculation (without modifying any formatting or structural changes).

This change would provide more accurate metrics for monitoring and debugging purposes, better aligning with users' expectations.

Please let me know if there are any additional considerations I should be aware of.
Please note that internally etcd uses the revision as the key, but I think we should count the number of the real keys from users perspective.

For example, when you execute the same command `./bin/etcdctl put k1 v1` three times, from bbolt perspective, there are three keys in the `key` bucket. But from users perspective, there is only one key. We should output 1 instead of 3 in this example,

```
$ ./bbolt inspect ../etcd/default.etcd/member/snap/db 
{
    "name": "root",
    "keyN": 0,
    "buckets": [
        {
            "name": "alarm",
            "keyN": 0
        },
        {
            "name": "auth",
            "keyN": 1
        },
        {
            "name": "authRoles",
            "keyN": 0
        },
        {
            "name": "authUsers",
            "keyN": 0
        },
        {
            "name": "cluster",
            "keyN": 1
        },
        {
            "name": "key",
            "keyN": 3
        },
        {
            "name": "lease",
            "keyN": 0
        },
        {
            "name": "members",
            "keyN": 1
        },
        {
            "name": "members_removed",
            "keyN": 0
        },
        {
            "name": "meta",
            "keyN": 4
        }
    ]
}
```

Fix patch:
diff --git a/etcdutl/snapshot/v3_snapshot.go b/etcdutl/snapshot/v3_snapshot.go
index 3d17dcbae51..81dde9a0d0e 100644
--- a/etcdutl/snapshot/v3_snapshot.go
+++ b/etcdutl/snapshot/v3_snapshot.go
@@ -126,6 +126,7 @@ func (s *v3Manager) Status(dbPath string) (ds Status, err error) {
 	defer db.Close()
 
 	h := crc32.New(crc32.MakeTable(crc32.Castagnoli))
+	seenKeys := make(map[string]struct{})
 
 	if err = db.View(func(tx *bolt.Tx) error {
 		// check snapshot file integrity first
@@ -175,8 +176,14 @@ func (s *v3Manager) Status(dbPath string) (ds Status, err error) {
 					if err != nil {
 						return fmt.Errorf("cannot unmarshal value, key: %q value: %q err: %w", k, v, err)
 					}
+					key := string(kv.Key)
+					// refer to https://etcd.io/docs/v3.5/learning/data_model/
+					if !mvcc.IsTombstone(k) {
+						seenKeys[key] = struct{}{}
+					} else {
+						delete(seenKeys, key)
+					}
 				}
-				ds.TotalKey++
 				return nil
 			}); err != nil {
 				return fmt.Errorf("error during bucket key iteration, name: %q err: %w", string(next), err)
@@ -187,6 +194,7 @@ func (s *v3Manager) Status(dbPath string) (ds Status, err error) {
 		return ds, err
 	}
 
+	ds.TotalKey = len(seenKeys)
 	ds.Hash = h.Sum32()
 	return ds, nil
 }
diff --git a/server/storage/mvcc/revision.go b/server/storage/mvcc/revision.go
index db44da29343..7d1addf2647 100644
--- a/server/storage/mvcc/revision.go
+++ b/server/storage/mvcc/revision.go
@@ -120,3 +120,7 @@ func BytesToBucketKey(bytes []byte) BucketKey {
 func isTombstone(b []byte) bool {
 	return len(b) == markedRevBytesLen && b[markBytePosition] == markTombstone
 }
+
+func IsTombstone(b []byte) bool {
+	return isTombstone(b)
+}


Test patch:
diff --git a/etcdutl/snapshot/v3_snapshot_test.go b/etcdutl/snapshot/v3_snapshot_test.go
index 426b17a3927..1971eefe2fc 100644
--- a/etcdutl/snapshot/v3_snapshot_test.go
+++ b/etcdutl/snapshot/v3_snapshot_test.go
@@ -118,6 +118,106 @@ func TestSnapshotStatusNegativeRevisionSub(t *testing.T) {
 	require.ErrorContains(t, err, "negative revision")
 }
 
+// TestSnapshotStatusTotalKey tests if snapshot status command correctly reports total number of valid keys.
+func TestSnapshotStatusTotalKey(t *testing.T) {
+	cases := []struct {
+		name     string
+		prepare  func(srv *etcdserver.EtcdServer)
+		expected int
+	}{
+		{
+			name: "duplicate keys",
+			prepare: func(srv *etcdserver.EtcdServer) {
+				keys := []string{"key1", "key2", "key1"}
+				val := make([]byte, len(keys))
+				for _, key := range keys {
+					for i := 0; i < 3; i++ {
+						req := etcdserverpb.PutRequest{
+							Key:   []byte(key),
+							Value: val,
+						}
+						_, err := srv.Put(context.TODO(), &req)
+						require.NoError(t, err)
+					}
+				}
+			},
+			expected: 2,
+		},
+		{
+			name: "mixed revisions",
+			prepare: func(srv *etcdserver.EtcdServer) {
+				// key1: create -> put -> delete
+				key := []byte("key1")
+				for i := 0; i < 3; i++ {
+					if i < 2 {
+						_, err := srv.Put(context.TODO(), &etcdserverpb.PutRequest{Key: key, Value: []byte(strconv.Itoa(i))})
+						require.NoError(t, err)
+					} else {
+						_, err := srv.DeleteRange(context.TODO(), &etcdserverpb.DeleteRangeRequest{Key: key})
+						require.NoError(t, err)
+					}
+				}
+			},
+			expected: 0,
+		},
+		{
+			name: "ignored tombstones",
+			prepare: func(srv *etcdserver.EtcdServer) {
+				// key1: create -> delete -> re-create -> delete
+				key := []byte("key1")
+				for i := 0; i < 2; i++ {
+					_, err := srv.Put(context.TODO(), &etcdserverpb.PutRequest{Key: key, Value: make([]byte, 1)})
+					require.NoError(t, err)
+					_, err = srv.DeleteRange(context.TODO(), &etcdserverpb.DeleteRangeRequest{Key: key})
+					require.NoError(t, err)
+				}
+			},
+			expected: 0,
+		},
+		{
+			name: "restored keys",
+			prepare: func(srv *etcdserver.EtcdServer) {
+				// key1: create -> delete -> re-create -> delete -> re-create
+				key := []byte("key1")
+				for i := 0; i < 5; i++ {
+					if i%2 == 0 {
+						_, err := srv.Put(context.TODO(), &etcdserverpb.PutRequest{Key: key, Value: make([]byte, 1)})
+						require.NoError(t, err)
+					} else {
+						_, err := srv.DeleteRange(context.TODO(), &etcdserverpb.DeleteRangeRequest{Key: key})
+						require.NoError(t, err)
+					}
+				}
+			},
+			expected: 1,
+		},
+		{
+			name: "mixed deletions",
+			prepare: func(srv *etcdserver.EtcdServer) {
+				// Put("key1") -> Put("key2")-> Delete("key1")
+				_, err := srv.Put(context.TODO(), &etcdserverpb.PutRequest{Key: []byte("key1"), Value: make([]byte, 1)})
+				require.NoError(t, err)
+				_, err = srv.Put(context.TODO(), &etcdserverpb.PutRequest{Key: []byte("key2"), Value: make([]byte, 1)})
+				require.NoError(t, err)
+				_, err = srv.DeleteRange(context.TODO(), &etcdserverpb.DeleteRangeRequest{Key: []byte("key1")})
+				require.NoError(t, err)
+			},
+			expected: 1,
+		},
+	}
+
+	for _, tc := range cases {
+		t.Run(tc.name, func(t *testing.T) {
+			dbpath := createDB(t, tc.prepare)
+
+			status, err := NewV3(zap.NewNop()).Status(dbpath)
+			require.NoError(t, err)
+
+			assert.Equal(t, tc.expected, status.TotalKey)
+		})
+	}
+}
+
 // insertKeys insert `numKeys` number of keys of `valueSize` size into a running etcd server.
 func insertKeys(t *testing.T, numKeys, valueSize int) func(*etcdserver.EtcdServer) {
 	t.Helper()
diff --git a/tests/e2e/ctl_v3_auth_test.go b/tests/e2e/ctl_v3_auth_test.go
index 40a879f1e9f..7391e647a85 100644
--- a/tests/e2e/ctl_v3_auth_test.go
+++ b/tests/e2e/ctl_v3_auth_test.go
@@ -279,8 +279,8 @@ func authTestSnapshot(cx ctlCtx) {
 	if st.Revision != 4 {
 		cx.t.Fatalf("expected 4, got %d", st.Revision)
 	}
-	if st.TotalKey < 3 {
-		cx.t.Fatalf("expected at least 3, got %d", st.TotalKey)
+	if st.TotalKey < 1 {
+		cx.t.Fatalf("expected at least 1, got %d", st.TotalKey)
 	}
 }
 
diff --git a/tests/e2e/ctl_v3_snapshot_test.go b/tests/e2e/ctl_v3_snapshot_test.go
index 5f145abab2c..c9dc03235d1 100644
--- a/tests/e2e/ctl_v3_snapshot_test.go
+++ b/tests/e2e/ctl_v3_snapshot_test.go
@@ -65,8 +65,8 @@ func snapshotTest(cx ctlCtx) {
 	if st.Revision != 5 {
 		cx.t.Fatalf("expected 4, got %d", st.Revision)
 	}
-	if st.TotalKey < 4 {
-		cx.t.Fatalf("expected at least 4, got %d", st.TotalKey)
+	if st.TotalKey < 2 {
+		cx.t.Fatalf("expected at least 2, got %d", st.TotalKey)
 	}
 }