7 ms·

I had to roll my own transactional database for an embedded product working in a very constrained environment (2MHz ARM, 2MB total memory). I did very extensive

I had to roll my own transactional database for an embedded product working in a very constrained environment (2MHz ARM, 2MB total memory). I did very extensive search and I found no product with the combination of characteristics I was looking for: - working in very small but more importantly, constant memory (predictability is a must for reliable embedded app), - provide provable transactional characteristics with guarantee to roll back to previous state in case transaction is interrupted and still be consistent and able to accept new transactions, - minimum storage overhead -- the amount of overhead was directly translating to competitiveness of the device at the time as multiple vendors tried to provide their own solutions for the same preexisting platform - storage write pattern that would provide wear leveling for the underlying flash I ended up writing my own database (less than 1k LOC total with encoding/decoding data using BER-TLV) that would meet all characteristics, take few tens of bytes of stack, take few bytes of overhead per write. The database would vacuum itself and coalesce record state automatically. It had some O(n^3) algorithms but THAT'S OK since the amount of data could never be so large that it could pose any problems. The project took 2 years to complete. I spent maybe a month designing, implementing and perfecting the database. I wouldn't say that the Akin's law of spacecraft design applies here. I would probably spend more than that if I had to integrate existing product and end up with inferior product anyway.

faitswulff 9y ago
The title is misleading - it's actually about how and why they did end up writing their own db. From the article: > There’s an old adage in software engineering — “never write your own database”. So why did the OneNote team go ahead and write one as part of upgrading OneNote’s local cache implementation?
- lmilcin 9y ago
  What I am really objecting to is those hard "rules". "Never optimize early". "Never roll your own database", etc. All those rules work for most but not all projects. It's the same as saying "You shall allways obey traffic rules". Maybe I should, but sometimes I may not want to brake on yellow light when I have clearly impatient driver tailgating me. As we gain experience we learn the world is not black and white. Akin's law #8 says: "In nature, the optimum is almost always in the middle somewhere. Distrust assertions that the optimum is at an extreme point."
  - plorntus 9y ago
    The article deliberately contradicts the title, it's literally stating the same thing you're saying but with a real world example (One Note) and why they needed to write their own.
  - deleted 9y ago
    [deleted]
  - deleted 9y ago
    [deleted]
  - ksk 9y ago
    But your objection is rather silly!! Those rules are meant for beginners. If you're not a beginner you already know when/if/how you can break the rules. It is correct to teach kids that they should tell the truth in every scenario, even if as adults we don't.
    - anyfoo 9y ago
      Exactly. Fully understand why should never do x, so that fully understand when you actually have to do x.
      - voodootrucker 9y ago
        values > principles > practices You are free to violate any of those on the right in the interest of the ones to the left.
        deleted 9y ago
        [deleted]
    - hutzlibu 9y ago
      "It is correct to teach kids that they should tell the truth in every scenario, even if as adults we don't." Not correct. Example, a stranger: "are you alone a home?" or "what is the keycode for the door" etc.
ghoul2 9y ago
Is this something publicly available? I am currently hunting around for an embedded database which has amazingly similar requirements, and have found nothing. I started my own db, but i'd love to be able to take a look at what you ended up with, if possible.
- lmilcin 9y ago
  It is proprietary, unfortunately, but you can pm me to discuss it. Once you understand the problem it isn't really difficult to implement it. The trick is to decide what kind of properties you really need and only implement what is absolutely necessary to achieve it. I did this in ANSI C using some of the stuff I have already implemented for the project. For example, I already had BER-TLV parser/serializer with very specific properties (managing collections within buffer of specified size, etc.) so I reused it for the file format and then again on application layer for the record format. The basic database is KV store kept in the form of a append-only log file. The entries are records of modifications performed to the database. The keys and the values are binary and the structure is managed by the application. Application supplies callback to perform some operations (for example, given a base version of the record and a patch, calculate the patched version of the record). The transactions were basically an identifier and a flag (is the entry end of transaction?) All algorithms are very simple and focused on constant use of memory. For example: coalescing operation was basically reading old file and writing alive records to a new file. I would traverse the old file entirely, for each record (O(n^3)) and, using callbacks supplied by the application, write end result of all committed transactions to the new file. After this was done to all records I would switch the files. Fetching any record meant doing linear search through all database entries to find all entries related to the record, taking base version and then successively applying all patches until entire database file is traversed. This is inefficient as hell but the use case was that the database was very rarely actually accessed. The typical use was to just write data to the database and it was only accessed after failure or in some very specific background tasks.
