Baidu Takes FPGA Approach to Accelerating SQL at Scale | Hacker News Reader

Baidu Takes FPGA Approach to Accelerating SQL at Scale

nextplatform.com

179 pointsokket62 comments

This is kind of amazing. I have often really wondered what would happen if you basically created a directed acyclic graph/dataflow for data processing (for example, how Apache Spark distributes processing/operations), and then accelerated the operations using physical implementations in FPGAs. After all, a SQL query, when optimized, is essentially a graph of operators that data flows through.

You do have to pass your data through the accelerator to get the processing... which potentially means huge volumes of data moving into this physical processing layer (probably can be done in parallel over a network at high speed) - I would assume this is why shared memory bandwidth was a problem.

This would provide some really interesting options though - imagine feeding data from two disparate databases (say, Oracle and SQL server) in a data flow into this thing - now you have accelerated cross database joins (as long as you can handle the bandwidth and processing on the way in).

There was this post before on HN previously lamenting the state of tools for working with FPGAs, and my related comment wondering if what Baidu has done here was possible:

- https://news.ycombinator.com/item?id=9408881

- https://news.ycombinator.com/item?id=9410160

> which potentially means huge volumes of data moving into this physical processing layer

You get to cheat at that, because the naive implementation loads too much data, while most of it is going to drop off at the filter level.

The ideal TPC-DS schema stores data partitioned by date and maintains a lookup index by item, store and clustered by store's state.

In a database organized like that, neither part of the Query-3

item.i_manufact_id = 436 or dt.d_moy=12

should actually look at every row in the data-set in brute-force fashion - you get to skip massive parts of the data by just inspecting the index or going to the specific date partition and do it much faster than a naive C++ full-scan.

However, if you were limited to a full-load + scan, this would really be killer to have a columnar format which can be handled by an FPGA. The really interesting quote in the blog (for me) is

> the data for the queries is pushed to the accelerator card in columnar format (which is blazingly fast for queries)

I sure could use FPGA filters for columnar data ... even after I've done all my indexing, since I can't index down AND clauses or OR clauses - unlike a traditional CPU, the FPGA will be able to evaluate my entire condition in one sequential flow instead of check + branching.

There is quite a bit of work on this topic in Databases, and stream processing is one of the primary use cases they identified (in particular, if you can put the FPGA device between the network and the CPU, it works out quite well). This is one of the early papers:

http://dl.acm.org/citation.cfm?id=1687730

This one appears to be a more recent survey paper by some of those authors:

http://www.morganclaypool.com/doi/abs/10.2200/S00514ED1V01Y2...

As someone else pointed out, this was also one of Netezza's differentiation.

That book likes like an excellent resource. Thank you for sharing.

This is all high-memory stuff though, so in the physical world it's all limited by cache speed and memory bus speed. And that generally is limited by branch prediction. So branch prediction is the area where a custom FPGA for SQL could see improvements.

Hard-wiring operators is a minor improvement but really not much because compared to memory access it's not the bottleneck.

For GPUs, not FPGAs, but PostgreSQL has PGStrom[1] for offloading large table scans. Still a work in progress.

[1] https://wiki.postgresql.org/wiki/PGStrom

CUDA Only. Is PGStrom in Active development? Or is it more of an proof of concept stage?

Looks active at github, https://github.com/pg-strom/devel

And machine learning in on the way - https://postgrespro.com/roadmap/56513

I'm an FPGA/ASIC engineer that does some software as a hobby (mostly clojure, some python. C and Pascal if you go back far enough).

Although I focus more on verification these days, I've done ASIC design for about 16 years.

I'd be very interested in working with anyone on figuring out if we can make something better by leveraging hardware.

Where are you based? I'm a software guy learning about hw :)

Portland, OR, but I've been working remotely for 10 years. Virtual coffee still isn't a thing unfortunately.

Hi, you might be interested in our lowRISC project which is working towards producing a fully open-source SoC implementing the RISC-V instruction set architecture. Some of the key features we are focusing on, minion cores and tagged memory http://www.lowrisc.org/docs/memo-2014-001-tagged-memory-and-... I think are good examples of how we may be able to improve software through leveraging hardware. You don't have an email address in your profile, so if you want to chat more email me at asb@lowrisc.org

