5 ms·

This is nice. At my last job, we developed an extremely high performance HyperLogLog server (hlld). Take a look if you're interested: https://github.com/armon/

This is nice. At my last job, we developed an extremely high performance HyperLogLog server (hlld). Take a look if you're interested: https://github.com/armon/hlld https://github.com/armon/hlld It processes over a 1MM ops per second on a basic MacBook Air. In production we saw it handle more. We never had to scale it over one server in order to handle millions of distinct metrics. As an ad company, my last company had a ridiculous fanout of metrics for every request. Every ad serve API request (of which we got thousands per second) would fan out to over 150 metrics EACH. So for 1000 requests per second we'd have to modify 150,000 metrics. Raw SQL updates of course fall down with this (even if we tone back their durability). Instead, we opted for accumulated for 10 to 60 seconds in bloomd and hlld and statsite, then aggregating and doing a single bulk SQL update. Worked incredibly well. We used it in combination with bloomd: https://github.com/armon/bloomd https://github.com/armon/bloomd Bloomd is another super high performance data structure server, but this time for bloom filters. You can read the READMEs to learn why they're better for their specific tasks. Both have been running in production for 2+ years. If you're not going to be using the data structures that much then Redis is a good choice. We personally used these servers alongside Redis for k/v.

arielweisberg 13y ago
There are several databases that will do 150k replicated updates a second on a 2 socket server. Heck, 150k multi-statement transactions has been realistic for years. 1 million on a MacBook air no, not yet. Not enough caching, JITing and precompilation to optimize away the overhead of SQL in anything that currently exists. This is not to talk down using the right tool for the job, but as soon as you want to do something a little more complicated than count you are right back to reinventing databases. That is basically what you are doing by implementing periodic group commit on top of a database.
- AaronFriel 13y ago
  Oh, there are dozens of databases that will do 150k transactions per second. The issue with database throughput for most applications is the storage layer, which is more difficult to fine tune when working with a cloud service. With Azure, you have to use one of their very large instances and connect and stripe virtual disks yourself to hit 40k IOs per second, and I think that's just barely possible. With Amazon, you are limited to about 48k IOPS and again, you have to use EBS and provisioned IOPS disks and stripe. Not sure about Google's services.
  - MichaelGG 13y ago
    Or take the VoltDB way and persist to memory (in the commercial version AFAIK).
    - AaronFriel 13y ago
      I would heartily disagree with their definition of persistence.
