--- title: Building a 2KB Histogram with Sub -0.2% Percentile Error description: Databend built base2histogram, a lightweight histogram library for tracking latency distributions inside a cloud-native data warehouse without slowing down the... canonical: https://daily.dev/posts/building-a-2kb-histogram-with-sub--0-2-percentile-error-qoiocscvi twitter:card: summary_large_image twitter:site: @dailydotdev og:type: website og:site_name: daily.dev og:title: Building a 2KB Histogram with Sub -0.2% Percentile Error | daily.dev og:description: Databend built base2histogram, a lightweight histogram library for tracking latency distributions inside a cloud-native data warehouse without slowing down the... og:url: https://daily.dev/posts/building-a-2kb-histogram-with-sub--0-2-percentile-error-qoiocscvi og:image: https://api.daily.dev/og/posts/QoIocscVI.png og:image:alt: Building a 2KB Histogram with Sub -0.2% Percentile Error og:image:width: 1200 og:image:height: 630 og:locale: en --- > ## Documentation Index > Fetch the complete documentation index at: https://daily.dev/llms.txt > Use this file to discover all available pages before exploring further. # Building a 2KB Histogram with Sub -0.2% Percentile Error **[Databend Blog](https://daily.dev/sources/databend)** · 9 min read · 0 upvotes · 0 comments ## Summary Databend built base2histogram, a lightweight histogram library for tracking latency distributions inside a cloud-native data warehouse without slowing down the hot path. It uses float-like bucket encoding (power-of-two groups with a WIDTH parameter controlling sub-bucket resolution) so recording a sample is O(1) via bit operations rather than sorting or rebalancing. At the default WIDTH=3, a histogram uses 2 KB of memory and covers the full u64 range with 252 buckets. For percentile estimation, the design introduces trapezoid interpolation, which infers density slope from neighboring buckets to estimate where within a bucket a percentile falls, cutting error from ~5-7% (midpoint method) to under 0.2% for log-normal latency distributions like API and database query latency. The library is open-sourced on GitHub. ## Full article daily.dev links to this article rather than hosting it. Read it at the original source: ## Questions this post answers ### How can I estimate latency percentiles more accurately from a histogram without storing extra data per bucket? Trapezoid interpolation estimates percentiles by inferring the density slope through a bucket from its two neighboring buckets, rather than assuming a flat or midpoint distribution. Using only the counts and boundaries of three adjacent buckets, this approach reduced percentile error from around 5-7% with midpoint estimation to under 0.2% for log-normal latency distributions, with zero additional storage. _daily.dev surfaces engineering deep dives like this for developers refining their own metrics pipelines._ ### How much memory does a histogram need to track latency percentiles with low error using base2histogram? At the default WIDTH=3 setting, base2histogram uses 2 KB of memory per histogram, covering 252 buckets across the full u64 range, and achieves sub-0.2% error on P50, P95, and P99 for log-normal latency workloads such as API and database query latency, using 1,000,000 sample benchmarks. WIDTH can be tuned from 520 B up to 15 KB for different precision needs. _track down memory-versus-precision tradeoffs like this one on daily.dev when tuning observability internals._ ### Why use power-of-two log-scale buckets instead of a smaller growth factor like 1.1x for a latency histogram? Power-of-two buckets let bucket indexing use a single leading-zero-count instruction, making recording O(1), whereas a 1.1x growth factor requires solving an exponential inequality to locate the correct bucket, which is far more expensive per sample. Float-like encoding with a fixed WIDTH parameter keeps bucket sizes roughly exponential while staying purely integer and bit-operation based. _developers weighing bucket-sizing tradeoffs for metrics systems can find write-ups like this on daily.dev._ ## Similar posts on daily.dev - [Create histogram metrics at ingest with OpenPipeline](https://daily.dev/posts/create-histogram-metrics-at-ingest-with-openpipeline-imvvjymcj) · Dynatrace · 0 upvotes · 0 comments - [On programming, statistics, and Java](https://daily.dev/posts/on-programming-statistics-and-java-8d0gstmw0) · Awesome Java Newsletter · 0 upvotes · 0 comments - [The 200ms latency: A developer’s guide to real-time personalization](https://daily.dev/posts/the-200ms-latency-a-developer-s-guide-to-real-time-personalization-u7s5bwkwz) · InfoWorld · 0 upvotes · 0 comments - [High Performance Rate Limiting at Databricks](https://daily.dev/posts/high-performance-rate-limiting-at-databricks-lln88cxlb) · ByteByteGo · 13 upvotes · 0 comments --- Tags: [#performance](https://daily.dev/tags/performance), [#rust](https://daily.dev/tags/rust), [#observability](https://daily.dev/tags/observability) [View this post on daily.dev](https://daily.dev/posts/building-a-2kb-histogram-with-sub--0-2-percentile-error-qoiocscvi) ```json {"@context":"https://schema.org","@graph":[{"@type":"Organization","@id":"https://daily.dev/#organization","name":"daily.dev","url":"https://daily.dev","logo":{"@type":"ImageObject","url":"https://daily.dev/apple-touch-icon.png","width":180,"height":180},"sameAs":["https://twitter.com/dailydotdev","https://github.com/dailydotdev","https://www.linkedin.com/company/daily-dev-ltd"]},{"@type":"WebSite","@id":"https://daily.dev/#website","url":"https://daily.dev","name":"daily.dev","publisher":{"@id":"https://daily.dev/#organization"},"potentialAction":{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https://daily.dev/search?q={search_term_string}"},"query-input":"required name=search_term_string"}}]} {"@context":"https://schema.org","@type":"TechArticle","headline":"Building a 2KB Histogram with Sub -0.2% Percentile Error","url":"https://daily.dev/posts/building-a-2kb-histogram-with-sub--0-2-percentile-error-qoiocscvi","mainEntityOfPage":{"@type":"WebPage","@id":"https://daily.dev/posts/building-a-2kb-histogram-with-sub--0-2-percentile-error-qoiocscvi"},"datePublished":"2026-08-16T08:53:56.803Z","dateModified":"2026-08-16T08:58:20.013Z","description":"Databend built base2histogram, a lightweight histogram library for tracking latency distributions inside a cloud-native data warehouse without slowing down the...","image":"https://media.daily.dev/image/upload/f_auto,q_auto/v1/posts/30c0c7cf5c8f06fad3f23bfa053cb1b1?_a=AQAEuop","thumbnailUrl":"https://media.daily.dev/image/upload/f_auto,q_auto/v1/posts/30c0c7cf5c8f06fad3f23bfa053cb1b1?_a=AQAEuop","isAccessibleForFree":true,"articleSection":"Databend Blog","inLanguage":"en","publisher":{"@type":"Organization","name":"daily.dev","url":"https://daily.dev","logo":{"@type":"ImageObject","url":"https://daily.dev/apple-touch-icon.png","width":180,"height":180}},"author":{"@type":"Organization","name":"Databend Blog","logo":"https://media.daily.dev/image/upload/s--Vkqa36Ma--/f_auto,q_auto/v1786870423/logos/databend?_a=BAMAMicg0","url":"https://daily.dev/sources/databend"},"commentCount":0,"discussionUrl":"https://daily.dev/posts/building-a-2kb-histogram-with-sub--0-2-percentile-error-qoiocscvi","interactionStatistic":[{"@type":"InteractionCounter","interactionType":{"@type":"LikeAction"},"userInteractionCount":0},{"@type":"InteractionCounter","interactionType":{"@type":"CommentAction"},"userInteractionCount":0}],"keywords":"performance,rust,observability","timeRequired":"PT9M"} {"@context":"https://schema.org","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https://daily.dev"},{"@type":"ListItem","position":2,"name":"Databend Blog","item":"https://daily.dev/sources/databend"},{"@type":"ListItem","position":3,"name":"Building a 2KB Histogram with Sub -0.2% Percentile Error"}]} {"@context":"https://schema.org","@type":"FAQPage","@id":"https://daily.dev/posts/building-a-2kb-histogram-with-sub--0-2-percentile-error-qoiocscvi#faq","mainEntity":[{"@type":"Question","name":"How can I estimate latency percentiles more accurately from a histogram without storing extra data per bucket?","acceptedAnswer":{"@type":"Answer","text":"Trapezoid interpolation estimates percentiles by inferring the density slope through a bucket from its two neighboring buckets, rather than assuming a flat or midpoint distribution. Using only the counts and boundaries of three adjacent buckets, this approach reduced percentile error from around 5-7% with midpoint estimation to under 0.2% for log-normal latency distributions, with zero additional storage. daily.dev surfaces engineering deep dives like this for developers refining their own metrics pipelines."}},{"@type":"Question","name":"How much memory does a histogram need to track latency percentiles with low error using base2histogram?","acceptedAnswer":{"@type":"Answer","text":"At the default WIDTH=3 setting, base2histogram uses 2 KB of memory per histogram, covering 252 buckets across the full u64 range, and achieves sub-0.2% error on P50, P95, and P99 for log-normal latency workloads such as API and database query latency, using 1,000,000 sample benchmarks. WIDTH can be tuned from 520 B up to 15 KB for different precision needs. track down memory-versus-precision tradeoffs like this one on daily.dev when tuning observability internals."}},{"@type":"Question","name":"Why use power-of-two log-scale buckets instead of a smaller growth factor like 1.1x for a latency histogram?","acceptedAnswer":{"@type":"Answer","text":"Power-of-two buckets let bucket indexing use a single leading-zero-count instruction, making recording O(1), whereas a 1.1x growth factor requires solving an exponential inequality to locate the correct bucket, which is far more expensive per sample. Float-like encoding with a fixed WIDTH parameter keeps bucket sizes roughly exponential while staying purely integer and bit-operation based. developers weighing bucket-sizing tradeoffs for metrics systems can find write-ups like this on daily.dev."}}]} ```