I've been working with FPGAs for 4 years and shortly on ASICs before that, did software in a previous life (and still do), do you have something specific in mind?

No, I personally don't. I was into reconfigurable computing for a while, sort of where I think intel is going with their combined CPU/FPGA project. Just In Time logic configuration.

But I figured I would throw my offer out in case there were people thinking they could solve or enhance something with an FPGA, but didn't have the experience to get started.

This looks pretty cool. Any idea of which database they're doing this on?

I don't see it listed out in the article anywhere. I would guess it's a FOSS database (i.e. either Postgres or MySQL) but also wouldn't be surprised if at their scale they've created something entirely in house.

MySQL is dominant in China Internet companies.

That's pretty interesting. Do you have a source for that?

NOTE: most of these website are in Chinese

Taobao http://mysql.taobao.org/index.php?title=首页 360buy http://www.infoq.com/cn/articles/exploration-of-distributed-...

Tencent http://tencentdba.com

DiDi http://os.51cto.com/art/201604/508514.htm

"Tencent is using PostgreSQL for data mart in their big data system" - https://pgconf.ru/en/2016/89691

I would say mysql is dominant in general.

> Postgres is getting its momentum in China, especially in 2015, one of the biggest insurance company is adopting Postgres, and Alibaba is providing Postgres service in their public cloud, also there are a lot of significant progress about the adoption. This talk will give an overview about the Postgres adoption in 2015 in China

https://pgconf.ru/en/2016/89691

> Alibaba has provided a relational database service (RDS) for postgres in our public cloud platform (aliyun.com, the currently biggest public cloud in China). We are also enabling internal applications to use postgres in our other internet business and we can share our experience

https://pgconf.ru/en/2016/89715

Actually, I am wondering if it has something to do with Hadoop and/or Apache Spark. The reason for that is that they mention Hive, Spark and Impala which are all SQL engines that live on top of Hadoop. Since the Hadoop ecosystem is mostly all open source, it would make sense that one could go fiddle with these open source optimizers to make this happen.

such FPGAs seems to be on the edge of what is export controlled, recently even regular Intel CPU got blocked for delivery to China :

http://www.pcworld.com/article/2908692/us-blocks-intel-from-...

and around an year ago some Russian guys got busted for selling the FPGAs to Russia (and those FPGAs were less powerful):

http://kron4.com/2015/03/21/sf-business-owner-arrested-for-a...

Baidu has an office here in US, they could build it here...I guess

It's no wonder Intel made a big FPGA acquisition lately. This sort of acceleration has enormous upside potential, especially if this sort of thing comes part and parcel with your CPU.

Intel is not alone - http://openpowerfoundation.org/blogs/fpga-acceleration-in-a-...

> In addition to the CAPI 2.0 coherent links running atop PCI-Express 4.0, there is a further enhanced CAPI protocol that runs atop the 25 Gb/sec Bluelink ports that is much more streamlined and we think is akin to something like NVM-Express for flash running over PCI-Express in that it eliminates a lot of protocol overhead from the PCI-Express bus

http://www.nextplatform.com/2016/08/24/big-blue-aims-sky-pow...

MapD does some of this, but with GPUs: https://www.mapd.com/product/

Finally! In 2011, when I was working on optimizing 100Gb databases on dedicated hardware for small businesses, everyone in the database world was talking SQL chips and PCI-E fast storage. Fast forward to today when cloud and virtualisation and now I'm working on "big data" 400Mb RDS instances. Its time we go "retro" and #gophysical for some things.

If anybody has the resources to start building dedicated FPGA (or whatever) instances for SQL workloads it would be one of the public cloud vendors (AWS, Azure, GCP).

Good! They will have to set aside servers that do just databases with SQL chips, but either way, I would be happy if they do that.

I would also be interested to see if there is a new trend to go back to owning commodity hardware, putting CoreOS+docker on it + a database with a hopefully inexpensive SQL chip. Moving away from VMware, massively expensive servers, massively expensive SANs, proprietary backups..

