Showing posts with label computers. Show all posts
Showing posts with label computers. Show all posts

Tuesday, June 24, 2025

You should use passkeys, but you should understand them first

If you've already heard of passkeys, you probably know that they are the technology that is supposed to replace passwords. But if you're not sure what passkeys are, or how they work, or how they're better than or different from passwords, don't get down on yourself. Most of the websites promoting passkeys do a terrible job of explaining them. I didn't understand them myself, so I decided to finally dig in and learn how they work. Now that I have a better understanding of passkeys, I can see how they fix certain problems with passwords. And I'd like to help you understand them, too.

One of the reasons I think most explanations of passkeys are confusing is that they fail to distinguish between two different aspects of how passkeys work, the authentication process, and key management. There are a couple prerequisites to understand the rest of this post. You will need to know just a bare minimum about how public and private keys work. You will also need to be familiar with password managers.

How does a password work?

Before we jump into explaining passkeys, it will be useful to review how passwords work. We'll break down passwords into the same two parts, authentication with passwords, and password management. Once we have passwords explained within this framework, understanding passkeys should be pretty straight forward.

Authentication with passwords

Alice decides that she wants to create an account on bob.com.

Alice: I'd like an account, please.
bob.com: Please give me a username and a password.
Alice: OK. I'd like my username to be "xXx4l1c3xXx" and password "hunter2".
bob.com: Great. You now have an account on bob.com.

Now that Alice has an account, what does the login flow look like?

Alice: I'd like to log in, please.
bob.com: OK. What is your username.
Alice: xXx4l1c3xXx
bob.com: OK. If you can prove to me you know the password for xXx4l1c3xXx, I will log you in.
Alice: My password is hunter2.
bob.com: Great. You're logged in.

This is the basic authentication flow for logging in with a password. There shouldn't be anything surprising here. One of the problems with this type of authentication is that to verify Alice's password, the website needs to know her password. This means, if an attacker gets ahold of bob.com's database, there is a possibility that they could discover Alice's password, and use it to take over her account. As we'll see later, passkeys solve this problem.

Password management

Now that Alice has created an account on bob.com, Alice has to keep track of that password somehow. She has a several options available to her. She could simply remember the password. She could write the password down on paper somewhere. She could use a password manager, like 1Password or BitWarden.

If you pay attention to these things, you probably know that using a password manager is the recommended method of keeping track of your passwords. If you rely on remembering your passwords, you are likely to take shortcuts like reusing passwords across multiple websites. This is insecure, because if an attacker gets your password from one website, they might be able to take over your account on other websites.

Writing passwords down can be insecure, because anyone with physical access to your password notebook will be able to compromise your account. A password manager stores your passwords in an encrypted format, to prevent unauthorized access. Password managers have other features to improve security, like helping you create a strong and unique password for each of your online accounts. There's a lot more to be said here, but there are many other good articles covering the benefits of using a password manager. If you don't already use a password manager, I encourage you to start.

How does a passkey work?

We'll follow roughly the same script with passkeys as we did with passwords, so you can see the similarities and differences between the two technologies.

Authentication with passkeys

Alice decides that she wants to create an account on bob.com.

Alice: I'd like an account, please.
bob.com: Please give me a username and a public key.

Alice generates a new public/private key pair locally on her computer.

Alice: I'd like my username to be "xXx4l1c3xXx", and here's my public key.
bob.com: Great. You now have an account on bob.com

Now that Alice has an account, what does the login flow look like?

Alice: I'd like to log in, please.
bob.com: OK. What is your username.
Alice: xXx4l1c3xXx
bob.com: OK. If you can prove to me you know the private key for xXx4l1c3xXx, I will log you in. Here is a blob of data. Please sign it with the private key and send it back to me.
Alice: OK, here's the blob of data with a digital signature.
bob.com: I've used the public key for xXx4l1c3xXx to verify the signature. You're logged in.

If you're familiar with how private and public keys work, this should be pretty simple to understand. For those not familiar, a digital signature is a way to prove you have the private key for a given public key. Bob.com challenges Alice to provide a valid signature, and if she can, she proves she has the private key she generated when creating the account.

One of the big benefits here is that the website only knows Alice's public key. If someone compromises bob.com's database and gets ahold of Alice's account information, there is no way for them to use the public key to log in to her account. To compromise Alice's account, they would have to get her private key, which she never shared with bob.com.

Passkey management

This is where, I think, things differ quite a lot from how passwords work. Instead of having to keep track of a relatively short bit of text, like "hunter2", you have to keep track of a cryptographic key that is something like a kilobyte of random-seeming data. It's not feasible for Alice to remember her private key, or write it down in a notebook somewhere. Even if it were feasible to remember the key, you have to use the key to calculate a digital signature in order to log in. That's not something you can really do by hand. If you use a passkey, you must use something like a password manager to store the key, and generate digital signatures.

This is, in my opinion, the biggest factor that improves security for the average user. You must use some sort of passkey manager. Since every passkey user uses a passkey manager of some kind, secure procedures can be programmed into the passkey managers to prevent attacks like phishing. You know that blob of data that bob.com sends to you and asks you to sign? Your passkey manager can check whether that blob of data actually came from bob.com. If Alice accidentally finds herself on evil-bob.com, a phishing website, and tries to log in, her passkey manager will see that evil-bob.com is not bob.com, and refuse to sign the request.

