11 ms·
LittleD – SQL database for IoT, can run queries in 1KB
- rattray 11y agoIs the size of SQLite really a problem? Is its reliability something that hardware devs are willing to sacrifice? (In other words, how big is SQLite and what are the size restrictions for IoT devices – I haven't built one before)
- pfalcon 11y agoLittleD is designed to run on devices the size of (higher-end) Arduinos. So, it's difference of not being able to use a database and being able to use it. Reliability is a different problem, which is addressed for deeply embedded devices is slightly different ways than for bloated servers (e.g. by employing flash memory properties, or monitoring power supply in realtime).
- pbreit 11y agoIn the project's defense, I didn't see the size comparison anywhere other than this submission.
- pfalcon 11y agoYes, currently you need to build it yourself to do size comparisons. Generally, this HN post is in argument to LittleD's author that people care about his project, and that he should care about its potential users (and contributors!) and provide better disclosure of LittleD's capabilities and traits, not requiring everyone to dig deep to get basic facts.
- geedy 11y agoYou've been very good at nudging me pfalcon. Thank you!
- teraflop 11y agoAlthough SQLite's memory overhead is tiny by the standards of modern desktops/servers/phones, it's still much too big for 8-bit microcontrollers like the Arduino. If you want to build something that costs tens of cents instead of tens of dollars, SQLite is way too big. For example, https://www.sqlite.org/about.html https://www.sqlite.org/about.html claims that SQLite can run in "very little heap (100KiB)"; this project targets an Atmel ATmega2560 which has only 8KiB of RAM. (I doubt "5 times smaller than SQLite" is a useful comparison; the limiting factor is probably RAM consumption, as opposed to executable code which can be stored in cheaper non-volatile memory.)
- pfalcon 11y agoI thought hard what to put in the subject (limited length, you know) - code size or working RAM size, but figured if I write "can run queries in 1KB", people won't get it ;-).
- rattray 11y agoConsider putting some comparisons on the readme!
- pfalcon 11y agoThat's what I'm telling LittleD's author too! I posted here on HN just to show him that it's not my whim, and other people think the same ;-).
- dang 11y agoSince the size comparison to SQLite in the title has made the thread mostly be an argument about size comparisons and SQLite, let's try the other phrase and see if we fare better. (Submitted title was "LittleD – SQL database for IoT, 5 times smaller than SQLite").
- collinmanderson 11y agoI actually saw the new title without SQLite, and I my first question was still how it compared to SQLite. :)
- raimue 11y agoLittleD targets devices the size of an Arduino, while SQLite requires at least some sort of operating system offering a filesystem interface. The feature set of LittleD is also reduced as it supports only simple queries. The corresponding paper [1] claims "SQLite requires at least 200 KB of code space and cannot run on popular platforms such as the Arduino." For comparison, Arduinos based on ATmega microcontrollers only offer up to 256 KB of flash memory at maximum. [1] https://dl.acm.org/citation.cfm?id=2554891 https://dl.acm.org/citation.cfm?id=2554891
- jly 11y agoSQLite definitely does not require a filesystem interface, or even standard OS interface. It does require some kind of storage, though, but that could be direct flash, RAM, etc. I have spent a lot of time with it on ARM Cortex-M-class devices on small RTOSes or even bare metal, and you can adapt it to almost anything by plugging in new VFS interfaces (http://www.sqlite.org/vfs.html http://www.sqlite.org/vfs.html). It does require at least 10s of kb of RAM as a heap to do pretty much anything, as others have stated.
- to3m 11y agoThe ATmegas only go up to 16KBytes RAM, with 4KBytes or less being usual. As a Harvard architecture device, none of your binary is memory-mapped, which can make porting existing code a bit annoying. sizeof(int)==2, which doesn't help either (however sizeof(void *)==2 as well, so there is at least that). It's rather unusual by today's standards. Certainly quite different from an ARM.
- listic 11y ago...though still the latest and sanest of that crop of micro's, IMHO. Designed in 1996, it was once marketed as "the first new 8-bit architecture designed in 20 years", I believe :-)
- pfalcon 11y agoYou can adapt, or have you adapted? I looked at SQLite internals, and decided that I'll skip that adaptation for now, seeing if someone else would do that. LittleD's author says that he looked into adapting SQLite, and that's how he decided to write LittleD.
- trymas 11y ago+1 SQLite is probably on of the most well tested piece of software on this globe. I do not know if this space saving is worth it.
- pfalcon 11y agoNo. But running SQL where you never could run it before (where SQLite couldn't fit even remotely) is definitely interesting.
- nickpsecurity 11y agoIt is if the space savings gets your product sales due to lower unit price with big $$$ resulting. That's why there's a market for 8-16bit processors. Most developers don't want it so much as need it because getting job done for $1 a CPU is better than using $10-$100. ;) EDIT to add two links by Ganssle to explain it better: http://www.ganssle.com/rants/8bitsisdead.htm http://www.ganssle.com/rants/8bitsisdead.htm http://www.ganssle.com/articles/8and16bit.htm http://www.ganssle.com/articles/8and16bit.htm I think Microchip's 8-bitters doing $1+ billion in business with better profits and dividends vs troubles of many in 32-64 bit markets says a lot.
- sitkack 11y agoThose articles are over a decade old. The size of silicon between an 8 or 16 or 32 bit ALU contained in an MCU is miniscule. Most of the space is taken up by peripherals and this is where Microchip has historically thrived but this is no longer so. There are a number of 32 bit MCUs that are cost competitive with 8 bit parts.
- nickpsecurity 11y agoHow about this month with a market survey? ;) http://www.edn.com/electronics-blogs/embedded-insights/4440832/8-bit-isn-t-dying--it-s-growing http://www.edn.com/electronics-blogs/embedded-insights/44408... Interesting details on how 8-bit companies are doing that from John Donovan the year before: https://www.digikey.com/en/articles/techzone/2014/feb/is-there-a-future-for-8-bit-mcus https://www.digikey.com/en/articles/techzone/2014/feb/is-the... We'd need a price list for the other thing. Can you get 32's with decent memory & low watts for a few bucks a CPU in low volume? Aside from that, you still think they're dead and useless with the new articles? I'll add that many chips from old nodes survived for decades due to stability. The new process nodes have all kinds of issues and break faster. So, there is that to consider if the application is long-term, safety-critical, or security-critical. Many in high assurance design stayed with old stuff (esp on SOI) because manufacturing bugs were less and interference/wear issues are lower.
- pilif 11y agoBack in 2004, I wrote code for the Intermec ck1 barcode scanner. It ran uClinux and had a stack size limited to 4K. That thing could only very barely run sqlite 2 (after applying a few patches to it works with the small stack size) and I could never get SQLite 3 to work. Granted. That was 10 years ago, but it was also quite a beefy device for its time. So while naturally the devices have become quite more powerful in the last 10 years, current IoT devices are also much more compact than the old ck1. As such I would say it's conceivable that you don't have the memory to easily run current SQLite on any of these devices.
- pfalcon 11y agoAlso mind that software doesn't stay the same either. As an example, LMDB (smaller, key-value DB) in its initial docs and slides bragged 30K of object size. Build current version, you'll get 60K, and there doesn't seem to be config options to just make it smaller. So either use older version, which is of course scary (who knows how many bugs was fixed later), or spend quite a lot of time tearing it apart, with unclear maintenance perspectives. Having something ROM and RAM optimized from the beginning seems like pretty good solution (if someone grew brave to do it).
- geedy 11y agoIn all honesty, keeping the ROM size small is the challenge.
- geedy 11y agoAs others have noted, the resource constraints associated with many of the most cost-effective 8/16/32-bit AVR or ARM devices simply cannot run on SQLite. I even looked at making it smaller before starting LittleD, but I deemed that a Herculean task. SQLite itself requires at least 100KiB of Heap space, sometimes many times more memory than already available: http://www.sqlite.org/about.html http://www.sqlite.org/about.html
- revelation 11y agoIt's not a tradeoff you are making, the fact is that your Arduino only has program space measured in the dozens KiB. If it doesn't fit, it doesn't fit. But that's not the biggest problem. SQLite, like most programs, relies on having a C library like glibc available. This is pretty much the intermediary person to the operating system - you can ask it for memory, it will allocate memory for you, you can ask it to open a file, it will facilitate that. Most programs assume it's always present and so the dependency isn't properly abstracted. This is a problem when you don't have an operating system. Notice also that you can't just go and implement or stub everything that glibc does. To do that, you would just end up having to add an operating system. (This particular rabbit hole goes much deeper. A lot of programs sadly don't depend on a C library, they depend on glibc in particular. This causes massive problems for systems that run Linux yet can't accomodate glibc, like OpenWRT. They use an alternative C library that works fine 99% of the time, and for the remaining 1% it will cause programs to silently misbehave or crash because of an implicit dependency on whatever glibc does. I had this problem with the hwclock utility which started segfaulting when OpenWRT switched to musl libc)
- pbreit 11y agoIn the project's defense, I didn't see the size comparison anywhere other than this submission.
- coleifer 11y agoThis looks like a very cool project. I cloned it and generated the docs, and while the code is certainly well-document, I didn't see any type of high-level narrative or public APIs. Was hoping to see at least a "littleD.h" or something, but it seems you have to do some source diving or look at the tests to figure out how to use this library.
- pfalcon 11y agoPlease go to https://github.com/graemedouglas/LittleD/issues/6 https://github.com/graemedouglas/LittleD/issues/6 and give it +1 then.
- geedy 11y agoI absolutely need to improve that side of it, there is no doubt. Thank you for the feedback!
- jasonwatkinspdx 11y agoGet a link to the paper up front in the readme.
- nitrogen 11y agoWhat is the advantage of using a database vs. rolling your own data structures on such a small device?
- pfalcon 11y agoThe same as on any other device I guess - you either need to sit and roll out your own data structures, or just take and use a database.
- nitrogen 11y agoI guess it depends on what you find more familiar. But at this device scale, one should really be comfortable with C data structures.
- emcq 11y agoDynamic queries and data serialization. Imagine sending just a text query (in SQL) around to a sensor network. It would be a fair amount of work to reproduce that on your own but seems like it can open up some nice features for distributed IoT
- nitrogen 11y agoIt still seems pretty inefficient. With 4KB of RAM I'd just store my data in an array of structs and send it in raw binary to the central server. The SQL also leaves potential for running unwanted SQL. I'm reminded of a commercial home automation platform that had agonizingly slow response times because the LCD controllers were sending raw, unauthenticated Python code to the 70MHz central controller.
- nickpsecurity 11y agoInteresting. Hope the author gets a usable subset there in a flexible coding style. Might be ported to other devices and become a general thing. Love the name, too, haha. Note: How much of a need is there for a SQL database on 8-bitters, etc? Can't one do that in a front-end at the client side and just have simple commands sent over network to device? What I always did for limited or security-critical devices. No way I'd put a whole 4GL on them lol.
- geedy 11y agoMy goal has always been to support a wide-variety of devices. As for the name, I cannot take credit. There is a good story behind it though. ;) As for the need, I sort of explained the motivation this comment: https://news.ycombinator.com/item?id=10622675 https://news.ycombinator.com/item?id=10622675. Data management would drastically reduce the development effort associated with data-intensive applications for smaller devices, in an IoT setting or otherwise. I've actually recently travelled to the University of Michigan to talk about this work, and got lots of good feedback. One of the professors invited me and has asked me to study with him, because he feels there is a need. One of his graduate students there is working on integrating LittleD into some of his work already!
- nickpsecurity 11y agoInteresting. The main drawback I saw was that your paper is one of those paywalled behind ACM. Many end up freely available on academics' sites, Citeseerx, etc. Yet, some portion are stuck where few will ever look at them. Another example recently on here was OcaPIC: Ocaml on PIC MCU's. Recent paper locked up where people can't read and improve it. Is there a public copy of your paper for people here to read? Might increase interest and contributions.
- geedy 11y agohttps://people.ok.ubc.ca/rlawrenc/research/Papers/LittleD.pdf https://people.ok.ubc.ca/rlawrenc/research/Papers/LittleD.pd...
- shanemhansen 11y agoI discovered my IOT camera in my home runs sqlite.
- donpdonp 11y agoWhat are the actually memory usage/recommended RAM sizes for LittleD?
- geedy 11y agoLittleD can be run using as little as 1KB of RAM for simple queries involving selections (WHERE clauses), projections (not just SELECT *) and joins. For queries with more than a couple joins, 2KB of RAM should still suffice.
- listic 11y agoWhen would you actually need a relational database running on such a small platform, today? I understand programming in general and microcontrollers; I was paid to program one. Still, surely nowadays a system with a tiny 8-bit microcontroller is probably considered as auxillary to some kind of larger machine, which should be way better equipped to do the heavy lifting such as SQL databases?
- Sanddancer 11y agoThere are still lots of uses for tiny microcontrollers that don't connect to a larger machine, or only do so on occasion. By having a database backend, you make it a lot easier to query the microcontroller out in the field for a specific subset of data, instead of it needing to dump everything out, wasting time and battery life.
- niutech 11y agoYou can easily get just part of your data using a binary tree or a hashtable and simple C functions like for, while, if. In most cases there is no need for a full-blown SQL engine.
- teraflop 11y agoOn the other hand, microcontrollers typically have ample Flash storage for code, but very limited amounts of RAM. Instead of making everyone rewrite their own memory-efficient data structures, it might well make sense to have a single, general-purpose implementation -- even if some of the code goes unused in a particular application.
- listic 11y agoWell, if you can really make SQL work well within such constraints and be convenient to use - I see no harm in it.
- niutech 11y agoKeep in mind that the Flash storage has a limited number of writes, so keeping frequently changing data in memory and choosing a right data structure can be crucial for your data's life span. SQL is not an universal solution for all use cases.
- jwiley 11y agoI haven't created large amounts of C/C++, so I'm certainly not an expert, but I was impressed by how well the source was commented and structured. Nice to see well documented, well thought out code, congrats
- geedy 11y agoWow, thank you for the feedback. I take a lot of pride in making the code readable. Maintaining a large C project by oneself for notorably fickle devices has been challenging, so you need to get all the of help you can.
- navls 11y ago/* Advance a pointer num_times times. Notice, this does no checking, so you better know what YOU ARE DOING!!!! */ The source is a pretty interesting read too.
- hliyan 11y agoI have written large amounts of C/C++ and I too am impressed by how well documented the code is (trust me, most C++ code isn't!)
- geedy 11y agoThank you! I actually have become more anal about code quality as I've gone along, to the point of annoying people. IonDB represents a much better coding standard, in my mind than LittleD. Like I say, every bit of documentation and cleanliness helps!
- tptacek 11y agoThis is really neat. What's a realistic use case for a SQL-like database running on a microcontroller?
- geedy 11y agoAuthor here. Any time you want to store historical data, and query that data later. Very similar to how you might imagine using a database for a website, just at a smaller scale. The project that inspired this work was a water metering project in Kelowna, BC. Basically, a friend of mine took a bunch of micro-controllers with soil moisture sensors, shoved them in the ground, and tried to come up with better demand-based watering schedules. It took them two months to develop the data management code, and knew it could have been days or hours with a proper database.
- tptacek 11y agoThanks! What would the storage look like for this? (I have an ulterior motive for asking, which is that I will probably end up shoplifting this code and embedding it into the next set of levels for our CTF game, which is serverside-emulated AVR).
- geedy 11y agoI did a fair amount of testing with arduino-based SD-card storage, but as long as you had some sort of way to store bytes to your preferred medium, that shouldn't be too hard to hack yourself. Check out https://github.com/graemedouglas/LittleD/blob/master/src/dbstorage/dbstorage.c https://github.com/graemedouglas/LittleD/blob/master/src/dbs... EDIT: Please let me know how/if you end up using it! Or if you run into bugs! :)
- VLM 11y agoIf I'm reading you right and extending your example more concretely, you're doing IoT SIMD parallelization, right? So rather than 1M soil moisture sensors continuously sending records to a central repo, you're giving the mesh network something exciting to do by distributing "select * from db where moisture<200" or whatever then collating all the responses, if any... There's a classic crypto thought experiment illustrating SIMD for cracking keys where the Chinese distribute 100M boom boxes (well, its an old thought experiment) and they randomly test keys and when the red light turns on indicating factor found, the owner of the radio turns it in for a substantial reward. And thats how SIMD key cracking gets a 27 bit parallelism speedup over one box. In the IoT era I assume its going to be a normal thing for lightbulbs and toasters to get powned to mine bitcoins and the like. You could probably extend both the real story and the old crypto thought experiment to help provide some docs. Then again I read your unit tests and they kind of document the system pretty well. Nice tests. In true supercomputer fashion, by going SIMD you've taken a formerly CPU bound problem, and turned it into an IO bound problem, but for little microcontrollers not classic supercomputer hardware, which I thought was pretty funny.
- geedy 11y agoI am the author of LittleD. I am more than happy to answer any questions. It has mostly been an academic project while I was doing during my undergrad, but I am now looking at continuing the project as part of a Ph.D. Of course, I would love to coordinate a broader development of this project. :) You may also be interested in another project I and some lab mates have been working on over the last couple of years, IonDB: https://github.com/iondbproject/iondb https://github.com/iondbproject/iondb. EDIT: You might also be interested in the initial paper, which can be found here: https://people.ok.ubc.ca/rlawrenc/research/Papers/LittleD.pdf https://people.ok.ubc.ca/rlawrenc/research/Papers/LittleD.pd... I investigated query precompilation in another paper I am waiting to here back on, and once everything has been a little better tested, that code will get pushed out as well. :) And seriously, if anybody is interested in contributing, I would love to have some help. Get in contact with me!
- krashidov 11y agoHow did you learn to write a database from scratch? What books, courses, tutorials do you recommend?
- geedy 11y agoI took a computer science course at the University of British Columbia's Okanagan campus called COSC404 under Professor Ramon Lawrence (who is/was also my research supervisor at UBC), which was on database implementation. It was here that I learned most of the material.
- gburt 11y agoI took the same course @geedy is speaking of (with him, in fact) and there are two good comparable resources I'm aware of: (1) Ramon's (excellent!) lecture notes themselves are currently (but not always) available on his website: https://people.ok.ubc.ca/rlawrenc/teaching/404/notes/index.html https://people.ok.ubc.ca/rlawrenc/teaching/404/notes/index.h... (2) Garcia-Molina, Ullman and Widom's book and courses taught on their work: http://www.amazon.ca/Database-System-Implementation-Hector-Garcia-Molina/dp/0130402648 http://www.amazon.ca/Database-System-Implementation-Hector-G... http://infolab.stanford.edu/~ullman/dbsi.html http://infolab.stanford.edu/~ullman/dbsi.html
- mirchiseth 11y agoThis would be a good learning project in CS classes as well.
- Carrok 11y agoAs someone who has spent the past year and change developing an automation system using the targeted platform (Megas) I can say that this sounds like a very bad way to do things. While I applaud the effort, and it will certainly be useful for many people for many other reasons, I don't think IoT is the best use case here. If your data is at all valuable/useful, you don't want it sitting out somewhere on some device that will hopefully/maybe be online when you go to query it. Plus now just to be able to query it remotely you will still need to develop some sort of API that lives on the device that can talk to the LittleD database. Finally if you really are doing 'IoT' you clearly have a bunch of things that you want to view/control from a centralized platform. When you have the devices talking to a server, you can do this. When you have to ask each device individually what is going on with it, this becomes much harder.
- geedy 11y agoThere isn't really a targeted platform. There just only happens to be one of me at the moment, and so I've only managed to compile it for a few devices. As you noted, its not really an IoT databases. It could be used as such, but thats not the reason I built it. I have also been working on the data transfer problem, because without the ability the share the data it is in fact kind of a useless platform in many applications. I have a job manager being developed that will allow for scheduled or ad-hoc execution of functions. I've also written some small library to encode LittleD results for network transmission. Using some basic networking stack, it would be easy to assemble these pieces into something that could be viewed/controlled from a centralized platform. LittleD could even be modified with relative ease to actually query over other LittleD instances! EDIT: I would actually like to encourage you to divulge some specific criticism for the IoT application. Are you specifically speaking to your automation system, or to IoT at large? It seems difficult to predict exactly how any one person might apply any given technology.
- jchrisa 11y agoWe've built a sync-enabled database, and even at 500 kb it's getting a lot of uptake in IoT applications. Open source databases: http://developer.couchbase.com/mobile http://developer.couchbase.com/mobile Info about how GE is using it: http://www.couchbase.com/nosql-resources/presentations/offline-first-and-how-ge-integrated-couchbase-mobile-in-less-than-90-days.html http://www.couchbase.com/nosql-resources/presentations/offli... Long story short: when you get the network stuff figured out, it's gonna be an interesting product. Feel free to contact me (info in profile) if you want to chat about how this can fit into the industry.
- SEJeff 11y agoI'd be quite interested to see this on an ESP8266 board. I use the Adafruit huzzah version[1] which comes with a lot of extra fluff for developers, but the core microcontroller is a 32 bit MCU with 64k of ram. It is about the size of a US Quarter Dollar coin and can be had for as low as ~$2 USD. [1] https://www.adafruit.com/products/2471 https://www.adafruit.com/products/2471
- geedy 11y agoWe've actually been looking at getting some newer devices, I'll look to add this to our list. Thanks!
- myth17 11y agoDo we have transaction (ACID) support? If not, have you thought about it? Is is feasible with the IOT constraints?