You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@kvrocks.apache.org by "jonathanc-n (via GitHub)" <gi...@apache.org> on 2024/09/07 02:56:21 UTC
[PR] feat: support count min sketch data structure and most commands [kvrocks]
jonathanc-n opened a new pull request, #2524:
URL: https://github.com/apache/kvrocks/pull/2524
references issue: #2425
The commands, IncrBy, Info, InitByDim, InitByProb, and Query have been made.
The merge command will still need working on, and go integration tests will be added for the future. I will also probably add a cache similar to the hyperloglog for in-memory operations.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@kvrocks.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat: support count min sketch data structure and most commands [kvrocks]
Posted by "mapleFU (via GitHub)" <gi...@apache.org>.
mapleFU commented on code in PR #2524:
URL: https://github.com/apache/kvrocks/pull/2524#discussion_r1770520260
##########
tests/gocase/unit/cms/cms_test.go:
##########
@@ -0,0 +1,245 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package cms
+
+import (
+ "context"
+ "fmt"
+ "strconv"
+ "testing"
+
+ "github.com/apache/kvrocks/tests/gocase/util"
+ "github.com/stretchr/testify/require"
+)
+
+func TestCountMinSketch(t *testing.T) {
+ // Define configuration options if needed.
+ // Adjust or add more configurations as per your CMS requirements.
+ configOptions := []util.ConfigOptions{
+ {
+ Name: "txn-context-enabled",
+ Options: []string{"yes", "no"},
+ ConfigType: util.YesNo,
+ },
+ // Add more configuration options here if necessary
+ }
+
+ // Generate all combinations of configurations
+ configsMatrix, err := util.GenerateConfigsMatrix(configOptions)
+ require.NoError(t, err)
+
+ // Iterate over each configuration and run CMS tests
+ for _, configs := range configsMatrix {
+ testCMS(t, configs)
+ }
+}
+
+// testCMS sets up the server with the given configurations and runs CMS tests
+func testCMS(t *testing.T, configs util.KvrocksServerConfigs) {
+ srv := util.StartServer(t, configs)
+ defer srv.Close()
+
+ ctx := context.Background()
+ rdb := srv.NewClient()
+ defer func() { require.NoError(t, rdb.Close()) }()
+
+ // Run individual CMS test cases
+ t.Run("basic add", func(t *testing.T) {
+ require.NoError(t, rdb.Do(ctx, "DEL", "cmsA").Err())
+
+ res := rdb.Do(ctx, "cms.initbydim", "cmsA", 100, 10)
+ require.NoError(t, res.Err())
+ require.Equal(t, "OK", res.Val())
+
+ require.Equal(t, []interface{}{"width", int64(100), "depth", int64(10), "count", int64(0)}, rdb.Do(ctx, "cms.info", "cmsA").Val())
+
+ res = rdb.Do(ctx, "cms.incrby", "cmsA", "foo", 1)
+ require.NoError(t, res.Err())
+ addCnt, err := res.Result()
+
+ require.NoError(t, err)
+ require.Equal(t, string("OK"), addCnt)
+
+ card, err := rdb.Do(ctx, "cms.query", "cmsA", "foo").Result()
+ require.NoError(t, err)
+ require.Equal(t, []interface{}([]interface{}{"1"}), card, "The queried count for 'foo' should be 1")
+ })
+
+ t.Run("cms.initbyprob - Initialization with Probability Parameters", func(t *testing.T) {
+ require.NoError(t, rdb.Do(ctx, "DEL", "cmsB").Err())
+
+ res := rdb.Do(ctx, "cms.initbyprob", "cmsB", "0.001", "0.1")
+ require.NoError(t, res.Err())
+ require.Equal(t, "OK", res.Val())
+
+ infoRes := rdb.Do(ctx, "cms.info", "cmsB")
+ require.NoError(t, infoRes.Err())
+ infoSlice, ok := infoRes.Val().([]interface{})
+ require.True(t, ok, "Expected cms.info to return a slice")
+
+ infoMap := make(map[string]interface{})
+ for i := 0; i < len(infoSlice); i += 2 {
+ key, ok1 := infoSlice[i].(string)
+ value, ok2 := infoSlice[i+1].(int64)
+ require.True(t, ok1 && ok2, "Expected cms.info keys to be strings and values to be int64")
+ infoMap[key] = value
+ }
+
+ require.Equal(t, int64(2000), infoMap["width"])
+ require.Equal(t, int64(4), infoMap["depth"])
+ require.Equal(t, int64(0), infoMap["count"])
+ })
+
+ t.Run("cms.incrby - Basic Increment Operations", func(t *testing.T) {
+ require.NoError(t, rdb.Do(ctx, "DEL", "cmsA").Err())
+ res := rdb.Do(ctx, "cms.initbydim", "cmsA", "100", "10")
+ require.NoError(t, res.Err())
+ require.Equal(t, "OK", res.Val())
+
+ elements := map[string]string{"apple": "7", "orange": "15", "mango": "3"}
+ for key, count := range elements {
+ res = rdb.Do(ctx, "cms.incrby", "cmsA", key, count)
+ require.NoError(t, res.Err())
+ require.Equal(t, "OK", res.Val())
+ }
+
+ for key, expected := range elements {
+ res = rdb.Do(ctx, "cms.query", "cmsA", key)
+ require.NoError(t, res.Err())
+ countSlice, ok := res.Val().([]interface{})
+ require.True(t, ok, "Expected cms.query to return a slice")
+ require.Len(t, countSlice, 1, "Expected cms.query to return a single count")
+ count, ok := countSlice[0].(string)
+ require.True(t, ok, "Expected count to be a string")
+ require.Equal(t, expected, count, fmt.Sprintf("Count for key '%s' mismatch", key))
+ }
+
+ // Verify total count
+ infoRes := rdb.Do(ctx, "cms.info", "cmsA")
+ require.NoError(t, infoRes.Err())
+ infoSlice, ok := infoRes.Val().([]interface{})
+ require.True(t, ok, "Expected cms.info to return a slice")
+
+ // Convert the slice to a map for easier access
+ infoMap := make(map[string]interface{})
+ for i := 0; i < len(infoSlice); i += 2 {
+ key, ok1 := infoSlice[i].(string)
+ value, ok2 := infoSlice[i+1].(int64)
+ require.True(t, ok1 && ok2, "Expected cms.info keys to be strings and values to be int64")
+ infoMap[key] = value
+ }
+
+ total := int64(0)
+ for _, cntStr := range elements {
+ cnt, err := strconv.ParseInt(cntStr, 10, 64)
+ require.NoError(t, err, "Failed to parse count string to int64")
+ total += cnt
+ }
+ require.Equal(t, total, infoMap["count"], "Total count mismatch")
+ })
+
+ // Increment operation on a non-existent CMS
+ t.Run("cms.incrby - Increment Non-Existent CMS", func(t *testing.T) {
+ res := rdb.Do(ctx, "cms.incrby", "nonexistent_cms", "apple", "5")
+ require.Error(t, res.Err())
+ })
+
+ // Query for non-existent element
+ t.Run("cms.query - Query Non-Existent Element", func(t *testing.T) {
+ require.NoError(t, rdb.Do(ctx, "DEL", "cmsA").Err())
+ res := rdb.Do(ctx, "cms.initbydim", "cmsA", "100", "10")
+ require.NoError(t, res.Err())
+ require.Equal(t, "OK", res.Val())
+
+ // Query a non-existent element
+ res = rdb.Do(ctx, "cms.query", "cmsA", "nonexistent")
+ require.NoError(t, res.Err())
+ countSlice, ok := res.Val().([]interface{})
+ require.True(t, ok, "Expected cms.query to return a slice")
+ require.Len(t, countSlice, 1, "Expected cms.query to return a single count")
+ count, ok := countSlice[0].(string)
+ require.True(t, ok, "Expected count to be a string")
+ require.Equal(t, "0", count, "Non-existent element should return count '0'")
+ })
+
+ // Merging CMS structures
Review Comment:
Can we also merge on unexists key? Includling uninitialized dest or sources
##########
tests/gocase/unit/cms/cms_test.go:
##########
@@ -0,0 +1,245 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package cms
+
+import (
+ "context"
+ "fmt"
+ "strconv"
+ "testing"
+
+ "github.com/apache/kvrocks/tests/gocase/util"
+ "github.com/stretchr/testify/require"
+)
+
+func TestCountMinSketch(t *testing.T) {
+ // Define configuration options if needed.
+ // Adjust or add more configurations as per your CMS requirements.
+ configOptions := []util.ConfigOptions{
+ {
+ Name: "txn-context-enabled",
+ Options: []string{"yes", "no"},
+ ConfigType: util.YesNo,
+ },
+ // Add more configuration options here if necessary
+ }
+
+ // Generate all combinations of configurations
+ configsMatrix, err := util.GenerateConfigsMatrix(configOptions)
+ require.NoError(t, err)
+
+ // Iterate over each configuration and run CMS tests
+ for _, configs := range configsMatrix {
+ testCMS(t, configs)
+ }
+}
+
+// testCMS sets up the server with the given configurations and runs CMS tests
+func testCMS(t *testing.T, configs util.KvrocksServerConfigs) {
+ srv := util.StartServer(t, configs)
+ defer srv.Close()
+
+ ctx := context.Background()
+ rdb := srv.NewClient()
+ defer func() { require.NoError(t, rdb.Close()) }()
+
+ // Run individual CMS test cases
+ t.Run("basic add", func(t *testing.T) {
+ require.NoError(t, rdb.Do(ctx, "DEL", "cmsA").Err())
+
+ res := rdb.Do(ctx, "cms.initbydim", "cmsA", 100, 10)
+ require.NoError(t, res.Err())
+ require.Equal(t, "OK", res.Val())
+
+ require.Equal(t, []interface{}{"width", int64(100), "depth", int64(10), "count", int64(0)}, rdb.Do(ctx, "cms.info", "cmsA").Val())
+
+ res = rdb.Do(ctx, "cms.incrby", "cmsA", "foo", 1)
+ require.NoError(t, res.Err())
+ addCnt, err := res.Result()
+
+ require.NoError(t, err)
+ require.Equal(t, string("OK"), addCnt)
+
+ card, err := rdb.Do(ctx, "cms.query", "cmsA", "foo").Result()
+ require.NoError(t, err)
+ require.Equal(t, []interface{}([]interface{}{"1"}), card, "The queried count for 'foo' should be 1")
+ })
+
+ t.Run("cms.initbyprob - Initialization with Probability Parameters", func(t *testing.T) {
+ require.NoError(t, rdb.Do(ctx, "DEL", "cmsB").Err())
+
+ res := rdb.Do(ctx, "cms.initbyprob", "cmsB", "0.001", "0.1")
+ require.NoError(t, res.Err())
+ require.Equal(t, "OK", res.Val())
+
+ infoRes := rdb.Do(ctx, "cms.info", "cmsB")
+ require.NoError(t, infoRes.Err())
+ infoSlice, ok := infoRes.Val().([]interface{})
+ require.True(t, ok, "Expected cms.info to return a slice")
+
+ infoMap := make(map[string]interface{})
+ for i := 0; i < len(infoSlice); i += 2 {
+ key, ok1 := infoSlice[i].(string)
+ value, ok2 := infoSlice[i+1].(int64)
+ require.True(t, ok1 && ok2, "Expected cms.info keys to be strings and values to be int64")
+ infoMap[key] = value
+ }
+
+ require.Equal(t, int64(2000), infoMap["width"])
+ require.Equal(t, int64(4), infoMap["depth"])
+ require.Equal(t, int64(0), infoMap["count"])
+ })
+
+ t.Run("cms.incrby - Basic Increment Operations", func(t *testing.T) {
+ require.NoError(t, rdb.Do(ctx, "DEL", "cmsA").Err())
+ res := rdb.Do(ctx, "cms.initbydim", "cmsA", "100", "10")
+ require.NoError(t, res.Err())
+ require.Equal(t, "OK", res.Val())
+
+ elements := map[string]string{"apple": "7", "orange": "15", "mango": "3"}
+ for key, count := range elements {
+ res = rdb.Do(ctx, "cms.incrby", "cmsA", key, count)
+ require.NoError(t, res.Err())
+ require.Equal(t, "OK", res.Val())
+ }
+
+ for key, expected := range elements {
+ res = rdb.Do(ctx, "cms.query", "cmsA", key)
+ require.NoError(t, res.Err())
+ countSlice, ok := res.Val().([]interface{})
+ require.True(t, ok, "Expected cms.query to return a slice")
+ require.Len(t, countSlice, 1, "Expected cms.query to return a single count")
+ count, ok := countSlice[0].(string)
+ require.True(t, ok, "Expected count to be a string")
+ require.Equal(t, expected, count, fmt.Sprintf("Count for key '%s' mismatch", key))
+ }
+
+ // Verify total count
+ infoRes := rdb.Do(ctx, "cms.info", "cmsA")
+ require.NoError(t, infoRes.Err())
+ infoSlice, ok := infoRes.Val().([]interface{})
+ require.True(t, ok, "Expected cms.info to return a slice")
+
+ // Convert the slice to a map for easier access
+ infoMap := make(map[string]interface{})
+ for i := 0; i < len(infoSlice); i += 2 {
+ key, ok1 := infoSlice[i].(string)
+ value, ok2 := infoSlice[i+1].(int64)
+ require.True(t, ok1 && ok2, "Expected cms.info keys to be strings and values to be int64")
+ infoMap[key] = value
+ }
+
+ total := int64(0)
+ for _, cntStr := range elements {
+ cnt, err := strconv.ParseInt(cntStr, 10, 64)
+ require.NoError(t, err, "Failed to parse count string to int64")
+ total += cnt
+ }
+ require.Equal(t, total, infoMap["count"], "Total count mismatch")
+ })
+
+ // Increment operation on a non-existent CMS
+ t.Run("cms.incrby - Increment Non-Existent CMS", func(t *testing.T) {
+ res := rdb.Do(ctx, "cms.incrby", "nonexistent_cms", "apple", "5")
+ require.Error(t, res.Err())
+ })
+
+ // Query for non-existent element
+ t.Run("cms.query - Query Non-Existent Element", func(t *testing.T) {
+ require.NoError(t, rdb.Do(ctx, "DEL", "cmsA").Err())
+ res := rdb.Do(ctx, "cms.initbydim", "cmsA", "100", "10")
+ require.NoError(t, res.Err())
+ require.Equal(t, "OK", res.Val())
Review Comment:
Can we also query a non-exists key like "cms.incrby - Increment Non-Existent CMS"
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@kvrocks.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat: support count min sketch data structure and most commands [kvrocks]
Posted by "jonathanc-n (via GitHub)" <gi...@apache.org>.
jonathanc-n commented on code in PR #2524:
URL: https://github.com/apache/kvrocks/pull/2524#discussion_r1751029749
##########
src/types/redis_cms.cc:
##########
@@ -0,0 +1,167 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#include "redis_cms.h"
+
+#include <stdint.h>
+
+#include "cms.h"
+
+namespace redis {
+
+rocksdb::Status CMS::GetMetadata(engine::Context &ctx, const Slice &ns_key,
+ CountMinSketchMetadata *metadata) {
+ return Database::GetMetadata(ctx, {kRedisCountMinSketch}, ns_key, metadata);
+}
+
+rocksdb::Status CMS::IncrBy(engine::Context &ctx, const Slice &user_key, const std::unordered_map<std::string, uint64_t> &elements) {
+ std::string ns_key = AppendNamespacePrefix(user_key);
+
+ LockGuard guard(storage_->GetLockManager(), ns_key);
+ CountMinSketchMetadata metadata{};
Review Comment:
Yeah, you would get a 0,0,0 pair
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@kvrocks.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat: support count min sketch data structure and most commands [kvrocks]
Posted by "jonathanc-n (via GitHub)" <gi...@apache.org>.
jonathanc-n commented on PR #2524:
URL: https://github.com/apache/kvrocks/pull/2524#issuecomment-2356397542
@PragmaTwice Would you be able to review this pr?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@kvrocks.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat: support count min sketch data structure and most commands [kvrocks]
Posted by "jonathanc-n (via GitHub)" <gi...@apache.org>.
jonathanc-n commented on code in PR #2524:
URL: https://github.com/apache/kvrocks/pull/2524#discussion_r1747885958
##########
src/types/cms.cc:
##########
@@ -0,0 +1,128 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#include "cms.h"
+
+#include <algorithm>
+#include <cmath>
+#include <cstdint>
+#include <vector>
+
+#include "glog/logging.h"
+
+void CMSketch::CMSDimFromProb(double error, double delta, uint32_t& width, uint32_t& depth) {
+ LOG(INFO) << error << delta;
+ width = std::ceil(2 / error);
+ depth = std::ceil(std::log10(delta) / std::log10(0.5));
+}
+
+size_t CMSketch::IncrBy(const char* item, size_t item_len, size_t value) {
+ size_t min_count = std::numeric_limits<size_t>::max();
+
+ for (size_t i = 0; i < depth_; ++i) {
+ uint32_t hash = HllMurMurHash64A(item, static_cast<int>(item_len), i);
Review Comment:
@mapleFU tyty for the review, i'll be revising it tmr.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@kvrocks.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat: support count min sketch data structure and most commands [kvrocks]
Posted by "jonathanc-n (via GitHub)" <gi...@apache.org>.
jonathanc-n commented on PR #2524:
URL: https://github.com/apache/kvrocks/pull/2524#issuecomment-2335025874
Was there a change to GetOptions recently? After the merge, it seems to be behaving different
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@kvrocks.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat: support count min sketch data structure and most commands [kvrocks]
Posted by "mapleFU (via GitHub)" <gi...@apache.org>.
mapleFU commented on PR #2524:
URL: https://github.com/apache/kvrocks/pull/2524#issuecomment-2335037472
> Was there a change made to GetOptions recently? There seems to be a problem after the merge.
Yes, the operations to db requires an options here.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@kvrocks.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat: support count min sketch data structure and most commands [kvrocks]
Posted by "jonathanc-n (via GitHub)" <gi...@apache.org>.
jonathanc-n commented on code in PR #2524:
URL: https://github.com/apache/kvrocks/pull/2524#discussion_r1750536180
##########
src/commands/cmd_cms.cc:
##########
@@ -0,0 +1,168 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#include <types/cms.h>
+#include <types/redis_cms.h>
+
+#include "commander.h"
+#include "commands/command_parser.h"
+#include "server/redis_reply.h"
+#include "server/server.h"
+
+namespace redis {
+
+/// CMS.INCRBY key item increment [item increment ...]
+class CommandCMSIncrBy final : public Commander {
+ public:
+ Status Execute(Server *srv, Connection *conn, std::string *output) override {
+ if ((args_.size() - 2) % 2 != 0) {
+ return Status::RedisTryAgain;
Review Comment:
should I make this part with a status parse instead of putting it in execute?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@kvrocks.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat: support count min sketch data structure and most commands [kvrocks]
Posted by "jonathanc-n (via GitHub)" <gi...@apache.org>.
jonathanc-n commented on PR #2524:
URL: https://github.com/apache/kvrocks/pull/2524#issuecomment-2350753570
@git-hulk @PragmaTwice I think a workflow can be run again with the changes
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@kvrocks.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat: support count min sketch data structure and most commands [kvrocks]
Posted by "mapleFU (via GitHub)" <gi...@apache.org>.
mapleFU commented on code in PR #2524:
URL: https://github.com/apache/kvrocks/pull/2524#discussion_r1765030678
##########
src/types/cms.h:
##########
@@ -0,0 +1,85 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#pragma once
+
+#include <memory>
+#include <vector>
+
+#include "server/redis_reply.h"
+#include "xxhash.h"
Review Comment:
I didn't see xxhash being used in header...
##########
src/types/cms.cc:
##########
@@ -0,0 +1,128 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#include "cms.h"
+
+#include <algorithm>
+#include <cmath>
+#include <cstdint>
+#include <vector>
+
+CMSketch::CMSketchDimensions CMSketch::CMSDimFromProb(double error, double delta) {
+ CMSketchDimensions dims;
+ dims.width = std::ceil(2 / error);
+ dims.depth = std::ceil(std::log10(delta) / std::log10(0.5));
+ return dims;
+}
+
+size_t CMSketch::IncrBy(std::string_view item, uint32_t value) {
+ size_t min_count = std::numeric_limits<size_t>::max();
+
+ for (size_t i = 0; i < depth_; ++i) {
+ uint64_t hash = XXH32(item.data(), static_cast<int>(item.size()), i);
+ size_t loc = GetLocation(hash, i);
+ if (array_[loc] > UINT32_MAX - value) {
+ array_[loc] = UINT32_MAX;
+ } else {
+ array_[loc] += value;
+ }
+ min_count = std::min(min_count, static_cast<size_t>(array_[loc]));
+ }
+ counter_ += value;
+ return min_count;
+}
+
+size_t CMSketch::Query(std::string_view item) const {
+ size_t min_count = std::numeric_limits<size_t>::max();
+
+ for (size_t i = 0; i < depth_; ++i) {
+ uint64_t hash = XXH32(item.data(), static_cast<int>(item.size()), i);
+ min_count = std::min(min_count, static_cast<size_t>(array_[GetLocation(hash, i)]));
+ }
+ return min_count;
+}
+
+int CMSketch::Merge(CMSketch* dest, size_t quantity, const std::vector<const CMSketch*>& src,
+ const std::vector<long long>& weights) {
+ if (checkOverflow(dest, quantity, src, weights) != 0) {
+ return -1;
+ }
+
+ for (size_t i = 0; i < dest->GetDepth(); ++i) {
+ for (size_t j = 0; j < dest->GetWidth(); ++j) {
+ int64_t item_count = 0;
+ for (size_t k = 0; k < quantity; ++k) {
+ item_count += static_cast<int64_t>(src[k]->array_[(i * dest->GetWidth()) + j]) * weights[k];
+ }
+ dest->GetArray()[(i * dest->GetWidth()) + j] = item_count;
+ }
+ }
+
+ for (size_t i = 0; i < quantity; ++i) {
+ dest->GetCounter() += src[i]->GetCounter() * weights[i];
+ }
+
+ return 0;
+}
+
+int CMSMergeParams(const CMSketch::MergeParams& params) {
+ return CMSketch::Merge(params.dest, params.num_keys, params.cms_array, params.weights);
+}
+
+int CMSketch::checkOverflow(CMSketch* dest, size_t quantity, const std::vector<const CMSketch*>& src,
Review Comment:
Also using `StatusOr` here?
##########
src/types/cms.h:
##########
@@ -0,0 +1,85 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#pragma once
+
+#include <memory>
+#include <vector>
+
+#include "server/redis_reply.h"
+#include "xxhash.h"
+
+class CMSketch {
+ public:
+ explicit CMSketch(uint32_t width, uint32_t depth, uint64_t counter, std::vector<uint32_t> array = {})
Review Comment:
Please not use default argument, which might being misused when we program later
##########
src/types/cms.cc:
##########
@@ -0,0 +1,128 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#include "cms.h"
+
+#include <algorithm>
+#include <cmath>
+#include <cstdint>
+#include <vector>
+
+CMSketch::CMSketchDimensions CMSketch::CMSDimFromProb(double error, double delta) {
+ CMSketchDimensions dims;
+ dims.width = std::ceil(2 / error);
+ dims.depth = std::ceil(std::log10(delta) / std::log10(0.5));
+ return dims;
+}
+
+size_t CMSketch::IncrBy(std::string_view item, uint32_t value) {
+ size_t min_count = std::numeric_limits<size_t>::max();
+
+ for (size_t i = 0; i < depth_; ++i) {
+ uint64_t hash = XXH32(item.data(), static_cast<int>(item.size()), i);
+ size_t loc = GetLocation(hash, i);
+ if (array_[loc] > UINT32_MAX - value) {
+ array_[loc] = UINT32_MAX;
+ } else {
+ array_[loc] += value;
+ }
+ min_count = std::min(min_count, static_cast<size_t>(array_[loc]));
+ }
+ counter_ += value;
+ return min_count;
+}
+
+size_t CMSketch::Query(std::string_view item) const {
+ size_t min_count = std::numeric_limits<size_t>::max();
+
+ for (size_t i = 0; i < depth_; ++i) {
+ uint64_t hash = XXH32(item.data(), static_cast<int>(item.size()), i);
+ min_count = std::min(min_count, static_cast<size_t>(array_[GetLocation(hash, i)]));
+ }
+ return min_count;
+}
+
+int CMSketch::Merge(CMSketch* dest, size_t quantity, const std::vector<const CMSketch*>& src,
+ const std::vector<long long>& weights) {
+ if (checkOverflow(dest, quantity, src, weights) != 0) {
+ return -1;
+ }
Review Comment:
Should we use `StatusOr<>` rather than `-1` code here?
##########
src/types/cms.cc:
##########
@@ -0,0 +1,128 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#include "cms.h"
+
+#include <algorithm>
+#include <cmath>
+#include <cstdint>
+#include <vector>
+
+CMSketch::CMSketchDimensions CMSketch::CMSDimFromProb(double error, double delta) {
+ CMSketchDimensions dims;
+ dims.width = std::ceil(2 / error);
+ dims.depth = std::ceil(std::log10(delta) / std::log10(0.5));
+ return dims;
+}
+
+size_t CMSketch::IncrBy(std::string_view item, uint32_t value) {
+ size_t min_count = std::numeric_limits<size_t>::max();
+
+ for (size_t i = 0; i < depth_; ++i) {
+ uint64_t hash = XXH32(item.data(), static_cast<int>(item.size()), i);
+ size_t loc = GetLocation(hash, i);
+ if (array_[loc] > UINT32_MAX - value) {
+ array_[loc] = UINT32_MAX;
+ } else {
+ array_[loc] += value;
+ }
+ min_count = std::min(min_count, static_cast<size_t>(array_[loc]));
+ }
+ counter_ += value;
+ return min_count;
+}
+
+size_t CMSketch::Query(std::string_view item) const {
+ size_t min_count = std::numeric_limits<size_t>::max();
+
+ for (size_t i = 0; i < depth_; ++i) {
+ uint64_t hash = XXH32(item.data(), static_cast<int>(item.size()), i);
+ min_count = std::min(min_count, static_cast<size_t>(array_[GetLocation(hash, i)]));
+ }
+ return min_count;
+}
+
+int CMSketch::Merge(CMSketch* dest, size_t quantity, const std::vector<const CMSketch*>& src,
+ const std::vector<long long>& weights) {
+ if (checkOverflow(dest, quantity, src, weights) != 0) {
+ return -1;
+ }
+
+ for (size_t i = 0; i < dest->GetDepth(); ++i) {
+ for (size_t j = 0; j < dest->GetWidth(); ++j) {
+ int64_t item_count = 0;
+ for (size_t k = 0; k < quantity; ++k) {
+ item_count += static_cast<int64_t>(src[k]->array_[(i * dest->GetWidth()) + j]) * weights[k];
Review Comment:
`GetLocation * weights[k]`?
##########
src/types/redis_cms.h:
##########
@@ -0,0 +1,50 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#pragma once
+
+#include "cms.h"
+#include "storage/redis_db.h"
+#include "storage/redis_metadata.h"
+
+namespace redis {
+
+class CMS : public Database {
+ public:
+ explicit CMS(engine::Storage *storage, const std::string &ns) : Database(storage, ns) {}
+
+ rocksdb::Status IncrBy(engine::Context &ctx, const Slice &user_key,
+ const std::unordered_map<std::string, uint64_t> &elements);
+ rocksdb::Status Info(engine::Context &ctx, const Slice &user_key, CMSketch::CMSInfo *ret);
+ rocksdb::Status InitByDim(engine::Context &ctx, const Slice &user_key, uint32_t width, uint32_t depth);
+ rocksdb::Status InitByProb(engine::Context &ctx, const Slice &user_key, double error, double delta);
+ rocksdb::Status Query(engine::Context &ctx, const Slice &user_key, const std::vector<std::string> &elements,
+ std::vector<uint32_t> &counters);
+
+ private:
+ [[nodiscard]] rocksdb::Status GetMetadata(engine::Context &ctx, const Slice &ns_key,
+ CountMinSketchMetadata *metadata);
+
+ // TODO (jonathanc-n)
Review Comment:
```suggestion
// TODO (jonathanc-n)
// [[nodiscard]] rocksdb::Status mergeUserKeys(engine::Context &ctx, const std::vector<Slice> &user_keys,
// std::vector<std::string> *register_segments);
```
Can you do like this?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@kvrocks.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat: support count min sketch data structure and most commands [kvrocks]
Posted by "jonathanc-n (via GitHub)" <gi...@apache.org>.
jonathanc-n commented on code in PR #2524:
URL: https://github.com/apache/kvrocks/pull/2524#discussion_r1767399703
##########
src/types/cms.cc:
##########
@@ -0,0 +1,128 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#include "cms.h"
+
+#include <algorithm>
+#include <cmath>
+#include <cstdint>
+#include <vector>
+
+CMSketch::CMSketchDimensions CMSketch::CMSDimFromProb(double error, double delta) {
+ CMSketchDimensions dims;
+ dims.width = std::ceil(2 / error);
+ dims.depth = std::ceil(std::log10(delta) / std::log10(0.5));
+ return dims;
+}
+
+size_t CMSketch::IncrBy(std::string_view item, uint32_t value) {
+ size_t min_count = std::numeric_limits<size_t>::max();
+
+ for (size_t i = 0; i < depth_; ++i) {
+ uint64_t hash = XXH32(item.data(), static_cast<int>(item.size()), i);
+ size_t loc = GetLocation(hash, i);
+ if (array_[loc] > UINT32_MAX - value) {
+ array_[loc] = UINT32_MAX;
+ } else {
+ array_[loc] += value;
+ }
+ min_count = std::min(min_count, static_cast<size_t>(array_[loc]));
+ }
+ counter_ += value;
+ return min_count;
+}
+
+size_t CMSketch::Query(std::string_view item) const {
+ size_t min_count = std::numeric_limits<size_t>::max();
+
+ for (size_t i = 0; i < depth_; ++i) {
+ uint64_t hash = XXH32(item.data(), static_cast<int>(item.size()), i);
+ min_count = std::min(min_count, static_cast<size_t>(array_[GetLocation(hash, i)]));
+ }
+ return min_count;
+}
+
+int CMSketch::Merge(CMSketch* dest, size_t quantity, const std::vector<const CMSketch*>& src,
+ const std::vector<long long>& weights) {
+ if (checkOverflow(dest, quantity, src, weights) != 0) {
+ return -1;
+ }
Review Comment:
I would rather avoid using statusor on the implementation layer, dealing with future errors gets difficult to track.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@kvrocks.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat: support count min sketch data structure and most commands [kvrocks]
Posted by "jonathanc-n (via GitHub)" <gi...@apache.org>.
jonathanc-n commented on code in PR #2524:
URL: https://github.com/apache/kvrocks/pull/2524#discussion_r1764543502
##########
src/types/redis_cms.h:
##########
@@ -0,0 +1,50 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#pragma once
+
+#include "cms.h"
+#include "storage/redis_db.h"
+#include "storage/redis_metadata.h"
+
+namespace redis {
+
+class CMS : public Database {
+ public:
+ explicit CMS(engine::Storage *storage, const std::string &ns) : Database(storage, ns) {}
+
+ rocksdb::Status IncrBy(engine::Context &ctx, const Slice &user_key,
+ const std::unordered_map<std::string, uint64_t> &elements);
+ rocksdb::Status Info(engine::Context &ctx, const Slice &user_key, CMSketch::CMSInfo *ret);
+ rocksdb::Status InitByDim(engine::Context &ctx, const Slice &user_key, uint32_t width, uint32_t depth);
+ rocksdb::Status InitByProb(engine::Context &ctx, const Slice &user_key, double error, double delta);
+ rocksdb::Status Query(engine::Context &ctx, const Slice &user_key, const std::vector<std::string> &elements,
+ std::vector<uint32_t> &counters);
+
+ private:
+ [[nodiscard]] rocksdb::Status GetMetadata(engine::Context &ctx, const Slice &ns_key,
+ CountMinSketchMetadata *metadata);
+
+ // TODO (jonathanc-n)
Review Comment:
@mapleFU the mergeuserkeys function
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@kvrocks.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat: support count min sketch data structure and most commands [kvrocks]
Posted by "mapleFU (via GitHub)" <gi...@apache.org>.
mapleFU commented on code in PR #2524:
URL: https://github.com/apache/kvrocks/pull/2524#discussion_r1759611920
##########
src/types/cms.cc:
##########
@@ -0,0 +1,128 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#include "cms.h"
+
+#include <algorithm>
+#include <cmath>
+#include <cstdint>
+#include <vector>
+
+CMSketch::CMSketchDimensions CMSketch::CMSDimFromProb(double error, double delta) {
+ CMSketchDimensions dims;
+ dims.width = std::ceil(2 / error);
+ dims.depth = std::ceil(std::log10(delta) / std::log10(0.5));
+ return dims;
+}
+
+size_t CMSketch::IncrBy(std::string_view item, uint32_t value) {
+ size_t min_count = std::numeric_limits<size_t>::max();
+
+ for (size_t i = 0; i < depth_; ++i) {
+ uint64_t hash = HllMurMurHash64A(item.data(), static_cast<int>(item.size()), i);
Review Comment:
What about using xxhash32?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@kvrocks.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat: support count min sketch data structure and most commands [kvrocks]
Posted by "mapleFU (via GitHub)" <gi...@apache.org>.
mapleFU commented on code in PR #2524:
URL: https://github.com/apache/kvrocks/pull/2524#discussion_r1759613632
##########
src/types/cms.h:
##########
@@ -0,0 +1,89 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#pragma once
+
+#include <memory>
+#include <vector>
+
+#include "server/redis_reply.h"
+#include "vendor/murmurhash2.h"
Review Comment:
why murmurhash2 included here?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@kvrocks.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat: support count min sketch data structure and most commands [kvrocks]
Posted by "mapleFU (via GitHub)" <gi...@apache.org>.
mapleFU commented on PR #2524:
URL: https://github.com/apache/kvrocks/pull/2524#issuecomment-2406471656
Yes I'm back from holiday and working, would continue.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@kvrocks.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat: support count min sketch data structure and most commands [kvrocks]
Posted by "PragmaTwice (via GitHub)" <gi...@apache.org>.
PragmaTwice commented on code in PR #2524:
URL: https://github.com/apache/kvrocks/pull/2524#discussion_r1768547837
##########
src/storage/redis_metadata.h:
##########
@@ -335,3 +336,15 @@ class HyperLogLogMetadata : public Metadata {
EncodeType encode_type = EncodeType::DENSE;
};
+
+class CountMinSketchMetadata : public Metadata {
+ public:
+ uint32_t width;
+ uint32_t depth;
+ uint64_t counter = 0;
+ std::vector<uint32_t> array;
Review Comment:
Yeah it can be like how we handle the JSON data structure.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@kvrocks.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat: support count min sketch data structure and most commands [kvrocks]
Posted by "mapleFU (via GitHub)" <gi...@apache.org>.
mapleFU commented on code in PR #2524:
URL: https://github.com/apache/kvrocks/pull/2524#discussion_r1759611246
##########
src/types/cms.cc:
##########
@@ -0,0 +1,128 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#include "cms.h"
+
+#include <algorithm>
+#include <cmath>
+#include <cstdint>
+#include <vector>
+
+
+CMSketch::CMSketchDimensions CMSketch::CMSDimFromProb(double error, double delta) {
+ CMSketchDimensions dims;
+ dims.width = std::ceil(2 / error);
+ dims.depth = std::ceil(std::log10(delta) / std::log10(0.5));
Review Comment:
Why did this being solved? Would you mind point out the code resolve this problem?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@kvrocks.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat: support count min sketch data structure and most commands [kvrocks]
Posted by "mapleFU (via GitHub)" <gi...@apache.org>.
mapleFU commented on code in PR #2524:
URL: https://github.com/apache/kvrocks/pull/2524#discussion_r1759610957
##########
src/storage/redis_metadata.cc:
##########
@@ -329,7 +329,8 @@ bool Metadata::ExpireAt(uint64_t expired_ts) const {
bool Metadata::IsSingleKVType() const { return Type() == kRedisString || Type() == kRedisJson; }
bool Metadata::IsEmptyableType() const {
- return IsSingleKVType() || Type() == kRedisStream || Type() == kRedisBloomFilter || Type() == kRedisHyperLogLog;
+ return IsSingleKVType() || Type() == kRedisStream || Type() == kRedisBloomFilter || Type() == kRedisHyperLogLog ||
Review Comment:
Wait, isn't a CMSketch a Single-KV Type?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@kvrocks.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat: support count min sketch data structure and most commands [kvrocks]
Posted by "mapleFU (via GitHub)" <gi...@apache.org>.
mapleFU commented on code in PR #2524:
URL: https://github.com/apache/kvrocks/pull/2524#discussion_r1759615189
##########
src/types/cms.h:
##########
@@ -0,0 +1,89 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#pragma once
+
+#include <memory>
+#include <vector>
+
+#include "server/redis_reply.h"
+#include "vendor/murmurhash2.h"
+
+class CMSketch {
+ public:
+ explicit CMSketch(uint32_t width, uint32_t depth, uint64_t counter, std::vector<uint32_t> array = {})
+ : width_(width),
+ depth_(depth),
+ counter_(counter),
+ array_(array.empty() ? std::vector<uint32_t>(width * depth, 0) : std::move(array)) {}
+
+ static std::unique_ptr<CMSketch> NewCMSketch(uint32_t width, int32_t depth) {
Review Comment:
Ever used?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@kvrocks.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat: support count min sketch data structure and most commands [kvrocks]
Posted by "jonathanc-n (via GitHub)" <gi...@apache.org>.
jonathanc-n commented on PR #2524:
URL: https://github.com/apache/kvrocks/pull/2524#issuecomment-2365003387
@mapleFU something seems to be a little odd here, I ran clang-format on all changed files and its running into formatting issues
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@kvrocks.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat: support count min sketch data structure and most commands [kvrocks]
Posted by "mapleFU (via GitHub)" <gi...@apache.org>.
mapleFU commented on code in PR #2524:
URL: https://github.com/apache/kvrocks/pull/2524#discussion_r1750289859
##########
src/commands/cmd_cms.cc:
##########
@@ -0,0 +1,168 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#include <types/cms.h>
+#include <types/redis_cms.h>
+
+#include "commander.h"
+#include "commands/command_parser.h"
+#include "server/redis_reply.h"
+#include "server/server.h"
+
+namespace redis {
+
+/// CMS.INCRBY key item increment [item increment ...]
+class CommandCMSIncrBy final : public Commander {
+ public:
+ Status Execute(Server *srv, Connection *conn, std::string *output) override {
+ if ((args_.size() - 2) % 2 != 0) {
+ return Status::RedisTryAgain;
+ }
+ redis::CMS cms(srv->storage, conn->GetNamespace());
+ engine::Context ctx(srv->storage);
+ rocksdb::Status s;
+ std::unordered_map<std::string, uint64_t> elements;
+ for (size_t i = 2; i < args_.size(); i += 2) {
+ std::string key = args_[i];
+ uint64_t value = 0;
+ try {
+ value = std::stoull(args_[i + 1]);
Review Comment:
we have `ParseInt` in `parse_util.h`?
##########
src/commands/cmd_cms.cc:
##########
@@ -0,0 +1,168 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#include <types/cms.h>
+#include <types/redis_cms.h>
+
+#include "commander.h"
+#include "commands/command_parser.h"
+#include "server/redis_reply.h"
+#include "server/server.h"
+
+namespace redis {
+
+/// CMS.INCRBY key item increment [item increment ...]
+class CommandCMSIncrBy final : public Commander {
+ public:
+ Status Execute(Server *srv, Connection *conn, std::string *output) override {
+ if ((args_.size() - 2) % 2 != 0) {
+ return Status::RedisTryAgain;
Review Comment:
?
##########
src/types/cms.cc:
##########
@@ -0,0 +1,128 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#include "cms.h"
+
+#include <algorithm>
+#include <cmath>
+#include <cstdint>
+#include <vector>
+
+
+CMSketch::CMSketchDimensions CMSketch::CMSDimFromProb(double error, double delta) {
+ CMSketchDimensions dims;
+ dims.width = std::ceil(2 / error);
+ dims.depth = std::ceil(std::log10(delta) / std::log10(0.5));
Review Comment:
Should we also try to adding a verify to check the width and depth not too large or too small ?
##########
src/commands/cmd_cms.cc:
##########
@@ -0,0 +1,168 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#include <types/cms.h>
+#include <types/redis_cms.h>
+
+#include "commander.h"
+#include "commands/command_parser.h"
+#include "server/redis_reply.h"
+#include "server/server.h"
+
+namespace redis {
+
+/// CMS.INCRBY key item increment [item increment ...]
+class CommandCMSIncrBy final : public Commander {
+ public:
+ Status Execute(Server *srv, Connection *conn, std::string *output) override {
+ if ((args_.size() - 2) % 2 != 0) {
+ return Status::RedisTryAgain;
+ }
+ redis::CMS cms(srv->storage, conn->GetNamespace());
+ engine::Context ctx(srv->storage);
+ rocksdb::Status s;
+ std::unordered_map<std::string, uint64_t> elements;
+ for (size_t i = 2; i < args_.size(); i += 2) {
+ std::string key = args_[i];
+ uint64_t value = 0;
+ try {
+ value = std::stoull(args_[i + 1]);
+ } catch (const std::exception &e) {
+ return Status::InvalidArgument;
+ }
+ elements[key] = value;
+ }
+
+ s = cms.IncrBy(ctx, args_[1], elements);
+ if (!s.ok()) {
+ return {Status::RedisExecErr, s.ToString()};
+ }
+
+ *output = redis::SimpleString("OK");
+ return Status::OK();
+ }
+};
+
+/// CMS.INFO key
+class CommandCMSInfo final : public Commander {
+ public:
+ Status Execute(Server *srv, Connection *conn, std::string *output) override {
+ redis::CMS cms(srv->storage, conn->GetNamespace());
+ engine::Context ctx(srv->storage);
+ rocksdb::Status s;
+ std::unordered_map<std::string, uint64_t> elements;
+ std::vector<uint64_t> ret{};
+
+ s = cms.Info(ctx, args_[1], &ret);
+
+ if (s.IsNotFound()) {
+ return {Status::RedisExecErr, s.ToString()};
+ }
+
+ if (!s.ok() && !s.IsNotFound()) {
+ return {Status::RedisExecErr, s.ToString()};
+ }
+
+ *output = redis::Array({redis::BulkString("width"), redis::Integer(ret[0]), redis::BulkString("depth"),
+ redis::Integer(ret[1]), redis::BulkString("count"), redis::Integer(ret[2])});
+
+ return Status::OK();
+ }
+};
+
+/// CMS.INITBYDIM key width depth
+class CommandCMSInitByDim final : public Commander {
+ public:
+ Status Execute(Server *srv, Connection *conn, std::string *output) override {
+ redis::CMS cms(srv->storage, conn->GetNamespace());
+ engine::Context ctx(srv->storage);
+ rocksdb::Status s;
+ uint64_t width = std::stoull(args_[2]);
+ uint64_t depth = std::stoull(args_[3]);
Review Comment:
ParseInt
##########
src/types/redis_cms.cc:
##########
@@ -0,0 +1,167 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#include "redis_cms.h"
+
+#include <stdint.h>
+
+#include "cms.h"
+
+namespace redis {
+
+rocksdb::Status CMS::GetMetadata(engine::Context &ctx, const Slice &ns_key,
+ CountMinSketchMetadata *metadata) {
+ return Database::GetMetadata(ctx, {kRedisCountMinSketch}, ns_key, metadata);
+}
+
+rocksdb::Status CMS::IncrBy(engine::Context &ctx, const Slice &user_key, const std::unordered_map<std::string, uint64_t> &elements) {
+ std::string ns_key = AppendNamespacePrefix(user_key);
+
+ LockGuard guard(storage_->GetLockManager(), ns_key);
+ CountMinSketchMetadata metadata{};
Review Comment:
If not exists, does this mean getting a `<0, 0, 0>` pair? What does it means?
##########
src/storage/redis_metadata.h:
##########
@@ -335,3 +336,15 @@ class HyperLogLogMetadata : public Metadata {
EncodeType encode_type = EncodeType::DENSE;
};
+
+class CountMinSketchMetadata : public Metadata {
+ public:
+ uint32_t width;
+ uint32_t depth;
+ uint64_t counter;
Review Comment:
Should this have default value?
##########
src/commands/cmd_cms.cc:
##########
@@ -0,0 +1,168 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#include <types/cms.h>
+#include <types/redis_cms.h>
+
+#include "commander.h"
+#include "commands/command_parser.h"
+#include "server/redis_reply.h"
+#include "server/server.h"
+
+namespace redis {
+
+/// CMS.INCRBY key item increment [item increment ...]
+class CommandCMSIncrBy final : public Commander {
+ public:
+ Status Execute(Server *srv, Connection *conn, std::string *output) override {
+ if ((args_.size() - 2) % 2 != 0) {
+ return Status::RedisTryAgain;
+ }
+ redis::CMS cms(srv->storage, conn->GetNamespace());
+ engine::Context ctx(srv->storage);
+ rocksdb::Status s;
+ std::unordered_map<std::string, uint64_t> elements;
+ for (size_t i = 2; i < args_.size(); i += 2) {
+ std::string key = args_[i];
+ uint64_t value = 0;
+ try {
+ value = std::stoull(args_[i + 1]);
+ } catch (const std::exception &e) {
+ return Status::InvalidArgument;
+ }
+ elements[key] = value;
+ }
+
+ s = cms.IncrBy(ctx, args_[1], elements);
+ if (!s.ok()) {
+ return {Status::RedisExecErr, s.ToString()};
+ }
+
+ *output = redis::SimpleString("OK");
+ return Status::OK();
+ }
+};
+
+/// CMS.INFO key
+class CommandCMSInfo final : public Commander {
+ public:
+ Status Execute(Server *srv, Connection *conn, std::string *output) override {
+ redis::CMS cms(srv->storage, conn->GetNamespace());
+ engine::Context ctx(srv->storage);
+ rocksdb::Status s;
+ std::unordered_map<std::string, uint64_t> elements;
+ std::vector<uint64_t> ret{};
+
+ s = cms.Info(ctx, args_[1], &ret);
+
+ if (s.IsNotFound()) {
+ return {Status::RedisExecErr, s.ToString()};
+ }
+
+ if (!s.ok() && !s.IsNotFound()) {
+ return {Status::RedisExecErr, s.ToString()};
+ }
+
+ *output = redis::Array({redis::BulkString("width"), redis::Integer(ret[0]), redis::BulkString("depth"),
+ redis::Integer(ret[1]), redis::BulkString("count"), redis::Integer(ret[2])});
Review Comment:
Can you use a struct for `ret` rather than a `vector`?
##########
src/commands/cmd_cms.cc:
##########
@@ -0,0 +1,168 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#include <types/cms.h>
+#include <types/redis_cms.h>
+
+#include "commander.h"
+#include "commands/command_parser.h"
+#include "server/redis_reply.h"
+#include "server/server.h"
+
+namespace redis {
+
+/// CMS.INCRBY key item increment [item increment ...]
+class CommandCMSIncrBy final : public Commander {
+ public:
+ Status Execute(Server *srv, Connection *conn, std::string *output) override {
+ if ((args_.size() - 2) % 2 != 0) {
+ return Status::RedisTryAgain;
+ }
+ redis::CMS cms(srv->storage, conn->GetNamespace());
+ engine::Context ctx(srv->storage);
+ rocksdb::Status s;
+ std::unordered_map<std::string, uint64_t> elements;
+ for (size_t i = 2; i < args_.size(); i += 2) {
+ std::string key = args_[i];
+ uint64_t value = 0;
+ try {
+ value = std::stoull(args_[i + 1]);
+ } catch (const std::exception &e) {
+ return Status::InvalidArgument;
+ }
+ elements[key] = value;
+ }
+
+ s = cms.IncrBy(ctx, args_[1], elements);
+ if (!s.ok()) {
+ return {Status::RedisExecErr, s.ToString()};
+ }
+
+ *output = redis::SimpleString("OK");
+ return Status::OK();
+ }
+};
+
+/// CMS.INFO key
+class CommandCMSInfo final : public Commander {
+ public:
+ Status Execute(Server *srv, Connection *conn, std::string *output) override {
+ redis::CMS cms(srv->storage, conn->GetNamespace());
+ engine::Context ctx(srv->storage);
+ rocksdb::Status s;
+ std::unordered_map<std::string, uint64_t> elements;
Review Comment:
never used?
##########
src/types/cms.cc:
##########
@@ -0,0 +1,128 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#include "cms.h"
+
+#include <algorithm>
+#include <cmath>
+#include <cstdint>
+#include <vector>
+
+
+CMSketch::CMSketchDimensions CMSketch::CMSDimFromProb(double error, double delta) {
+ CMSketchDimensions dims;
+ dims.width = std::ceil(2 / error);
+ dims.depth = std::ceil(std::log10(delta) / std::log10(0.5));
+ return dims;
+}
+
+size_t CMSketch::IncrBy(std::string_view item, size_t value) {
+ size_t min_count = std::numeric_limits<size_t>::max();
+
+ for (size_t i = 0; i < depth_; ++i) {
+ uint64_t hash = HllMurMurHash64A(item.data(), static_cast<int>(item.size()), i);
+ size_t loc = (hash % width_) + (i * width_);
+ array_[loc] += value;
+ if (array_[loc] < value) {
+ array_[loc] = UINT32_MAX;
+ }
Review Comment:
can this changed to check overflow?
##########
src/commands/cmd_cms.cc:
##########
@@ -0,0 +1,168 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#include <types/cms.h>
+#include <types/redis_cms.h>
+
+#include "commander.h"
+#include "commands/command_parser.h"
+#include "server/redis_reply.h"
+#include "server/server.h"
+
+namespace redis {
+
+/// CMS.INCRBY key item increment [item increment ...]
+class CommandCMSIncrBy final : public Commander {
+ public:
+ Status Execute(Server *srv, Connection *conn, std::string *output) override {
+ if ((args_.size() - 2) % 2 != 0) {
+ return Status::RedisTryAgain;
+ }
+ redis::CMS cms(srv->storage, conn->GetNamespace());
+ engine::Context ctx(srv->storage);
+ rocksdb::Status s;
+ std::unordered_map<std::string, uint64_t> elements;
+ for (size_t i = 2; i < args_.size(); i += 2) {
+ std::string key = args_[i];
+ uint64_t value = 0;
+ try {
+ value = std::stoull(args_[i + 1]);
+ } catch (const std::exception &e) {
+ return Status::InvalidArgument;
+ }
+ elements[key] = value;
+ }
+
+ s = cms.IncrBy(ctx, args_[1], elements);
+ if (!s.ok()) {
+ return {Status::RedisExecErr, s.ToString()};
+ }
+
+ *output = redis::SimpleString("OK");
+ return Status::OK();
+ }
+};
+
+/// CMS.INFO key
+class CommandCMSInfo final : public Commander {
+ public:
+ Status Execute(Server *srv, Connection *conn, std::string *output) override {
+ redis::CMS cms(srv->storage, conn->GetNamespace());
+ engine::Context ctx(srv->storage);
+ rocksdb::Status s;
+ std::unordered_map<std::string, uint64_t> elements;
+ std::vector<uint64_t> ret{};
+
+ s = cms.Info(ctx, args_[1], &ret);
+
+ if (s.IsNotFound()) {
+ return {Status::RedisExecErr, s.ToString()};
+ }
+
+ if (!s.ok() && !s.IsNotFound()) {
+ return {Status::RedisExecErr, s.ToString()};
+ }
+
+ *output = redis::Array({redis::BulkString("width"), redis::Integer(ret[0]), redis::BulkString("depth"),
+ redis::Integer(ret[1]), redis::BulkString("count"), redis::Integer(ret[2])});
+
+ return Status::OK();
+ }
+};
+
+/// CMS.INITBYDIM key width depth
+class CommandCMSInitByDim final : public Commander {
+ public:
+ Status Execute(Server *srv, Connection *conn, std::string *output) override {
+ redis::CMS cms(srv->storage, conn->GetNamespace());
+ engine::Context ctx(srv->storage);
+ rocksdb::Status s;
+ uint64_t width = std::stoull(args_[2]);
+ uint64_t depth = std::stoull(args_[3]);
+
+ s = cms.InitByDim(ctx, args_[1], width, depth);
+ if (!s.ok()) {
+ return {Status::RedisExecErr, s.ToString()};
+ }
+
+ *output = redis::SimpleString("OK");
+ return Status::OK();
+ }
+};
+
+/// CMS.INITBYPROB key error probability
+class CommandCMSInitByProb final : public Commander {
+ public:
+ Status Execute(Server *srv, Connection *conn, std::string *output) override {
+ redis::CMS cms(srv->storage, conn->GetNamespace());
+ engine::Context ctx(srv->storage);
+ rocksdb::Status s;
+ double error = std::stod(args_[2]);
+ double delta = std::stod(args_[3]);
Review Comment:
ParseFloat
##########
src/types/cms.cc:
##########
@@ -0,0 +1,128 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#include "cms.h"
+
+#include <algorithm>
+#include <cmath>
+#include <cstdint>
+#include <vector>
+
+
+CMSketch::CMSketchDimensions CMSketch::CMSDimFromProb(double error, double delta) {
+ CMSketchDimensions dims;
+ dims.width = std::ceil(2 / error);
+ dims.depth = std::ceil(std::log10(delta) / std::log10(0.5));
+ return dims;
+}
+
+size_t CMSketch::IncrBy(std::string_view item, size_t value) {
Review Comment:
why value is a size_t here?
##########
src/types/cms.cc:
##########
@@ -0,0 +1,128 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#include "cms.h"
+
+#include <algorithm>
+#include <cmath>
+#include <cstdint>
+#include <vector>
+
+
+CMSketch::CMSketchDimensions CMSketch::CMSDimFromProb(double error, double delta) {
+ CMSketchDimensions dims;
+ dims.width = std::ceil(2 / error);
+ dims.depth = std::ceil(std::log10(delta) / std::log10(0.5));
+ return dims;
+}
+
+size_t CMSketch::IncrBy(std::string_view item, size_t value) {
+ size_t min_count = std::numeric_limits<size_t>::max();
+
+ for (size_t i = 0; i < depth_; ++i) {
+ uint64_t hash = HllMurMurHash64A(item.data(), static_cast<int>(item.size()), i);
+ size_t loc = (hash % width_) + (i * width_);
Review Comment:
can you extract the loc to a helper function?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@kvrocks.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat: support count min sketch data structure and most commands [kvrocks]
Posted by "mapleFU (via GitHub)" <gi...@apache.org>.
mapleFU commented on PR #2524:
URL: https://github.com/apache/kvrocks/pull/2524#issuecomment-2337231702
Nice, I'll take a round tonight
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@kvrocks.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat: support count min sketch data structure and most commands [kvrocks]
Posted by "jonathanc-n (via GitHub)" <gi...@apache.org>.
jonathanc-n commented on code in PR #2524:
URL: https://github.com/apache/kvrocks/pull/2524#discussion_r1749371934
##########
src/types/cms.h:
##########
@@ -0,0 +1,82 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#pragma once
+
+#include <assert.h>
+
+#include <atomic>
+#include <iostream>
+#include <vector>
+
+#include "vendor/murmurhash2.h"
+
+class CMSketch {
+ public:
+ explicit CMSketch(uint32_t width = 0, uint32_t depth = 0, uint64_t counter = 0, std::vector<uint32_t> array = {})
+ : width_(width),
+ depth_(depth),
+ counter_(counter),
+ array_(array.empty() ? std::vector<uint32_t>(width * depth, 0) : std::move(array)) {}
+
+ ~CMSketch() = default;
+
+ static CMSketch* NewCMSketch(size_t width, size_t depth) { return new CMSketch(width, depth); }
+
+ static void CMSDimFromProb(double error, double delta, uint32_t& width, uint32_t& depth);
+
+ size_t IncrBy(const char* item, size_t item_len, size_t value);
+
+ size_t Query(const char* item, size_t item_len) const;
+
+ static int Merge(CMSketch* dest, size_t quantity, const std::vector<const CMSketch*>& src,
+ const std::vector<long long>& weights);
+
+ struct MergeParams {
+ CMSketch* dest;
+ size_t num_keys;
+ std::vector<const CMSketch*> cms_array;
+ std::vector<long long> weights;
+ };
+
+ int CMSMergeParams(const MergeParams& params);
+
+ uint64_t& GetCounter() { return counter_; }
+ std::vector<uint32_t>& GetArray() { return array_; }
Review Comment:
No, for a cms, it is storing counters and not unique objects.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@kvrocks.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat: support count min sketch data structure and most commands [kvrocks]
Posted by "jonathanc-n (via GitHub)" <gi...@apache.org>.
jonathanc-n commented on PR #2524:
URL: https://github.com/apache/kvrocks/pull/2524#issuecomment-2367178737
@mapleFU test cases are implemented!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@kvrocks.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat: support count min sketch data structure and most commands [kvrocks]
Posted by "mapleFU (via GitHub)" <gi...@apache.org>.
mapleFU commented on code in PR #2524:
URL: https://github.com/apache/kvrocks/pull/2524#discussion_r1764541357
##########
src/types/redis_cms.h:
##########
@@ -0,0 +1,50 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#pragma once
+
+#include "cms.h"
+#include "storage/redis_db.h"
+#include "storage/redis_metadata.h"
+
+namespace redis {
+
+class CMS : public Database {
+ public:
+ explicit CMS(engine::Storage *storage, const std::string &ns) : Database(storage, ns) {}
+
+ rocksdb::Status IncrBy(engine::Context &ctx, const Slice &user_key,
+ const std::unordered_map<std::string, uint64_t> &elements);
+ rocksdb::Status Info(engine::Context &ctx, const Slice &user_key, CMSketch::CMSInfo *ret);
+ rocksdb::Status InitByDim(engine::Context &ctx, const Slice &user_key, uint32_t width, uint32_t depth);
+ rocksdb::Status InitByProb(engine::Context &ctx, const Slice &user_key, double error, double delta);
+ rocksdb::Status Query(engine::Context &ctx, const Slice &user_key, const std::vector<std::string> &elements,
+ std::vector<uint32_t> &counters);
+
+ private:
+ [[nodiscard]] rocksdb::Status GetMetadata(engine::Context &ctx, const Slice &ns_key,
+ CountMinSketchMetadata *metadata);
+
+ // TODO (jonathanc-n)
Review Comment:
todo what?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@kvrocks.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat: support count min sketch data structure and most commands [kvrocks]
Posted by "jonathanc-n (via GitHub)" <gi...@apache.org>.
jonathanc-n commented on code in PR #2524:
URL: https://github.com/apache/kvrocks/pull/2524#discussion_r1759624118
##########
src/storage/redis_metadata.cc:
##########
@@ -329,7 +329,8 @@ bool Metadata::ExpireAt(uint64_t expired_ts) const {
bool Metadata::IsSingleKVType() const { return Type() == kRedisString || Type() == kRedisJson; }
bool Metadata::IsEmptyableType() const {
- return IsSingleKVType() || Type() == kRedisStream || Type() == kRedisBloomFilter || Type() == kRedisHyperLogLog;
+ return IsSingleKVType() || Type() == kRedisStream || Type() == kRedisBloomFilter || Type() == kRedisHyperLogLog ||
Review Comment:
Oh, sorry about that, i was thinking due to the different variables, that it would be instead put under emptyable type. But after review it makes more sense as a singlekvtype
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@kvrocks.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat: support count min sketch data structure and most commands [kvrocks]
Posted by "mapleFU (via GitHub)" <gi...@apache.org>.
mapleFU commented on PR #2524:
URL: https://github.com/apache/kvrocks/pull/2524#issuecomment-2350717963
I'm outing these days, so maybe late reply
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@kvrocks.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat: support count min sketch data structure and most commands [kvrocks]
Posted by "jonathanc-n (via GitHub)" <gi...@apache.org>.
jonathanc-n commented on code in PR #2524:
URL: https://github.com/apache/kvrocks/pull/2524#discussion_r1751253532
##########
src/commands/cmd_cms.cc:
##########
@@ -0,0 +1,168 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#include <types/cms.h>
+#include <types/redis_cms.h>
+
+#include "commander.h"
+#include "commands/command_parser.h"
+#include "server/redis_reply.h"
+#include "server/server.h"
+
+namespace redis {
+
+/// CMS.INCRBY key item increment [item increment ...]
+class CommandCMSIncrBy final : public Commander {
+ public:
+ Status Execute(Server *srv, Connection *conn, std::string *output) override {
+ if ((args_.size() - 2) % 2 != 0) {
+ return Status::RedisTryAgain;
Review Comment:
@mapleFU alright should be good!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@kvrocks.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat: support count min sketch data structure and most commands [kvrocks]
Posted by "jonathanc-n (via GitHub)" <gi...@apache.org>.
jonathanc-n commented on PR #2524:
URL: https://github.com/apache/kvrocks/pull/2524#issuecomment-2339391522
@mapleFU do the changes seem right? sorry for the bother.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@kvrocks.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat: support count min sketch data structure and most commands [kvrocks]
Posted by "mapleFU (via GitHub)" <gi...@apache.org>.
mapleFU commented on code in PR #2524:
URL: https://github.com/apache/kvrocks/pull/2524#discussion_r1756286475
##########
src/storage/redis_metadata.h:
##########
@@ -335,3 +336,15 @@ class HyperLogLogMetadata : public Metadata {
EncodeType encode_type = EncodeType::DENSE;
};
+
+class CountMinSketchMetadata : public Metadata {
+ public:
+ uint32_t width;
+ uint32_t depth;
+ uint64_t counter = 0;
+ std::vector<uint32_t> array;
Review Comment:
@git-hulk @PragmaTwice
I'm thinking about handling the `array`. Since regarding the cmsketch as a string is ok to me, but parsing it to an `std::vector` is a bit weird to me. Can we take a `Buffer` and do zero copying when doing this?
Like:
```
LoadMetadata from string. When storing, forcing LittleEndian in the array
When reading from metadata, report error if not length enough, and hold a sliced buffer on underlying data
When read/write, using memcpy to avoid unaligned access.
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@kvrocks.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat: support count min sketch data structure and most commands [kvrocks]
Posted by "jonathanc-n (via GitHub)" <gi...@apache.org>.
jonathanc-n commented on PR #2524:
URL: https://github.com/apache/kvrocks/pull/2524#issuecomment-2345080747
@PragmaTwice Is the workflow able to run again?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@kvrocks.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat: support count min sketch data structure and most commands [kvrocks]
Posted by "jonathanc-n (via GitHub)" <gi...@apache.org>.
jonathanc-n commented on PR #2524:
URL: https://github.com/apache/kvrocks/pull/2524#issuecomment-2375884144
@mapleFU Does this seem fine to move forward?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@kvrocks.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat: support count min sketch data structure and most commands [kvrocks]
Posted by "mapleFU (via GitHub)" <gi...@apache.org>.
mapleFU commented on code in PR #2524:
URL: https://github.com/apache/kvrocks/pull/2524#discussion_r1759619788
##########
src/types/cms.cc:
##########
@@ -0,0 +1,128 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#include "cms.h"
+
+#include <algorithm>
+#include <cmath>
+#include <cstdint>
+#include <vector>
+
+
+CMSketch::CMSketchDimensions CMSketch::CMSDimFromProb(double error, double delta) {
+ CMSketchDimensions dims;
+ dims.width = std::ceil(2 / error);
+ dims.depth = std::ceil(std::log10(delta) / std::log10(0.5));
Review Comment:
Let me change the wording here, can we assure:
1. the cmsketch memory used less than 50MB
2.the cmsketch memory used greater than 0
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@kvrocks.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat: support count min sketch data structure and most commands [kvrocks]
Posted by "mapleFU (via GitHub)" <gi...@apache.org>.
mapleFU commented on code in PR #2524:
URL: https://github.com/apache/kvrocks/pull/2524#discussion_r1759611337
##########
src/types/cms.cc:
##########
@@ -0,0 +1,128 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#include "cms.h"
+
+#include <algorithm>
+#include <cmath>
+#include <cstdint>
+#include <vector>
+
+CMSketch::CMSketchDimensions CMSketch::CMSDimFromProb(double error, double delta) {
+ CMSketchDimensions dims;
+ dims.width = std::ceil(2 / error);
+ dims.depth = std::ceil(std::log10(delta) / std::log10(0.5));
+ return dims;
+}
+
+size_t CMSketch::IncrBy(std::string_view item, uint32_t value) {
+ size_t min_count = std::numeric_limits<size_t>::max();
+
+ for (size_t i = 0; i < depth_; ++i) {
+ uint64_t hash = HllMurMurHash64A(item.data(), static_cast<int>(item.size()), i);
+ size_t loc = GetLocation(hash, i);
+ if (array_[loc] > UINT32_MAX - value) {
+ array_[loc] = UINT32_MAX;
+ } else {
+ array_[loc] += value;
+ }
+ min_count = std::min(min_count, static_cast<size_t>(array_[loc]));
+ }
+ counter_ += value;
+ return min_count;
+}
+
+size_t CMSketch::Query(std::string_view item) const {
+ size_t min_count = std::numeric_limits<size_t>::max();
+
+ for (size_t i = 0; i < depth_; ++i) {
+ uint64_t hash = HllMurMurHash64A(item.data(), static_cast<int>(item.size()), i);
+ min_count = std::min(min_count, static_cast<size_t>(array_[(hash % width_) + (i * width_)]));
+ }
+ return min_count;
+}
+
+int CMSketch::Merge(CMSketch* dest, size_t quantity, const std::vector<const CMSketch*>& src,
+ const std::vector<long long>& weights) {
+ if (checkOverflow(dest, quantity, src, weights) != 0) {
+ return -1;
+ }
+
+ for (size_t i = 0; i < dest->GetDepth(); ++i) {
+ for (size_t j = 0; j < dest->GetWidth(); ++j) {
+ int64_t item_count = 0;
+ for (size_t k = 0; k < quantity; ++k) {
+ item_count += static_cast<int64_t>(src[k]->array_[(i * dest->GetWidth()) + j]) * weights[k];
+ }
+ dest->GetArray()[(i * dest->GetWidth()) + j] = item_count;
+ }
+ }
+
+ for (size_t i = 0; i < quantity; ++i) {
+ dest->GetCounter() += src[i]->GetCounter() * weights[i];
+ }
+
+ return 0;
+}
+
+int CMSMergeParams(const CMSketch::MergeParams& params) {
+ return CMSketch::Merge(params.dest, params.num_keys, params.cms_array, params.weights);
+}
+
+int CMSketch::checkOverflow(CMSketch* dest, size_t quantity, const std::vector<const CMSketch*>& src,
+ const std::vector<long long>& weights) {
+ int64_t item_count = 0;
+ int64_t cms_count = 0;
+ size_t width = dest->GetWidth();
+ size_t depth = dest->GetDepth();
+
+ for (size_t i = 0; i < depth; ++i) {
+ for (size_t j = 0; j < width; ++j) {
+ item_count = 0;
+ for (size_t k = 0; k < quantity; ++k) {
+ int64_t mul = 0;
+
+ if (__builtin_mul_overflow(src[k]->GetArray()[(i * width) + j], weights[k], &mul) ||
+ (__builtin_add_overflow(item_count, mul, &item_count))) {
+ return -1;
+ }
+ }
+
+ if (item_count < 0 || item_count > UINT32_MAX) {
+ return -1;
+ }
+ }
+ }
+
+ for (size_t i = 0; i < quantity; ++i) {
+ int64_t mul = 0;
+
+ if (__builtin_mul_overflow(src[i]->GetCounter(), weights[i], &mul) ||
+ (__builtin_add_overflow(cms_count, mul, &cms_count))) {
+ return -1;
+ }
+ }
+
+ if (cms_count < 0) {
+ return -1;
+ }
+
+ return 0;
+}
Review Comment:
fmt: `\n` after this
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@kvrocks.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat: support count min sketch data structure and most commands [kvrocks]
Posted by "PragmaTwice (via GitHub)" <gi...@apache.org>.
PragmaTwice commented on code in PR #2524:
URL: https://github.com/apache/kvrocks/pull/2524#discussion_r1768548767
##########
src/storage/redis_metadata.h:
##########
@@ -335,3 +336,15 @@ class HyperLogLogMetadata : public Metadata {
EncodeType encode_type = EncodeType::DENSE;
};
+
+class CountMinSketchMetadata : public Metadata {
+ public:
+ uint32_t width;
+ uint32_t depth;
+ uint64_t counter = 0;
+ std::vector<uint32_t> array;
Review Comment:
But here I'm more interested in whether it's better to be a single key or putting the array in subkeys.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@kvrocks.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat: support count min sketch data structure and most commands [kvrocks]
Posted by "mapleFU (via GitHub)" <gi...@apache.org>.
mapleFU commented on code in PR #2524:
URL: https://github.com/apache/kvrocks/pull/2524#discussion_r1747882239
##########
src/types/cms.cc:
##########
@@ -0,0 +1,128 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#include "cms.h"
+
+#include <algorithm>
+#include <cmath>
+#include <cstdint>
+#include <vector>
+
+#include "glog/logging.h"
+
+void CMSketch::CMSDimFromProb(double error, double delta, uint32_t& width, uint32_t& depth) {
+ LOG(INFO) << error << delta;
+ width = std::ceil(2 / error);
+ depth = std::ceil(std::log10(delta) / std::log10(0.5));
+}
+
+size_t CMSketch::IncrBy(const char* item, size_t item_len, size_t value) {
+ size_t min_count = std::numeric_limits<size_t>::max();
+
+ for (size_t i = 0; i < depth_; ++i) {
+ uint32_t hash = HllMurMurHash64A(item, static_cast<int>(item_len), i);
Review Comment:
I don't know getting u32 from u64 hash a good idea...
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@kvrocks.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat: support count min sketch data structure and most commands [kvrocks]
Posted by "jonathanc-n (via GitHub)" <gi...@apache.org>.
jonathanc-n commented on PR #2524:
URL: https://github.com/apache/kvrocks/pull/2524#issuecomment-2335026478
Was there a change made to GetOptions recently? There seems to be a problem after the merge.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@kvrocks.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat: support count min sketch data structure and most commands [kvrocks]
Posted by "jonathanc-n (via GitHub)" <gi...@apache.org>.
jonathanc-n commented on code in PR #2524:
URL: https://github.com/apache/kvrocks/pull/2524#discussion_r1767397310
##########
src/types/cms.cc:
##########
@@ -0,0 +1,128 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#include "cms.h"
+
+#include <algorithm>
+#include <cmath>
+#include <cstdint>
+#include <vector>
+
+CMSketch::CMSketchDimensions CMSketch::CMSDimFromProb(double error, double delta) {
+ CMSketchDimensions dims;
+ dims.width = std::ceil(2 / error);
+ dims.depth = std::ceil(std::log10(delta) / std::log10(0.5));
+ return dims;
+}
+
+size_t CMSketch::IncrBy(std::string_view item, uint32_t value) {
+ size_t min_count = std::numeric_limits<size_t>::max();
+
+ for (size_t i = 0; i < depth_; ++i) {
+ uint64_t hash = XXH32(item.data(), static_cast<int>(item.size()), i);
+ size_t loc = GetLocation(hash, i);
+ if (array_[loc] > UINT32_MAX - value) {
+ array_[loc] = UINT32_MAX;
+ } else {
+ array_[loc] += value;
+ }
+ min_count = std::min(min_count, static_cast<size_t>(array_[loc]));
+ }
+ counter_ += value;
+ return min_count;
+}
+
+size_t CMSketch::Query(std::string_view item) const {
+ size_t min_count = std::numeric_limits<size_t>::max();
+
+ for (size_t i = 0; i < depth_; ++i) {
+ uint64_t hash = XXH32(item.data(), static_cast<int>(item.size()), i);
+ min_count = std::min(min_count, static_cast<size_t>(array_[GetLocation(hash, i)]));
+ }
+ return min_count;
+}
+
+int CMSketch::Merge(CMSketch* dest, size_t quantity, const std::vector<const CMSketch*>& src,
+ const std::vector<long long>& weights) {
+ if (checkOverflow(dest, quantity, src, weights) != 0) {
+ return -1;
+ }
+
+ for (size_t i = 0; i < dest->GetDepth(); ++i) {
+ for (size_t j = 0; j < dest->GetWidth(); ++j) {
+ int64_t item_count = 0;
+ for (size_t k = 0; k < quantity; ++k) {
+ item_count += static_cast<int64_t>(src[k]->array_[(i * dest->GetWidth()) + j]) * weights[k];
Review Comment:
No, i believe they dont do the same
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@kvrocks.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat: support count min sketch data structure and most commands [kvrocks]
Posted by "mapleFU (via GitHub)" <gi...@apache.org>.
mapleFU commented on code in PR #2524:
URL: https://github.com/apache/kvrocks/pull/2524#discussion_r1747881097
##########
src/types/cms.h:
##########
@@ -0,0 +1,82 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#pragma once
+
+#include <assert.h>
+
+#include <atomic>
+#include <iostream>
Review Comment:
Why?
##########
src/types/cms.h:
##########
@@ -0,0 +1,82 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#pragma once
+
+#include <assert.h>
+
+#include <atomic>
+#include <iostream>
+#include <vector>
+
+#include "vendor/murmurhash2.h"
+
+class CMSketch {
+ public:
+ explicit CMSketch(uint32_t width = 0, uint32_t depth = 0, uint64_t counter = 0, std::vector<uint32_t> array = {})
+ : width_(width),
+ depth_(depth),
+ counter_(counter),
+ array_(array.empty() ? std::vector<uint32_t>(width * depth, 0) : std::move(array)) {}
+
+ ~CMSketch() = default;
+
+ static CMSketch* NewCMSketch(size_t width, size_t depth) { return new CMSketch(width, depth); }
+
+ static void CMSDimFromProb(double error, double delta, uint32_t& width, uint32_t& depth);
+
+ size_t IncrBy(const char* item, size_t item_len, size_t value);
+
+ size_t Query(const char* item, size_t item_len) const;
+
+ static int Merge(CMSketch* dest, size_t quantity, const std::vector<const CMSketch*>& src,
+ const std::vector<long long>& weights);
+
+ struct MergeParams {
+ CMSketch* dest;
+ size_t num_keys;
+ std::vector<const CMSketch*> cms_array;
+ std::vector<long long> weights;
+ };
+
+ int CMSMergeParams(const MergeParams& params);
+
+ uint64_t& GetCounter() { return counter_; }
+ std::vector<uint32_t>& GetArray() { return array_; }
+
+ const uint64_t& GetCounter() const { return counter_; }
+ const std::vector<uint32_t>& GetArray() const { return array_; }
+
+ size_t GetWidth() const { return width_; }
+ size_t GetDepth() const { return depth_; }
Review Comment:
Why do they shift between u32 and size_t?
##########
src/types/cms.h:
##########
@@ -0,0 +1,82 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#pragma once
+
+#include <assert.h>
+
+#include <atomic>
+#include <iostream>
+#include <vector>
+
+#include "vendor/murmurhash2.h"
+
+class CMSketch {
+ public:
+ explicit CMSketch(uint32_t width = 0, uint32_t depth = 0, uint64_t counter = 0, std::vector<uint32_t> array = {})
Review Comment:
Why using default args?
##########
src/types/cms.h:
##########
@@ -0,0 +1,82 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#pragma once
+
+#include <assert.h>
+
+#include <atomic>
+#include <iostream>
+#include <vector>
+
+#include "vendor/murmurhash2.h"
+
+class CMSketch {
+ public:
+ explicit CMSketch(uint32_t width = 0, uint32_t depth = 0, uint64_t counter = 0, std::vector<uint32_t> array = {})
+ : width_(width),
+ depth_(depth),
+ counter_(counter),
+ array_(array.empty() ? std::vector<uint32_t>(width * depth, 0) : std::move(array)) {}
+
+ ~CMSketch() = default;
+
+ static CMSketch* NewCMSketch(size_t width, size_t depth) { return new CMSketch(width, depth); }
+
+ static void CMSDimFromProb(double error, double delta, uint32_t& width, uint32_t& depth);
Review Comment:
Would you mind encapsulate `(width, depth)` to a struct, and just return the struct?
##########
src/types/cms.h:
##########
@@ -0,0 +1,82 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#pragma once
+
+#include <assert.h>
+
+#include <atomic>
+#include <iostream>
+#include <vector>
+
+#include "vendor/murmurhash2.h"
+
+class CMSketch {
+ public:
+ explicit CMSketch(uint32_t width = 0, uint32_t depth = 0, uint64_t counter = 0, std::vector<uint32_t> array = {})
+ : width_(width),
+ depth_(depth),
+ counter_(counter),
+ array_(array.empty() ? std::vector<uint32_t>(width * depth, 0) : std::move(array)) {}
+
+ ~CMSketch() = default;
Review Comment:
Remove this?
##########
src/commands/commander.h:
##########
@@ -73,6 +73,7 @@ enum class CommandCategory : uint8_t {
Bit,
BloomFilter,
Cluster,
+ CMS,
Review Comment:
Would this better being CMSketh? Or `CountMinSketch`?
##########
src/types/cms.h:
##########
@@ -0,0 +1,82 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#pragma once
+
+#include <assert.h>
+
+#include <atomic>
+#include <iostream>
+#include <vector>
+
+#include "vendor/murmurhash2.h"
+
+class CMSketch {
+ public:
+ explicit CMSketch(uint32_t width = 0, uint32_t depth = 0, uint64_t counter = 0, std::vector<uint32_t> array = {})
+ : width_(width),
+ depth_(depth),
+ counter_(counter),
+ array_(array.empty() ? std::vector<uint32_t>(width * depth, 0) : std::move(array)) {}
+
+ ~CMSketch() = default;
+
+ static CMSketch* NewCMSketch(size_t width, size_t depth) { return new CMSketch(width, depth); }
+
+ static void CMSDimFromProb(double error, double delta, uint32_t& width, uint32_t& depth);
+
+ size_t IncrBy(const char* item, size_t item_len, size_t value);
+
+ size_t Query(const char* item, size_t item_len) const;
+
+ static int Merge(CMSketch* dest, size_t quantity, const std::vector<const CMSketch*>& src,
+ const std::vector<long long>& weights);
+
+ struct MergeParams {
+ CMSketch* dest;
+ size_t num_keys;
+ std::vector<const CMSketch*> cms_array;
+ std::vector<long long> weights;
+ };
+
+ int CMSMergeParams(const MergeParams& params);
+
+ uint64_t& GetCounter() { return counter_; }
+ std::vector<uint32_t>& GetArray() { return array_; }
Review Comment:
Would a set array being better here?
##########
src/types/cms.h:
##########
@@ -0,0 +1,82 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#pragma once
+
+#include <assert.h>
+
+#include <atomic>
+#include <iostream>
+#include <vector>
+
+#include "vendor/murmurhash2.h"
+
+class CMSketch {
+ public:
+ explicit CMSketch(uint32_t width = 0, uint32_t depth = 0, uint64_t counter = 0, std::vector<uint32_t> array = {})
+ : width_(width),
+ depth_(depth),
+ counter_(counter),
+ array_(array.empty() ? std::vector<uint32_t>(width * depth, 0) : std::move(array)) {}
+
+ ~CMSketch() = default;
+
+ static CMSketch* NewCMSketch(size_t width, size_t depth) { return new CMSketch(width, depth); }
Review Comment:
Why call new explicitly? Shouldn't a unique_ptr being returned in this case?
##########
src/types/cms.h:
##########
@@ -0,0 +1,82 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#pragma once
+
+#include <assert.h>
+
+#include <atomic>
+#include <iostream>
+#include <vector>
+
+#include "vendor/murmurhash2.h"
+
+class CMSketch {
+ public:
+ explicit CMSketch(uint32_t width = 0, uint32_t depth = 0, uint64_t counter = 0, std::vector<uint32_t> array = {})
+ : width_(width),
+ depth_(depth),
+ counter_(counter),
+ array_(array.empty() ? std::vector<uint32_t>(width * depth, 0) : std::move(array)) {}
+
+ ~CMSketch() = default;
+
+ static CMSketch* NewCMSketch(size_t width, size_t depth) { return new CMSketch(width, depth); }
+
+ static void CMSDimFromProb(double error, double delta, uint32_t& width, uint32_t& depth);
+
Review Comment:
`const char* item, size_t item_len` -> can this be change to std::string_view
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@kvrocks.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat: support count min sketch data structure and most commands [kvrocks]
Posted by "jonathanc-n (via GitHub)" <gi...@apache.org>.
jonathanc-n commented on code in PR #2524:
URL: https://github.com/apache/kvrocks/pull/2524#discussion_r1747888498
##########
src/commands/commander.h:
##########
@@ -73,6 +73,7 @@ enum class CommandCategory : uint8_t {
Bit,
BloomFilter,
Cluster,
+ CMS,
Review Comment:
I think CMS is fine, CountMinSketch would be too long. HyperLogLog is also written as HLL here, so it is consistent.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@kvrocks.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat: support count min sketch data structure and most commands [kvrocks]
Posted by "mapleFU (via GitHub)" <gi...@apache.org>.
mapleFU commented on code in PR #2524:
URL: https://github.com/apache/kvrocks/pull/2524#discussion_r1751165865
##########
src/commands/cmd_cms.cc:
##########
@@ -0,0 +1,168 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#include <types/cms.h>
+#include <types/redis_cms.h>
+
+#include "commander.h"
+#include "commands/command_parser.h"
+#include "server/redis_reply.h"
+#include "server/server.h"
+
+namespace redis {
+
+/// CMS.INCRBY key item increment [item increment ...]
+class CommandCMSIncrBy final : public Commander {
+ public:
+ Status Execute(Server *srv, Connection *conn, std::string *output) override {
+ if ((args_.size() - 2) % 2 != 0) {
+ return Status::RedisTryAgain;
Review Comment:
When arg mismatch, try again never solving this, it should report input is invalid
Besides, the arg-parsing framework can well handle this?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@kvrocks.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat: support count min sketch data structure and most commands [kvrocks]
Posted by "jonathanc-n (via GitHub)" <gi...@apache.org>.
jonathanc-n commented on PR #2524:
URL: https://github.com/apache/kvrocks/pull/2524#issuecomment-2336866126
I believe this pr should be good
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@kvrocks.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat: support count min sketch data structure and most commands [kvrocks]
Posted by "mapleFU (via GitHub)" <gi...@apache.org>.
mapleFU commented on PR #2524:
URL: https://github.com/apache/kvrocks/pull/2524#issuecomment-2345463608
> do the changes seem right? sorry for the bother.
Sorry for delaying, I'll take a pass
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@kvrocks.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat: support count min sketch data structure and most commands [kvrocks]
Posted by "mapleFU (via GitHub)" <gi...@apache.org>.
mapleFU commented on code in PR #2524:
URL: https://github.com/apache/kvrocks/pull/2524#discussion_r1759613349
##########
src/types/cms.cc:
##########
@@ -0,0 +1,128 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#include "cms.h"
+
+#include <algorithm>
+#include <cmath>
+#include <cstdint>
+#include <vector>
+
+CMSketch::CMSketchDimensions CMSketch::CMSDimFromProb(double error, double delta) {
+ CMSketchDimensions dims;
+ dims.width = std::ceil(2 / error);
+ dims.depth = std::ceil(std::log10(delta) / std::log10(0.5));
+ return dims;
+}
+
+size_t CMSketch::IncrBy(std::string_view item, uint32_t value) {
+ size_t min_count = std::numeric_limits<size_t>::max();
+
+ for (size_t i = 0; i < depth_; ++i) {
+ uint64_t hash = HllMurMurHash64A(item.data(), static_cast<int>(item.size()), i);
+ size_t loc = GetLocation(hash, i);
+ if (array_[loc] > UINT32_MAX - value) {
+ array_[loc] = UINT32_MAX;
+ } else {
+ array_[loc] += value;
+ }
+ min_count = std::min(min_count, static_cast<size_t>(array_[loc]));
+ }
+ counter_ += value;
+ return min_count;
+}
+
+size_t CMSketch::Query(std::string_view item) const {
+ size_t min_count = std::numeric_limits<size_t>::max();
+
+ for (size_t i = 0; i < depth_; ++i) {
+ uint64_t hash = HllMurMurHash64A(item.data(), static_cast<int>(item.size()), i);
+ min_count = std::min(min_count, static_cast<size_t>(array_[(hash % width_) + (i * width_)]));
Review Comment:
Why didn't `GetLocation` used here?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@kvrocks.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat: support count min sketch data structure and most commands [kvrocks]
Posted by "mapleFU (via GitHub)" <gi...@apache.org>.
mapleFU commented on code in PR #2524:
URL: https://github.com/apache/kvrocks/pull/2524#discussion_r1759611748
##########
src/types/cms.cc:
##########
@@ -0,0 +1,128 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#include "cms.h"
+
+#include <algorithm>
+#include <cmath>
+#include <cstdint>
+#include <vector>
+
+CMSketch::CMSketchDimensions CMSketch::CMSDimFromProb(double error, double delta) {
+ CMSketchDimensions dims;
+ dims.width = std::ceil(2 / error);
+ dims.depth = std::ceil(std::log10(delta) / std::log10(0.5));
+ return dims;
+}
+
+size_t CMSketch::IncrBy(std::string_view item, uint32_t value) {
+ size_t min_count = std::numeric_limits<size_t>::max();
+
+ for (size_t i = 0; i < depth_; ++i) {
+ uint64_t hash = HllMurMurHash64A(item.data(), static_cast<int>(item.size()), i);
Review Comment:
Please, a uint64_t as hash might overflows uint32_t, making `array_` likely to randomly set uint32 max
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@kvrocks.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat: support count min sketch data structure and most commands [kvrocks]
Posted by "mapleFU (via GitHub)" <gi...@apache.org>.
mapleFU commented on PR #2524:
URL: https://github.com/apache/kvrocks/pull/2524#issuecomment-2350702696
@jonathanc-n would you mind fix the lint?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@kvrocks.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org