Most mainstream password managers, such as 1Password and BitWarden, already support the use of passkeys. If you are interested in trying out passkeys, I recommend using one of these password managers to experiment with passkeys. Before messing with login credentials for one of your real accounts, try creating an account on a passkey demo website, like passkeys.io. Passkeys.io just consists of a login screen, and nothing else, so you can safely experiment with creating an account and logging in.

In terms of using your password manager to log in with a passkey, the user experience is most similar to logging in with a password using the auto-fill feature of your password manager. On a website's login screen, you will click the "login with a passkey" button, unlock your password manager, select which account you want to log in with, then the password manager will perform the cryptographic operations outlined earlier in this post to complete the login process.

What's the deal with bluetooth/biometrics/MFA/etc.?

Lots of videos about passkeys make a big deal about logging in with your fingerprint, or connecting your phone to your laptop with bluetooth. Why haven't I mentioned any of that yet? Because they are not strictly necessary. Not necessarily a bad idea, but not central to how passkeys work.

Earlier, I said passkeys force you to use "something like a password manager." There are actually a number of different options for storing and managing your private keys. The technical term here is "authenticator." "Authenticator" is an umbrella term that just means, "the thing that stores your keys, and creates digital signatures." A password manager is just one specific style of authenticator.

Lately, operating systems have begun to offer built-in authenticators to manage your passkeys. These have pros and cons. For example, they may store your passkey in a special bit of secure hardware, but then you may not be able to copy that key to be used on another device. This is why if you store a passkey in this way on your phone, in order to log in on your laptop, your laptop and phone have to talk to each other over bluetooth. This offers a higher level of security, but less convenience, and maybe the danger of losing your passkeys if something happens to your phone. I won't go into much more depth here, because I don't feel I have a good enough understanding to talk about this without misspeaking. The pros and cons of different types of authenticators is also worth a whole article on its own.

If this last section of the post is at all confusing, don't worry too much about it right now. The main point here is that, for the most part, what kind of authenticator you use is up to you. If you want to try out using passkeys, start by using a password manager. While there are pros and cons to different kinds of authenticators, at the very least, using passkeys with a password manager is probably a step up from using passwords with a password manager. And it's definitely a step up from not using a password manager at all. Once you're comfortable with using passkeys with a password manager, start looking into the other types of authenticators and see if they're right for you.

At the very least, I hope this post helped you understand passkeys a little better. And now that you understand passkeys, and see how they can keep your accounts safe, maybe you'll give them a try.

Thursday, November 1, 2018

Doing NaNoWriMo my own way

NaNoWriMo is something I've been vaguely aware of for several years now. I've seen it mentioned online, and my brother even participated in it once.

If you're not familiar with NaNoWriMo, it stands for National Novel Writing Month. The goal of the event is to write about 1600 words every day during the month of November. If you keep up your pace, you will have written a 50,000 word novel by the end of the month.

I've never had a huge appetite for literature. I rarely make it past the first hundred pages of a book, and have very little interest in writing fiction. But I do program. And there are projects that I've wanted to work on, but never gotten around to. So, instead of writing a novel, I'm going to spend every day in November working on a programming project.

Introducing, HamBot.

HamBot will be a Twitch chat bot intended to be run from a Raspberry Pi on your home network.

Twitch chat bots come in two basic flavors. There are chat bots like the StreamLabs chat bot that you run from your personal computer. The other flavor is a bot hosted and run by other people, like NightBot. The benefit of a hosted bot is that it is always on, even when you are not streaming. The downside is that you relinquish a lot of control. A streamer friend complained to me recently that the chat bot she uses has no way to export data, such as channel quotes or stream currency (fake internet points by viewers the longer they watch the stream).

HamBot's goal is to provide the benefits of a hosted solution, while leaving the streamer in full control of their chat bot. HamBot will be "hosted" on an inexpensive Raspberry Pi that a streamer can connect to their home router, do a bit of configuration, and then leave on 24/7.

The main design problem here will be to make installation and administration user friendly to the average streamer. This is the main thing I intend to solve by the end of November. HamBot itself will not have many advanced features. Those are fairly easy to add once the basic installation problem has been solved.

If you like, you can follow along here: https://github.com/haydenmuhl/hambot

Friday, February 7, 2014

Fixing a bonehead mistake in Solr

I was poking around in one of our Solr cores at work when I got this output from a query.
{
  "responseHeader": {
    "status": 0,
    "QTime": 248,
    "params": {
      "indent": "true",
      "q": "*:*",
      "_": "1391802519673",
      "wt": "json"
    }
  },
  "response": {
    "numFound": 36529751,
    "start": 0,
    "docs": [
      {
        "userId": "ERROR:SCHEMA-INDEX-MISMATCH,stringValue=3304997"
      },
      {
        "userId": "ERROR:SCHEMA-INDEX-MISMATCH,stringValue=3645477"
      },
      {
        "userId": "ERROR:SCHEMA-INDEX-MISMATCH,stringValue=3645478"
      },
      {
        "userId": "ERROR:SCHEMA-INDEX-MISMATCH,stringValue=3645479"
      },
      {
        "userId": "ERROR:SCHEMA-INDEX-MISMATCH,stringValue=3645480"
      },
      {
        "userId": "ERROR:SCHEMA-INDEX-MISMATCH,stringValue=3496486"
      },
      {
        "userId": "ERROR:SCHEMA-INDEX-MISMATCH,stringValue=3645481"
      },
      {
        "userId": "ERROR:SCHEMA-INDEX-MISMATCH,stringValue=3645482"
      },
      {
        "userId": "ERROR:SCHEMA-INDEX-MISMATCH,stringValue=3645484"
      },
      {
        "userId": "ERROR:SCHEMA-INDEX-MISMATCH,stringValue=3645485"
      }
    ]
  }
}
The reason for the error is that I reworked the schema of the core. I changed this field from a string to a long, and I forgot to delete all the existing records before reindexing.