- mitchellh 13y ago
  We would've preferred to not have to write these things. If you knew me you'd know I'm not a "build things because we can" type of person. We spent a week tuning PostgreSQL trying to get it fast enough, and couldn't (due to the restrictions of ACID we were trying to break). We then hired an outside DB consultancy for a handful of hours, since they claimed they could do it, since consultants for a few hours is cheaper than us writing a DB, and they ultimately came back and said "SQL isn't the right choice for this." I can see how you can make your comment without understanding this context and more. But really, I promise you SQL didn't work AT ALL. This is primarily due to the type of data we were putting in there: we needed some aggregates like totals, averages, standard deviation, etc. To get this data, you need to have it inserted first, and we were requesting on the fly in real time at a pretty large rate. This would cause the CPU of the SQL servers to go up pretty hard WHILE also serving hundreds of thousands of insert/update ops/sec. We could've solved this by adding read slaves and all that, but now we're talking expensive CapEx for something we were confident we could fix with some C in a week or two. Enter: the two servers linked in my parent comment. We sacrificed durability, accuracy, and some level of safety (if the server crashes before an accumulation period once every X seconds, you lose that data) for raw speed. We calculated out the acceptable tolerances (max % off the real value) and tuned our data structures to that (bloomd and hlld both expose these tunables). We then ran both servers in parallel to our existing SQL solution for a few weeks to verify the numbers were correct. Finally, we switched over. Like I said, when we built that we were doing maybe 450,000 metrics per second. That was 2 years ago. Now they're doing much much more than that, and both hlld and bloomd are running on a single m3.medium with no persistence (they aggregate then issue a single large UPDATE to SQL) with no issue. The amortized operating expenses (human labor) cost of developing the servers, along with the thousands saved in server costs, and with the effectively zero ops overhead (they never go down, they're stateless, etc.) has been well worth it. Hope that makes our decision a little clearer.
  - wpietri 13y ago
    Very well put. I think people who have only built SQL-based solutions tend to underestimate the labor and ops overhead of SQL-based solutions for problems that don't fit the typical SQL use cases very well. It's nice to read of a long-running example like this.
- SubuSS 13y ago
  Can you point me to one such perf benchmark? Thx.
antirez 13y ago
Hello! I'm sure a specialized server can use even the latest couple clock cycles at its best, but the Redis implementation performs very reasonably. I ran the following two benchmark simultaneously against my Macbook Air 11" that are able to trigger the worst case scenario from the point of view of the HLL data structure: ./redis-benchmark -P 64 -r 100000000 -n 100000000 \ pfadd hll __rand_int__ pfadd hll __rand_int__: 320125.56 And ./redis-benchmark -P 64 -r 100000000 -n 100000000 \ pfcount hll pfcount hll: 313309.62 Since we are adding random integers in the range from 0 to 100 million we are basically triggering the worst case in which the updates are as frequent as possible in the registers. At the same time HLLCOUNT is running in the other benchmark forcing the update of the cached cardinality as often as possible. Yet we get around 640k ops/sec in a single core, that multiplied for the 4 cores of an Air i7 gets you to 2.4m ops/sec. EDIT 1: Note that while I'm using random data as argument of PFADD, we are not using N HLLs but a single one, so tis benchmark is surely biased as cache misses are rare. But using multiple keys will not be terrible like losing an order of magnitude, just a reasonable percentage of OPS will go away. EDIT 2: I had a process running in background consuming a lot of CPU, actually I tried again and reached 900k OPS/sec for core, but read EDIT 1 for more info.
- mitchellh 13y ago
  Yes, Redis performs well. I don't think I ever actually compared to hlld to Redis in my comment, except to say you LOSE data structures by using hlld specifically. I was not making a comparison. I was showing another potential solution.
  - antirez 13y ago
    No problem at all with comparing! And thanks for commenting. I wrote my message since you wrote "If you're looking for much higher performance than what Redis ...". My idea is just that at the level of performance of the HLL Redis implementation to add a new component to an infrastructure for the sake of faster HLL should be considered with care, but specialized solutions may be better in many regards of course.
  - VikingCoder 13y ago
pinars 13y ago
As a quick side note, PostgreSQL had the HyperLogLog data type for a while: https://github.com/aggregateknowledge/postgresql-hll https://github.com/aggregateknowledge/postgresql-hll For people who need SQL and HyperLogLog, we found this extension to work pretty well.
zheng 13y ago
Just wanted to say thank you for hlld/bloomd! At my old company we were looking into uses for them just because the idea and footprint was so cool. We had a couple ideas for hlld and the overhead was so small that we could basically add it to our servers for free.
pimeys 13y ago
Also working in an ad company and also using bloomd, it rocks. For HyperLogLog, we actually utilize our column based big data store. It is possible, also pretty easily, to create the HyperLogLog algorithm as an SQL query, which we can use to aggregate several useful metrics. This is super useful when you can combine it easily with several other metrics that are not using the HyperLogLog, e.g. making another facts table for your star schema.
hangonhn 13y ago
You can expand on how you combined it with bloomd? Thanks.

arielweisberg 13y ago

There are several databases that will do 150k replicated updates a second on a 2 socket server. Heck, 150k multi-statement transactions has been realistic for years. 1 million on a MacBook air no, not yet. Not enough caching, JITing and precompilation to optimize away the overhead of SQL in anything that currently exists. This is not to talk down using the right tool for the job, but as soon as you want to do something a little more complicated than count you are right back to reinventing databases. That is basically what you are doing by implementing periodic group commit on top of a database.

AaronFriel 13y ago
Oh, there are dozens of databases that will do 150k transactions per second. The issue with database throughput for most applications is the storage layer, which is more difficult to fine tune when working with a cloud service. With Azure, you have to use one of their very large instances and connect and stripe virtual disks yourself to hit 40k IOs per second, and I think that's just barely possible. With Amazon, you are limited to about 48k IOPS and again, you have to use EBS and provisioned IOPS disks and stripe. Not sure about Google's services.
- MichaelGG 13y ago
  Or take the VoltDB way and persist to memory (in the commercial version AFAIK).
  - AaronFriel 13y ago
    I would heartily disagree with their definition of persistence.
mitchellh 13y ago
We would've preferred to not have to write these things. If you knew me you'd know I'm not a "build things because we can" type of person. We spent a week tuning PostgreSQL trying to get it fast enough, and couldn't (due to the restrictions of ACID we were trying to break). We then hired an outside DB consultancy for a handful of hours, since they claimed they could do it, since consultants for a few hours is cheaper than us writing a DB, and they ultimately came back and said "SQL isn't the right choice for this." I can see how you can make your comment without understanding this context and more. But really, I promise you SQL didn't work AT ALL. This is primarily due to the type of data we were putting in there: we needed some aggregates like totals, averages, standard deviation, etc. To get this data, you need to have it inserted first, and we were requesting on the fly in real time at a pretty large rate. This would cause the CPU of the SQL servers to go up pretty hard WHILE also serving hundreds of thousands of insert/update ops/sec. We could've solved this by adding read slaves and all that, but now we're talking expensive CapEx for something we were confident we could fix with some C in a week or two. Enter: the two servers linked in my parent comment. We sacrificed durability, accuracy, and some level of safety (if the server crashes before an accumulation period once every X seconds, you lose that data) for raw speed. We calculated out the acceptable tolerances (max % off the real value) and tuned our data structures to that (bloomd and hlld both expose these tunables). We then ran both servers in parallel to our existing SQL solution for a few weeks to verify the numbers were correct. Finally, we switched over. Like I said, when we built that we were doing maybe 450,000 metrics per second. That was 2 years ago. Now they're doing much much more than that, and both hlld and bloomd are running on a single m3.medium with no persistence (they aggregate then issue a single large UPDATE to SQL) with no issue. The amortized operating expenses (human labor) cost of developing the servers, along with the thousands saved in server costs, and with the effectively zero ops overhead (they never go down, they're stateless, etc.) has been well worth it. Hope that makes our decision a little clearer.
- wpietri 13y ago
  Very well put. I think people who have only built SQL-based solutions tend to underestimate the labor and ops overhead of SQL-based solutions for problems that don't fit the typical SQL use cases very well. It's nice to read of a long-running example like this.
SubuSS 13y ago
Can you point me to one such perf benchmark? Thx.

antirez 13y ago

Hello! I'm sure a specialized server can use even the latest couple clock cycles at its best, but the Redis implementation performs very reasonably. I ran the following two benchmark simultaneously against my Macbook Air 11" that are able to trigger the worst case scenario from the point of view of the HLL data structure: ./redis-benchmark -P 64 -r 100000000 -n 100000000 \ pfadd hll __rand_int__ pfadd hll __rand_int__: 320125.56 And ./redis-benchmark -P 64 -r 100000000 -n 100000000 \ pfcount hll pfcount hll: 313309.62 Since we are adding random integers in the range from 0 to 100 million we are basically triggering the worst case in which the updates are as frequent as possible in the registers. At the same time HLLCOUNT is running in the other benchmark forcing the update of the cached cardinality as often as possible. Yet we get around 640k ops/sec in a single core, that multiplied for the 4 cores of an Air i7 gets you to 2.4m ops/sec. EDIT 1: Note that while I'm using random data as argument of PFADD, we are not using N HLLs but a single one, so tis benchmark is surely biased as cache misses are rare. But using multiple keys will not be terrible like losing an order of magnitude, just a reasonable percentage of OPS will go away. EDIT 2: I had a process running in background consuming a lot of CPU, actually I tried again and reached 900k OPS/sec for core, but read EDIT 1 for more info.

mitchellh 13y ago
Yes, Redis performs well. I don't think I ever actually compared to hlld to Redis in my comment, except to say you LOSE data structures by using hlld specifically. I was not making a comparison. I was showing another potential solution.
- antirez 13y ago
  No problem at all with comparing! And thanks for commenting. I wrote my message since you wrote "If you're looking for much higher performance than what Redis ...". My idea is just that at the level of performance of the HLL Redis implementation to add a new component to an infrastructure for the sake of faster HLL should be considered with care, but specialized solutions may be better in many regards of course.
- VikingCoder 13y ago

pinars 13y ago

As a quick side note, PostgreSQL had the HyperLogLog data type for a while: https://github.com/aggregateknowledge/postgresql-hll https://github.com/aggregateknowledge/postgresql-hll For people who need SQL and HyperLogLog, we found this extension to work pretty well.

zheng 13y ago

Just wanted to say thank you for hlld/bloomd! At my old company we were looking into uses for them just because the idea and footprint was so cool. We had a couple ideas for hlld and the overhead was so small that we could basically add it to our servers for free.

pimeys 13y ago

Also working in an ad company and also using bloomd, it rocks. For HyperLogLog, we actually utilize our column based big data store. It is possible, also pretty easily, to create the HyperLogLog algorithm as an SQL query, which we can use to aggregate several useful metrics. This is super useful when you can combine it easily with several other metrics that are not using the HyperLogLog, e.g. making another facts table for your star schema.

hangonhn 13y ago

You can expand on how you combined it with bloomd? Thanks.