unbendable 9y ago
It's "funny" how you (and many others too) didn't read the article and just commented based on the title.
- goatlover 9y ago
  It's as if RTFA was a real thing.
nerfhammer 9y ago
wonder if sqlite would work for something like that, if you can get away from sql, i.e., strings.
- nbevans 9y ago
  It can. Just make sure you "prepare ()" your statements. This turns them into a compiled set of VM instructions.
  - lmilcin 9y ago
    The issue being sqlite did not even remotely meet the criteria: - it requires operating system, - its memory footprint even in best case way larger than total memory available on the system, - can't work in constant amount of memory (no dynamic allocations after application startup, compile-time verifiable stack usage) - can't provably continue from any power cycle -- there is no guaranteed automated recovery method in case of unfortunate power cycle - data storage overhead was unacceptable for the application
    - SQLite 9y ago
      You are no doubt correct about points (2) and (5). But just to set the record straight, points (1), (3), and (4) are mistaken. The standard build of SQLite uses an OS, but there is a compile-time option to omit the OS dependency. It then falls to the developer to implement about a dozen methods on an object that will read/write from whatever storage system is used by the device. People do this. We know it works. We once had a customer use SQLite as the filesystem on their tiny little machine. Likewise, the use of malloc() is enabled by default but can be disabled at compile-time. Without malloc(), your application has to provide SQLite a chunk of memory to use at startup. But that is all the memory that SQLite will ever use, guaranteed. Internally, SQLite subdivides and allocates the big chunk of memory, but we have mathematical proof that this can be done without ever encountering a memory allocation error. (Details are too long for this reply, but are covered in the SQLite documentation.) Finally, we do have proof that SQLite can continue after a power cycle - assuming certain semantics provided by the storage layer. Hence, the proof depends on your underlying hardware and those methods you write to access the hardware for (1) above. But assuming those all behave as advertised, SQLite is proof against data loss following an unexpected power cut. We have demonstrated this by both code analysis, and experimentally. So probably you were correct to write your own database in this case. My point is that SQLite did not miss your requirements by quite as big a margin as you suppose. If you had had a bigger hardware budget (SQLite needs about 0.5MB of code space and a similar amount of RAM, though the more RAM you feed it the faster it runs) then you might have been able to save yourself about two years of development effort.

faitswulff 9y ago

The title is misleading - it's actually about how and why they did end up writing their own db. From the article: > There’s an old adage in software engineering — “never write your own database”. So why did the OneNote team go ahead and write one as part of upgrading OneNote’s local cache implementation?

lmilcin 9y ago
What I am really objecting to is those hard "rules". "Never optimize early". "Never roll your own database", etc. All those rules work for most but not all projects. It's the same as saying "You shall allways obey traffic rules". Maybe I should, but sometimes I may not want to brake on yellow light when I have clearly impatient driver tailgating me. As we gain experience we learn the world is not black and white. Akin's law #8 says: "In nature, the optimum is almost always in the middle somewhere. Distrust assertions that the optimum is at an extreme point."
- plorntus 9y ago
  The article deliberately contradicts the title, it's literally stating the same thing you're saying but with a real world example (One Note) and why they needed to write their own.
- deleted 9y ago
  [deleted]
- deleted 9y ago
  [deleted]
- ksk 9y ago
  But your objection is rather silly!! Those rules are meant for beginners. If you're not a beginner you already know when/if/how you can break the rules. It is correct to teach kids that they should tell the truth in every scenario, even if as adults we don't.
  - anyfoo 9y ago
    Exactly. Fully understand why should never do x, so that fully understand when you actually have to do x.
    - voodootrucker 9y ago
      values > principles > practices You are free to violate any of those on the right in the interest of the ones to the left.
      - deleted 9y ago
        [deleted]
  - hutzlibu 9y ago
    "It is correct to teach kids that they should tell the truth in every scenario, even if as adults we don't." Not correct. Example, a stranger: "are you alone a home?" or "what is the keycode for the door" etc.

