tag:blogger.com,1999:blog-81360121479291679332024-03-13T02:46:01.610-07:00Th30z (Matteo Bertozzi Code)Matteo Bertozzihttp://www.blogger.com/profile/04630649852079843031noreply@blogger.comBlogger116125tag:blogger.com,1999:blog-8136012147929167933.post-7817834159914029962023-02-04T02:51:00.002-08:002023-02-07T02:52:15.852-08:00New Blog Url<p><a href="https://matteobertozzi.github.io/"> https://matteobertozzi.github.io/</a></p>Matteo Bertozzihttp://www.blogger.com/profile/04630649852079843031noreply@blogger.com0tag:blogger.com,1999:blog-8136012147929167933.post-45816460424740635432012-06-24T10:26:00.000-07:002013-02-01T22:18:37.836-08:00Data-center Rolling Upgrades coordinated by ZooKeeper<div class="" style="clear: both; text-align: center;">
</div>
<div style="text-align: left;">
Still playing around trying to improve the daily deploy work in the data-centers.<br />
<br />
The idea is to replace a sequential/semi-manual process with something more automatic that don't need human intervention unless some failure happens.<br />
<br />
Services and Deploy rules:</div>
<div style="text-align: left;">
<ul>
<li>Services has dependencies (Service B depends on Service A), Deploy order matter!</li>
<li>You can't bring down all the machines at the same time! </li>
<li>One or more machine can be unreachable during the deploy (network problems, hw failures, ...).</li>
<li>Each machine need to be self-sufficient!</li>
</ul>
<div>
Must to Have (Monitoring)</div>
<div>
<ul>
<li>Current service state of each machines (online/offline, service v1, v2)</li>
<li>Current "deploy" state (Ready to roll?)</li>
</ul>
</div>
<div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj797cnm6cLAS1PueKIlo_0ytN6BzxTy97B-aFQF45zL5feTau_4eeLYlx_8vXEFWMMjfwMMaxpJY9jaHGmIO1zZ-dfTZhe98atCPg8PuUNgjSaJNM6jmqPIb_AT5dP69XdHUmkh6pZOg0/s1600/Zk-Deploy.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj797cnm6cLAS1PueKIlo_0ytN6BzxTy97B-aFQF45zL5feTau_4eeLYlx_8vXEFWMMjfwMMaxpJY9jaHGmIO1zZ-dfTZhe98atCPg8PuUNgjSaJNM6jmqPIb_AT5dP69XdHUmkh6pZOg0/s1600/Zk-Deploy.png" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
The idea is quite simple, using ZooKeeper to keep track of each Service (A, B, ..., K) with the list of machines available (<i>ephemeral znodes</i>) and to keep track of te deploy state <i>("staging")</i>.<br />
<ul>
<li>/dc/current: Contains a list of services with the list of online machines <i>(and relative service version)</i>.</li>
<li>/dc/staging: Contains a list of services with the list of machines ready to roll.</li>
<li>/dc/deploy: Deploy order queue each node represent the service to upgrade.</li>
</ul>
When you're ready to deploy something new you can create the new znodes:<br />
<ul>
<li><span style="background-color: white;">Add services to "staging" with the useful metadata (version, download path, ...)</span></li>
<li><span style="background-color: white;">Define a deploy "order" queue</span></li>
</ul>
<div>
Each service is notified about the new staging version and starts downloading <i style="background-color: white;">(see "<a href="http://th30z.blogspot.se/2012/06/data-center-deploy-using-torrent-and.html">data-center deploy using torrent and mlock()</a>" post)</i><span style="background-color: white;">. Once the download is completed, the service register it self to the "staging" queue.</span></div>
</div>
<div>
<br />
Now the tricky part is when can I start switching to the new version? The idea is to specify a quorum foreach service. The First machine in the "Staging" queue for the first service in the "Deploy" queue, looks for the quorum, and when is time shutdown it self and restart the new service. Once is done adds it self to the "Current" list and remove it self from the staging queue.<br />
<br />
And one by one each machine start upgrading it self, until the deploy queue is empty. If a machine is down during the deploy, the "Current" node is checked to find which version is the most popular, and the service will be started.</div>
</div>
Matteo Bertozzihttp://www.blogger.com/profile/04630649852079843031noreply@blogger.com7Stockholm, Sweden59.32893 18.0649159.199335 17.749053 59.458525 18.380767000000002tag:blogger.com,1999:blog-8136012147929167933.post-57021387418126888852012-06-02T09:53:00.001-07:002012-06-02T09:53:27.480-07:00Data-center deploy using torrent and mlock()<i>Every morning you come in the office hoping that the nightly job that produce your blobs has finished... and if everything is fine, you spend the rest of the day hoping that none of the machines fails during transfer...</i><br />
If you've a service that consume static data and you've more than one datacenter, probably everyday you face the problem of distributing data on all your service machines.<br />
<br />
<div style="text-align: right;">
<span style="text-align: center;">Remember: 60MiB/sec * 1hour = ~210GiB</span></div>
<div style="text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjBYEPamLx4Bx5J15hLRWdcteokCExLjP0sQQOwGhl_drzUhtr7spj1PrEc8sGNHjnv_Ynzq-ef8DTcB7NcBIDHJSfV0tjTAlwEWjahTsrUaJetAPZFx676VtXuaG91YJCmBKEoJ68ijjU/s1600/BtDistMachines.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjBYEPamLx4Bx5J15hLRWdcteokCExLjP0sQQOwGhl_drzUhtr7spj1PrEc8sGNHjnv_Ynzq-ef8DTcB7NcBIDHJSfV0tjTAlwEWjahTsrUaJetAPZFx676VtXuaG91YJCmBKEoJ68ijjU/s1600/BtDistMachines.png" /></a><br />
So what are the possible solution to transfer this blobs?</div>
The first solution is copying all the data to one machine in each datacenter, and then each machine with the data is responsible to copy everything to all the other machines inside the datacenter.<br />
<i>Note: prefer rsync over scp, since if you lost connection with scp you need to retransfer everything from byte zero.</i><br />
<br />
But what happens if a machine is down?<br />
One of the solution is making all the machines part of this distribution, removing identities. Every machine is equal, every machine need to fetch these blobs. So, instead of using rsync from the "build" machine to the dist-host and from dist-host to service machines the "build" machine send an information "I've new data" and each machine starts fetching this data in a collaborative way (using bittorrent).<br />
<br />
Each machine <i>(build-machine/dist-hosts/services) </i>need to run a <a href="https://github.com/matteobertozzi/misc-common/blob/master/torrent/torrent.py">torrent client</a>, you can implement your torrent client in few lines of python using <a href="http://libtorrent.com/">libtorrent</a>. The idea is to fetch from a feed hosted on a build machine the latest blobs.torrent and start downloading. The build machine will be the initial seeder, but then every machine will be part of the data distribution. By writing your own <a href="https://github.com/matteobertozzi/misc-common/blob/master/torrent/tracker.py">tracker</a> you can also tune your peer selection, preferring machines inside your datacenter or inside your rack to avoid cross-site latency.<br />
<br />
Another important thing to remember, if your service rely on the buffer-cache to keep data in memory, is to tell to the system, to avoid evict your pages otherwise you'll probably see your service starting to slow down once you start to copy data to that machine... So make sure to mlock() your heavily used pages or if your blobs can be kept in memory use <a href="http://hoytech.com/vmtouch/">vmtouch</a> to do the trick (vmtouch -l -d -m 64G blob) remember to add memlock entry for your user in /etc/security/limits.d/ otherwise you'll see mlock() fail.<br />
<br />
You can find the source code of a simple command line bit-torrent client and a tracker at <a href="https://github.com/matteobertozzi/misc-common/tree/master/torrent">https://github.com/matteobertozzi/misc-common/tree/master/torrent</a>.Matteo Bertozzihttp://www.blogger.com/profile/04630649852079843031noreply@blogger.com0Stockholm, Sweden59.3155556 18.033888959.307452600000005 18.0141479 59.3236586 18.0536299tag:blogger.com,1999:blog-8136012147929167933.post-88005234438922295402012-04-21T19:00:00.000-07:002012-05-18T04:00:33.087-07:00Improve and Tune your service/app with some statistics<i>One of the good thing to be in a data-driven company is that every decision must be based on the data that you've collected. For someone this means just Marketing decision, but you can do the same thing to improve your services, applications and code.</i><br />
<br />
Think at these questions:<br />
<ul>
<li>Is my code faster/slower between version A and B?</li>
<li>Is my code using much/more memory between version A and B?</li>
<li>Is someone still using feature A?</li>
<li>Which are the most used features?</li>
</ul>
If you look at the question, you can easy realize that these are not problems related just to big companies with lots of data, so even your small application can benefit from some stats.<br />
<br />
One of the main stopper to do that is that is really difficult modify your application to add some stats support, because you really don't know what are your questions and you don't know what kind of output do you want.<br />
<br />
What do you want is just a tiny call like: collect("func(x) time", 10sec)<br />
And sometimes later you can decide.. ok I want to see what is the average of func(x) time between jan-feb (version A) and mar-apr (version B).<br />
Or if you want keep track of features used you can call something like: collect("feature-used", "My Feature A"). And later you can decide to query for specified feature X to see when is last time that was used, or you can query for the most used features or something else.. but is really difficult to know in advance what you want to keep track.<br />
<br />
<i>Ok, now that you've understood a bit the problem that we want to solve, the fun part begins.</i><br />
The main idea is to have a super light-weight "Stats Uploader" to collect your data with one single line of code and send to a collector, later on you can ask questions to your data (completely detached from your application).<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj3HCbQBlQkK6lKinL8Y7SV3buTvRU-nbpiepNLWJkTkvSscm1KqMzljbNEZxmZmLhHvKlgTydN91WE2Mzl65eflfXSTgXnKZnLCpGOo25SvwgEOzzjJNzLzj63JfngKQujWdgw4haY8s8/s1600/CollectionAggregationVisualization.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj3HCbQBlQkK6lKinL8Y7SV3buTvRU-nbpiepNLWJkTkvSscm1KqMzljbNEZxmZmLhHvKlgTydN91WE2Mzl65eflfXSTgXnKZnLCpGOo25SvwgEOzzjJNzLzj63JfngKQujWdgw4haY8s8/s1600/CollectionAggregationVisualization.png" /></a></div>
As you can see from the schema above, your application send data to a "<i>Collector</i>" service, that can store your information in different ways (You can write your custom Sink to take care of specific keys, and store in a format that fit better your needs).<br />
The <i>Aggregator</i> fetch the data required to answer your question and applies your custom logic to extract your answer.<br />
The <i>Viewer</i> is just a front-end to display nicely your data, like a web service that plot some charts and table. It ask questions to the aggregator and displays to you.<br />
<br />
<i>The code is available on github at <a href="https://github.com/matteobertozzi/skvoz">https://github.com/matteobertozzi/skvoz</a>.</i><br />
<i>Probably I'll give a talk about this at <a href="https://ep2012.europython.eu/">EuroPython</a> (<a href="https://ep2012.europython.eu/">EP2012</a>) .</i>Matteo Bertozzihttp://www.blogger.com/profile/04630649852079843031noreply@blogger.com0Stockholm, Sweden59.32893 18.0649159.199335 17.749053 59.458525 18.380767000000002tag:blogger.com,1999:blog-8136012147929167933.post-79416002806990307962012-04-20T20:00:00.000-07:002012-04-20T20:00:00.212-07:00Embedded Store, under the hood...This week I've found an interesting bug, that can be summarized in this way. <i>The user does not have any idea of what happens under the hood, and his main usage is always against your design.</i><br />
<br />
To give you more context, the bug was related to embedded storage systems, something like bsddb, sqlite or just your simple B+Tree or your on-disk HashTable.<br />
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj58JNPr7Gq0GyfPsrW_pgyH7LStBwsGXpUqeicjWXdMXdiXaHZW8FHBKkf7TqZ-ijEJppKKXSn8qEl8LjkFFCkwyChvEpatUQk2FoojBUgZT98Io0oBEcsNK_somA2vi6GHQlywX98VZE/s1600/SimpleEmbeddedStoreAPI.png" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj58JNPr7Gq0GyfPsrW_pgyH7LStBwsGXpUqeicjWXdMXdiXaHZW8FHBKkf7TqZ-ijEJppKKXSn8qEl8LjkFFCkwyChvEpatUQk2FoojBUgZT98Io0oBEcsNK_somA2vi6GHQlywX98VZE/s1600/SimpleEmbeddedStoreAPI.png" /></a><br />
So, How an embedded storage system is designed?<br />
As you can see from the simplified schema on the right<br />
<ul>
<li>The lowest level is the raw access to the disk data structure (e.g. B+Tree, HashTable, ...) so each request goest directly to disk.</li>
<li>On top of that, to speedup things, you add a cache to avoid fetching data from disk all the time.</li>
<li>And everything is packed in a nice api that provides you some sort of get and put functionality, at maximum speed using the cache.</li>
</ul>
<br />
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj80alWy8PgMNOvvPPyuQHdhzKfJLBOjWjNrMEJ_ByKZbPgyVd2Cw3JqYlFV6zzU_FV8tPKVwJSQ8LPvyQNnYka3eSf4Aka-B3-b-6j7mbEh82xRLjKpx-eJ9rp-1Eybd2WeVel7X294bo/s1600/EmbedStoreUsage1.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj80alWy8PgMNOvvPPyuQHdhzKfJLBOjWjNrMEJ_ByKZbPgyVd2Cw3JqYlFV6zzU_FV8tPKVwJSQ8LPvyQNnYka3eSf4Aka-B3-b-6j7mbEh82xRLjKpx-eJ9rp-1Eybd2WeVel7X294bo/s1600/EmbedStoreUsage1.png" /></a>Everything seems fine, You can create an application that access your library capable of handling tons of request without accessing the disk due to the cache layer and so on, and you can think even to build a service to be able to query your storage from a remote host, and here the problems begin.<br />
<br />
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhbSBmJN8CmYvAQQXPsZjhxh-FoAftsQqgKt1O3_CiXqwTydCf96d99F7zdikKxHiXP4oi7V1BFIsL6gJGsF6fNU_E1Cu5WxctNug2PywTxKsjE6Riu8iR8wh92MfSc3vsw1FkQz1ddIWA/s1600/EmbedStoreUsage2.png" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhbSBmJN8CmYvAQQXPsZjhxh-FoAftsQqgKt1O3_CiXqwTydCf96d99F7zdikKxHiXP4oi7V1BFIsL6gJGsF6fNU_E1Cu5WxctNug2PywTxKsjE6Riu8iR8wh92MfSc3vsw1FkQz1ddIWA/s1600/EmbedStoreUsage2.png" /></a><br />
Your first super happy user arrive and decide to build its super scalable infrastructure with your embedded storage.<br />
..and what is the easy way to get a super scalable service? obviously adding some threads.. but threads are not a problem, because the user has learned the lesson and now knows that he should not use shared variables. So the brilliant solution is each thread has its own instance of the "storage object", to be more clear each thread do something like db.open("super-storage.db")<br />
<br />
Everything seems fine... but after a couples of days the user started crying... sometimes data is missing, logs contains strange page not found messages, some part of the store is corrupted, and so on...<br />
<br />
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEibuhaqbJvsiBlqD_VmDiLiy5A8-xOaOb9TsjoCW-UTDiVadouT5YNvVbJ0AJYXVegUuT0PRoSR-LOnyfgpY_E612hMGZZWVwzO14OjVJ3UySJPautJYq9LK4aiqLHui-qOIvKDLsK-CFY/s1600/EmbedStoreUsage3.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEibuhaqbJvsiBlqD_VmDiLiy5A8-xOaOb9TsjoCW-UTDiVadouT5YNvVbJ0AJYXVegUuT0PRoSR-LOnyfgpY_E612hMGZZWVwzO14OjVJ3UySJPautJYq9LK4aiqLHui-qOIvKDLsK-CFY/s1600/EmbedStoreUsage3.png" /></a>Can you spot the problem? Yes, is the cache...<br />
No one is aware of the changes in the file, every thread use its own cache, and the first request to a block not in cache ends up to create some bad state.<br />
<br />
So the solution for the user is to use the library as you've designed, with just one thread/process/what ever that access the store file.<br />
<br />
But if you want slow down your super cool library and make the user happy you can always add an ID to the super-block and every time the user request something... you fetch the super-block from disk, compare with the one in cache, and if they are different you can just invalidate all the caches...Matteo Bertozzihttp://www.blogger.com/profile/04630649852079843031noreply@blogger.com3tag:blogger.com,1999:blog-8136012147929167933.post-81266575358489573522012-02-26T05:10:00.000-08:002012-02-26T22:02:13.839-08:00Thoughts on bucket flushing, block size and compression...<div class="separator" style="clear: both; text-align: left;">
<i>This post is just a collection of thoughts, on how to store data. I hope to get some feedback and new ideas from you guys, thanks!</i></div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
Since I've started working on B*Trees, I've always assumed to have a fixed block size. With this "restriction" & "simplification", you can easily come up with a block in this format:</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjRC3WuDQ91ThurTvGHzFIn0K7D-O7nv4-1K6bNzZbGJSdAxBZZ732B6pGr9m6cX9l6a4HSthkCssAVFV0R8PrfmAmYrSFA-Y1aeQeboXZIvllidrUOtD2LBiu00mMg_W3CidRWc57N4w8/s1600/Bucket-Fixed-BlkSize.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjRC3WuDQ91ThurTvGHzFIn0K7D-O7nv4-1K6bNzZbGJSdAxBZZ732B6pGr9m6cX9l6a4HSthkCssAVFV0R8PrfmAmYrSFA-Y1aeQeboXZIvllidrUOtD2LBiu00mMg_W3CidRWc57N4w8/s1600/Bucket-Fixed-BlkSize.png" /></a></div>
<div class="separator" style="clear: both; text-align: left;">
Keys are packed together in the beginning of the block and values are packed together in the end of the block, growing up toward the center. In this way you don't have to move data when a new key is added or keys & values when one value grows.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
Assuming that your inserts in the block are already sorted (e.g. flush "memstore" to disk), in this way you can even compress keys & values with different algorithms.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
<i>...but, with the fixed size block and values starting from the end you need to allocate a full block.</i></div>
<br />
In contrast, you can "stream" your data and flush it, just few kb of data at the time. In this case you don't have to allocate a full block, but you've lost the ability to use different compressions for keys & values and the ability to keep in memory only the keys without doing memcpys.<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiQiKlBMsX-br2x-GgbyyT7GlWoocTouszL3CqEwfa6BRd4KHO_8Ov1RVVsclxK_DXnQPDADAu_CbBPjGex6_cv5HUcjQ0L9WNOEKB2ckW1V08aKMDowmctVbnou36LFprqr5StxxAyrvU/s1600/Bucket-Streming.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiQiKlBMsX-br2x-GgbyyT7GlWoocTouszL3CqEwfa6BRd4KHO_8Ov1RVVsclxK_DXnQPDADAu_CbBPjGex6_cv5HUcjQ0L9WNOEKB2ckW1V08aKMDowmctVbnou36LFprqr5StxxAyrvU/s1600/Bucket-Streming.png" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
Another possibility is traverse the data twice, the first time writing the keys and the second time writing the values. In this case you gained the different compression features but if you're using compression you're not able to stop after a specified block size threshold because you don't know how much space each key & value takes.</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgkD2cjcdcCG3cmG3WJ8KTsnJwjjyAx4q-_9vi00wjL4zX_z-VSBJdxyPo2pbGMxeCWnoHojxDJiXOWk0oSKkO1wABJuDH7YMokG25C-xRt5CYoYgvYVyJYR0jmRXm5iIv9M5nq6C2xQNc/s1600/Bucket-Fixed-Items.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgkD2cjcdcCG3cmG3WJ8KTsnJwjjyAx4q-_9vi00wjL4zX_z-VSBJdxyPo2pbGMxeCWnoHojxDJiXOWk0oSKkO1wABJuDH7YMokG25C-xRt5CYoYgvYVyJYR0jmRXm5iIv9M5nq6C2xQNc/s1600/Bucket-Fixed-Items.png" /></a></div>
<br />
<div>
<i>Any comments, thoughts, ideas?</i></div>Matteo Bertozzihttp://www.blogger.com/profile/04630649852079843031noreply@blogger.com0tag:blogger.com,1999:blog-8136012147929167933.post-68694497465699035562012-02-26T04:39:00.001-08:002012-02-26T22:01:47.189-08:00Moved to Stockholm & Back to Music and Data!<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEge7YsLLC7VP5Chffe_e_FN-AIpq2pQ4t5BnpwQ7ELRT3BqSmvPZ9O1G5mnajBhP3rxbdnw0YzpRsiCFBnfKjJFvWU71KLUbub8oatwBMiLEmZhXJL66Tr6511_7ySyAkw0qI_meDdmiqE/s1600/LDSM-Spotify.JPG" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="400" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEge7YsLLC7VP5Chffe_e_FN-AIpq2pQ4t5BnpwQ7ELRT3BqSmvPZ9O1G5mnajBhP3rxbdnw0YzpRsiCFBnfKjJFvWU71KLUbub8oatwBMiLEmZhXJL66Tr6511_7ySyAkw0qI_meDdmiqE/s400/LDSM-Spotify.JPG" width="297" /></a></div>
A couple of weeks ago I've started my new job at <a href="http://www.spotify.com/">Spotify AB</a> (<a href="http://maps.google.com/maps?q=Stockholm,+Sweden&z=5">Stockholm, Sweden</a>).<br />
<br />
The last two years at <a href="http://www.develer.com/">Develer</a> (<a href="http://maps.google.com/maps?q=Florence,+Italy&z=6">Florence, Italy</a>) were fantastic, great environment, great people, great conferences <a href="http://www.pycon.it/pycon4">PyCon4</a>, <a href="http://ep2012.pycon.it/">Euro Python</a>, <a href="http://www.qtday.it/">QtDay</a>, and I've to thank especially <i>Giovanni Bajo</i>, <i>Lorenzo Mancini</i>, <i>Simone Roselli</i> and <i>Francesco Pallanti</i> (<a href="http://www.ariazero.it/">AriaZero</a>), and many more, for all the support in these two years. Thanks again guys!<br />
<br />
...but now I'm here, new company, new country, new language (funny language) and new challenges.<br />
<br />
Stockholm is beautiful and is not that cold as I had imagined, (even with -18 degrees celsius), but I'm still don't able to find good biscuits, how can you live without biscuits?<br />
<br />
Since my new job is more about networking & data, new blog post will be slightly different, from the previous ones... less ui oriented and more data & statistic oriented.<br />
<br />
Keep a look at interesting <a href="http://meetup.com/cities/se/stockholm/">meetup in stockholm</a>, I will be there. <i>(Next one is <a href="http://www.meetup.com/pysthlm/">Python Stockholm</a>)</i>.<br />
<br />
<div style="text-align: right;">
<i>...And don't forget to use <a href="http://www.spotify.com/">Spotify</a> (Love, Discover, Share Music)!</i></div>Matteo Bertozzihttp://www.blogger.com/profile/04630649852079843031noreply@blogger.com0tag:blogger.com,1999:blog-8136012147929167933.post-5644816265224755262012-02-05T10:15:00.000-08:002012-02-26T22:01:15.587-08:00AesFS - Encrypted File-System layerLast week I've spent a couple of hours playing with OpenSSL and CommonCrypto, and the result is a tiny layer on top the file-system to encrypt/decrypt files using <a href="http://it.wikipedia.org/wiki/Advanced_Encryption_Standard">AES</a>.<br />
<br />
The source code is available on <a href="https://github.com/matteobertozzi">my github</a> at <a href="https://github.com/matteobertozzi/misc-common/tree/master/aesfs">misc-common/aesfs</a>. To build just run '<i>python build.py</i>' and the result is placed in <i>./build/aesfs/</i> and <i>./build/aespack/</i>. AesPack is a command line utility to pack and unpack single files, while aesfs is a fuse file-system.<br />
<br />
You can run aesfs with:<br />
<pre><code>aesfs -o root=/my/plaindir /mnt/encrypted</code></pre>
Since AesFS is on top your file-system you've to specify (with -o root) the directory where you want to store files, while the /mnt/ is the mount point where you can read/write your files in clear.<br />
<br />
Files are written in blocks of 4k (8 bytes of header, 16 extra bytes for aes, and 4072 bytes of data). Check <a href="https://github.com/matteobertozzi/misc-common/blob/master/aesfs/src/block.h"><i>block.h</i></a> and <i><a href="https://github.com/matteobertozzi/misc-common/blob/master/aesfs/src/block.h">block.c</a></i> for more information.Matteo Bertozzihttp://www.blogger.com/profile/04630649852079843031noreply@blogger.com2tag:blogger.com,1999:blog-8136012147929167933.post-80148182438903186562011-11-19T08:59:00.000-08:002011-11-19T09:40:20.773-08:00Drawing Charts with Python & Qt4Back again with some graphics stuff that can be useful in monitoring applications.<br />
As you can immagine, this charts are 100% QPainter. The source code is available on <a href="https://github.com/matteobertozzi/blog-code/blob/master/qt4-charts/chart.py">blog-code@github</a>.<br />
<br />
<b>Pie Chart</b><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgjgzItW4QxzwNDjZPTwgfxeeKe0grz5h86-PxUy0GPIQ5CnIXaCRYDVTPLsR55b3YOdUZCGkE-XXC3_BkGqdUYz2ZijJxGMd4UmnfhKkahI-Pyo1Aa3YMeU1fkggg02uxZ2WLcscgPhSY/s1600/pie.png" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="140" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgjgzItW4QxzwNDjZPTwgfxeeKe0grz5h86-PxUy0GPIQ5CnIXaCRYDVTPLsR55b3YOdUZCGkE-XXC3_BkGqdUYz2ZijJxGMd4UmnfhKkahI-Pyo1Aa3YMeU1fkggg02uxZ2WLcscgPhSY/s200/pie.png" width="200" /></a>
<br />
<pre>table = DataTable()
table.addColumn('Lang')
table.addColumn('Rating')
table.addRow(['Java', 17.874])
table.addRow(['C', 17.322])
table.addRow(['C++', 8.084])
table.addRow(['C#', 7.319])
table.addRow(['PHP', 6.096])
chart = PieChart(table)
chart.save('pie.png', QSize(240, 240), legend_width=100)
</pre>
<br />
The usage is really simple, you have to create your table with columns and data, create a chart object using the table that you've created and you can call the draw() or save() method to show/save the chart somewhere.<br />
<br />
<b>Scattered Chart</b>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhN7_uu2WPDCsEBA1xnOLBt813oaWOz0zcmAwGWYYTo3hr8PAYM2gWrLR2ylpiVRWWYnTEO6Q_cjggcwYRNVoA-xAsaKm_sMCQbLvIWZzV7xwov-HkF73uq5XxR1Um4Z7YR1I739YSixgA/s1600/scatter.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="152" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhN7_uu2WPDCsEBA1xnOLBt813oaWOz0zcmAwGWYYTo3hr8PAYM2gWrLR2ylpiVRWWYnTEO6Q_cjggcwYRNVoA-xAsaKm_sMCQbLvIWZzV7xwov-HkF73uq5XxR1Um4Z7YR1I739YSixgA/s320/scatter.png" width="320" /></a></div>
<pre>chart = ScatterChart(table)
chart.haxis_title = 'Proc input'
chart.haxis_vmin = 0
chart.haxis_vmax = 16
chart.haxis_step = 2
chart.vaxis_title = 'Quality'
chart.vaxis_vmin = 90
chart.vaxis_vmax = 104
chart.vaxis_step = 1
</pre>
<br />
<br />
You can customize the min/max value and the step of horizontal and vertical axis, ore you can use the default calculated on your data. You can also set the Reference column with setHorizontalAxisColumn() or setVerticalAxisColumn().<br />
<br />
<b>Area Chart</b><br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhouEGOVinWOYAUXp_BGPOCHSERP01aEXUdAVvoMUnibDqiQsREA1Aa6Mae0qeKDa8i-krDgjCb3kahbRCDWJzfDK8_iJKJFb0MGQG7Blg1OGRQUyJndybSwATWhNi3NK86f1yg9V3TH9U/s1600/area.png" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="153" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhouEGOVinWOYAUXp_BGPOCHSERP01aEXUdAVvoMUnibDqiQsREA1Aa6Mae0qeKDa8i-krDgjCb3kahbRCDWJzfDK8_iJKJFb0MGQG7Blg1OGRQUyJndybSwATWhNi3NK86f1yg9V3TH9U/s320/area.png" width="320" /></a></div>
<pre>table = DataTable()
table.addColumn('Time')
table.addColumn('Site 1')
table.addColumn('Site 2')
table.addRow([ 4.00, 120, 500])
table.addRow([ 6.00, 270, 460])
table.addRow([ 8.30, 1260, 1120])
table.addRow([10.15, 2030, 540])
table.addRow([12.00, 520, 890])
table.addRow([18.20, 1862, 1500])
chart = AreaChart(table)
chart.setHorizontalAxisColumn(0)
chart.haxis_title = 'Time'
chart.haxis_vmin = 0.0
chart.haxis_vmax = 20.0
chart.haxis_step = 5
chart.save('area.png', QSize(400, 240), legend_width=100)
</pre>
<br />
<br />
<b>Line Chart</b><br />
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgaHax31Jz930blX9bUBCymhDNoFPY9sSt3ummvj3YMUsqJS6d-b42FSQF2bvmmgVGqgCrFx0TEtxrD_JEjzk1MP7FhmknLhdEjDZu_f2tAVm4GlMi0Tl4E3ebR1hK_TzEGCWeF8nBrJKE/s1600/line.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="153" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgaHax31Jz930blX9bUBCymhDNoFPY9sSt3ummvj3YMUsqJS6d-b42FSQF2bvmmgVGqgCrFx0TEtxrD_JEjzk1MP7FhmknLhdEjDZu_f2tAVm4GlMi0Tl4E3ebR1hK_TzEGCWeF8nBrJKE/s320/line.png" width="320" /></a>
<br />
<br />
<pre>chart = LineChart(table)
chart.setHorizontalAxisColumn(0)
chart.haxis_title = 'Time'
chart.haxis_vmin = 0.0
chart.haxis_vmax = 20.0
chart.haxis_step = 2
</pre>
<br />
<br />
<br />
Once again, the code is available on github at <a href="https://github.com/matteobertozzi/blog-code/blob/master/qt4-charts/chart.py">blog-code/qt4-charts/chart.py</a>.Matteo Bertozzihttp://www.blogger.com/profile/04630649852079843031noreply@blogger.com1tag:blogger.com,1999:blog-8136012147929167933.post-52940255654240571592011-11-19T07:54:00.001-08:002011-11-19T09:39:45.225-08:00Don't miss the Florence Qt Day 2012<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh8z9lNhU7h1dxaXs8tSvzQlB3uUeOmdXdTctNbvHjNuDFSQzfpfwUlSdqsoIttKqISPh2BxMYk9saECZBjhyphenhyphenDAWIP5K4WpTF262bQKQDVrfbUZaWlM5I6MYLZt28eaB1Cpyvp4IlE7JhY/s1600/badge_320x192.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh8z9lNhU7h1dxaXs8tSvzQlB3uUeOmdXdTctNbvHjNuDFSQzfpfwUlSdqsoIttKqISPh2BxMYk9saECZBjhyphenhyphenDAWIP5K4WpTF262bQKQDVrfbUZaWlM5I6MYLZt28eaB1Cpyvp4IlE7JhY/s1600/badge_320x192.jpg" /></a></div>
The conference will take place on 27/28 January 2012, AC Hotel Firenze Porta al Prato (Florence, Italy). <b><i>And it is Free!</i></b><br />
<br />
<ul>
<li>The Qt Project</li>
<li>Qt 5.0</li>
<li>Qt Quick</li>
<li>Qt WebKit</li>
<li>Performance & Profiling</li>
<li>Qt in Use</li>
<li>...And many more</li>
</ul>
<br />
<br />
Take a look at <a href="http://www.qtday.it/">http://www.qtday.it</a> for more information.Matteo Bertozzihttp://www.blogger.com/profile/04630649852079843031noreply@blogger.com0tag:blogger.com,1999:blog-8136012147929167933.post-51023957870589506692011-07-30T23:52:00.000-07:002016-12-22T21:09:17.719-08:00RaleighFS to enter in the in-memory key-value store market<i>A couple of guys asked me about RaleighFS, and why is called File-System instead of Database, and the answer is that the project is started back in 2005 as a simple Linux Kernel File-System, to evolve in something different.</i><br />
<br />
<b>Abstract Storage Layer</b><br />
I like to say that RaleighFS is an Abstract Storage Layer, because is main components are designed to be plugable. For example the namespace can be flat or hierarchical, and the other objects don't feel the difference.<br />
<ul>
<li>Store Multiple Objects with different Types (HashTable, SkipList, Tree, Extents, Bitmap, ...)</li>
<li>Each Object as it's own on-disk format (Log, B*Tree, ...).</li>
<li>Observable Objects - Get Notified when something change.</li>
<li>Flexible Namespace & Semantic for Objects.</li>
<li>Various Plain-Text & Binary Protocol Support (Memcache, ...)</li>
</ul>
<br />
<b>A New Beginning...</b><br />
Starting weeks ago, I've decided to rewrite and refactor a bit of code, stabilize the API and, this time, trying to bring the file-system and the network layer near to a stable release.<br />
<b>First Steps are:</b><br />
<ul>
<li>Release a functional network layer as soon as I can.</li>
<li>Providing a pluggable protocol interface.</li>
<li>Implement a <a href="http://memcachedb.googlecode.com/svn/trunk/doc/protocol.txt">memcache</a> capable and other protocols.</li>
</ul>
So, these first steps are all about networking, and unfortunately, this means dropping the sync part and keep just the the in-memory code (the file-system flush on memory pressure).<br />
<br />
<b>Current Status:</b><br />
Starting from today, some code is available on github under <a href="https://github.com/matteobertozzi/RaleighFS">raleighfs</a> project.<br />
<ul>
<li><i>src/zcl</i> contains the abstraction classes and some tool that is used by every piece of code.</li>
<li><i>src/raleighfs-core</i> contains the file-system core module.</li>
<li><i>src-raleighfs-plugins</i> contains all the file-system's pluggable objects and semantics layers.</li>
<li><i>src/raleigh-server currently</i> contains the entry point to run a memcache compatible (memccapable text protocol), and a redis get/set interface server. The in-memory storage is relegated in engine.{h,c} and is currently based on a Chained HashTable or a Skip List or a Binary Tree.</li>
</ul>
<br />
<b>How it Works</b><br />
As I said before the entry point is the ioloop, that allows clients to interactot through a specified protocol with the file-system's objects. Each "protocol handler" parse it's own format, convert it to the file-system one, and enqueue the request to a RequestQ that dispatch the request to the file-system. When the file-system has the answer push the response into the RequestQ and the client is notified. The inverse process is applied the file-system protocol is parsed and converted into the client one.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhlG9Xc2QxVESbIr_P0_z7r15CEpjnKwKKfDqpaMX3qOr1eOxKEQF7QQs8LHZ9vbbT-q5fSP15iXm8lAbbNJhTU_jwr6-0ECI7itA3rKgsEi7a54Wr4_sZ2EcmXtMO3Tt8nIIl7QLGGQAU/s1600/RaleighFSv5-550.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhlG9Xc2QxVESbIr_P0_z7r15CEpjnKwKKfDqpaMX3qOr1eOxKEQF7QQs8LHZ9vbbT-q5fSP15iXm8lAbbNJhTU_jwr6-0ECI7itA3rKgsEi7a54Wr4_sZ2EcmXtMO3Tt8nIIl7QLGGQAU/s1600/RaleighFSv5-550.png" /></a></div>
<br />
Having the RequestQ has a couple advantages, the first one is that you can wrap easily a protocol to communicate with the filesystem, the other one is that the RequestQ can dispatch the request to different servers. Another advantage is that the RequestQ can operate as a Read-Write Lock for each object allowing the file-system to have less lock...<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj-7XvdEWCyTP3UVnA3UupV3gtDb30gYkDXYvQ_A4cbhAR4s0g7rhR8VCx8ZKgf7hvE5Il2xlR12vX9BtVMZ0JBHsO_Ivsbe4SdIOath6PCUe6Btk6vPRDaDeUaKPptjkVx0lRXMFQEOFE/s1600/mc-bench-i5.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="300" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj-7XvdEWCyTP3UVnA3UupV3gtDb30gYkDXYvQ_A4cbhAR4s0g7rhR8VCx8ZKgf7hvE5Il2xlR12vX9BtVMZ0JBHsO_Ivsbe4SdIOath6PCUe6Btk6vPRDaDeUaKPptjkVx0lRXMFQEOFE/s640/mc-bench-i5.png" width="640" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<br />
<i>For more information ask me at theo.bertozzi (at) gmail.com.</i>Matteo Bertozzihttp://www.blogger.com/profile/04630649852079843031noreply@blogger.com0tag:blogger.com,1999:blog-8136012147929167933.post-31574106635666793722011-02-18T09:50:00.000-08:002011-02-18T09:50:16.872-08:00Getting started with AvroApache <a href="http://avro.apache.org/">Avro</a> is a language-neutral data serialization system. It's own data format can be processed by many languages (currently C, C++, Python, Java, Ruby and PHP).<br />
<br />
Avro provides:<br />
<ul><li>Rich data structures.</li>
<li>A compact, fast, binary data format.</li>
<li>A container file, to store persistent data.</li>
<li>Remote procedure call (RPC).</li>
</ul><br />
<span class="Apple-style-span" style="font-size: large;">Data Schema</span><br />
Avro relies on schemas, that specifies which fields and types an object is made. In this way, each datum is written with no per-value overhead. When Avro data is stored in a file, its schema is stored with it, so that files may be processed later by any program.<br />
<br />
Avro has traditional <a href="http://avro.apache.org/docs/current/spec.html#schema_primitive">Primitive Types</a> like int, float, string, ... and other <a href="http://avro.apache.org/docs/current/spec.html#schema_complex">Complex Types</a> like enum, record, array, ... You can use this types to create your own complex types like in example below:<br />
<pre><code>{
"type": "record",
"name": "Person",
"fields": [
{"name": "name", "type": "string"},
{"name": "age", "type": "int"},
{"name": "emails", "type": {"type": "array", "values": "string"}},
{"name": "father", "type": "Person"},
{"name": "mother", "type": "Person"},
]
}</code></pre>You can create schemes by code using the Schema class methods, or just parsing a json file using the Schema.parse() method.<br />
<br />
<span class="Apple-style-span" style="font-size: large;">Reading & Writing</span><br />
Once that you've written the schema you can start to serialize your objects, generating the right data structure for your types.<br />
<br />
An example of serialization for the schema written above, can be something like:<br />
<pre><code>public GenericData.Record serialize() {
GenericData.Record record = new GenericData.Record(schema);
record.put("name", this.name);
record.put("age", this.age);
int nemails = this.mails.length();
GenericData.Array emails = new GenericData.Array(nemails, emails_schema);
for (int i = 0; i < nemails; ++i)
record.put(this.mails[i]);
record.put("emails", emails);
record.put("father", this.father.serialize());
record.put("mother", this.mother.serialize());
}
</code></pre>The same code written in python looks like this:<br />
<pre><code>def serialize(self):
return { 'name', self.name,
'age', self.age,
'emails': self.mails,
'father': self.father.serialize()
'mother': self.mother.serialize()
}
</code></pre>Now that you've the Avro Object that reflect the schema, you've just to write it. To do that you've to use a DatumWriter that uses an Encoder to write the datum on an OutputStream.<br />
<pre><code>...
Encoder encoder = BinaryEncoder(outputStream);
GenericDatumWriter datumWriter = new GenericDatumWriter(schema);
datumWriter.write(person.serialize(), encoder);
...
</code></pre>As you can imagine, reading data is quite similar. Pick up a DatumReader and a Decoder that can read from an InputStream and start reading your Avro Objects.<br />
<pre><code>...
Decoder decoder = BinaryDecoder(inputStream);
GenericDatumReader datumReader = new GenericDatumReader(schema);
GenericData.Record record = new GenericData.Record(schema);
while (...) {
datumWriter.read(record, decoder);
// record.get("name")
// record.get("...");
}
...
</code></pre><br />
<span class="Apple-style-span" style="font-size: large;">Object Container Files</span><br />
Avro includes an object container file format. A file has a schema, and all objects stored in the file must be written according to that schema.<br />
<br />
Since Avro is designed to be used with Hadoop and Map-Reduce, the file format is similar to the <a href="http://www.cloudera.com/blog/2011/01/hadoop-io-sequence-map-set-array-bloommap-files/">Hadoop' SequenceFile</a>. Objects are grouped in blocks and each block may be compressed. Between each block a sync-marker is added to allow an efficient splitting of files.<br />
<pre><code>void testWrite (File file, Schema schema) throws IOException {
GenericDatumWriter datum = new GenericDatumWriter(schema);
DataFileWriter writer = new DataFileWriter(datum);
writer.setMeta("Meta-Key0", "Meta-Value0");
writer.setMeta("Meta-Key1", "Meta-Value1");
writer.create(schema, file);
for (Person p : people)
writer.append(p.serialize());
writer.close();
}
</code></pre>Since the File contains the schema, you don't need to specify a schema for the reader. You can extract the used by calling the getSchema() method of the reader.<br />
<pre><code>void testRead (File file) throws IOException {
GenericDatumReader datum = new GenericDatumReader();
DataFileReader reader = new DataFileReader(file, datum);
GenericData.Record record = new GenericData.Record(reader.getSchema());
while (reader.hasNext()) {
reader.next(record);
System.out.println("Name " + record.get("name") +
" Age " + record.get("age"));
}
reader.close();
}
</code></pre><i>For a more "advanced" reading operation, (see the File Evolution example), you can specify the expected file schema.</i><br />
<br />
<span class="Apple-style-span" style="font-size: large;">Data Evolution</span><br />
The first problem that you'll encounter working with a custom binary format, or even using an XML/JSON based, is to deal with data evolution.<br />
<br />
During your application development you will surely have to add, remove or rename some fields from the various data structures. To solve the compatibility problem you've to introduce a "versioning step", that transforms your "Version X" document to a "Version (X + 1)" format.<br />
<br />
Avro has this problem solved applying some <a href="http://avro.apache.org/docs/current/spec.html#Schema+Resolution">Schema Resolution</a> rules. <i>In brief...</i><br />
<ul><li>If a field is <b>added</b>, old document doesn't contains the field and the new readers uses the default value, specified in the schema.</li>
<li>If a field is <b>removed</b>, new readers doesn't read it and no one cares if it's present or not.</li>
<li>If a field is <b>renamed</b>, new schema must contains the old name of the field in it's alias list.</li>
</ul><br />
<i>Note, that only the forward compatibility is covered.</i><br />
<br />
<span class="Apple-style-span" style="font-size: large;">Inter-Process Calls</span><br />
Avro makes RPC really easy, with a few lines of code you can write a full client/server.<br />
<br />
First of all, you need to write your protocol schema, specifying each messasge with request and response objects.<br />
<pre><code>{
"namespace": "test.proto",
"protocol": "Test",
"messages": {
"xyz": {
"request": [{"name": "key", "type": "string"}],
"response": ["bytes", "null"]
}
}
}</code></pre>A simple java server can be written in this way. You define the respond method, handling each message, and for each message you return the related response object.<br />
<pre><code>static class Responder extends GenericResponder {
public Object respond (Protocol.Message message, Object request) {
String msgName = message.getName();
if (msgName == "xyz") {
// Make a response for 'xyz' get data from request
// GenericData.Record record = (GenericData.Record)request;
// e.g. record.get("key")
return(response_obj);
}
throw new AvroRuntimeException("unexcepcted message: " + msgName);
}
}
public static void main (String[] args)
throws InterruptedException, IOException
{
Protocol protocol = Protocol.parse(new File("proto-schema.avpr"));
HttpServer server = new HttpServer(new Responder(protocol), 8080);
server.start();
server.join();
}</code></pre>The client connects to the server, and send the message with the specified schema format.<br />
<pre><code>def main():
proto = protocol.parse(file('proto-schema.avpr').read())
client = ipc.HTTPTransceiver('localhost', 8080)
requestor = ipc.Requestor(proto, client)
result = requestor.request('xyz', {'key': 'Test Key'})
print result
client.close()
</code></pre><br />
I've made a couple of examples (written in C, Java and Python) that shows how to use Avro Serialization and Avro IPC. Sources are available on my github at <a href="https://github.com/matteobertozzi/Hadoop/tree/master/avro-examples">avro-examples</a>.Matteo Bertozzihttp://www.blogger.com/profile/04630649852079843031noreply@blogger.com2tag:blogger.com,1999:blog-8136012147929167933.post-17584087627035135222011-02-12T11:50:00.000-08:002011-02-12T11:50:42.364-08:00Linux cgroups: Memory Threshold NotifierThrough cgroups Notification API you can be notified about changing status of a cgroup. Memory cgroup implements memory thresholds using cgroups notification API, It allows to register multiple memory and memsw thresholds and gets notifications when it crosses.<br />
<br />
This can be very useful if you want to maintain a cache but you don't want to exceed a certain size of memory.<br />
<br />
To register a threshold application need:<br />
<ul><li>create an eventfd using eventfd(2);</li>
<li>open memory.usage_in_bytes or memory.memsw.usage_in_bytes;</li>
<li>write string like "<event_fd> <fd of memory.usage_in_bytes> <threshold>"</li>
</ul><pre>...
// Open cgroup file (e.g. "memory.oom_control" or "memory.usage_in_byte")
snprintf(path, PATH_MAX, "%s/%s", cgroup, file);
cgroup_ctrl->fd = open(path, O_RDONLY);
cgroup_ctrl->efd = eventfd(0, 0);
// Prepare ctrl_string e.g.
// <event_fd> <fd of memory.oom_control>
// <event_fd> <fd of memory.usage_in_bytes> <threshold>
snprintf(ctrl_string, CTRL_STRING_MAX,
"%d %d", cgroup_ctrl->efd, cgroup_ctrl->fd);
// Write ctrl_string to cgroup event_control
snprintf(path, PATH_MAX, "%s/cgroup.event_control", cgroup);
fd = open(path, O_WRONLY);
write(fd, ctrl_string, strlen(ctrl_string));
close(fd);
...
</pre>Now you can add eventfd() descriptor to your epoll()/select() event loop and wait your notification. Here, you can handle your cache release.<br />
<pre>...
nfds = epoll_wait(epfd, events, NEVENTS, TIMEOUT);
for (i = 0; i < nfds; ++i) {
if (events[i].data.fd == cgroup_ctrl->efd) {
/* Memory Threshold Notification */
read(cgroup_ctrl->efd, &result, sizeof(uint64_t));
/* free some memory */
}
}
...
</pre>A full demo source code is avable on github at <a href="https://github.com/matteobertozzi/blog-code/tree/master/cgroup-mem-threshold">cgroup-mem-threshold demo</a>.Matteo Bertozzihttp://www.blogger.com/profile/04630649852079843031noreply@blogger.com0tag:blogger.com,1999:blog-8136012147929167933.post-15862597580451627612011-02-09T13:18:00.000-08:002011-02-09T13:18:59.114-08:00HBase I/O: HFile<div class="p1" style="font: 12px Helvetica; margin: 0px;">In the beginning HBase uses MapFile class to store data persistently to disk, and then (from version 0.20) a new file format is introduced. HFile is a specific implementation of MapFile with HBase related features.</div><div class="separator" style="clear: both;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjzRDnlF7yE739EPD1Q-IwVvO9s-GQXrzqlwpyfHb7Qp4AsPv9LHovRWvRUT3-5JwnaZPwgCX0-If3Uq7pfpEmMI_mtNY9ojrYXLb6P19SpLIVTz7cF-FRPlwffvkKgd0da-ZfEELoBAOU/s1600/HFile-Block-Record.png" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjzRDnlF7yE739EPD1Q-IwVvO9s-GQXrzqlwpyfHb7Qp4AsPv9LHovRWvRUT3-5JwnaZPwgCX0-If3Uq7pfpEmMI_mtNY9ojrYXLb6P19SpLIVTz7cF-FRPlwffvkKgd0da-ZfEELoBAOU/s1600/HFile-Block-Record.png" /></a></div><div class="p1" style="font: 12px Helvetica; margin: 0px;"><br />
HFile doesn't know anything about key and value struct/type (row key, qualifier, family, timestamp, …). As Hadoop' SequenceFile (Block-Compressed), keys and values are grouped in blocks, and blocks contains records. Each record has two Int Values that contains Key Length and Value Length followed by key and value byte-array.<br />
<br />
HFile.Writer has only a couple of append overload methods, one for KeyValue class and the other for byte-array type. As for SequenceFile, each key added must be greater than the previous one. If this condition is not satisfied an IOException() is raised.</div><div class="p1" style="font: 12px Helvetica; margin: 0px;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEifJGy7ximRVX0JKf0yAlV3Wu889NselGI8xKAKmFYP8rGJHBSAt8mwAK_H1FYEY_RU8KsyGTWq9MAnOK5qVnfDKa4aFVRtpLS2rYqHe9nJd5ojF6fgnZF_iqUKj4NvmdtZTul0EZ9y1js/s1600/HFile.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEifJGy7ximRVX0JKf0yAlV3Wu889NselGI8xKAKmFYP8rGJHBSAt8mwAK_H1FYEY_RU8KsyGTWq9MAnOK5qVnfDKa4aFVRtpLS2rYqHe9nJd5ojF6fgnZF_iqUKj4NvmdtZTul0EZ9y1js/s320/HFile.png" width="153" /></a></div><div class="p1" style="font: 12px Helvetica; margin: 0px;"></div><div class="p1" style="font: 12px Helvetica; margin: 0px;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgLX9Bwxr2xk8doHP42rBoQDruAnyI0DIgrZ8FdN_oGXhmpWx2ZQKnXlTL1AEKY2OhtXYsiD94VcV7Cn-p2CsTvFUO-axFiYGhf5qD9jRgDIjVp0NlaBhsXom4Mv19sDtoriVeqhc5df08/s1600/HFile-Block.png" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"></a><span class="Apple-style-span" style="color: black;"> </span><br />
<span class="Apple-style-span" style="color: black;">By default each 64k of data (key + value) records are squeezed together in a block and the block is written to the HFile OutputStream with the specified compression, if specified. Compression Algorithm and Block size are both (long)constructor arguments.</span><br />
<br />
<span class="Apple-style-span" style="color: black;">One thing that SequenceFile is not good at, is adding Metadata. Metadata can be added to SequenceFile just from the constructor, so you need to prepare all your metadata before creating the Writer.</span><br />
<br />
<span class="Apple-style-span" style="color: black;">HFile adds two "metadata" type. One called Meta-Block and the other called FileInfo. Both metadata types are kept in memory until close() is called. </span><br />
<br />
<span class="Apple-style-span" style="color: black;">Meta-Block is designed to keep large amount of data and its key is a String, while FileInfo is a simple Map and is preferred for small information and keys and values are both byte-array. Region-server' StoreFile uses Meta-Blocks to store a BloomFilter, and FileInfo for Max SequenceId, Major compaction key and Timerange info.</span><br />
<br />
<span class="Apple-style-span" style="color: black;">On close(), Meta-Blocks and FileInfo is written to the OutputStream. To speedup lookups an Index is written for Data-Blocks and Meta-Blocks, Those indices contains n records (where n is the number of blocks) with block information (block offset, size and first key). </span><br />
<span class="Apple-style-span" style="color: black;">At the end a Fixed File Trailer is written, this block contains offsets and counts for all the HFile Indices, HFile Version, Compression Codec and other few information.</span><br />
<br />
<span class="Apple-style-span" style="color: black;">Once the file is written, the next step is reading it. You've to start by loading FileInfo, the loadFileInfo() of </span><span class="Apple-style-span" style="color: black;">HFile.Reader </span><span class="Apple-style-span" style="color: black;">loads in memory the Trailer-block and all the indices, that allows to easily query keys. Through the HFileScanner you can seek to a specified key, and iterate over.</span></div><div class="p1" style="font: 12px Helvetica; margin: 0px;"><div class="separator" style="clear: both; text-align: center;"></div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjTXRA0QcWQ_dut8SuiAFapFtEXMvqxdsSMsaIAFLowu4mPSUutUdNWI2ZjBWqG6fTtNUMhgaXXl7NJCh4nHFPhokGmeMMXlxzSeUIQN3PKCoVpY2bhgfPBrPa5hXcY6_2R6kHBNpRtIAc/s1600/HFile-Structure.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjTXRA0QcWQ_dut8SuiAFapFtEXMvqxdsSMsaIAFLowu4mPSUutUdNWI2ZjBWqG6fTtNUMhgaXXl7NJCh4nHFPhokGmeMMXlxzSeUIQN3PKCoVpY2bhgfPBrPa5hXcY6_2R6kHBNpRtIAc/s1600/HFile-Structure.png" /></a></div>The picture above, describe the internal format of HFile...</div>Matteo Bertozzihttp://www.blogger.com/profile/04630649852079843031noreply@blogger.com6tag:blogger.com,1999:blog-8136012147929167933.post-60160985736645375242011-01-30T09:32:00.000-08:002011-01-30T09:32:22.754-08:00Zero-Copy Memory<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg11X_gYiYDt1f1d4P7MKicIxce3t4AZRIw_thEg__qe-GrfdXK00Qy4w6-rygz9u52XJZkEAi1JL8ntqo7WN0sFCdNHc30o_qrWAjRo1b2B3xnrK4ncgUqzaZes_-QPP1O34mwM5LPy-s/s1600/RefCount.png" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="139" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg11X_gYiYDt1f1d4P7MKicIxce3t4AZRIw_thEg__qe-GrfdXK00Qy4w6-rygz9u52XJZkEAi1JL8ntqo7WN0sFCdNHc30o_qrWAjRo1b2B3xnrK4ncgUqzaZes_-QPP1O34mwM5LPy-s/s320/RefCount.png" width="320" /></a>Looking at my code paths, I've seen many methods that read from a data-structure to a buffer and then write back it to another data structure, and so on...<br />
<br />
<i>For example read from disk, write to a block cache, read a piece of data and put it in another other data-structure for processing. </i><br />
<br />
One way to avoid all this memcpy and data duplication is to use a copy-on-write data-structure. For strings or "single-block-data" is pretty easy. As you can see on picture above, you've a chunk of memory that is referenced from different objects. Each object keeps a pointer to the data and if needed an offset and a length to reference just a part of the data.<br />
<br />
If someone call write() on one of those objects, internally data-blob is duplicated and modified. In this way the modified objects points to a new block and the others points to the old block.<br />
<br />
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj2PjpfDAsayjD-R1qTFtXYN4-JBKogJ_ANHHpdpraEb-L4yVeVbMPZsdcTayul-kWLStzTRqZnawkeDb-Lw_JNhXsdps6MEhA9shdFtbkZSuf52hfrNQ8LE9qj2Jot7ca6uoXDdxjI4to/s1600/ZeroMemCopy.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="172" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj2PjpfDAsayjD-R1qTFtXYN4-JBKogJ_ANHHpdpraEb-L4yVeVbMPZsdcTayul-kWLStzTRqZnawkeDb-Lw_JNhXsdps6MEhA9shdFtbkZSuf52hfrNQ8LE9qj2Jot7ca6uoXDdxjI4to/s320/ZeroMemCopy.png" width="320" /></a>This is a really simple copy-on-write technique and the string class is really suitable for that. But looking at my code, this case doesn't happen often... In the common case, I've object that references two or more blocks and sometimes happens that i need to remove or inject data in the middle of the buffer.<br />
<br />
Extent-tree that i use for the Flow Objects in RaleighFS plus copy-on-write on blocks has the behavior that I need to avoid all this memcpy and data duplication.<br />
<br />
Extent-Tree allows you to read from a list of blocks as a single block. Each block as an offset and a length, and blocks are sorted by offset, in the tree. This allows you to reach your specified offset fast and insert or remove at any specified offset.<br />
<br />
Using this extent-tree has the advantage that you can avoid to memcpy large blocks from a data-structure to another, you can merge two extent tree or do other fancy thing without allocate new memory and copy data to it. But insert and split require a malloc, so you've to tune your node and extent allocation with an object pool, and this is pretty simple due to the fixed size of those object.<br />
<br />
<i>I've made a draft implementation that you can find on my <a href="https://github.com/matteobertozzi/blog-code/tree/master/zero-copy-mem">github repo</a>.</i>Matteo Bertozzihttp://www.blogger.com/profile/04630649852079843031noreply@blogger.com0tag:blogger.com,1999:blog-8136012147929167933.post-86565088369186976232011-01-16T03:44:00.000-08:002011-01-16T05:12:18.507-08:00Hadoop I/O: Sequence, Map, Set, Array, BloomMap FilesHadoop' SequenceFile provide a persistent data structure for binary key-value pairs. In contrast with other persistent key-value data structures like B-Trees, you can't seek to a specified key editing, adding or removing it. This file is append-only.<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgn7v5W2RizzuokbGKevdfcPlSjsovxiZjeb7te81zwxN8hKRpGAakAFaKvc1puStzopfmz_QfV-P-m8lFGG0d0zHgurQcAKwYAV06ElEI7CyBEU3T9OVKnUXWKe0Njd9peo711qPNtHxs/s1600/seqfile-layout.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="57" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgn7v5W2RizzuokbGKevdfcPlSjsovxiZjeb7te81zwxN8hKRpGAakAFaKvc1puStzopfmz_QfV-P-m8lFGG0d0zHgurQcAKwYAV06ElEI7CyBEU3T9OVKnUXWKe0Njd9peo711qPNtHxs/s400/seqfile-layout.png" width="400" /></a></div><br />
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjvjF-9sPmNMz3nqqgW5qmnL6IHN9W11EaSBGE1MDwIggljKpe-F4jeVAaoL7O__FOxruXxbEmDeyi9rHawQuiJ3BT-bK6E4czC4goDtUulKVqF-5JTOIRbpMVYx1qK_3QQlt6DLsEiPx4/s1600/SequenceFileHeader.png" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="200" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjvjF-9sPmNMz3nqqgW5qmnL6IHN9W11EaSBGE1MDwIggljKpe-F4jeVAaoL7O__FOxruXxbEmDeyi9rHawQuiJ3BT-bK6E4czC4goDtUulKVqF-5JTOIRbpMVYx1qK_3QQlt6DLsEiPx4/s200/SequenceFileHeader.png" width="158" /></a>SequenceFile has 3 available formats: An "Uncompressed" format, A "Record Compressed" format and a "Block-Compressed". All of them share a header that contains a couple of information that allows the reader to recognize is format. There're Key and Value Class Name that allows the Reader to instantiate those classes, via reflection, for reading. The version number and format (Is Compressed, Is Block Compressed), if compression is enabled the Compression Codec class name field is added to the header.<br />
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgHLuZ5rl-3XW1yMtIKlafKsWl-sDaNLFpHn0347rZhbw2YYfdeMFwC_hNRlqZ83M0RnccytvFIyCk8vCAJPaXPVxDH-cVsQ0k_HWhrfK0CplhS9Z5NngAGupky6OZPh35QWLDX4wfEL08/s1600/SequenceFileMeta.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="200" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgHLuZ5rl-3XW1yMtIKlafKsWl-sDaNLFpHn0347rZhbw2YYfdeMFwC_hNRlqZ83M0RnccytvFIyCk8vCAJPaXPVxDH-cVsQ0k_HWhrfK0CplhS9Z5NngAGupky6OZPh35QWLDX4wfEL08/s200/SequenceFileMeta.png" width="150" /></a><br />
<br />
The sequence file also can contains a "secondary" key-value list that can be used as file Metadata. This key-value list can be just a Text/Text pair, and is written to the file during the initialization that happens in the SequenceFile.Writer constructor, so you can't edit your metadata.<br />
<div><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh_bx_xOCKnfudLJCzmctwief84oxszksIkW5LB6-jAcAEabbDI7ekv3DtTzngFppnSF_5HchuuR0hlxHhGXE9FZMfrAX9i8R7om_sGKBwTu_IWXsej-1hd04jaFVTcr73uDgmDV4bpUbc/s1600/SequenceFileRecord.png" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="146" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh_bx_xOCKnfudLJCzmctwief84oxszksIkW5LB6-jAcAEabbDI7ekv3DtTzngFppnSF_5HchuuR0hlxHhGXE9FZMfrAX9i8R7om_sGKBwTu_IWXsej-1hd04jaFVTcr73uDgmDV4bpUbc/s200/SequenceFileRecord.png" width="200" /></a><br />
As seen Sequence File has 3 available formats, the "Uncompressed" and the "Record Compressed" are really similar. Each call to the append() method adds a record to the sequence file the record contains the length of the whole record (key length + value length), the length of the key and the raw data of key and value. The difference between the compressed and the uncompressed version is that the value raw data is compressed, with the specified codec, or not.<br />
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgviBgSVFLFH-orQgMnE4fBgp0fENyW3604K3uVshj332xT9jckQ3ARNXZC5UeHNLBQM7KbYsCGD5lBFkxVBIBGY-3OlueEOM4gVrcXwqwbHrV4753HQMIblTVReYu023zkjBoMIhypxOo/s1600/SequenceFileBlock.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="166" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgviBgSVFLFH-orQgMnE4fBgp0fENyW3604K3uVshj332xT9jckQ3ARNXZC5UeHNLBQM7KbYsCGD5lBFkxVBIBGY-3OlueEOM4gVrcXwqwbHrV4753HQMIblTVReYu023zkjBoMIhypxOo/s200/SequenceFileBlock.png" width="200" /></a>In contrast the "Block-Compressed" format is more compression-aggressive. Data is not written until it reach a threshold, and when the threshold is reached all keys are compressed together, the same happens for the values and the auxiliary lists of key and value lengths.<br />
As you can see in the figure on the left, a block record contains a VInt with the number of the buffered records and 4 compressed blocks that contains a list with the length of the keys, the list of keys, another list with the length of the values and finally the list of values. Before each block a sync marker is written.<br />
<br />
Hadoop SequenceFile is the base data structure for the other types of files, like MapFile, SetFile, ArrayFile and BloomMapFile.<br />
<br />
</div><div><div>The <b>MapFile</b> is a directory that contains two SequenceFile: the data file ("/data") and the index file ("/index"). The data contains all the key, value records but key N + 1 must be greater then or equal to the key N. This condition is checked during the append() operation, if checkKey fail it throws an IOException "Key out of order".</div><div><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhaQak47yHjJj1cyrSEV76LeCDTQ0XZsAKpeg0UQHz70IHfy5VwzUbkHx_E1Q1x4oEYXq059Dadt8eGmMTKanxNosI2LP7n4LA3qi8CEvQM1iI5Ez0rQYCu79Spr7K8QnMloPKMEQJSWsM/s1600/bloommap.png" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="220" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhaQak47yHjJj1cyrSEV76LeCDTQ0XZsAKpeg0UQHz70IHfy5VwzUbkHx_E1Q1x4oEYXq059Dadt8eGmMTKanxNosI2LP7n4LA3qi8CEvQM1iI5Ez0rQYCu79Spr7K8QnMloPKMEQJSWsM/s320/bloommap.png" width="320" /></a>The Index file is populated with the key and a LongWritable that contains the starting byte position of the record. Index does't contains all the keys but just a fraction of the keys, you can specify the indexInterval calling setIndexInterval() method. The Index is read enteirely into memory, so if you've large map you can set a index skip value that allows you to keep in memory just a fraction of the index keys.</div><div><br />
</div><div>SetFile and ArrayFile are based on MapFile, and their implementation are</div><div>just few lines of code. The <b>SetFile</b> instead of append(key, value) as just the key field append(key) and the value is always the NullWritable instance. The <b>ArrayFile</b> as just the value field append(value) and the key is a LongWritable that contains the record number, count + 1. The <b>BloomMapFile</b> extends the MapFile adding another file, the bloom file "/bloom", and this file contains a serialization of the DynamicBloomFilter filled with the added keys. The bloom file is written entirely during the close operation.<br />
<br />
<i>If you want to play with SequenceFile, MapFile, SetFile, ArrayFile without using Java, I've written a naive implementation in python. You can find it, in my github repository <a href="https://github.com/matteobertozzi/Hadoop/tree/master/python-hadoop">python-hadoop</a>.</i></div></div>Matteo Bertozzihttp://www.blogger.com/profile/04630649852079843031noreply@blogger.com4tag:blogger.com,1999:blog-8136012147929167933.post-19059521785092033812011-01-08T20:52:00.000-08:002011-01-08T20:52:57.323-08:00[TIP] Daily Repository Diff via MailIf your 200 mail every morning are still not enough, you can add this script to your daily cron.<br />
<br />
The following scripts that you can find <a href="https://github.com/matteobertozzi/blog-code/blob/master/repo-mail-diff/">here</a>, allows you to send diffs of repositories that you follow. The bash scripts below allows you to update your git/svn/hg repository and keep a diff in a plain and html format (using <a href="http://www.pixelbeat.org/scripts/ansi2html.sh">ansi2html</a>).<br />
<br />
<pre>git_diff() {
cd $repo_url/$1
git_repo_url=`git remote show origin | grep "Fetch URL" | cut -d ' ' -f 5-`
echo "GIT Diff $1 ($2) - $git_repo_url"
git fetch
git diff --color HEAD origin/HEAD | $ansi2html > $diff_dir/$2.html
git diff HEAD origin/HEAD > $diff_dir/$2.diff
git merge origin/HEAD
}
hg_diff() {
cd $repo_url/$1
hg_repo_url=`hg showconfig | grep paths\.default | cut -d '=' -f 2-`
echo "HG Diff $1 ($2) - $hg_repo_url"
hg incoming --patch --git | $ansi2html > $diff_dir/$2.html
hg incoming --patch --git > $diff_dir/$2.diff
hg pull -u
}
svn_diff() {
cd $repo_url/$1
svn_repo_url=`svn info | grep URL | cut -d ' ' -f 2-`
svn_repo_rev=`svn info | grep "Last Changed Rev" | cut -d ' ' -f 4-`
echo "SVN Diff $1 ($2) - $svn_repo_url"
svn di $svn_repo_url -r$svn_repo_rev | $ansi2html > $diff_dir/$2.html
svn di $svn_repo_url -r$svn_repo_rev > $diff_dir/$2.diff
svn up
}
# Fetch my repos (xxx_diff repo_path diff_name)
git_diff "linux/linux-2.6" "linux-2.6"
svn_diff "apache/lucene" "lucene"
hg_diff "java/jdk" "hotspot-jdk7"
</pre><br />
After running repo-diff script that allows you to update your favorites repositories and saving diff files, you can send them using he send-mail script.<br />
<br />
<pre>diff_dir="~/.repo-diffs"
mail_address="th30z@localhost"
for html_file in `ls -1 $diff_dir/*.html` ; do
repo_name=`basename $html_file | sed 's/\.html$//g'`
diff_file=`echo $html_file | sed 's/\.html$/\.diff/g'`
boundary="==`echo $repo_name | md5sum | cut -d ' ' -f -1`"
alt_boundary="==`echo $boundary | md5sum | cut -d ' ' -f -1`"
echo "Send Repo Diff $repo_name - $html_file"
(
echo "MIME-Version: 1.0"
echo "Subject: Repo-Diff: $repo_name"
echo "To: $mail_address"
echo "Content-Type: multipart/mixed; boundary=$boundary"
echo "--$boundary"
echo "Content-Type: multipart/alternative; boundary=$alt_boundary"
echo
echo "--$alt_boundary"
echo "Content-Type: text/plain"
echo
cat $diff_file
echo "--$alt_boundary"
echo "Content-Type: text/html"
echo
cat $html_file
echo
echo "--$alt_boundary--"
echo "--$boundary"
echo "Content-Type: Application/Binary_Attachment;
name=\"`basename $diff_file`\""
echo "Content-Disposition: attachment;
filename=\"`basename $diff_file`\""
echo "Content-Transfer-Encoding: uuencode"
echo
uuencode $diff_file $diff_file
) | sendmail $mail_address
done
</pre><br />
This script, for each file generated from the repo-diff script sends you a mail with the diff as body and attachment.<br />
<br />
Scripts are available on my <a href="https://github.com/matteobertozzi/blog-code.git">github repository</a> under blog-code/repo-mail-diff.<br />
<div style="text-align: center;"><a href="https://github.com/matteobertozzi/blog-code/tree/master/repo-mail-diff">https://github.com/matteobertozzi/blog-code.git</a></div>Matteo Bertozzihttp://www.blogger.com/profile/04630649852079843031noreply@blogger.com0tag:blogger.com,1999:blog-8136012147929167933.post-26949935241074864742010-12-29T11:00:00.000-08:002010-12-29T23:52:27.568-08:00Disk Failure, Raid Corruption and CRCsThis week is started with a raid corruption due to a disk failure. Disk has continued to work without notifying anyone about the corruption, but this is somehow acceptable. The inacceptable thing is that the file-system is not aware about its data state. The "Old File-Systems" are not interested in user data and even with journaling, user data is not a priority.<br />
<br />
<i>As a Spare-Time File-System Developer, is really funny saying "With my File-System, This failure <span class="" id="result_box" lang="en"><span class="hps" title="Click for alternate translations">would not have</span> <span class="hps" title="Click for alternate translations">happened!"</span></span></i><br />
<br />
<b><span style="font-size: small;">Simple Solution: B-Tree and CRCs</span></b><br />
A really simple way to solve this problem is adding CRC to user data, or better (from file-system point of view) adding a CRC on every block. If the file-system is entirely based on B-Tree (when I say B-Tree, I mean B*Tree or B+Tree) you can simple add CRC for the block in the node header, and CRC for the child in the blocks pointer.<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgQSV8KLGIMoz_EnhH5jDBltp_tewWtUTIbzAqxVcRoPqUqfbwpqEPzGDOlB4vtJCSJVMLZ6NTvuShpFh119lTrCPz-yzSlR6CIOrehtZ-wtUKMkCKpoJ8Zj5WibXv_jaaxj_W_YEzA2_Y/s1600/BTreeCRC.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgQSV8KLGIMoz_EnhH5jDBltp_tewWtUTIbzAqxVcRoPqUqfbwpqEPzGDOlB4vtJCSJVMLZ6NTvuShpFh119lTrCPz-yzSlR6CIOrehtZ-wtUKMkCKpoJ8Zj5WibXv_jaaxj_W_YEzA2_Y/s1600/BTreeCRC.jpg" /></a></div><br />
Excluding from a moment the super-block and other things... You start reading the root of the tree (1st block), if node crc check fail there's something wrong with your disk-read (or maybe your memory, but this is less probable). When you start traversing the tree the check is even better and "secure".<br />
<br />
<i>Checking the CRC on the block read is good, but having the CRC stored in a different location, and read at a different time is even better.</i><br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg8ZiGh7onu_0NNuwesIAttrXWyi6brzkKYQQ1q7Om1XkkU-ZI7wAvAiMbiu-puusPBlvHOD6c4IdcEi3m4T7E1spZP54F9Rb4r4VWADJT1XNPeUhTh3l_-bsJfugLSxFGaV9xiU0UYL2A/s1600/BTreeCRCExtents.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg8ZiGh7onu_0NNuwesIAttrXWyi6brzkKYQQ1q7Om1XkkU-ZI7wAvAiMbiu-puusPBlvHOD6c4IdcEi3m4T7E1spZP54F9Rb4r4VWADJT1XNPeUhTh3l_-bsJfugLSxFGaV9xiU0UYL2A/s1600/BTreeCRCExtents.jpg" /></a></div>Storing CRC of the child node within the pointer gives you the ability to do a double integrity check. When data becomes larger and cannot be stored in a tree node, you can do the same thing with the extents (Pointers and CRC).<br />
<br />
<i>Another maybe more "intrusive" solution is storing a CRC for every N bytes of data, but I think that this more acceptable for a user-space "crc-fs" implementation (This approach is implemented in Hadoop's ChecksumFileSystem class).</i><br />
<br />
Yesterday night I've implemented a quick and dirty B+Tree, it's not tuned for speed but for a didactic view. It has a couple of nice features like Pointers with CRC and Variable Length nodes to be able to compress nodes on disk. You can find the source code on my <a href="https://github.com/matteobertozzi/carthage">github repository</a> (<a href="https://github.com/matteobertozzi/carthage/tree/master/btree">B+Tree Code</a>).Matteo Bertozzihttp://www.blogger.com/profile/04630649852079843031noreply@blogger.com0tag:blogger.com,1999:blog-8136012147929167933.post-11749666057297104192010-11-06T10:22:00.000-07:002010-11-06T10:22:25.030-07:00Cocoa: Black Window Titlebar<div class="separator" style="clear: both; text-align: left;">Starting with Quicktime X and now with Facetime, Apple has introduced a new black ui titlebar. There's no NS component at the moment or any flag of NSWindow, so I've decided to throw away ten minutes to write my own black titlebar.</div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjCpHV8jxw6RyF_5jb6P52EW3kWbdm7Tkkx2kNJxj8jJNL_g5d3Bq-uFYt8bn1IzOiQKvVkkJnmkFr8wJn9deheAFfagFnuZ-xEnQKoyC5HXBiFjV-RxhnEhQVhneT3wNxm82gmhAucRgM/s1600/MacBlackWindowTitleBar.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjCpHV8jxw6RyF_5jb6P52EW3kWbdm7Tkkx2kNJxj8jJNL_g5d3Bq-uFYt8bn1IzOiQKvVkkJnmkFr8wJn9deheAFfagFnuZ-xEnQKoyC5HXBiFjV-RxhnEhQVhneT3wNxm82gmhAucRgM/s1600/MacBlackWindowTitleBar.png" /></a></div>I've created a NSWindow class (<a href="https://github.com/matteobertozzi/blog-code/blob/master/MacBlackWindow/BlackWindow.h">BlackWindow.h</a>/<a href="https://github.com/matteobertozzi/blog-code/blob/master/MacBlackWindow/BlackWindow.m">BlackWindow.m</a>) that initializes a window without borders (styleMask NSBorderlessWindowMask) and I've created a NSView that draws the titlebar (<a href="https://github.com/matteobertozzi/blog-code/blob/master/MacBlackWindow/BlackWindowTitleView.h">BlackWindowTitleView.h</a>/<a href="https://github.com/matteobertozzi/blog-code/blob/master/MacBlackWindow/BlackWindowTitleView.m">BlackWindowTitleView.m</a>).<br />
The titlebar redraws itself when some changes are applied to the window. With key value observing for title, document edited, ... and NSNotificationCenter for KeyNotifications the titlebar knows what to do.<br />
<br />
Source code can be found on my <a href="https://github.com/matteobertozzi/">GitHub</a> under <a href="https://github.com/matteobertozzi/blog-code/tree/master/MacBlackWindow/">blog-code/MacBlackWindow</a>.<br />
<div style="text-align: center;">git clone https://github.com/matteobertozzi/blog-code.git</div>Matteo Bertozzihttp://www.blogger.com/profile/04630649852079843031noreply@blogger.com3tag:blogger.com,1999:blog-8136012147929167933.post-10411634176022565262010-10-15T22:07:00.000-07:002010-10-15T22:36:26.320-07:00Python: Inverted Index for dummiesAn Inverted Index is an index data structure storing a mapping from content, such as words or numbers, to its document locations and is generally used to allow fast full text searches.<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjw_2v58mAahN7d9z_4iZeyPAD2U1bhtpPz1AJZ9wA2vp2j_6W5Ytc1g-nQ0xH278SzMbRVuatsKwuFLRJZsl3T9oQ-nsOrQb8bPC0lxtQJ7-LgmwPycJogRt8it3PE4-kiosRG4MtQKvY/s1600/invertedIndex.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjw_2v58mAahN7d9z_4iZeyPAD2U1bhtpPz1AJZ9wA2vp2j_6W5Ytc1g-nQ0xH278SzMbRVuatsKwuFLRJZsl3T9oQ-nsOrQb8bPC0lxtQJ7-LgmwPycJogRt8it3PE4-kiosRG4MtQKvY/s1600/invertedIndex.jpg" /></a></div><br />
<br />
The first step of Inverted Index creation is Document Processing In our case is word_index() that consist of word_split(), normalization and the deletion of stop words ("the", "then", "that"...).<br />
<pre>def word_split(text):
word_list = []
wcurrent = []
windex = None
for i, c in enumerate(text):
if c.isalnum():
wcurrent.append(c)
windex = i
elif wcurrent:
word = u''.join(wcurrent)
word_list.append((windex - len(word) + 1, word))
wcurrent = []
if wcurrent:
word = u''.join(wcurrent)
word_list.append((windex - len(word) + 1, word))
return word_list
</pre>word_split() is quite a long function that does a really simple job split words. You can rewrite it with just one line using something like re.split('\W+', text).<br />
<pre>def words_cleanup(words):
cleaned_words = []
for index, word in words:
if len(word) < _WORD_MIN_LENGTH or word in _STOP_WORDS:
continue
cleaned_words.append((index, word))
return cleaned_words
def words_normalize(words):
normalized_words = []
for index, word in words:
wnormalized = word.lower()
normalized_words.append((index, wnormalized))
return normalized_words
</pre>Cleanup and Normalize are just to function filters to apply after word_split(). In this case cleanup remove the stopwords (frozenset of strings) and normalize convert word in lower case. But you can do something more like removing accents, transform to singular or something else. <br />
<pre>def word_index(text):
words = word_split(text)
words = words_normalize(words)
words = words_cleanup(words)
return words
</pre>word_index() is just an helper, take an input text and does all the word splitting/normalization job and the result is a list of tuple that contains position and word. [(1, u'niners'), (13, u'coach')].<br />
<pre>def inverted_index(text):
inverted = {}
for index, word in word_index(text):
locations = inverted.setdefault(word, [])
locations.append(index)
return inverted
</pre>Finally we've our invertex_index() method that take a text as input and returns a dictionary with words as keys and locations (position of the words in the document) as values.<br />
<pre>def inverted_index_add(inverted, doc_id, doc_index):
for word, locations in doc_index.iteritems():
indices = inverted.setdefault(word, {})
indices[doc_id] = locations
return inverted
</pre>The Previous method, inverted_index(), returns a dictionary with just the information for the specified document. So inverted_index_add() add Document's inverted index to a Multi-Document Inverted Index. Here we've words that are keys of the dictionary and values are dictionary with doc_id as key and document location as values. {'week':{'doc2': [149], 'doc1': [179, 187]}}.<br />
<pre>def search(inverted, query):
words = [word for _, word in word_index(query) if word in inverted]
results = [set(inverted[word].keys()) for word in words]
return reduce(lambda x, y: x & y, results) if results else []
</pre>Now that we've the inverted index, we're able to do queries on it. The function above takes a Multi-Document Inverted index and a query, and returns the set of documents that contains all the words that you've searched.<br />
<br />
<i>Obviously to make a serious search function you need to add ranking, phrase matches, stemming and other features of full-text search. And you need to write your dictionary using an on disk btree. But this is a basis example, of how to build an inverted index.</i><br />
<br />
Source code can be found on my GitHub repository under <a href="http://github.com/matteobertozzi/blog-code/blob/master/py-inverted-index/invindex.py">py-inverted-index</a>:<br />
<div style="text-align: center;">git clone http://github.com/matteobertozzi/blog-code.git</div>Matteo Bertozzihttp://www.blogger.com/profile/04630649852079843031noreply@blogger.com1tag:blogger.com,1999:blog-8136012147929167933.post-50559616206177765222010-10-09T08:35:00.000-07:002010-10-09T08:35:35.824-07:00Unsigned Int of specified bit lengthFinally I've added 128+ bit support to RaleighFS Table Object Row Index. I don't need much operation on indices only inc, dec and compare, but I've implemented other couple of methods (add, and, or, xor) and now there's a mini <a href="http://github.com/matteobertozzi/carthage/tree/master/uintx/">uintX</a> library available at <a href="http://github.com/matteobertozzi">GitHub</a>.<br />
<br />
<pre>...
uint8_t index[16]; // 128bit unsigned integer
uintx_init(index, 128U); // Initialize 128bit index to zero.
uintx_inc(index, 128U); // Increment Index (Now is One)
uintx_dec(index, 128U); // Decrement Index (Now is Zero)
uintx_from_u64(index, 128U, 8192U); // Now index is 8192
uintx_add64(index, 128U, 5U); // Add 5 to index
uintx_compare(index, 128U, 8197U); // Return 0
uintx_compare(index, 128U, 9197U); // Return -1
uintx_compare(index, 128U, 0U); // Return 1
...
</pre><br />
The API is quite simple pass your object (uint8_t vector) and its bit size (uint8_t[16] is 128bit) and other args needed to the method. Of course you can replace 128 with 256, 512 or everything else.<br />
<br />
The source code can be found at my <a href="http://github.com/matteobertozzi/carthage/tree/master/uintx/">GitHub</a> in the <a href="http://github.com/matteobertozzi/carthage/tree/master/uintx/">uintx</a> folder:<br />
<div style="text-align: center;">http://github.com/matteobertozzi/carthage.git</div>Matteo Bertozzihttp://www.blogger.com/profile/04630649852079843031noreply@blogger.com0tag:blogger.com,1999:blog-8136012147929167933.post-16354375371590052522010-09-25T01:50:00.000-07:002010-09-25T01:50:06.815-07:00iOS4: Core Motion ViewerI'm playing with Core Motion (Accelerometer and Gyroscope) of my new iPod Touch 4th. And I've written a simple app to look at the values of Motion Sensors. Code is not so much interesting, but it an useful app to check motion values.<div><br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhMBLACn42v7b8jGuPKcilJbc4IkxPQ8w6pd752CicConXfIw7lSAjxlWiGiGuZKraR1tNqIrqiehnUeSQMDSwfymZxxIfuW0hSI9DPmWUeAKmP9E2o07nHoGevypP2JpEdkxE5UFNMO4M/s1600/MotionViewer.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="213" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhMBLACn42v7b8jGuPKcilJbc4IkxPQ8w6pd752CicConXfIw7lSAjxlWiGiGuZKraR1tNqIrqiehnUeSQMDSwfymZxxIfuW0hSI9DPmWUeAKmP9E2o07nHoGevypP2JpEdkxE5UFNMO4M/s320/MotionViewer.png" width="320" /></a></div><div><br />
</div><div>Source Code can be found on <a href="http://github.com/matteobertozzi/blog-code">GitHub</a> at:</div><div style="text-align: center;"><a href="http://github.com/matteobertozzi/blog-code/tree/master/MotionViewer/">http://github.com/matteobertozzi/blog-code/tree/master/MotionViewer/</a></div></div>Matteo Bertozzihttp://www.blogger.com/profile/04630649852079843031noreply@blogger.com0tag:blogger.com,1999:blog-8136012147929167933.post-60941901258677226872010-09-19T01:39:00.000-07:002010-09-19T01:39:45.452-07:00Python: NetStack/CoreAsyncToday I've added to my GitHub Respositories <a href="http://github.com/matteobertozzi/netstack-coreasync">NetStack/CoreAsync</a> a python "package" (It's much more a bunch of utility classes) that allows you to code in async/parallel way, that I use to build my networking apps.<br />
<pre>def concurrent_func(text):
for i in range(5):
print text, 'STEP', i
yield
coreasync.dispatch_concurrent(lambda: concurrent_func("Context 1"))
coreasync.dispatch_concurrent(lambda: concurrent_func("Context 2"))
coreasync.runloop()
</pre><br />
Package contains a small Async HTTP Server implementation that you can easily use:<br />
<pre>def handle_response(socket, addr, request, headers, body):
yield socket.send(...)
def handle_error(socket, addr, error):
yield socket.send(...)
coreasync.httpserver.httpServerLoop(HOST, PORT, handle_response, handle_error)
print 'HTTP Server is Running on', HOST, PORT
coreasync.runloop()
</pre><br />
You can find <a href="http://github.com/matteobertozzi/netstack-coreasync/tree/master/coreasync/">Source Code</a> and <a href="http://github.com/matteobertozzi/netstack-coreasync/tree/master/examples/">Examples</a> at GitHub:<br />
<div style="text-align: center;">git clone http://github.com/matteobertozzi/netstack-coreasync.git</div>Matteo Bertozzihttp://www.blogger.com/profile/04630649852079843031noreply@blogger.com1tag:blogger.com,1999:blog-8136012147929167933.post-87117495238298158002010-08-15T00:04:00.002-07:002010-09-17T21:55:34.159-07:00Qt4 Http Request ParserQt 4.4 introduces <a href="http://doc.trolltech.com/4.6/qnetworkrequest.html" title="Qt Network Request">QNetworkRequest</a> and <a href="http://doc.trolltech.com/4.6/qnetworkaccessmanager.html" title="Qt Network Access Manager">QNetworkAccessManager</a> to help you with your HTTP client request. But if you want parse an HTTP Request, because you're writing an HTTP server, it seems that there's nothing already done (comment here, if I've missed it).<br />
<br />
So, this morning I've written a little class that help you with HTTP Request parse:<br />
<br />
<ul><li>static HttpRequest fromData (const QByteArray& data);</li>
<li>static HttpRequest fromStream (QIODevice *buffer);</li>
</ul><br />
There's a couple of method that you can use to parse your request data, and some others method to retrieve headers, method type, url and body data.<br />
<br />
<em>Qt is used only for QHash, QByteArray and QIODevice classes, you've to implement all the "socket" logic, to handle your client request and response.</em><br />
<br />
The Source code is available here: <a href="http://th30z.netsons.org/wp-content/uploads/qt-http-request.zip" title="Qt Http Request Parser Source Code">Qt4 Http Request Parser Source Code</a>.Matteo Bertozzihttp://www.blogger.com/profile/04630649852079843031noreply@blogger.com6tag:blogger.com,1999:blog-8136012147929167933.post-37054659295044611642010-08-13T23:40:00.002-07:002010-09-18T06:10:16.597-07:00Self Contained C Data Structures and Utils RepositoryI've rewritten a couple of data structure and utils (C lang) that I use for my RaleighFS Project, and I've released it at <a href="http://github.com/matteobertozzi/carthage">github</a> under BSD License.<br />
<br />
At the moment there are some data structures and helper functions:<br />
<ul><li>Memory Pool - Simple Memory Allocator.</li>
<li>Memory Utils - memcpy(), memset(), memcmp(), memswap() with some variants.</li>
<li>Memory Block - copy-on-write block.</li>
<li>Hashed Containers: Hashtable, Set, Bag.</li>
<li>Queue - FIFO/Circular Queue.</li>
<li>Cache - LRU/MRU Cache.</li>
<li>WorkQueue - Lightweight pthread workqueue.</li>
<li>Sort/Merge functions.</li>
</ul><br />
Every "object" is self contained, you can grab the "hashtable.c/hashtable.h" file to be ready to use the hashtable, no other dependence is required. And if data structure require a malloc() you can specify your own allocator during object initialization.<br />
<div style="text-align: center;">git clone <a href="http://github.com/matteobertozzi/carthage" title="GIT Repository">http://github.com/matteobertozzi/carthage.git</a></div>Matteo Bertozzihttp://www.blogger.com/profile/04630649852079843031noreply@blogger.com0