Oops.

Okay, so how to fix it? I was able to determine that searching on the userId field with a numerical value would not return any of the corrupted records. A query like userId:[0 TO *] would select all valid records and exclude all corrupted records. I could invert that by doing *:* -userId:[0 TO *] to select all the corrupted records. A quick delete by query, and all the corrupted records disappeared.

Saturday, April 13, 2013

Losing is Fun: A minimal tutorial for maximum Fun

Dwarf Fortress is an incredible game, but the menu system presents a significant hurdle for newbies. I recently got started and had to rely on the wealth of information available at the Dwarf Fortress Wiki, but in the end I think I regret using it too much.

The motto of Dwarf Fortress is "Losing is Fun." You cannot "win" this game. Your fortress will fall eventually. Seeing how your fortress falls is all part of the Fun of Dwarf Fortress. This way, you learn from your mistakes, so hopefully each fortress will be less disastrous more spectacular than the last. If you read too much about game mechanics before you start playing, you miss a lot of this Fun. This tutorial is meant to give you a minimal boost, to get you over the initial non-Fun of learning how to navigate the arcane set of menus, without giving away any Fun ruining spoilers.

Just to give you a taste of some of the problems with the menu system, scrolling through menu options is very inconsistent and haphazard. Sometimes you use arrow keys. Sometimes you use the number pad. Sometimes you use (+) and (-). Sometimes you use (u, h, k, m). You will have to pay attention to the on screen instructions for using each menu.

Worldgen


The first step in Dwarf Fortress is creating the world your dwarves are going to inhabit. Select the Create New World! option. The world generation menu is pretty straight forward. To begin with, use the default settings. World generation takes a few minutes to complete, so go look at cat pictures or something while your computer does its thing.

World generation is a one time thing. When your first fortress falls, don't generate a new world. Just set up a new fortress somewhere else in the same world. One of the coolest aspects of Dwarf Fortress is that the world is persistent, and incredibly detailed. That means that you can go back later to reclaim the ruins of an old fortress.

Embark!


Embarking just means choosing where to stake your claim. Select the Start Playing menu, and the Dwarf Fortress option. These menus are pretty straight forward, too. Use the commands across the bottom of your screen to select a location.

There are a couple keys to finding a good site. You want a site rich in raw materials, like wood, rock, metals and animals. Aquifers are bad. Flux is good. Once you've found a place that looks good you can Embark (e). Learning where to embark is Fun.

Once you have embarked, you will see a screen full of incomprehensible characters. You can get information about what each symbol means by using the Look (k) command. When you place the cursor over a square of the map, you will see information about what is occupying that square on the right hand side of your screen. Take some time to get a basic idea of what your surroundings look like.

If you ever get lost somewhere in the menu system, just keep hitting Esc repeatedly until you get back to the main screen. If you hit Esc too many times, it will just toggle between the main screen and the options menu.

To avoid ambiguity, all menu options will be given as a series of keystrokes as if you were navigating there from the main screen.

Strike the Earth!


One of the most important activities is mining. To start mining, open the Designation menu and select Mine (d, d). Use the arrow keys to mark sections of the map you would like to excavate. Parts of the map that you can mine are going to be solid black. If you don't see any solid black areas of the map, skip ahead to the section on Z-Levels, then come back here.

If you accidentally mark an area for excavation that you didn't mean to, you can use the Remove Designation (d, x) option to unmark these areas. When you unpause the game (space bar), your dwarves will get to work carrying out your wishes.

You should notice that while marking places for excavation, you never issued an order to a dwarf. In Dwarf Fortress, you only have indirect control over your dwarves. All you can do is issue a general order that this or that should be done. If a dwarf with that particular skill is available, then he or she will do the job. If no dwarf has the skill you need, then the job doesn't get done. This puts Dwarf Fortress about half way between a game like SimCity and The Sims. SimCity does not simulate the actions of individual people. The Sims does, but you have to micromanage every action that your Sims take. The game play of Dwarf Fortress presents some interesting challenges, because your dwarves will sometimes act in Fun and unpredictable ways.

Buildings


One of the more confusing things about Dwarf Fortress is what does and does not count as a "building". Things like tables and chairs count as "buildings", and are in the same menu as wells and bridges. Even more confusing is the error message you get when you try to build some of these "buildings". If you open up the Building menu and try to "build" a table (b, t), you will get the error message "Needs table". WTF does that mean?

For an object like a table, "building" the table really means placing a fully constructed table somewhere for use. Before you can place a table somewhere for use, you must "construct" the table in the first place.