Would be very interesting to see.

Very cool work but since its easy to get memory-bandwidth bound with SQL I would wonder if it would make more sense to use GPUs with 10X the bandwidth. I know FPGAs will be getting HBM as well so this might help.

Disclaimer: I work at MapD, a GPU database company. (http://www.mapd.com)

Online stock brokers and finance companies have been using FPGAs for quite some time now because of latency as a microsecond can literally cost them millions. It is good to see these beasts making their way into crunching "Big Data" in non-finance domain.

isn't this already implemented in Datawarehouse appliances like Netezza (now part of IBM), which targeted solving the problem of analytical queries on huge sets of data??

I guess Baidu hired some former Netezza guys and they decided to copy/steal from their former company to meet with their KPIs,which is quite common here in China

Ahh yes, my old boss was next door neighbours with the Netezza CEO back in the early days circa '06. I worked a little with the platform back then, and i saw this article and was like, thats they they did! Back then, u had to shard ur database to take advantage of the parrallel processing, not sure how far its come now.

They are crazy! Very interesting case. How they support such DB? As I know FPGA has limits on updates.

What tools they use to create relational algebra?

> As I know FPGA has limits on updates.

I'm not sure what you're trying to refer to here. Are you confusing FPGAs with flash memory?

There are FPGAs (mostly Microsemi) that use internal flash memory to hold their configuration, but you are correct, most use eeproms/

Probably not. A hardware description language (HDL) is used to program the behavior of the FPGA (that's the FP in FPGA). The HDL is usually stored in flash or EEPROM. As you mention, flash supports a finite number of writes; I'm not sure about EEPROM behavior. The bottom line is that the typical FPGA can only be programmed a fixed number of times (e.g., I think Altera is ~100). Some FPGAs can only be programmed once.

Many FPGAs these days have flash memories that are good for ~10K writes.

EEPROMs are mostly only used for CPLDs (very cheap very very small FPGAs)... "Big" FPGAs as used here use SRAM, and are rated to be reprogrammed 100s of thousands of times, but should last for millions. I have reprogrammed my Xilinx and Altera FPGAs hundreds of times over a course of a couple of days ;)

EDIT: I should note that in the case of using SRAM, the device would only be programmed as long as the device is powered on. You would use EEPROM even on large FPGAs if you have the same design to be flashed to the FPGA between reboots. I personally never use EEPROM for storing the design as I have my FPGAs constantly connected to a computer for programming. My main point is that the FPGA can be programmed a functionally infinite number of times, though if you want the design to remain through reboots through an external memory, the limitation is that external memory, not the FPGA itself.

Are you able to simulate your Rex chip on one FPGA, do you just do a piece at a time, or over several? And what kind of FPGA's? Curious what hardware it takes to support developing something like that.

We do most stuff on a single FPGA... Our development flow is parameterized in a way so we can generate RTL with different numbers of tiles, SRAM per tile, and many other details within seconds of an RTL change. We have an Achronix Speedster that can fit 16 of our cores on it (our full test chip), while our cheaper Xilinx Kintex Ultrascale boards can comfortably fit 8 but can do 16 if we cut the SRAM size down from what we have in the real chip. You could split designs across FPGAs (The Dini Group sells systems using Xilinx and Altera chips built for this), but I have heard it is a real PITA, and we're doing fine with what we have right now.

I'd love to get a real ASIC simulation/emulation platform like Synopsys's Zebu or HAPS... Both use multiple Xilinx FPGAs linked together and easily integrate with the Synopsys EDA flow. Cadence also has the Palladium emulation platform, but those boxes approach the cost of a house in the Bay Area.

"We have an Achronix Speedster"

My favorite!

"Both use multiple Xilinx FPGAs linked together and easily integrate with the Synopsys EDA flow. Cadence also has the Palladium emulation platform, but those boxes approach the cost of a house in the Bay Area."

Sounds like a business opportunity for someone. I know it could be cheaper and still profitable.

> The bottom line is that the typical FPGA can only be programmed a fixed number of times

This is only true if the configuration is rewritten to flash every time the device is reconfigured, which would not be typical. Any design which depended on reconfiguring an FPGA frequently would reconfigure the device directly using JTAG or active serial programming, or would switch between multiple configurations in flash.

I personally have several FPGA development boards which I've reconfigured hundreds of times. There is effectively no limit to the number of times a device can be reconfigured; the configuration is stored in SRAM, which has no write limit.

Typically you only program them a handful of times. (first release of logic, then re-programming for updates if there are any)

Once a logic structure is in place, it's just a matter of passing signals/data through the FPGA.

most Fpgas can be passively loaded from a processor, one word at a time. That processor can get the FPGA image from anywhere. It takes longer to load an FPGA this way but it gives you a lot more flexibility and avoids the issue you're concerned about.

"Some FPGAs can only be programmed once."

That's not an FPGA then. That's a PLA. Even then most of those can be reset using ultra-violet light, a simple process.

> That's not an FPGA then. That's a PlA.

No, it's still called "FPGA". The "field-programmable" part refers to them being programmable after they have been manufactured, by someone else than the chip manufacturer. It doesn't matter if you can't reprogram it after it's been soldered onto a board, that's not what "field-programmable" means.

> Even then most of those can be reset using ultra-violet light, a simple process.

Once-programmable FPGAs are typically anti-fuse based. There is no way to reset their programming (we're working with space-grade single-programmable FPGAs, and yes, we're extremely careful about what gets put on them).

The host PC does all the database accesses and the FPGAs do the processing (search, filter, etc.) on the fly. Therefore there is no problem with updates.

> As I know FPGA has limits on updates.

HFT firms have been banging on the drum of making FPGA's infinity programmable for a decade and lots of commercial FPGA's can be re-flashed now without worrying about the number of times you do it.

I've seen re-flash counts up to 100,000 times.

Hey put this in the "what has HFT actually done for the world" list of answers:)