ghoul2 9y ago

Is this something publicly available? I am currently hunting around for an embedded database which has amazingly similar requirements, and have found nothing. I started my own db, but i'd love to be able to take a look at what you ended up with, if possible.

lmilcin 9y ago
It is proprietary, unfortunately, but you can pm me to discuss it. Once you understand the problem it isn't really difficult to implement it. The trick is to decide what kind of properties you really need and only implement what is absolutely necessary to achieve it. I did this in ANSI C using some of the stuff I have already implemented for the project. For example, I already had BER-TLV parser/serializer with very specific properties (managing collections within buffer of specified size, etc.) so I reused it for the file format and then again on application layer for the record format. The basic database is KV store kept in the form of a append-only log file. The entries are records of modifications performed to the database. The keys and the values are binary and the structure is managed by the application. Application supplies callback to perform some operations (for example, given a base version of the record and a patch, calculate the patched version of the record). The transactions were basically an identifier and a flag (is the entry end of transaction?) All algorithms are very simple and focused on constant use of memory. For example: coalescing operation was basically reading old file and writing alive records to a new file. I would traverse the old file entirely, for each record (O(n^3)) and, using callbacks supplied by the application, write end result of all committed transactions to the new file. After this was done to all records I would switch the files. Fetching any record meant doing linear search through all database entries to find all entries related to the record, taking base version and then successively applying all patches until entire database file is traversed. This is inefficient as hell but the use case was that the database was very rarely actually accessed. The typical use was to just write data to the database and it was only accessed after failure or in some very specific background tasks.

unbendable 9y ago

It's "funny" how you (and many others too) didn't read the article and just commented based on the title.

goatlover 9y ago
It's as if RTFA was a real thing.

nerfhammer 9y ago

wonder if sqlite would work for something like that, if you can get away from sql, i.e., strings.

nbevans 9y ago
It can. Just make sure you "prepare ()" your statements. This turns them into a compiled set of VM instructions.
- lmilcin 9y ago
  The issue being sqlite did not even remotely meet the criteria: - it requires operating system, - its memory footprint even in best case way larger than total memory available on the system, - can't work in constant amount of memory (no dynamic allocations after application startup, compile-time verifiable stack usage) - can't provably continue from any power cycle -- there is no guaranteed automated recovery method in case of unfortunate power cycle - data storage overhead was unacceptable for the application
  - SQLite 9y ago
    You are no doubt correct about points (2) and (5). But just to set the record straight, points (1), (3), and (4) are mistaken. The standard build of SQLite uses an OS, but there is a compile-time option to omit the OS dependency. It then falls to the developer to implement about a dozen methods on an object that will read/write from whatever storage system is used by the device. People do this. We know it works. We once had a customer use SQLite as the filesystem on their tiny little machine. Likewise, the use of malloc() is enabled by default but can be disabled at compile-time. Without malloc(), your application has to provide SQLite a chunk of memory to use at startup. But that is all the memory that SQLite will ever use, guaranteed. Internally, SQLite subdivides and allocates the big chunk of memory, but we have mathematical proof that this can be done without ever encountering a memory allocation error. (Details are too long for this reply, but are covered in the SQLite documentation.) Finally, we do have proof that SQLite can continue after a power cycle - assuming certain semantics provided by the storage layer. Hence, the proof depends on your underlying hardware and those methods you write to access the hardware for (1) above. But assuming those all behave as advertised, SQLite is proof against data loss following an unexpected power cut. We have demonstrated this by both code analysis, and experimentally. So probably you were correct to write your own database in this case. My point is that SQLite did not miss your requirements by quite as big a margin as you suppose. If you had had a bigger hardware budget (SQLite needs about 0.5MB of code space and a similar amount of RAM, though the more RAM you feed it the faster it runs) then you might have been able to save yourself about two years of development effort.