Some of the most important buildings in the game are Workshops (b, w). Workshops are where your dwarves turn raw materials into useful objects. You will need workshops, but figuring out which workshops you need, and for what can lead to a lot of Fun.

Most buildings don't do anything on their own. In order for them to be useful, you have to designate tasks to be carried out by your dwarves at the buildings. You can interact with a building using the Set Building Tasks/Prefs command (q). In this mode, when you move your cursor near a building, you will get a menu of what you can do with that building. This will be very important with your workshops early in the game.

Z-Levels


The world of Dwarf Fortress is a three dimensional one. The map that the game presents to you is really just a horizontal cross section of this three dimensional world. One single cross section is called a Z-level. That's because typically a flat plane is represented with two coordinates, X and Y. Three dimensions are represented by X, Y and Z, where Z denotes the vertical dimension. I like to think of Z-levels as the pictures that an MRI or CT scan produces. Horizontal cross sections that you have to visualize stacked on top of each other.

To navigate down to lower Z-levels use the (>) key. To navigate to higher Z-levels use the (<) key. In order to dig between Z-levels, you will need to construct stairs or ramps. The various flavors of stairs and ramps can be found in the Designations menu along side the Mine command. These will need to be placed correctly in order for your dwarves to gain access to other Z-levels. You should experiment and have some Fun with this.

Miscellaneous Tips and Hints


Here are a couple more menus you should familiarize yourself with early on. Zones (i) and Stockpiles (p) are important. Play around with them to see what they do. Create a stockpile and see how your dwarves react to it. If it didn't seem to do anything, try creating a different type of stockpile. Do the same with zones.

The View Units (v) menu is also very important. In this mode, when you move your cursor near a creature, you will see some of the creatures stats and characteristics. Of particular importance is the Labor menu (v, p, l). It lets you designate which types of tasks a particular dwarf will perform.

My last advice is to not get too frustrated. Remember, "Losing is Fun." If your fortress falls, just start a new one. In my own process of learning the game, I try to focus on learning one thing at a time. For example, focus on how to acquire a particular raw material. Once you've acquired the raw material, see if you can figure out what that raw material is useful for. Nearly everything in this game has a use of some type.

On to the Fun


That should be enough information to at least get you started. I've deliberately left out a lot of key information that will hopefully result in a lot of Fun in your early fortresses. Once you've learned where to embark and familiarized yourself with the menus in this tutorial, you should be able to put together a fairly successful fortress. The key is to learn from your mistakes so you have a completely new and unexpected type of Fun in your next fortress.

To recap, these are the key menus you need to be familiar with to get your first fortress off (in?) the ground.

  • Look (k) - See what stuff is on a particular tile.
  • Designations (d) - Important commands like Mine can be found here
  • Building (b) - Used to erect buildings and place furniture around your fortress
  • Set Building Tasks/Prefs (q) - Interact with finished buildings
  • Zones (i) - Designate areas for certain uses
  • Stockpiles (p) - Designate areas for certain other uses
  • View (v) - View and set your dwarves' characteristics
And finally, access the third dimension by navigating Z-levels using (<) and (>).

Have Fun. :-)

Thursday, March 21, 2013

Compiling a custom dictionary for Kuromoji and Solr

The user dictionary functionality of Solr's Kuromoji tokenizer is extremely useful and easy to use, but it isn't always the right tool for the job. In my case, I'm migrating our system off of the MeCab tokenizer. MeCab also allows you customize the tokenization, but the two models are completely different. In Kuromoji's user dictionary, you take an untokenized phrase and provide the custom tokenization. In MeCab, you just supply a list of words to augment its dictionary. The only way to migrate MeCab's custom dictionary to Kuromoji's user dictionary is by hand.

Fortunately, Kuromoji uses the same base data set as MeCab to build its statistical model for tokenization, and all the data in the base data set is in the same format as the custom MeCab dictionary. Getting Kuromoji to use the custom MeCab dictionary just requires recompiling Kuromoji's dictionary. Figuring out how to do this was surprisingly painless.

In order to compile your new dictionary, you will need...
  1. A copy of the MeCab-IPADIC data
  2. A copy of the Solr source code
  3. A Solr distribution of the same version as your source code
  4. A servlet container in which to run Solr

Download MeCab-IPADIC


A tarball of the MeCab dictionary can be downloaded from SourceForge at the following link.


Unpack the tarball to a directory of your choice. From now on I will be referring to this directory as the "dictionary source" directory, or as $DICTSRC in code examples. If you look inside the dictionary source directory, you will see several CSV files. These files use the EUC-JP character encoding scheme. Any custom dictionary will need to be in the same format.

If you open up one of the CSV files, you will see something like this.

いっぽう,555,555,5224,接続詞,*,*,*,*,*,いっぽう,イッポウ,イッポー
そもそも,555,555,4784,接続詞,*,*,*,*,*,そもそも,ソモソモ,ソモソモ
では,555,555,5262,接続詞,*,*,*,*,*,では,デハ,デワ
そういや,555,555,5420,接続詞,*,*,*,*,*,そういや,ソウイヤ,ソーイヤ
かたや,555,555,5368,接続詞,*,*,*,*,*,かたや,カタヤ,カタヤ

The data in each field is roughly as follows.

