mirror of
https://github.com/hanzoai/traces.git
synced 2026-10-30 18:20:41 +00:00
049323c40f
* starting parquet support starting parquet support. some things are still todo: compaction, find trace by ID Co-Authored-By: Annanay Agarwal <[email protected]> Co-Authored-By: Martin Disibio <[email protected]> * add parquet reusable streaming block * Add parquet compaction * Add findTraceByID logic and parquet -> proto conversion Signed-off-by: Annanay <[email protected]> * Switch findtracebyid to readrow until we get SeekToRow working * Fix error handling in bufferedReaderAt. Add various instrumentation and log messages * Use jsonpb to roundtrip event attributes * Improve buffered reader when reading near end of file. More instrumentation and tidiness * Add totalBlockBytes instrumentation. Fix inspectedBytes instrumentation * parquet.FindTraceByID check bloom * Make compator flush on trace count until we get the row group size target working * Support maxDuration in parquet search * Correct attribute translation for array/kvlist Signed-off-by: Annanay <[email protected]> * extend roundtrip test Signed-off-by: Annanay <[email protected]> * Use default page buffer size * Fix size url param to be uint64 * Increase parquet searches to 1MB stripes * Add test for findtracebyid * make row group size configurable Signed-off-by: Annanay <[email protected]> * Record parquet footer size in block meta and short-circuit header/footer reads * Add tests for SubstringPredicate * Switch compaction to compact blocks of same version, use re-usable buffer in findtracebyid Signed-off-by: Annanay <[email protected]> * Add search support for remaining well-known attributes and span status, add search tests * Benchmark substringPredicate * Make block version configurable, default to v2 * memoize substringPredicate * Update segmentio/parquet-go to catch SeekToRow fix, revert hack in FindTraceByID Signed-off-by: Annanay <[email protected]> * Add multi block prefetch iterator for use in compactor Signed-off-by: Annanay <[email protected]> * Add BufferedWriter with outgoing queue to flush traces async Signed-off-by: Annanay <[email protected]> Make compactor block complete async Signed-off-by: Annanay <[email protected]> * First pass CLI to dump schema and column sizes from block Signed-off-by: Annanay <[email protected]> * honor search start/end time range * Improve error message, add blockID Signed-off-by: Annanay <[email protected]> * Fix race in InstrumentedPredicate with atomics * Make bufferedReaderAt not single-threaded * Debug SeekToRow panic, add test data from vulture tenant Signed-off-by: Annanay <[email protected]> * fix test * repair tests * Address println warnings * Experiment with bookmark prefetch Signed-off-by: Annanay <[email protected]> Remove quitCh from bookmark Signed-off-by: Annanay <[email protected]> * fix prefetch on the bookmarks Signed-off-by: Annanay <[email protected]> * lint * tracker -> RowNumber, lint * delete unused predicates * lint * lint * mod vendor * remove pool from buffered writer queue Signed-off-by: Annanay <[email protected]> * post merge cleanup Signed-off-by: Annanay <[email protected]> * Close quitCh instead of attempting to signal to it Signed-off-by: Annanay <[email protected]> * split multiblock and prefetch iterators, refactor around interface Signed-off-by: Annanay <[email protected]> * Split search into 2 phases to avoid loading traceid/display columns unless there is a match * Make columnIterator.SeekTo do something * update to catch segmentio/parquet-go#220 Signed-off-by: Annanay <[email protected]> * Fix column index to store entire 32-byte trace ID string. lint * Make parquet honor the adjusted start/end times that come from the wal * post merge cleanup: use compaction metric callbacks Signed-off-by: Annanay <[email protected]> * serverless sum/mods Signed-off-by: Annanay <[email protected]> * parquetquery predicates handle column index not present * Make parquet compaction really honor input block start/end times, add universal test at tempodb-level * parquet skip page indexes while searching to reduce latency on openfile * More testing around iterators and combiner Signed-off-by: Annanay <[email protected]> * Update to latest parquet lib to catch rle bitpack fix * Review feedback: LatestEncoding -> DefaultEncoding * Pass block footerSize through serverless * mod vendor for serverless * Fix tests * add blockID to error message in block iterator Signed-off-by: Annanay <[email protected]> * increase readvalues buffer, add more span instrumentation Signed-off-by: Annanay <[email protected]> * changelog and docs * Remove the use of async writer in vparquet compactor Signed-off-by: Annanay <[email protected]> Co-authored-by: Annanay Agarwal <[email protected]>
291 lines
6.0 KiB
Go
291 lines
6.0 KiB
Go
package brotli
|
|
|
|
import (
|
|
"math"
|
|
"math/bits"
|
|
)
|
|
|
|
/* Copyright 2013 Google Inc. All Rights Reserved.
|
|
|
|
Distributed under MIT license.
|
|
See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
|
|
*/
|
|
|
|
/* Utilities for fast computation of logarithms. */
|
|
|
|
func log2FloorNonZero(n uint) uint32 {
|
|
return uint32(bits.Len(n)) - 1
|
|
}
|
|
|
|
/* A lookup table for small values of log2(int) to be used in entropy
|
|
computation.
|
|
|
|
", ".join(["%.16ff" % x for x in [0.0]+[log2(x) for x in range(1, 256)]]) */
|
|
var kLog2Table = []float32{
|
|
0.0000000000000000,
|
|
0.0000000000000000,
|
|
1.0000000000000000,
|
|
1.5849625007211563,
|
|
2.0000000000000000,
|
|
2.3219280948873622,
|
|
2.5849625007211561,
|
|
2.8073549220576042,
|
|
3.0000000000000000,
|
|
3.1699250014423126,
|
|
3.3219280948873626,
|
|
3.4594316186372978,
|
|
3.5849625007211565,
|
|
3.7004397181410922,
|
|
3.8073549220576037,
|
|
3.9068905956085187,
|
|
4.0000000000000000,
|
|
4.0874628412503400,
|
|
4.1699250014423122,
|
|
4.2479275134435852,
|
|
4.3219280948873626,
|
|
4.3923174227787607,
|
|
4.4594316186372973,
|
|
4.5235619560570131,
|
|
4.5849625007211570,
|
|
4.6438561897747244,
|
|
4.7004397181410926,
|
|
4.7548875021634691,
|
|
4.8073549220576037,
|
|
4.8579809951275728,
|
|
4.9068905956085187,
|
|
4.9541963103868758,
|
|
5.0000000000000000,
|
|
5.0443941193584534,
|
|
5.0874628412503400,
|
|
5.1292830169449664,
|
|
5.1699250014423122,
|
|
5.2094533656289501,
|
|
5.2479275134435852,
|
|
5.2854022188622487,
|
|
5.3219280948873626,
|
|
5.3575520046180838,
|
|
5.3923174227787607,
|
|
5.4262647547020979,
|
|
5.4594316186372973,
|
|
5.4918530963296748,
|
|
5.5235619560570131,
|
|
5.5545888516776376,
|
|
5.5849625007211570,
|
|
5.6147098441152083,
|
|
5.6438561897747244,
|
|
5.6724253419714961,
|
|
5.7004397181410926,
|
|
5.7279204545631996,
|
|
5.7548875021634691,
|
|
5.7813597135246599,
|
|
5.8073549220576046,
|
|
5.8328900141647422,
|
|
5.8579809951275719,
|
|
5.8826430493618416,
|
|
5.9068905956085187,
|
|
5.9307373375628867,
|
|
5.9541963103868758,
|
|
5.9772799234999168,
|
|
6.0000000000000000,
|
|
6.0223678130284544,
|
|
6.0443941193584534,
|
|
6.0660891904577721,
|
|
6.0874628412503400,
|
|
6.1085244567781700,
|
|
6.1292830169449672,
|
|
6.1497471195046822,
|
|
6.1699250014423122,
|
|
6.1898245588800176,
|
|
6.2094533656289510,
|
|
6.2288186904958804,
|
|
6.2479275134435861,
|
|
6.2667865406949019,
|
|
6.2854022188622487,
|
|
6.3037807481771031,
|
|
6.3219280948873617,
|
|
6.3398500028846252,
|
|
6.3575520046180847,
|
|
6.3750394313469254,
|
|
6.3923174227787598,
|
|
6.4093909361377026,
|
|
6.4262647547020979,
|
|
6.4429434958487288,
|
|
6.4594316186372982,
|
|
6.4757334309663976,
|
|
6.4918530963296748,
|
|
6.5077946401986964,
|
|
6.5235619560570131,
|
|
6.5391588111080319,
|
|
6.5545888516776376,
|
|
6.5698556083309478,
|
|
6.5849625007211561,
|
|
6.5999128421871278,
|
|
6.6147098441152092,
|
|
6.6293566200796095,
|
|
6.6438561897747253,
|
|
6.6582114827517955,
|
|
6.6724253419714952,
|
|
6.6865005271832185,
|
|
6.7004397181410917,
|
|
6.7142455176661224,
|
|
6.7279204545631988,
|
|
6.7414669864011465,
|
|
6.7548875021634691,
|
|
6.7681843247769260,
|
|
6.7813597135246599,
|
|
6.7944158663501062,
|
|
6.8073549220576037,
|
|
6.8201789624151887,
|
|
6.8328900141647422,
|
|
6.8454900509443757,
|
|
6.8579809951275719,
|
|
6.8703647195834048,
|
|
6.8826430493618416,
|
|
6.8948177633079437,
|
|
6.9068905956085187,
|
|
6.9188632372745955,
|
|
6.9307373375628867,
|
|
6.9425145053392399,
|
|
6.9541963103868758,
|
|
6.9657842846620879,
|
|
6.9772799234999168,
|
|
6.9886846867721664,
|
|
7.0000000000000000,
|
|
7.0112272554232540,
|
|
7.0223678130284544,
|
|
7.0334230015374501,
|
|
7.0443941193584534,
|
|
7.0552824355011898,
|
|
7.0660891904577721,
|
|
7.0768155970508317,
|
|
7.0874628412503400,
|
|
7.0980320829605272,
|
|
7.1085244567781700,
|
|
7.1189410727235076,
|
|
7.1292830169449664,
|
|
7.1395513523987937,
|
|
7.1497471195046822,
|
|
7.1598713367783891,
|
|
7.1699250014423130,
|
|
7.1799090900149345,
|
|
7.1898245588800176,
|
|
7.1996723448363644,
|
|
7.2094533656289492,
|
|
7.2191685204621621,
|
|
7.2288186904958804,
|
|
7.2384047393250794,
|
|
7.2479275134435861,
|
|
7.2573878426926521,
|
|
7.2667865406949019,
|
|
7.2761244052742384,
|
|
7.2854022188622487,
|
|
7.2946207488916270,
|
|
7.3037807481771031,
|
|
7.3128829552843557,
|
|
7.3219280948873617,
|
|
7.3309168781146177,
|
|
7.3398500028846243,
|
|
7.3487281542310781,
|
|
7.3575520046180847,
|
|
7.3663222142458151,
|
|
7.3750394313469254,
|
|
7.3837042924740528,
|
|
7.3923174227787607,
|
|
7.4008794362821844,
|
|
7.4093909361377026,
|
|
7.4178525148858991,
|
|
7.4262647547020979,
|
|
7.4346282276367255,
|
|
7.4429434958487288,
|
|
7.4512111118323299,
|
|
7.4594316186372973,
|
|
7.4676055500829976,
|
|
7.4757334309663976,
|
|
7.4838157772642564,
|
|
7.4918530963296748,
|
|
7.4998458870832057,
|
|
7.5077946401986964,
|
|
7.5156998382840436,
|
|
7.5235619560570131,
|
|
7.5313814605163119,
|
|
7.5391588111080319,
|
|
7.5468944598876373,
|
|
7.5545888516776376,
|
|
7.5622424242210728,
|
|
7.5698556083309478,
|
|
7.5774288280357487,
|
|
7.5849625007211561,
|
|
7.5924570372680806,
|
|
7.5999128421871278,
|
|
7.6073303137496113,
|
|
7.6147098441152075,
|
|
7.6220518194563764,
|
|
7.6293566200796095,
|
|
7.6366246205436488,
|
|
7.6438561897747244,
|
|
7.6510516911789290,
|
|
7.6582114827517955,
|
|
7.6653359171851765,
|
|
7.6724253419714952,
|
|
7.6794800995054464,
|
|
7.6865005271832185,
|
|
7.6934869574993252,
|
|
7.7004397181410926,
|
|
7.7073591320808825,
|
|
7.7142455176661224,
|
|
7.7210991887071856,
|
|
7.7279204545631996,
|
|
7.7347096202258392,
|
|
7.7414669864011465,
|
|
7.7481928495894596,
|
|
7.7548875021634691,
|
|
7.7615512324444795,
|
|
7.7681843247769260,
|
|
7.7747870596011737,
|
|
7.7813597135246608,
|
|
7.7879025593914317,
|
|
7.7944158663501062,
|
|
7.8008998999203047,
|
|
7.8073549220576037,
|
|
7.8137811912170374,
|
|
7.8201789624151887,
|
|
7.8265484872909159,
|
|
7.8328900141647422,
|
|
7.8392037880969445,
|
|
7.8454900509443757,
|
|
7.8517490414160571,
|
|
7.8579809951275719,
|
|
7.8641861446542798,
|
|
7.8703647195834048,
|
|
7.8765169465650002,
|
|
7.8826430493618425,
|
|
7.8887432488982601,
|
|
7.8948177633079446,
|
|
7.9008668079807496,
|
|
7.9068905956085187,
|
|
7.9128893362299619,
|
|
7.9188632372745955,
|
|
7.9248125036057813,
|
|
7.9307373375628867,
|
|
7.9366379390025719,
|
|
7.9425145053392399,
|
|
7.9483672315846778,
|
|
7.9541963103868758,
|
|
7.9600019320680806,
|
|
7.9657842846620870,
|
|
7.9715435539507720,
|
|
7.9772799234999168,
|
|
7.9829935746943104,
|
|
7.9886846867721664,
|
|
7.9943534368588578,
|
|
}
|
|
|
|
/* Faster logarithm for small integers, with the property of log2(0) == 0. */
|
|
func fastLog2(v uint) float64 {
|
|
if v < uint(len(kLog2Table)) {
|
|
return float64(kLog2Table[v])
|
|
}
|
|
|
|
return math.Log2(float64(v))
|
|
}
|