I've never seen an advertised limit on FPGAs. You'd probably grow old and die before you ran out of reflashes since that process takes a fair amount of time. 100,000 flashes at even five minutes each is over a year of relentless flashing.

Is there a Jenkins plugin for that? :)

What are you talking about?

> HFT firms have been banging on the drum of making FPGA's infinity programmable for a decade

That's strange, because FPGAs have been infinitely reprogrammable for longer than that.

> lots of commercial FPGA's can be re-flashed now

That's even stranger, because the vast majority of commercial FPGAs are not flash-based, but SRAM-based and can be reprogrammed as often as the registers in your CPU. Besides, HFT firms would be using SRAM-based FPGAs because they are faster and larger than flash-based ones, the advantages of flash-based ones are useless to them.

> "what has HFT actually done for the world"

Well, not this, that's for sure.

Most FPGAs (all except for a dozen or so) use SRAM to hold the configuration while in operation. SRAM has no limit to how many times it can change states. Off-chip flash typically stores the configuration for long term needs and the FPGA loads the configuration from that at power-up. Applications that require frequent changing of the configuration use processors to load from somewhere else instead (hdd, network, some other storage meachanism.)

FPGAs generally use RAM based look up tables and have to reload their configuration (programming) from non-volatile memory at power up. Since an FPGA is a RAM based device, it doesn't really have a limit on how many times you can reprogram it.

Naive question, but wouldn't this work only with ECC-enabled graphics cards like NVidia Quadros? Possibly that's the only reasonable choice for servers, but the price is much higher.

They're using a Xilinx FPGA card, not a GPU. These are two totally different things, though the FGPA card is usually a lot more expensive than any GPU on the market.

isn't this already implemented in datawarehouse appliances like Netezza (now part of IBM)?

Most likely I believe the answer is yes. But since these appliances have been proprietary, not much is publicly known about what they do internally. I suspect that some design like the one we are seeing here at Baidu has been their secret sauce for some time.

It's no secret. Netezza has been using FPGAs since the beginning. Here is a link to a paper that describes the Netezza approach: http://www.redbooks.ibm.com/redpapers/pdfs/redp4725.pdf

The Baidu approach seems very similar.

Reply on news.ycombinator.com