[prev in list] [next in list] [prev in thread] [next in thread]
List: rhq-commits
Subject: [rhq] modules/enterprise
From: John Sanda <jsanda () fedoraproject ! org>
Date: 2013-12-12 15:15:11
Message-ID: 20131212151511.20DA161132 () fedorahosted ! org
[Download RAW message or body]
modules/enterprise/remoting/cli/src/main/samples/modules/rhq.storage.sizing.js | \
117 +++++++++- 1 file changed, 114 insertions(+), 3 deletions(-)
New commits:
commit ed941d7573d2d3c5ae63a11c53ecaa2d990ca65a
Author: John Sanda <jsanda@redhat.com>
Date: Thu Dec 12 10:14:12 2013 -0500
calculate bloom filters
diff --git a/modules/enterprise/remoting/cli/src/main/samples/modules/rhq.storage.sizing.js \
b/modules/enterprise/remoting/cli/src/main/samples/modules/rhq.storage.sizing.js \
index 77c22fd..d185f56 100644
--- a/modules/enterprise/remoting/cli/src/main/samples/modules/rhq.storage.sizing.js
+++ b/modules/enterprise/remoting/cli/src/main/samples/modules/rhq.storage.sizing.js
@@ -24,8 +24,113 @@
var time = new Time();
+ function BloomFilter(keys) {
+ function BloomSpecification(k, bucketsPerElement) {
+ this.K = k;
+ this.bucketsPerElement = bucketsPerElement;
+ }
+
+ // This is taken directly from BloomCalculations.java
+ this.probs = [
+ [1.0], // dummy row representing 0 buckets per element
+ [1.0, 1.0], // dummy row representing 1 buckets per element
+ [1.0, 0.393, 0.400],
+ [1.0, 0.283, 0.237, 0.253],
+ [1.0, 0.221, 0.155, 0.147, 0.160],
+ [1.0, 0.181, 0.109, 0.092, 0.092, 0.101], // 5
+ [1.0, 0.154, 0.0804, 0.0609, 0.0561, 0.0578, 0.0638],
+ [1.0, 0.133, 0.0618, 0.0423, 0.0359, 0.0347, 0.0364],
+ [1.0, 0.118, 0.0489, 0.0306, 0.024, 0.0217, 0.0216, 0.0229],
+ [1.0, 0.105, 0.0397, 0.0228, 0.0166, 0.0141, 0.0133, 0.0135, \
0.0145], + [1.0, 0.0952, 0.0329, 0.0174, 0.0118, 0.00943, 0.00844, 0.00819, \
0.00846], // 10 + [1.0, 0.0869, 0.0276, 0.0136, 0.00864, 0.0065, 0.00552, \
0.00513, 0.00509], + [1.0, 0.08, 0.0236, 0.0108, 0.00646, 0.00459, \
0.00371, 0.00329, 0.00314], + [1.0, 0.074, 0.0203, 0.00875, 0.00492, \
0.00332, 0.00255, 0.00217, 0.00199, 0.00194], + [1.0, 0.0689, 0.0177, \
0.00718, 0.00381, 0.00244, 0.00179, 0.00146, 0.00129, 0.00121, 0.0012], + \
[1.0, 0.0645, 0.0156, 0.00596, 0.003, 0.00183, 0.00128, 0.001, 0.000852, \
0.000775, 0.000744], // 15 + [1.0, 0.0606, 0.0138, 0.005, 0.00239, 0.00139, \
0.000935, 0.000702, 0.000574, 0.000505, 0.00047, 0.000459], + [1.0, 0.0571, \
0.0123, 0.00423, 0.00193, 0.00107, 0.000692, 0.000499, 0.000394, 0.000335, \
0.000302, 0.000287, 0.000284], + [1.0, 0.054, 0.0111, 0.00362, 0.00158, \
0.000839, 0.000519, 0.00036, 0.000275, 0.000226, 0.000198, 0.000183, 0.000176], + \
[1.0, 0.0513, 0.00998, 0.00312, 0.0013, 0.000663, 0.000394, 0.000264, 0.000194, \
0.000155, 0.000132, 0.000118, 0.000111, 0.000109], + [1.0, 0.0488, 0.00906, \
0.0027, 0.00108, 0.00053, 0.000303, 0.000196, 0.00014, 0.000108, 8.89e-05, \
7.77e-05, 7.12e-05, 6.79e-05, 6.71e-05] // 20 + ]; // the first column is a dummy \
column representing K=0. +
+ var self = this;
+ var excess = 20;
+ var bitset_excess = 20;
+ var minBuckets = 2;
+ var minK = 1;
+ var optKPerBuckets = [];
+ var maxFalsePosProb = 0.01;
+
+
+ for (i = 0; i < this.probs.length; i++) {
+ var min = java.lang.Double.MAX_VALUE;
+ var prob = this.probs[i];
+ for (j = 0; j < prob.length; j++) {
+ if (prob[j] < min) {
+ min = prob[j];
+ optKPerBuckets[i] = Math.max(minK, j);
+ }
+ }
+ }
+
+ var bucketsPerElement = maxBucketsPerElement(keys);
+ var spec = computeBloomSpec(bucketsPerElement, maxFalsePosProb);
+ var numBits = (keys * spec.bucketsPerElement) + bitset_excess;
+ var wordCount = bits2words(numBits);
+
+ if (wordCount > java.lang.Integer.MAX_VALUE) {
+ throw "Bloom filter size is > 16GB, reduce the bloom_filter_fp_chance";
+ }
+
+ var bytes = wordCount * 8;
+ this.size = bytes + 8;
+
+ function maxBucketsPerElement(numElements) {
+ numElements = Math.max(1, numElements);
+ var v = (java.lang.Long.MAX_VALUE - excess) / keys;
+ if (v < 1) {
+ throw "Cannot compute probabilities for " + numElements + " elements.";
+ }
+ return Math.min(self.probs.length - 1, v);
+ }
+
+ // This is taken from BloomCalculations.java
+ function computeBloomSpec(maxBucketsPerElement, maxFalsePosProb) {
+ var maxK = self.probs[maxBucketsPerElement].length - 1;
+
+ // Handle the trivial cases
+ if(maxFalsePosProb >= self.probs[minBuckets][minK]) {
+ return new BloomSpecification(2, optKPerBuckets[2]);
+ }
+ if (maxFalsePosProb < self.probs[maxBucketsPerElement][maxK]) {
+ throw "Unable to satisfy " + maxFalsePosProb + " with " + \
maxBucketsPerElement + " buckets per element"; + }
+
+ // First find the minimal required number of buckets:
+ var bucketsPerElement = 2;
+ var K = optKPerBuckets[2];
+ while(self.probs[bucketsPerElement][K] > maxFalsePosProb){
+ bucketsPerElement++;
+ K = optKPerBuckets[bucketsPerElement];
+ }
+ // Now that the number of buckets is sufficient, see if we can relax K
+ // without losing too much precision.
+ while(self.probs[bucketsPerElement][K - 1] <= maxFalsePosProb) {
+ K--;
+ }
+ println('K = ' + K + ', bucketsPerElement = ' + bucketsPerElement);
+ return new BloomSpecification(K, bucketsPerElement);
+ }
+
+ function bits2words(numBits) {
+ return (((numBits-1)>>>6)+1);
+ }
+ }
+
/**
- * Encapsulates sizing data for a set of rows, having the samae number of columns \
and + * Encapsulates sizing data for a set of rows, having the same number of \
columns and
* each column being the same size.
*/
function RowInfo() {
@@ -124,6 +229,7 @@
schedules) {
var table = new Table(name);
table.data = calculateData(schedules, columnSize, rowKeySize, duration);
+ table.bloomFilter = new BloomFilter(5).size;
util.foreach(table.data.rows, function(interval) {
var rowInfo = table.data.rows[interval];
@@ -216,8 +322,8 @@
var rowKeyValueSize = 4;
var columnNameSize = 8;
- return calculateMetricsTableSize('raw_metrics', columnSize, rowKeySize, \
rowKeyValueSize, columnNameSize, time.week,
- schedules);
+ return calculateMetricsTableSize('raw_metrics', columnSize, rowKeySize, \
rowKeyValueSize, columnNameSize, + time.week, schedules);
};
/**
@@ -261,4 +367,9 @@
exports.sizeOf24HourMetrics = function(schedules) {
return calculateAggregatesTableSize('twenty_four_hour_metrics', time.day * 365, \
schedules); };
+
+ // exposed for testing
+ exports.bloomFilter = function(keys) {
+ return new BloomFilter(keys).size;
+ }
})();
\ No newline at end of file
_______________________________________________
rhq-commits mailing list
rhq-commits@lists.fedorahosted.org
https://lists.fedorahosted.org/mailman/listinfo/rhq-commits
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic