Runner in the High

技術のことをかくこころみ

JavaScriptにおける配列操作の計算量オーダー

日本語だとググっても出てこなかったのでまとめた

操作 計算量
検索 O(n)
添字アクセス O(1)
挿入(splice) O(n)
削除(splice) O(n)
削除(delete) O(1)
最後に追加 O(1)
先頭に追加 O(n)
スワップ O(1)

添字アクセスがO(1)だったりするのは、JavaScriptの配列は連結リストなどではなく単なるインデクスをキーで持つObjectだから。

ちなみにdeleteを使った削除というのはspliceと違って要素がundefinedと交換されるだけのものなので後続要素への走査が走らないためO(1)になる。

参考: https://stackoverflow.com/questions/11514308/big-o-of-javascript-arrays

結果整合性について

歴史

  • かつて、分散システムのデータ複製における唯一無二の理想は「更新されたデータは即座に反映される」というものだった。
  • 70年台の分散システム技術において試みられているものの多くは、いくら背後にたくさんのシステムが控えているとしても「使う人間からはひとつのシステムを使っている」ように見せることで、その観点から主に議論されていたものの多くはデータの一貫性(Consistency)をいかにして獲得するかという部分に主眼が置かれたものだった。
  • 90年台中頃からインターネット・システムの規模が大型化してくると、開発者の多くはデータの一貫性を犠牲にしてもスケーラビリティを担保することが重要なのではないかと考えはじめた。
  • AWSは世界規模で利用されるシステムを開発するにあたってあらゆる場所でレプリケーション技術を活用してきたが、その中で結果整合性モデルはレプリケーションにおいてデータの一貫性を担保するための技術として提供されてきた。
  • AmazonのCTOであるWerner Vogelsは「並行処理における書き込み・読み込みパフォーマンスの担保」と「データロックによるノードの可用性の低下の抑止」の2つの観点から、データの一貫性はスケーラブルな大規模システムにおいてはさほど重視される必要はないと考えている。

強整合性と結果整合性の違い

強整合性 結果整合性
データのロック あり なし
スケーラビリティ 低い 高い
一貫性 担保される すぐには担保されない
  • 強整合性 の場合、データの更新の際にデータベースをロックすることによってデータの一貫性(Consistency)を担保するが、ロックされる期間が長いほどその間のデータベース・アクセスがブロックされ、可用性(Availability)を犠牲にすることになる。
  • 結果整合性 はデータの更新でデータベースがロックされることはないため、可用性とスケーラビリティを維持することができる。その代わりノード間でのデータの一貫性はデータ複製にかかる時間に依存することになるため、必ずしも担保されない。

その他

結果整合性は必ずしも高度な分散システム固有の難解な技術ではなく、多くのモダンなRDBMSは同期・非同期レプリケーションのシステムが組み込まれている。同期的レプリケーションの場合にはレプリケーションの更新はトランザクションの一部として行われるが、非同期的レプリケーショントランザクションログの伝播の前にプライマリーでのデータ更新が失敗すると、ノード間で一貫性のないデータが生まれることになる。つまり非同期レプリケーションRDBMSにおける古典的な結果整合性のケースのひとつである。

参考

AnyValを継承する意味

ScalaでDDDなコードのアプリケーションを作ろうとしているときに UserId など値型はどうするべきか の記事を読み、「専用の値クラスを作る」のパターンでふと 「ここでケースクラスが AnyVal を継承する理由ってなんだ...?」 と思ったので調べた。

case class PersonId(value: Long) extends AnyVal
case class PersonName(value: String) extends AnyVal
case class OrganizationId(value: Long) extends AnyVal

case class Person(id: PersonId, name: PersonName, organizationId: OrganizationId)
// ...

AnyValを継承すると

AnyValを継承すると値オブジェクトになる。値オブジェクトを継承したクラスはひとつの値しかとれない。

// OK
class Melo(val a: Int) extends AnyVal

// NG
class Melo(val a: Int, val n: String) extends AnyVal

AnyVal を使うことによって 実行時のオブジェクト割り当てを回避することができる ようになる。具体的には上の例でいうと Melo クラスはコンパイル時は Melo クラスだが、実行時は Int として解釈される(アンボクシング)

だが、パターンマッチングなどで型検査が必要になると、 Int としてアンボクシングされた値が再び Melo としてボクシングされることになるため、パフォーマンスに影響を与える。

結論

雑に言うと AnyValを継承したクラスを使うとパフォーマンスが向上する っぽい。

個人的にはDDDにおける値オブジェクトをコードで表現するにあたって、もし 引数がひとつしかない のであれば、どんなケースでも AnyVal を継承しない理由がないように思える... というか、調べていて値クラスという名前がたまたまDDDっぽいだけであって、これならべつにエンティティの実装だって可能なら AnyVal 継承クラスでえんちゃうの、と思ってしまった。

ただ、例えばバリデーションロジックで 「〜文字以下かどうかをチェックする」 みたいなビジネスルールがあったとき、クラスの中に MAXIMUM_LENGTH みたいな定数を宣言するのは普通だが AnyVal を継承しているクラスの中で val による宣言ができないという制約がある。

コレに関しては、以下のようなメソッドを定義してしまえばいいのでは、という同期からのアイデアをもらったが、果たしてアリなのか...?

class Text(value: String) extends AnyVal {
  def MAXIMUM_LENGTH = 100
}

参考文献

Rubyにおけるポリモーフィズムとダック・タイピング

自分がOOPをそれっぽく学んだのは、サンディ・メッツの「オブジェクト指向設計実践ガイド」だが、この本だとダック・タイピングはバキバキにでてくる一方であまりポリモーフィズムについては詳しく書かれていない。thoughtbotのブログの記事、Rubyとポリモーフィズムによると、Rubyにおけるポリモーフィズムは「継承」と「ダック・タイピング」によって実装できるらしい。

継承

まずは継承のパターン。GenericParserというクラスを継承したis-a関係のJsonParserXmlParserを定義し、parseメソッドをオーバーライドしている。

class GenericParser
  def parse
    raise NotImplementedError, 'Implementation required.' 
  end
end

class JsonParser < GenericParser
  def parse
    # Jsonをパースする実装 
  end
end

class XmlParser < GenericParse
  def parse
    # XMLをパースする実装 
  end
end

parser = XmlParser.new
parser.parse

parser = JsonParser.new
parser.parse

ダック・タイピング

つぎにダック・タイピング。ダック・タイピングでは、各パーサ実装はなんのクラスも継承せず、とにかくparseというメソッドを持っているということだけが共通している。

class XmlParser
  def parse
    # Jsonをパースする実装 
  end
end

class JsonParser
  def parse
    # XMLをパースする実装 
  end
end

class GenericParser
  def parse(parser)
    parser.parse
  end
end

parser = GenericParser.new
parser.parse(XmlParser.new)
parser.parse(JsonParser.new)

実装の違い

  • 継承 のコードでは、パーサを使う部分でそれが XmlParser なのか JsonParser なのかが意識されてparseメソッドが呼び出されている。
  • ダック・タイピング のコードでは、parseメソッドを呼び出すGenericParserは、そのメソッドを持つparserが何かを意識していない。

ということが分かる。

継承によるコードは、それぞれのパーサが「誰なのか」(=なにを継承しているか)が分かることによって、パーサに何ができるか(どんなインターフェースを持っているか)を判断できる。一方で、ダック・タイピングとはすなわち「誰か」ではなく「何をするか」によってオブジェクトを見分けるため、パーサがparseメソッドを呼び出せるということを期待するだけでインターフェースは意識しない。

ダック・タイピングとポリモーフィズムの関係

「なるほど、ということはダック・タイピングはポリモーフィズムのサブセットなのだろうか?」 という疑問が湧いてくる。

これまで自分は、ポリモーフィズムとはis-a関係にある継承クラスが抽象クラスと共通したインターフェースで個々の振る舞いを特化したものに変えること、というような理解をしていた。なので、必ずしも共通したインターフェースが保証される関係ではないダック・タイピングはポリモーフィズムに該当しないと考えていたわけだ。だがWikipediaのポリモーフィズムのページによると、ダック・タイピングは動的ポリモーフィズム(英: Runtime Polymorphism)というものに該当するようだ。この意味では、ダック・タイピングは継承に並んでポリモーフィズムを実現するための手段であると言っても良いのではないかと思う。

とはいえ、Googleポリモーフィズムとダック・タイピングについて調べるとStackoverflowの質問がそこそこヒットするが、回答者によってポリモーフィズムとダック・タイピングの関係をどう捉えるかというのは割れているように見える。ある人は 「ダック・タイピングはポリモーフィズムするための方法の一つで間違いないよ」 と言ったり、またある人は ポリモーフィズムはインターフェースによる明示性(explicitness)を必要をするものだからダック・タイピングは違う」 と言ったりしている。やはり、これに関してはもう少しOOPの原典的なものにあたったほうがいいのかもしれない。

雑なDNSの理解

  • Domain Name Systemの略
  • インターネットに接続されているすべてのコンピューターはIPアドレスを割り振られているが、数字でサイトを記憶しておくのは難しいので、DNSで覚えやすい文字列への解決を行う。
  • ARPANET時代はひとつのHOSTS.TXTにすべて書き込まれたものをFTPで共有していたが、ファイルがでかくなりすぎたのでDNS鯖が生まれた。
  • UNIX系OSにある /etc/hostsDNSと同じ役割を持っている。
    • これはARPANET時代のHOSTS.TXTの名残で、ローカルだけでDNSに問い合わせないドメイン名解決を行いたいときにはここに書いておく。
    • 開発で localhost:3000 とかを hoge.net とかにしておくと楽になったりする(?)
    • localhost127.0.0.1 に解決されているのはこのファイルによって。

名前解決

たとえばPCのブラウザで hogehoge.net へリクエストを送るまでの例

  1. [PC] ブラウザで hogehoge.net を開く。
  2. [PC] /etc/hosts に該当するIPアドレスとの組み合わせがあればそれで解決
  3. [家庭用ルーター] プロバイダからDNSルートサーバのIPアドレスを受け取る
  4. [家庭用ルーター] hogehoge.netDNSルートサーバに問い合わせる。
  5. [DNSルートサーバ] net DNSサーバが管理しているという旨を家庭用ルーターに伝える
  6. [家庭用ルーター] net DNSサーバへ hogehoge.net を問い合わせる
  7. [net DNSサーバ] hogehoge.netドメインを解決し、IPアドレスである 123.45.6.78 を家庭用ルーターへ伝える。
  8. [家庭用ルーター] PCへ 123.45.6.78 を伝える
  9. [PC] ブラウザは 123.45.6.78 へリクエストを送ってデータを取得したりする。

参考: インターネット10分講座 DNS - JPNIC