Field 1 - A word to be used for tokenization
Field 2 - Left cost
Field 3 - Right cost
Field 4 - Word cost
Fields 5-10 - Part of speech
Field 11 - Base form
Field 12 - Reading
Field 13 - Pronunciation

Fields 2, 3, and 4 have to do with the statistical model for tokenization. For the purposes of constructing your custom dictionary, treat fields 2 and 3 as magic numbers mapping to part of speech. Column 4 is the "cost" of the word itself. The lower the cost of the word, the more likely it is to be used in a tokenization. Fields 5-10 should be copied from the appropriate MeCab CSV files. I don't know enough about Japanese to know the differences between fields 11, 12, and 13.

Once you have your custom dictionary ready, drop it into the dictionary source directory along with the rest of the MeCab CSV files.

Set up Solr


Set up your servlet container and deploy the Solr WAR file. Make sure that your servlet container expands the war file so that you can access its contents. The expanded Solr webapp directory will be referred to as $WEBAPP. If the directory $WEBAPP/WEB-INF/classes does not exist, create it.

Open a terminal and find the Solr source code you downloaded. This directory will be referred to as $SOLRSRC. Run the following commands.

> cd $SOLRSRC/lucene/analysis/kuromoji
> ant compile-tools

Compile your dictionary


At this point, we should have everything necessary to compile the custom dictionary. Run the following commands.

> cd $SOLRSRC/lucene/build/analysis/kuromoji/classes/tools/
> java -cp ".:$WEBAPP/WEB-INF/lib/*" \
org.apache.lucene.analysis.ja.util.DictionaryBuilder \
ipadic $DICTSRC $WEBAPP/WEB-INF/classes euc-jp false

Once this completes, you can inspect the files that it created in $WEBAPP/WEB-INF/classes. There will be a deep hierarchy of directories, and then nine binary files that make up your dictionary. One of the JAR files in the lib directory contains a set of files with the same names as these, but the Java servlet spec says that the servlet container should first look in the classes directory, then look in the lib directory. Having your dictionary in the classes directory will override the dictionary packaged with your Solr distribution.

You should now have a Solr instance with a custom Japanese dictionary for tokenization. Start up your servlet container and test it out.

Tuesday, March 19, 2013

Custom Japanese tokenization in Solr 4.0

Solr 4.0 (really, it's been there since 3.6) has a new analysis module for handling Japanese, called Kuromoji. Kuromoji was developed by Atilika, Inc., who donated it to Solr. I don't speak Japanese myself, but I've been doing some preliminary tests with a Japanese coworker, and it seems to work fairly well.

However, it's not perfect. It will miss an occasional phrase, and is especially problematic with domain specific phrases. To get around this, the Japanese tokenizer accepts a user dictionary, where you can list custom tokenizations. Unfortunately, I couldn't find any documentation on the format for the user dictionary. Fortunately, there is a sample user dictionary in the unit tests for the Japanese tokenizer.


# Custom segmentation for long entries
日本経済新聞,日本 経済 新聞,ニホン ケイザイ シンブン,カスタム名詞
関西国際空港,関西 国際 空港,カンサイ コクサイ クウコウ,テスト名詞

# Custom reading for sumo wrestler
朝青龍,朝青龍,アサショウリュウ,カスタム人名

# Silly entry:
abcd,a b cd,foo1 foo2 foo3,bar
abcdefg,ab cd efg,foo1 foo2 foo4,bar


It's a fairly straight forward CSV format. A hash character (#) starts a comment that continues to the end of a line. Empty lines are ignored. Each non-empty line has four fields separated by commas. After some testing, I was able to figure out what each field in the CSV was.

  1. Untokenized phrase
  2. Tokenized phrase
  3. Reading, or pronunciation
  4. Part of speech

There are a couple particulars you need to be aware of when putting together your user dictionary.

Every field is required - If you do not have all four fields your core will not load properly.

Tokenized phrase and reading - These fields are lists of words delimited by spaces. It is important that both the tokenized phrase and the reading have the same number of words. If you don't have this, your core will not load properly.

Spaces around commas - The CSV parser is very picky about format. You should never have any spaces surrounding the commas separating fields. Your core may or may not load, but can get other strange errors during tokenization.

I haven't tested this extensively, but I don't believe there is any way to escape a comma or a hash character. The CSV parser will accept fields surrounded by quote marks, but putting a comma or hash inside a quoted string does not seem to change how it is interpreted. Fortunately, this seems like it would be a very rare use case.

Thursday, January 3, 2013

Grokking Solr Trie Fields

I've been trying to wrap my head around Solr's trie field types for the past week, and finally made a break through.

Trie


The first thing you need to understand is the idea of a trie data type. Here's a basic outline of the data structure. Let's say you want to index the following list of words.

bad
bag
bar
bin
bit

We can arrange these words in a tree structure as follows.

b--a--d
|  |
|  |--g
|  |
|  \--r
|
\--i--n
   |
   \--t

To reconstruct one of the words you start at the root node of the tree, and work your way towards a leaf node, keeping track of the letters you encounter along the way. Depending on what you're using the trie data structure for, you may store some piece of data in one of the leaf nodes. If you want more information about the trie data structure, I will refer you to the Wikipedia page, which is fairly complete and easy to understand.

Solr's version of the trie


Another term for a trie is a "prefix tree". Solr uses this idea of prefixes to index numbers so that it can perform range queries efficiently. Just like we can organize words into tries, we can also organize numbers into tries.

Let's say I want to index the integer 3735928559. For clarity, let's rewrite that in hexadecimal, 0xDEADBEEF. When we index this using a TrieIntField, Solr stores the integer four times at different levels of precision.

0xDE000000
0xDEAD0000
0xDEADBE00
0xDEADBEEF

What Solr is doing here is constructing numbers with different length prefixes. This would be equivalent to a trie with this structure.

DE--AD--BE--EF

The reason that this allows for fast range queries is because of what the prefixes represent. The prefixes represent a range of values. It might be better to think of them indexed like this, instead.

0xDExxxxxx
0xDEADxxxx
0xDEADBExx
0xDEADBEEF

Each "x" represents an unset digit. That means the entry 0xDEADxxxx represents every number from 0xDEAD0000 to 0xDEADFFFF. You can get a better feel for this if you play around in the analysis section of the Solr admin console.

Precision Step


The option to set the precision step was the part that I understood the least. The available documentation is rather dense and unhelpful. The precision step lets you tune your index, trading range query speed for index size. A smaller precision step will result in a larger index and faster range queries. A larger precision step will result in a smaller index and slower range queries.

In the example above, I was using a precision step of 8, the default. What the precision step means is how many bits get pruned off the end of the number. Let's see what would happen if we indexed 0xDEADBEEF with a precision step of 12.

0xDExxxxxx
0xDEADBxxx
0xDEADBEEF

And here with a precision step of 4.

0xDxxxxxxx
0xDExxxxxx
0xDEAxxxxx
0xDEADxxxx
0xDEADBxxx
0xDEADBExx
0xDEADBEEx
0xDEADBEEF

As you can see, compared to the default precision step of 8, a precision step of 4 doubled the number of entries in the index. The way it speeds up range searches is by allowing better granularity. If I wanted to search for the documents matching the range 0xDEADBEE0 to 0xDEADBEEF with the default precision step, I would have to check all 16 records in the index and merge the results. With the precision step of 4, I can check the one record for 0xDEADBEEx and get the results I want.

That's a bit of a cherry picked example, but arbitrary range queries will be faster. How that works is left as an exercise for the reader.

May 5, 2015 - I originally thought that the trie data type was not supported directly by Lucene, but this is incorrect. Tokenization of numeric types into the various prefixes is the default behavior of Lucene when indexing numbers.

Sunday, November 11, 2012

Custom Solr token filter factories with arguments

Many of the token filter factories, tokenizer factories, and char filter factories that come bundled with Solr accept parameters from a schema.xml. The documentation for writing your own filters and tokenizers doesn't include any details for how to access these parameters, but it's pretty easy to figure out by inspecting the source code for one of the included factories.

The MappingCharFilterFactory takes a path to a file as a parameter. The Javadoc for the MappingCharFilterFactory shows the declaration to put in schema.xml.
<charFilter class="solr.MappingCharFilterFactory" mapping="mapping.txt"/>
In the source code for the MappingCharFilterFactory we can find the following line.
mapping = args.get("mapping"); 
Looking through the class hierarchy, all token filter factories, tokenizer factories, and char filter factories are descendants of AbstractAnalysisFactory where args is declared as a protected variable. All you have to do access the parameters passed from schema.xml is access the args map. args can also be accessed via the getArgs() function.

Wednesday, October 31, 2012

Solr 4.0 and the BaseTokenFilterFactory

At work, we're upgrading from an ancient version of Lucene to the shiny new Solr 4.0. Unfortunately, the documentation on the Lucene wiki hasn't quite caught up with the most recent version of the software. I would fix omissions like this as I found them, but the wiki does not seem to accept public edits.

There were three classes in Solr 3.6 for creating custom analyzers. Those classes were the BaseCharFilterFactory, BaseTokenizerFactory, and the BaseTokenFilterFactory. These three classes were in the documented package, org.apache.solr.analysis, through Solr 4.0 ALPHA, but as of the BETA release, they have been moved and renamed.

In Solr 4.0, the new classes are the CharFilterFactory, TokenizerFactory, and TokenFilterFactory. They can be found in the org.apache.lucene.analysis.util package, which is part of Lucene's analyzers-common project

Handy links:
Thanks to comment 7 for pointing this out.

Friday, June 29, 2012

Another shell script to share

At home I get a lot of use out of the tree command line utility. It gives me a quick and easy way to look at a nested directory structure without having to leave the command line. The computers at work don't have the tree utility, and every so often I really miss it.

So, I wrote my own.

Here's a bash script that is a simplified version of the tree utility.

#!/bin/bash

tree() {
    local prefix=$1
    local dir=$2
    local count=`ls -l $dir | wc -l`
 
    if [[ $count -eq 0 ]]
    then
        return
    fi
 
    local i=1
    local bar="|"
    local nextPrefix="|   "
 
    for file in "$dir"/*
    do
        i=$(($i + 1))
        if [[ $i -eq $count ]]
        then
            bar="\`"
            nextPrefix="    "
        fi
        filename=$(basename $file)
        echo "$prefix$bar---$filename"
        if [[ -d $file ]]
        then
            tree "$prefix$nextPrefix" $file
        fi
    done
}


if [[ -z $1 ]]
then
    dir=`pwd`
else
    dir=$1
fi

if [[ ! -e $dir ]]
then
    echo "Directory $dir does not exist"
    exit 1
elif [[ ! -d $dir ]]
then
    echo "$dir is not a directory"
    exit 2
fi

basename $dir
tree "" $dir

Wednesday, March 28, 2012

Back to school

I've started taking classes as part of the Embedded Systems Engineering certificate offered through UC Irvine Extension. Just last week I finished up my first course in the certificate program. It was the requisite software engineering course that I imagine every such program has. Overall, the course was fairly dull, and I can't say I got much out of it.

The deliverables for the course consisted of a five question multiple choice quiz every week, and four larger assignments. Two of these assignments were research papers, which were little more than book reports based on our assigned reading. The other two assignments were demonstrations of the Hatley-Pirbhai Methodology (HPM). HPM is mostly just a repackaged waterfall workflow, but with a requirements document following a specific structure. None of these were particularly interesting, challenging or fun.

Although the course was rather disappointing on the whole, I can't say I got nothing out of it. Much of the required reading had very little to do with software engineering and instead was more a survey of common hardware found in embedded systems. Not having an extensive background in hardware, there was a lot of new information for me. I now have a much better appreciation for things like system bus protocols, and the details of how DMA works. This was also my first exposure to a digital signal processor architecture, when previously I only was familiar with MIPS and x86 type instruction sets.

Unfortunately, I only got to read about all this, and not actually get my hands dirty, but that's going to change. My second class* starts up this week, which is an intro to embedded programming, and my dev board just arrived in the mail. I haven't had a chance to play with it very much, but I can already tell this class is going to be much better than the last. The AVR board we are using has fun blinky LEDs, but sadly no piezo buzzer to annoy the roommates with.

* You may think it's odd to have the first class in a curriculum to be software engineering, and you would be right. My "first" and "second" classes should have been reversed in order. I ended up taking them out of order because I started the program at an odd time with regards to class schedules. In the end, I think this will turn out for the best. I have accidentally eaten my vegetables first, which means now there's nothing left for me but dessert.

Monday, December 12, 2011

Free Chromebook

I'm on a plane at the moment, flying to Chicago. It turns out, Google is promoting its Chromebooks by offering them free for the duration of your flight. You give them your name, email address and swipe a credit card, and you get free use of a Chromebook and on board wi-fi. This is great for two reasons. First, I can entertain myself with cat pictures and rage comics for the three hours it will take me to get to Chicago. Second, I get to play around with a Chromebook.

I've only been using it for about a half an hour, but already I can say I would not buy one of these. The main reason is that it is just not the right device for me. I mean, it's basically a computer that can only run Chrome. Don't get me wrong, Chrome is a great browser, but I just need my computers to be able to do more than that.

I do understand the use case for a computer like this. Let's say you run something like a large customer support call center. The software needs for your call center could easily be filled by web applications. With something like a Chromebook, if a computer craps out on you, IT can just grab another Chromebook off a shelf and your employee can get back to taking calls.

Unfortunately, even if I were in a position where a computer like this were to be useful, I still wouldn't buy a Chromebook. The experience of trying to write this blog post has been little short of infuriating. The hardware simply does not work well, at all. The keyboard regularly registers double key presses, resuultiing in worrds like thesee. The touch pad is not much better. It will often not register your finger movements at all. I suppose it's possible that these computers have seen a lot of miles, and a lot of different people have used them, but it just makes me wonder how long it would be before my own use would result in similar behavior.

One thing this experience has shown me is the appeal of a netbook. I brought my laptop with me on this trip, and I can see where my laptop would just be too big to comfortably use on a plane. It is also quite heavy compared to this. If I were to travel more, I think something like an Eee PC would be a worthwhile investment. But that will have to wait. I think my next purchase is going to be an Android tablet of some flavor so I can read on the train during my morning and evening commute.

Update: I'm waiting for my plane back to San Francisco, and they have the free Chrommebooks again. I'm just writing to confirmm that this CChromebook has the samme problems that the last one had. Ick. Oh, well. The frustration is worth the free wifi.

Friday, October 28, 2011

Damn it, I'm actually going to do it this time

I have dipped my toe in the water of Linux From Scratch (LFS) a couple times before, but I never followed through with it. Well, I'm making another go at it, but this time I intend to follow through. I'm applying to grad schools to study operating systems, and I'm recently unemployed which gives me plenty of free time. I also have two computers to work with, which means I can screw up my LFS system without having to worry about losing important data or access to a computer.

I'm in the middle of step one at the moment. I'm formatting the disks on my tower. I will install Ubuntu 10.04 on the smaller of the two disks, and the larger disk will be where I will build my LFS system.

Tuesday, September 13, 2011

Grails events

I couldn't find a complete list of Grails events, so I've tried to compile one. Using various text processing tools, I chewed through all of the Grails scripts in my Grails 1.3.7 installation, and here's what I came up with.
  • AppCfgEnd
  • AppCfgStart
  • AppLoadEnd
  • AppLoadStart
  • CreatedArtefact
  • CreatedFile
  • CreateWarEnd
  • CreateWarStart
  • DocEnd
  • DocSkip
  • DocStart
  • Exiting
  • GenerateControllerEnd
  • GenerateViewsEnd
  • InstallPluginStart
  • IntegrateWithInit
  • PackagePluginEnd
  • PackagePluginStart
  • PackagingEnd
  • PluginLoadEnd
  • PluginLoadStart
  • PluginUninstalled
  • SetClasspath
  • StatsStart
  • StatusError
  • StatusFinal
  • StatusUpdate
  • TestCompileEnd
  • TestCompileStart
  • TestPhaseEnd
  • TestPhasesEnd
  • TestPhasesStart
  • TestPhaseStart
  • TestProduceReports
  • TestSuiteEnd
  • TestSuiteStart
  • WebXmlEnd
  • WebXmlStart
I don't know what all of them do, but it should be easy enough to guess from the name.

Git and empty directories

One minor annoyance I have with Git is that it cannot track empty directories. This is especially annoying if you are working with an application framework, which creates an intricate structure of empty directories.

A common work-around you will see is to create an empty .gitignore file in each empty directory. It's not a very elegant solution, but it gets the job done. The trick is making sure you actually find every empty directory. So, I wrote a simple bash script, gitify.sh, to do it for you.
#!/bin/bash


gitify() {
    if [[ -z $(ls -1A "$1") ]]
    then
        touch "$1/.gitignore"
    else
        for file in "$1"/*
        do
            if [ -d "$file" ]
            then
                gitify "$file"
            fi
        done
    fi
}


rootdir=$(readlink -f .)


gitify $rootdir
Just navigate to the root directory of your Git project, and run the script. It will descend from the working directory into all subdirectories and drop a zero byte .gitignore file in any empty directory it finds. Just git-add all the newly created files and check them in to your repository.

I'm posting this not so much for the benefit of others as for myself. This is probably the fifth time I've written this script, because I keep losing it or deleting it. Maybe now that it's posted on the internet I won't lose it so easily.

Tuesday, May 10, 2011

Groovy on Grails: Serving static files from the root context

Grails is a great platform for web development, but there are certain things that are fairly trivial to do in a production environment that are rather difficult in a development environment. One of those is serving up static files from the root of your host name. These could be anything, like robots.txt or crossdomain.xml. It's simple enough to do this with Tomcat. Simply configure your ROOT context, drop in the files and you're done.

But how do you do this in a development environment? Generally, a developer will use the grails run-app command. This invokes a built-in instance of Jetty, which makes your Grails application available at the URL http://localhost:8080/yourApp/. It's easy enough to serve static files from below the yourApp directory. Simply drop them in the web-app folder in your Grails project, but there isn't any way to serve static files from above this.

The problem is that Grails is not designed to work this way. Many of the solutions I found online try to work against Grails' design, such as hacking at the internals directly, or forcing the configuration to serve everything from the root context. These have potential problems when it comes to things like upgrading Grails, or deploying to production.

Instead, I opted to find an external mechanism to serve these static files. This way the Grails application can remain untethered from the rest of its environment. It doesn't need to be aware of what's going on outside its context, its realm of control. This can be accomplished with Apache and mod_proxy. We can use Apache to serve documents from the root, then we can use mod_proxy to delegate any requests from a subdirectory to the Jetty instance used by Grails.

1. Install Apache httpd 2.2

The specifics of installing httpd are beyond the scope of this blog post. If your operating system has a packaging system (apt-get, yum, etc.), use that. If not, refer to the available Apache documentation.


For the rest of this tutorial, I will be assuming use of a Linux system.

Start httpd.
sudo /sbin/service httpd start
Test that it is installed correctly using a web browser.

2. Create a root directory

Pick a location on your disk where you will keep your static files. This will be the document root for httpd. I will be using /var/grails_root.
mkdir /var/grails_root
touch /var/grails_root/crossdomain.xml
3. Create a VirtualHost in httpd.conf

Open httpd.conf in your favorite text editor.
vim /etc/httpd/conf/httpd.conf
Pick your favorite port, and create a virtual host on that port. I will be using 9090, but any port will do.

Add these lines to httpd.conf
Listen 9090
<VirtualHost *:9090>
    DocumentRoot "/var/grails_root"
    <Directory "/var/grails_root">
        Allow from all
    </Directory>
</VirtualHost>
Restart httpd
sudo /sbin/service httpd restart
Test that you are now able to access the static files in your document root directory. If not, you will need to fix this before moving on to the next step.

4. Enable mod_proxy and mod_proxy_http

You need to load both of these modules. mod_proxy has the base functionality for proxying, and the mod_proxy_xxx modules have information specific to a protocol. They ship standard with httpd 2.2, so you shouldn't need to install anything extra.

Add these lines to httpd.conf
LoadModule proxy_module modules/mod_proxy.so
LoadModule proxy_http_module modules/mod_proxy_http.so
Now modify the virtual host you set up in the previous step. (You can omit the comments)
<VirtualHost *:9090>
    DocumentRoot "/var/grails_root"
    <Directory "/var/grails_root">
        Allow from all
    </Directory>
# New lines start here
    ProxyRequests Off
    <Proxy *>
        Order deny,allow
        Allow from all
    </Proxy>
    ProxyPass /grailsApp http://your.grails.server:8080/grailsApp
# New lines end here
</VirtualHost>
Restart httpd
sudo /sbin/service httpd restart
Now, you should be able to access both your static files and your Grails app via port 9090.

More information on this can be found here.