<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Atsushi Takayama on Medium]]></title>
        <description><![CDATA[Stories by Atsushi Takayama on Medium]]></description>
        <link>https://medium.com/@taka.atsushi?source=rss-b64b37102e90------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*tEXwuePyTKgMnWK0ImbY6Q.jpeg</url>
            <title>Stories by Atsushi Takayama on Medium</title>
            <link>https://medium.com/@taka.atsushi?source=rss-b64b37102e90------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Tue, 17 Nov 2026 18:59:41 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@taka.atsushi/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Courseraのオンライン修士2年目が終わった]]></title>
            <link>https://medium.com/@taka.atsushi/coursera%E3%81%AE%E3%82%AA%E3%83%B3%E3%83%A9%E3%82%A4%E3%83%B3%E4%BF%AE%E5%A3%AB2%E5%B9%B4%E7%9B%AE%E3%81%8C%E7%B5%82%E3%82%8F%E3%81%A3%E3%81%9F-cdd9ce1dc6ec?source=rss-b64b37102e90------2</link>
            <guid isPermaLink="false">https://medium.com/p/cdd9ce1dc6ec</guid>
            <dc:creator><![CDATA[Atsushi Takayama]]></dc:creator>
            <pubDate>Sat, 25 Dec 2021 07:18:31 GMT</pubDate>
            <atom:updated>2021-12-27T02:37:07.780Z</atom:updated>
            <content:encoded><![CDATA[<p>以前にこちらのブログを書いて、その後も継続して読まれているようなので、近況をアップデートしておきます。</p><p><a href="https://medium.com/@taka.atsushi/coursera%E3%81%A7%E3%82%A4%E3%83%AA%E3%83%8E%E3%82%A4%E5%A4%A7%E5%AD%A6%E3%81%AE%E3%82%B3%E3%83%B3%E3%83%94%E3%83%A5%E3%83%BC%E3%82%BF%E3%83%BC%E3%82%B5%E3%82%A4%E3%82%A8%E3%83%B3%E3%82%B9%E5%A4%A7%E5%AD%A6%E9%99%A2%E3%81%AB%E5%87%BA%E9%A1%98%E3%81%97%E3%82%88%E3%81%86%E3%81%A8%E3%81%97%E3%81%9F-2072ddbebaf9">Courseraでイリノイ大学のコンピューターサイエンス大学院に出願しようとした</a></p><h3>私は誰？</h3><p>高山です。2020年からNewsPicksでCTOをしています。上の記事を書いたときはピクシブでCTOをしていました。</p><p>2017年頃からぼんやりと大学院入学を考えはじめたのですが、そしたらたまたまイリノイ大学のことを知って書いたのが上の記事です。それから1年ほどかけて準備して出願して、ちょうど転職した月とまったく同じ2020年の2月に入学して社会人大学院生をしています。</p><h3>コースについて</h3><p>まず、University of Illinoisと名の付く大学にはUrbana-Champaign (UIUC)とChicago (UIC)とSpringfield (UIS)の3つの大学があります。これらは別々の大学です。早稲田と慶應ぐらい別物だと思います。</p><p>Courseraで入学できるのはUIUCです。UIUCのコンピューターサイエンスはものすごく由緒正しく、Marc AndreessenがMosaicブラウザを作ったりChris LattnerがLLVMを作ったのもここだそうです。厚切りジェイソンさんも先輩です。</p><p>Courseraで履修できるのは<a href="https://cs.illinois.edu/academics/graduate/professional-mcs/online-master-computer-science">Master of Computer Science (MCS)</a>と<a href="https://cs.illinois.edu/academics/graduate/professional-mcs/online-master-computer-science-data-science">Master of Computer Science in Data Science (MCS-DS)</a>の2つです。MCSではコンパイラーとか画像処理とかクラウドコンピューティングなど幅広い単位が提供されていて、MCS-DSはほぼ同じ内容ですが幅ではなく深さを求めるので統計などの単位を多く取る必要があります。僕自身はMCSに入学しましたが、これまで受けたクラスはMCS-DSとしても使える単位ばかりなので、今からMCS-DSに切り替えることも可能のはずです。（確かそう聞いた記憶）</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*845PNYmBochRBKpAaC-BHA.png" /></figure><p>修了までに取得しないといけないクラスは8つで、1年に3学期なので、1学期に1クラスのペースでやっていけば2年半で終わります。これまでに受けたクラスは次のとおりです。</p><ul><li><strong>Database Systems</strong> : RDBのリレーショナルモデルとかグラフDBとかをやりました。正直知っている内容ばかりでしたが、最初なので敢えてそういうのを選びました。</li><li><strong>Statistical Modeling in R</strong> : 線形回帰について3ヶ月かけてみっちり勉強しました。帰無仮説とかt検定とかR²とかLOO-CVとかAICとかBICとか。授業だけではわからなかったので一番教科書を読みました。教科書は<a href="https://daviddalpiaz.github.io/appliedstats/probability-and-statistics-in-r.html">こちら</a>のオリジナル教材です。</li><li><strong>Distributed Systems</strong> : リーダー選出とかQuorumとかGossipとか分散KVSについて勉強しました。かなりハードなクラスでしたが、入学前にCourseraでこの講義に潜っていたので（それが推奨されている）、勉強するのが2度目だったのでなんとか通過できました。</li><li><strong>Computational Photography</strong> : 写真を加工する古典的アルゴリズムについて学びました。人物を消したり別の画像の一部を挿入したり、HDRやガンマ補正の仕組みなど。最後は3Dモデルを写真に挿入するプロジェクトでした。プログラミングが激ムズでした。</li><li><strong>Data Visualization</strong> : データの可視化の手法について学びました。特にインタラクティブなグラフをTableauやD3.jsで作る方法を学びました。一番簡単なクラスでした。</li><li><strong>Practical Statistical Learning</strong> : Ridge, Lasso, ランダムフォレスト, GBM, EMアルゴリズム, SVMなどなどを学びました。プログラミング課題はKaggleの練習問題のような内容でした。</li></ul><p>授業はCourseraで動画が毎週2時間ぶんぐらいですが、理解しようとしながら見ると半日〜1日がかりになることが多かったです。その後1時間ぐらいのクイズと呼ばれる小テストが毎週あります。中間試験と期末試験もあります。</p><p>それ以外にもプログラミング課題が2週間に1回ぐらいあります。これはほとんど自動採点で、こちらも半日〜1日ぐらいかけて解いています。プロジェクトのレポート課題があるクラスもあります。プロジェクトは数週間かけてちょっとずつやります。</p><p>全部を真面目にやっていると、週末だけで終わらせるのはかなり大変です。ありがたいことに日本には祝日がありますし、たまに休みも取りながらなんとか期日通りに課題を仕上げてきました。</p><h3>所感</h3><p>2年目が終わった時点で考えていることを書き残しておきます。</p><h4>時間について</h4><p>まず一番の感想は、想像以上にストイックでしんどいです。休日はほぼすべて使ってようやくこなせるぐらいですし、常に締め切りに追われている気苦労があります。仕事の締め切りと重なったときは恐怖です。</p><p>最初は意気込んでAを狙いに行っていましたが、途中から気持ちを切り替えて、仕事との両立を目指すことにしました。クイズと課題の状況から学期の途中で今の成績がわかるので、酷い状況じゃなければ5%ぐらいの点数は捨てに行っても良いと思うようにしています。一応ここまではB+以上でやってきています。ちなみに400レベルのクラスで一つでもB-未満が付くと強制退学だそうです。（500レベルだとC未満で強制退学）</p><p>常にペースメイキングしてくれるのは僕の勉強のスタイルにはとても有効に機能しています。「ソフトウェアエンジニアたるもの常に勉強」と言われますが、僕はOSS活動も個人プロジェクトも続かない人間です。時間があるとだいたい仕事のコードを書いてるかYouTubeなどで技術解説やカンファレンス発表を見ていました。今は仕事のコードからプログラミング課題に、YouTubeからCourseraにそれぞれ変わって、毎週ノルマが課されるというぐらいです。やってることはあまり変わらないのに学位まで取れてお得な気がします。</p><p>時間を捻出するためにはかなり頑張りました。家事を極力自動化するのはもちろん、料理は2週間分まとめて作って冷凍したり。家の居心地に投資して週末は家から出くても苦にならないようにしたり。コロナでステイホームな風潮になったりリモートワークになった時期に入学できたのは本当にラッキーでした。</p><h4>価値について</h4><p>次に大きな感想は、修士に必要な単位を取ったからといって<a href="https://tech.preferred.jp/ja/blog/27nishikawa/">コンピューターサイエンスのすべての分野に精通</a>するなんてことは無いということです。（当然ですけど）</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*_dCFjUK_LpYAe-MFDyAEiQ.jpeg" /><figcaption><a href="https://twitter.com/dominicwalliman/status/1154034153349738498">https://twitter.com/dominicwalliman/status/1154034153349738498</a></figcaption></figure><p>勉強した分野についてはある程度網羅的にカバーされて自信になりますが、それでも全体のうちごく一部を少し囓ったぐらいなんだと思うと、無知の知が深まったに過ぎません。</p><p>そもそもアメリカのコンピューターサイエンスの学位自体、シリコンバレーなどで優遇されるのでそのための「就職予備校」として進化してきた側面がかなり大きいはずです。修士をやったらコンピューターサイエンスのすべての分野に精通できるんだろうかという過度な期待は無くなりました。</p><p>人脈もできずアメリカの就労ビザがもらえるわけでもなく、修論も無いため研究する力も身に付かないこのオンライン修士には何の価値があるんだろうかと思うこともあります。（お得な気がすると書いたばかりですが）</p><p>そんなことも入学してみなければ知れなかったことですし、知らなかったことを体験を通じて知れたことに価値があると思います。歴史的に見ても、教育に幅広い人がアクセスできるようになったことで、教育の価値が減って見向きもされなくなるということは無く、逆に必須と見なされるようになってきたので（高卒や大卒のように）、同じようなことが起きると思っています。</p><h4>効果について</h4><p>ソフトウェアエンジニアリングにまつわる仕事をしていると、コンピューターサイエンスの知識は役立っている感覚が多々あります。また、仕事で比較的すぐ必要そうだと思って取った単位もかなりあります。ここは社会人学生の醍醐味です。</p><p>もちろん、仕事でQuorumを実装することは無かったとしても、<a href="https://docs.aws.amazon.com/ja_jp/amazondynamodb/latest/developerguide/backuprestore_HowItWorks.html">DynamoDBのバックアップに関するドキュメント</a>を読んでいて<a href="https://en.wikipedia.org/wiki/Chandy%E2%80%93Lamport_algorithm">Chandy-Lamport Snapshotアルゴリズム</a>が想像できるのはDistributed Systemsを取ったおかげです。機械学習のクラスはもっと直接的に役立っています。</p><p>給料が上がるとか転職につながるかというと、まだそこまでは無いですが、長いキャリアの中でいつかは武器にするつもりです。</p><p>僕自身ソフトウェアエンジニアの採用に関わる仕事をしていますが、「Courseraで修士をやってます」という人が来ても参考程度にするぐらいでしょう。しかし、「Coursearで修士を取ってその専門を活かして数年仕事をしていました」という人であればけっこう優遇すると思います。そんなふうに使う予定です。</p><p>副次的な効果として、入学する前にTOEFL対策を頑張ったおかげで英文を日本語の半分ぐらいのスピードで苦なく読めるようになり、入学してから教科書をけっこう読んだことで英語の専門書を読むことに抵抗がなくなりました。また、英文を読む量が増えたことでレポートを書くときに文章がすらすら浮かんでくることを実感しています。</p><p>最後に、修論が無いことについて思うところを書いておきます。</p><p>修論が無いため、研究する力はこのコースでは得られないと思います。日本の博士後期課程に入学しようと思うと修論相当の提出が求められると思いますので、そこは別で頑張る必要があります。（いつか頑張りたい）</p><p>アメリカでは大学院というと前期・後期の概念が無くDoctorの取得を目指すのが主流で、途中で退学するときにお情けでMasterをもらうことをMaster Outと言ったりします。そんな文化ですが、コンピューターサイエンスはMaster Outであっても重宝されるため、「就職予備校」としてMasterコースが作られるようになったのだと想像しています。詳しい人がいれば教えてほしいです。</p><h3>これから</h3><p>順当にいけば来年の夏頃に修了のはずなので、強制退学にならないように頑張ります。</p><p>その後については、やはり論文を書けるようになりたいですね。そのためには、来年中には<a href="https://www.slideshare.net/Ochyai/1-ftma15">落合陽一メソッド</a>の「鬼コース」（下のスライドを参照）をやってみようと思います。</p><p>人生100年と思ってじっくり気長にやっていきます。</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/638/1*I7f4ScZTu8qE5TUL-cHv2Q.jpeg" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/638/1*_d9_n2GwBr_9RHfkhITAvw.jpeg" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/638/1*j-sSzSNm3ovLho0m8KDtww.jpeg" /></figure><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=cdd9ce1dc6ec" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[『事業をエンジニアリングする技術者たち Engineering in VOYAGE』を読んだ]]></title>
            <link>https://medium.com/@taka.atsushi/%E4%BA%8B%E6%A5%AD%E3%82%92%E3%82%A8%E3%83%B3%E3%82%B8%E3%83%8B%E3%82%A2%E3%83%AA%E3%83%B3%E3%82%B0%E3%81%99%E3%82%8B%E6%8A%80%E8%A1%93%E8%80%85%E3%81%9F%E3%81%A1-engineering-in-voyage-%E3%82%92%E8%AA%AD%E3%82%93%E3%81%A0-9ef85b02150?source=rss-b64b37102e90------2</link>
            <guid isPermaLink="false">https://medium.com/p/9ef85b02150</guid>
            <dc:creator><![CDATA[Atsushi Takayama]]></dc:creator>
            <pubDate>Sat, 12 Sep 2020 08:58:09 GMT</pubDate>
            <atom:updated>2020-09-12T09:12:55.010Z</atom:updated>
            <content:encoded><![CDATA[<p>献本をいただいてからしばらく経ってしまいましたが、読了しました。</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*UCbpyh8hRQKJgmkkk7T1uA.jpeg" /><figcaption><a href="https://www.amazon.co.jp/dp/B08GSQ4BL3">https://www.amazon.co.jp/dp/B08GSQ4BL3</a></figcaption></figure><p>広木大地さんが「読むインターンシップ」と書いてて、とても納得したので、VOYAGEさんにインターンしてる気分で読みました。</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*C44Hs838Z598OPhfOHtb5g.png" /><figcaption><a href="https://www.facebook.com/hirokidaichi/posts/10217896457386338">https://www.facebook.com/hirokidaichi/posts/10217896457386338</a></figcaption></figure><h3>ビジョンを掲げないこと</h3><p><a href="https://voyagegroup.com/company/philosophy/">VOYAGEさんの経営理念のページ</a>を見ると、「ビジョンは掲げてない」とはっきり書いてあります。</p><p>僕自身はミッション・ビジョンの旗印のもとに集う組織が好きで、今勤めているユーザベースも「経済情報で、世界をかえる」を全員で実現することを目指す組織なのですが、ビジョンを掲げないことでどんな良さがあるのかも理解できているつもりです。</p><p>VOYAGEさんはビジョンを掲げない代わりに、「SOUL=360°スゴイ」というSOULと、行動指針としてCREEDを掲げています。</p><p>つまり、CREEDを体現する<strong>スゴイ人達がスゴイことを成し遂げることを全力で後押しする会社</strong>なんだと思っています。</p><p>「スゴイ」とは若干違うのかもしれませんが、「カッコイイ」について本の147ページに書かれています。（僕は同様の意味だと捉えました）</p><blockquote>サポーターズ代表である楓博光の想いを端的に表したのが、この「「カッコイイオトナ」を増やす」というフレーズです。どんな大人が「カッコイイ」かは折に触れて再定義しているんですが、「自分たちがなりたい未来を選んで自分で決めて進んでいけるような大人」を増やしていけるサービスでありたいと考えています。</blockquote><h3>事業をエンジニアリングする技術者とは</h3><p>インタビューされているエンジニア達は皆そんな「カッコイイオトナ」です。</p><p>ゲーム攻略メディアを一人で立ち上げて5年でライター30人を抱える事業にしたエンジニアも、15年で1200テーブルに成長してしまったシステムを徐々に紐解いて450テーブルにしたエンジニアも、ついカッとなって改善しまくってたらCTOになってたエンジニアも、みんなカッコイイしスゴイ。</p><p>事業を担うエンジニアとして自分で責任持って考えて行動して課題解決にあたっているからこそ、誰に使われるわけでもなく「自分たちがなりたい未来を選んで自分で決めて進んでいけるような大人」になっています。</p><p>過去20年のウェブ技術の進化は、より少人数で事業が実現できる方向への進化でした。それを最大限活用して、徹底して少人数エンジニアチームによる事業貫いてきたからこそ、一人一人のエンジニアがカッコイイ会社でいられるのだろうと思います。</p><h3>おことわり</h3><p>上記はあくまで外部から見た想像ですのであしからず。</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9ef85b02150" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[新卒研修でエンジニアのお仕事について話しました]]></title>
            <link>https://medium.com/@taka.atsushi/%E6%96%B0%E5%8D%92%E7%A0%94%E4%BF%AE%E3%81%A7%E3%82%A8%E3%83%B3%E3%82%B8%E3%83%8B%E3%82%A2%E3%81%AE%E3%81%8A%E4%BB%95%E4%BA%8B%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6%E8%A9%B1%E3%81%97%E3%81%BE%E3%81%97%E3%81%9F-fe4d4fb825db?source=rss-b64b37102e90------2</link>
            <guid isPermaLink="false">https://medium.com/p/fe4d4fb825db</guid>
            <dc:creator><![CDATA[Atsushi Takayama]]></dc:creator>
            <pubDate>Thu, 04 Apr 2019 16:59:47 GMT</pubDate>
            <atom:updated>2019-04-05T08:08:10.460Z</atom:updated>
            <content:encoded><![CDATA[<p>ピクシブの2019年度の新卒研修で発表した内容です。</p><p>文脈としては、新卒全員（ビジネス職も含む）に社内の色んな職種について話すパートでエンジニアの職種について話してくれとのことだったのですが、「今こういう仕事があります」だと深みがないので、「なぜこういう仕事があるのか」を重点的に話すことにしました。</p><h3>エンジニアリングとは</h3><p>エンジニアリング：<strong>課題解決のためにシステムを作ること</strong></p><p>システム：<strong>複数の要素が相互作用しながら動く仕組みのこと</strong></p><p>ソフトウェアエンジニアリング：<strong>課題解決のためにソフトウェアというシステムを作ること</strong></p><p>ソフトウェアも、複数の要素が相互作用しながら動く仕組みですね。</p><h4>Q: ソフトウェアではない「システム」は何がありますか？</h4><p>例えば、「風が吹けば桶屋が儲かる」。</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/525/1*3igQtWu9dYAra8rf_KIpKA.png" /></figure><p>人と人との関係も、システムといえます。</p><h3>ソフトウェアエンジニアリングの歴史</h3><p>元々は、こういう機械を作るのがエンジニアリングでした。「エンジン」ですね。</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/449/1*urAVF67fnjsiIqPq43PHCQ.jpeg" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/464/1*5y_KWQnyj2PIC0fsEje7ig.jpeg" /></figure><p>1960年代頃にソフトウェアエンジニアという言葉が生まれたようです。</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/303/1*Mu2AaWq72gx7qamarpyi-Q.jpeg" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/356/1*qBXQHK1QZDC4rUDoe7RTKw.jpeg" /></figure><p>1990年頃まで、ソフトウェアは「機械の一部として売るもの」でした。（組み込みソフトウェア）</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/276/1*nO50r2xztzbuhxqa0qc8Bg.jpeg" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/225/1*eKU7dTjGBTtjUNiJmEjVNA.jpeg" /></figure><p>1995年頃からパソコンが普及して、パッケージソフトというものが生まれました。</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/250/1*Y6SWPVJ4uFTUB5BajAzmog.jpeg" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/400/1*jzEOrXPh8tAtb_kTL9HtEg.png" /></figure><p>同じく1995年頃からインターネットが普及して、ウェブサービスが生まれました。</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/500/1*A2s9EueVDwXfr-rS20qHmQ.jpeg" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/590/1*4x92s-XmTdcP7Lj1d80vfQ.jpeg" /></figure><p>ウェブサービスのソフトウェアは、サーバーで動きます。サーバーはデータセンターというところにあります。</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/630/1*5jgl7gOSQjyBN1RqEVghRw.jpeg" /></figure><h4>Q: 組み込みソフトウェアと、パッケージソフトと、ウェブサービスの大きな違いは何でしょうか？</h4><p>リリースの頻度が全然違います。</p><ul><li>1度きり</li><li>数ヶ月〜数年に1回</li><li>毎日〜毎週</li></ul><p>頻繁にリリースできるということは、頻繁に改善できるということです。</p><p>2000年頃はドットコムバブルというものがあって、数万社がライバル達に先んじて成功しようと戦っていました。Googleですら、検索エンジン会社の中では18番目と後発でした。</p><p>毎日リリースして毎日改善することは、ウェブサービスの会社にとっては生命線です。そのためには、ソフトウェア開発のやり方をそれまでと大きく変える必要がありました。</p><p>要件定義に数週間、開発に数ヶ月、テストに数週間なんて、とてもじゃないですがかけていられません。</p><h3>アジャイルソフトウェア開発</h3><p>そんな流れの中で出てきた考え方がリーンとかアジャイルという考え方です。（Lean = 無駄のない、Agile = 俊敏な）</p><p>いかに最速で最高の価値をユーザーに届けていくか、その開発プロセスを常に改善し続けましょう、という考え方です。</p><p><strong>すべての仕事は、「本質的な価値提供」をするための「作業」から成り立っています。</strong></p><p>作業は減らし、本質的な価値提供は増やしたいですよね。</p><p>例えば、メールを送るのは作業で、本質的な価値提供は「相手に情報を伝えること」のはずです。（さらに本質的な価値提供は、情報が伝わった結果のアクションが起こることのはずです）<br>メールのテンプレを作っておくとか、メールじゃなくてSlackにするとかでも、目的が達成できれば良いわけです。</p><p><strong>ソフトウェアエンジニアリングも同様です。脳内で組み立てた処理がコードを書かずに動いたら一番良いはずです。</strong></p><p>実際、世の中はそういう方向に猛スピードで進化してきました。</p><p>例えばRuby on Railsは、一般的なウェブアプリケーションで作るようなものを最小限のコードで実現することを目指して作られたフレームワークです。</p><h3>ここまでのまとめ</h3><ul><li>「いかに最速で最高の価値をユーザーに届けていくか、その開発プロセスを常に改善し続けましょう」という流れ</li><li>「作業」を減らして「本質的な価値提供」を簡単に実現できるようにソフトウェアエンジニアリングは進化している</li></ul><p>（ここまで20分ぐらい）</p><h3>社内の「エンジニア」とその周辺のお仕事紹介</h3><p>ここまでの内容を踏まえて、「実際にやっている仕事」だけではなく、「本質的な価値」と「本質的な価値提供を効率化する仕事」にフォーカスして見ていきます。</p><h3>サーバーサイドエンジニア</h3><p>RubyやPHPやScalaやJavaやGoなどを書いて、サーバーで動く<strong>ビジネスロジック</strong>や、ビジネスロジック同士を繋ぐ処理を作ります。</p><p>ビジネスロジックとは、サービスとして提供したい処理の本体のことです。</p><p>「商品を3件カートに入れて注文すると、発送のフローにまわる」みたいなのがビジネスロジックです。</p><h4>本質的な価値</h4><p>ビジネスロジックをソフトウェアとして実現することです。</p><h4>本質的な価値提供を効率化する仕事</h4><p>Ruby on Railsのようなフレームワークを作ったり、ソフトウェアをリリース（デプロイ）するためのソフトウェアを作ったりすることです。</p><h3>インフラエンジニア</h3><p>サーバーや、その上で動くOSやミドルウェアを管理します。</p><h4>本質的な価値</h4><p>サーバーサイドエンジニアがビジネスロジックに集中できるように、サーバーやOSやミドルウェアのことを（あまり）意識しなくてもソフトウェアが動く状態を実現することです。</p><h4>本質的な価値提供を効率化する仕事</h4><p>インフラエンジニアが手作業でやっている仕事を自動化する、あるいは無くすことです。</p><h3>フロントエンドエンジニア</h3><p>JavaScriptなどを書いてUIを作ります。</p><h4>本質的な価値</h4><p>サービスが提供したいユーザー体験を、ウェブのUIとして実現することです。</p><h4>本質的な価値提供を効率化する仕事</h4><p>ReactやVueのようなフロントエンドのフレームワークを作ったり、サーバーサイドのAPIをフロントエンドから使いやすいように作ったりすることです。</p><h3>アプリエンジニア</h3><p>iPhoneやAndroidのアプリを作ります。</p><p>広い意味では、VRoidを作っているUnityエンジニアもアプリエンジニアと言えるかもしれません。</p><h4>本質的な価値</h4><p>サービスが提供したいユーザー体験を、アプリのUIとして実現することです。</p><h4>本質的な価値提供を効率化する仕事</h4><p>よく使うコンポーネントなどを<strong>ライブラリ</strong>として作ったり、既に公開されているライブラリに機能追加することで、ゼロから作らなくても良くなります。</p><p>アプリを作るための設計指針を作って、次にコードを書く人が迷わないようにするのも効率化のための仕事です。</p><h3>レコメンドエンジニア</h3><p>機械学習などを使ってレコメンドを実現します。</p><h4>本質的な価値</h4><p>サービスが実現したいユーザー体験を、レコメンドを通じて実現することです。</p><h4>本質的な価値提供を効率化する仕事</h4><p>データ活用の基盤を整備したり、データを使える状態にしたり、機械学習のフレームワークを整えることです。</p><h3>その他</h3><p>以上が社内で多いエンジニアですが、他にも次のようなお仕事もあります。</p><h4>配信技術エンジニア</h4><p>画像や動画の変換と配信に関する開発をします。</p><h4>テストエンジニア</h4><p>エンジニアがテストを書くための仕組みを整えます。</p><p>自動テストがあることで、バグに早めに気付けるので開発が効率化します。</p><h4>セキュリティエンジニア</h4><p>これも同様に、セキュリティを強化することでサービス開発を効率化します。</p><h4>データアナリスト / UXリサーチャー</h4><p>データ分析のためのコードを書くが、サービスを開発するとは限りません。</p><p>このような、コードは書くけれど大きなシステムを組み上げるわけではないお仕事は今後増えていくと思います。</p><h4>デザイナー</h4><p>フロントエンドのコードも書くけど肩書き上はデザイナーというパターンもあります。</p><h4>マネージャー / CTO</h4><p><strong>経営の</strong>課題解決のために<strong>開発組織という</strong>システムを作ることがお仕事です。</p><p>（ここまで40分）</p><h3>ソフトウェアエンジニアのキャリア</h3><p>ソフトウェアエンジニアのキャリアをとりあえず2つ紹介します。</p><h4>本質的な価値提供の効率化を追求する</h4><p>（ソフトウェアエンジニアに限らず）すべての仕事は「本質的な価値提供」と「作業」から成り立っており、「作業」を減らして「本質的な価値提供」を増やすことが求められます。</p><p>作業 : 効率化 = 8 : 2 ぐらいの考え方で仕事をすると良いと思います。</p><p>もし効率化のほうに向いていれば、チームと相談して6 : 4とか5 : 5ぐらいにすると良いと思います。</p><p>もっと追求したくなったら、技術開発本部と相談して専業化できるかもしれません。<br>（もしくは、転職のときかもしれません）</p><h4>本質的な価値提供のために、隣接分野に進む</h4><p>アプリエンジニアもサーバーサイドのエンジニアも、本質的には「ユーザーにサービスを届ける」ことなので、目的のためなら手段は選ばずに色々な技術に手を出してみるのは、俯瞰した視点を得られ、キャリアにとってもプラスになると思います。</p><p>本質的な価値提供のために配信技術のような難しいエンジニアリングに挑戦してみるのも、もちろんプラスになると思います。</p><p>データ分析したりデザインをやったりマネジメントをするのも、実は本質的な価値提供はまったく同じです。</p><h3>ソフトウェアエンジニアの将来</h3><p>サーバーサイドエンジニアやフロントエンドエンジニアという職種ができたのは、たったの10年前ぐらいです。<br>（その前はウェブエンジニアとHTMLコーダーとかがありました）</p><p>今ある職種も、たぶん10年後は別の名前に分かれていると思います。</p><p>10年もすると、プログラミングできることが当たり前な時代が来ます。<br>世間一般ではまだ先でしょうが、少なくともIT企業はそうなるはずです。</p><p>つまり、時代が変わっても応用が効くように挑戦し続けることが大事です！</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=fe4d4fb825db" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Coursera: Cloud Computing Concepts, Part 1]]></title>
            <link>https://medium.com/@taka.atsushi/coursera-cloud-computing-concepts-part-1-538df331ff41?source=rss-b64b37102e90------2</link>
            <guid isPermaLink="false">https://medium.com/p/538df331ff41</guid>
            <category><![CDATA[coursera]]></category>
            <category><![CDATA[big-data]]></category>
            <dc:creator><![CDATA[Atsushi Takayama]]></dc:creator>
            <pubDate>Sun, 17 Mar 2019 04:34:43 GMT</pubDate>
            <atom:updated>2019-04-13T15:34:01.818Z</atom:updated>
            <content:encoded><![CDATA[<p><a href="https://www.coursera.org/learn/cloud-computing">Cloud Computing Concepts, Part 1 | Coursera</a></p><h3># 2019/03/16 Week 1 Lesson 1: Introduction to Clouds</h3><h4>## 1.1: Why Clouds?</h4><p>Operation cost, saves development time.</p><h4>## 1.2: What is a Cloud?</h4><p>Cloud = Lots of storage + compute cycles nearby</p><h4>## 1.3: Introduction to Clouds: History</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/792/1*TVkgMowAGLA1K4nuiUv_nA.png" /></figure><h4>## 1.4: Introduction to Clouds: What’s New in Today’s Clouds</h4><p>4 distinctive features of today’s clouds:</p><ul><li><strong>Massive scale</strong></li><li><strong>On-demand access</strong></li><li><strong>Data-intensive Nature</strong></li><li><strong>New Cloud Programming Paradigm</strong></li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/776/1*x_vdutg4AJtPS3l6WUm2uw.png" /></figure><h4>## 1.5: Introduction to Clouds: New Aspects of Clouds</h4><p>On-demand: renting a <strong>cab</strong> vs renting a <strong>car</strong> or buying one</p><p>HaaS (HW), IaaS, PaaS, SaaS</p><p>Data-Intensive Computing: <strong>focus shifts from computation to the data</strong>. CPU utilization no longer the most important resource metric, instead I/O is (disk and/or network)</p><h4>## 1.6: Introduction to Clouds: Economics of Clouds</h4><p>Outsource or own?: If service is running for more than a years or so, owning is cheaper (in terms of the hardware price only)</p><p>Break-even point for storage is much smaller than the overall cost.</p><p>As a result: <strong>Cloud providers benefit monetarily most from storage</strong></p><h3># 2019/03/16 Week 1 Lesson 2: Clouds are Distributed Systems</h3><h4>## 2.1: A cloud IS a distribution system</h4><ul><li>Servers communicate amongst one another</li><li>Clients communicate with servers</li><li>Clients may also communicate with each other (eg. P2P)</li></ul><p>Nicknames for “distributed system” include peer-to-peer systems, grids, clusters, timeshared computes (Data Processing Industry; 60&#39;s-70&#39;s), then <strong>cloud.</strong></p><p>Core concepts are the same!</p><h4>## 2.2: What is a distributed system?</h4><p>What is an Operating System?</p><ul><li>User interface to hardware (device drivers)</li><li>Provides abstractions (processes, file system)</li><li>Resource manager (scheduler)</li><li>Means of communication (networking)</li><li>etc.</li></ul><p>A working definition of “Distributed System”: A distributed system is a collection of entities, each of which is <strong>autonomous</strong>, <strong>programmable</strong>, <strong>asynchronous </strong>and<strong> failure-prone</strong>, and which communicate through an <strong>unreliable</strong> communication medium.</p><p>Many interesting problems:</p><ul><li>P2P systems (Gnutella, Kazaa, BitTorrent)</li><li>Cloud Infrastructures (AWS, Azure, Google Cloud)</li><li>Cloud Storage (KVS, NoSQL, Cassandra)</li><li>Cloud Programming (MapReduce, Storm, Pregel)</li><li>Coordination (Paxos, Leader Election, Snapshots)</li><li>Managing Many Clients and Servers Concurrently (Concurrency Control, Replication Control)</li></ul><p>Challenges:</p><ul><li>Failures: no longer the exception, but rather a norm</li><li>Scalability: 1000s of machines, Terabytes of data</li><li>Asynchrony: clock skew and clock drift</li><li>Concurrency: 1000s of machine interacting with each other accessing the same data</li><li>…</li></ul><h3># 2019/03/16 Week 1 Lesson 3: MapReduce</h3><h4>## 3.1: MapReduce Paradigm</h4><ul><li>Map: &lt;file name, file content&gt; → [&lt;key, value&gt;]</li><li>Reduce: &lt;key, [value]&gt; → &lt;key, value&gt;</li></ul><p>Many ways to assign reduce servers to keys for load balancing.</p><p>eg. Hash partitioning: hash(key) % (number of reduce servers)</p><h4>## 3.2: MapReduce Examples</h4><p>Distributed Grep:</p><ul><li>Input: large set of files</li><li>Output: lines that match pattern</li><li>Map: emits a line if it matches the supplied pattern</li><li>Reduce: copies the intermediate data to output</li></ul><p>Reverse Web-Link Graph:</p><ul><li>Input: web graph: tuple (a, b) where (page a → page b)</li><li>Output: for each page, list of pages that link to it</li><li>Map: &lt;source, target&gt; → &lt;target, source&gt;</li><li>Reduce: emits &lt;target, list(source)&gt;</li></ul><p>Count of URL access frequency:</p><ul><li>Input: logs of accessed URLs</li><li>Output: for each URL, % of total accesses for that URL</li><li>Map: log files → &lt;URL, 1&gt;</li><li>Multiple Reduces: &lt;URL, count&gt;</li><li>then chain</li><li>Map: &lt;URL, URL count&gt; → &lt;1, (&lt;URL, URL count&gt;)&gt;</li><li>Single Reducer: Sums up URL counts to calculate overall count, then emit multiple &lt;URL, URL count/overall count&gt;</li></ul><p>Sort: (well, it’s easy because MapReduce does sort on Map’s output and Reduce’s input)</p><ul><li>Input: series of &lt;key, value&gt; pairs</li><li>Output: sorted &lt;value&gt;s</li><li>Map: &lt;key, value&gt; → &lt;value, _&gt; (identity)</li><li>Reduce: &lt;key, value&gt; → &lt;key, value&gt; (identity)</li><li>Partition function: partition keys across reducers based on ranges (not hash partitioning)</li></ul><h4>## 3.3: MapReduce Scheduling</h4><p>Make sure no Reduce tasks start before all Map and Shuffle tasks finish; the <strong>barrier</strong> between the Map phase and the Reduce phase.</p><p>Without the barrier;</p><ul><li>A MapReduce run may be <strong>incorrect</strong> since some of the key-value pairs generated by Maps may never be processed by a Reduce <strong>if the reduce function is called exactly once per key</strong>.</li><li>All MapReduce runs could be <strong>correct</strong> if Reduces <strong>maintain partial results</strong> for keys, and <strong>update</strong> these as new key-value pairs come in.</li></ul><p>Intermediate files between Map and Reduce need not be visible, so storing files close to the nodes for performance;</p><ul><li>Map input: from distributed file system</li><li>Map output: to local file system</li><li>Reduce input: from (multiple) remote disks</li><li>Reduce output: to distributed file system</li></ul><p>YARN (Yet Another Resource Negotiator) in Hadoop 2.x+:</p><ul><li>Global <strong>Resource Manager</strong> (RM): scheduling</li><li>Per-server <strong>Node Manager</strong> (NM): daemon and server-specific functions</li><li>Per-application (job) <strong>Application Master</strong> (AM): container negotiation with RM and NMs &amp; detecting task failures of the job</li></ul><p>containers = (some CPU + some memory) packages in a server</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/478/1*AlPMrwR3hCTub9dco79uDA.png" /></figure><h4>## 3.4: MapReduce Fault-Tolerance</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/437/1*PJYjbrt7FLOoVIP7YGDVqw.png" /></figure><p>The slowest machine slows the entire job down → <strong>speculative execution</strong>: perform backup execution of straggler task</p><p><strong>Locality</strong></p><ul><li>run Map task on a machine that contains a replica of corresponding input data</li><li>on failing that, on the same rack that contains the rack with the data</li><li>on failing that, anywhere</li></ul><h3># 2019/03/23 Week 2 Lesson 1: Gossip</h3><h4>## 1.1: Multicast Problem</h4><p>Spread a piece of information from a node to a group of nodes.</p><p>NOT broadcast, where message is sent to the entire network.</p><p>Requirements (as far as cloud computing is concerned):</p><ul><li>Fault tolerance: nodes may crash, packets may be dropped</li><li>Scalability: 1000’s of nodes</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/439/1*_7H8Id7uKn-r02wnuFsHVw.png" /></figure><p>Problem: Scalability. O(N) where N = size of the network</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/481/1*A5l5uFPaCy2pDDFFizetVw.png" /></figure><p>Time to reach the leaf of the tree: O(logN)</p><p>If a node close to the trunk fails, then branches don’t receive messages.</p><p>Use either ACKs (acknowledgements) or NAKs (negative acknowledgements) to repair.</p><ul><li>SRM (Scalable Reliable Multicast): use NAKs, but adds random delays and uses exponential backoff to avoid NAK storms</li><li>RMTP (Reliable Multicast Transport Protocol): use ACKs, but ACKs only sent to designated receivers, which then re-transmit missing multicasts</li></ul><p>Still O(N) ACK/NAK overhead</p><h4>## 1.2: The Gossip Protocol</h4><p>“Gossip” or “Epidemic” Multicast:</p><p>Periodically (like every 5 secs), a node randomly picks b nodes from the network and sends gossip messages.</p><ul><li>Use UDP because the entire protocol is quite reliable</li><li>Typically b = 2 (or very small number)</li></ul><p>Other nodes do the same after receiving multicast.</p><p>Duplicate happens.</p><p>Nodes that have received a piece of information are called <strong>infected</strong>, others are called <strong>uninfected</strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/447/1*YOJ-K3sw_mzIiTcVTEppLg.png" /></figure><h4>## 1.3: Gossip Analysis</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/647/1*Q5XUgGQrbwXPlH0pJ6e1QQ.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/575/1*lvSo4yUU6CbzRUu0zfQoKQ.png" /></figure><p>There are xy ways to make infected &amp; uninfected pairs, so the rate of infection is βxy.</p><p>dx/dt = -βxy = -βx(n+1-x)</p><p>The solution tells that y goes very quickly to n+1.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/513/1*OmCfBlAGfCsbNIYMaxmsmQ.png" /></figure><p>(algebra for this approximation appears at the end of the lecture)</p><p>In the gossip protocol, the probability that a particular infected node picks a particular uninfected node is β = b/n.</p><p>t = c log(n) is expressing t in terms of every log(n) rounds that have happened so far.</p><p>Even if c and b are both small numbers, 1/(n^(cb-2)) goes to zero very quickly.</p><ul><li>Low latency: within c log(n) rounds,</li><li>Reliability: all but 1/(n^(cb-2)) number of nodes receive the message</li><li>Lightweight: each node has transmitted no more than cb log(n) gossip messages</li></ul><p><strong>Fault-tolerance</strong></p><ul><li>Packet loss: replace b by b * (rate of packet loss)</li><li>Node failure: replace n by n * (failure rate) and b by b * (failure rate)</li></ul><p><strong>Pull gossip</strong></p><p>In all forms of gossip, it takes O(logN) rounds before about N/2 gets the gossip. (think about a spanning tree)</p><p>Pull gossip is faster than push gossip in the second half.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/519/1*cxnbNSC9gJlUqXkCP91L6Q.png" /></figure><p>This is super-exponential: O(log(logN))</p><p><strong>Topology-aware gossip</strong></p><p>Random target: router face O(N) load</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/227/1*K_NgNCquBsDswBOKDla3Dw.png" /></figure><ul><li>Router load = O(1)</li><li>Dissemination time = O(logN)</li></ul><h4>## 1.4: Gossip Implementations</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/448/1*558bhlTnc-uUv7VMCraSWA.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/591/1*Q0UdLLw_XOFpGOll4j0yRA.png" /></figure><h3># 2019/03/23 Week 2 Lesson 2: Membership</h3><h4>## 2.1: What is Group Membership List?</h4><p>Process group based systems</p><ul><li>Clouds/Datacenters</li><li>Replicated servers</li><li>Distributed databases</li></ul><p>Crash-stop/Fail-stop process failures: once a member of the group (called process) fails, it stops executing any instructions.</p><p>→different from other failure models, such as a crash recovery failure model where processes can recover</p><p>Membership list: list of non-faulty processes</p><p>Membership protocol (group membership protocol): protocol to maintain membership list</p><p>A major challenge is that the membership protocol has to communicate over an unreliable communication medium.</p><ul><li>Complete list at all time: strongly consistent, eg. virtual synchrony</li><li>Almost-complete list: weakly consistent, eg. gossip-style, SWIM, etc.</li><li>Partial-random list: eg. SCAMP, T-MAN, Cyclon, etc.</li></ul><p>A membership protocol must have;</p><ul><li>Failure detector: find out that one of the members failed</li><li>Dissemination: inform about joins, leaves, and failures of processes</li></ul><h4>## 2.2: Failure Detectors</h4><p>Failure is <strong>norm rather than the exception</strong> in a large scale data center.</p><ul><li><strong>Completeness</strong>: each failure is detected (by a non-faulty process)</li><li><strong>Accuracy</strong>: there is no mistaken detection</li><li>Speed: time to first detection</li><li>Scale: equal load on each member &amp; network message load</li></ul><p>Completeness &amp; Accuracy cannot be met together 100% in lossy networks.</p><p>Preferably: completeness is guaranteed, and accuracy is probabilistically guaranteed</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/719/1*h9BHXtbhc2OMS6Lov88Y6Q.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/786/1*oqT7NxYrwS3trEc3zKFgcg.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/751/1*IPJnuO3JbMhZAdRO15N1rQ.png" /></figure><h4>## 2.3: Gossip-Style Membership</h4><p>Gossip-style failure detection is a variant of all-to-all heartbeating (more robust).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/783/1*SSgzkppiCMCGK8D9UZj3ug.png" /></figure><p>Each member maintains a table of;</p><ul><li>Address: process ID</li><li>Heartbeat counter: how many heartbeats were received by the process</li><li>Time: local time at which last time the heartbeat was received</li></ul><p>Periodically a process sends out the entire table to a few of its neighbors at random.</p><p>When a node receives the membership list, it updates the local list in such a way that;</p><ul><li>by looking at the table row by row,</li><li>if the heartbeat counter in the received table is greater than that of the local table,</li><li>then update the counter and set the time to the current time in the local table.</li></ul><p>If a particular row is last updated more than a threshold time ago, then mark the process as failure.</p><ul><li>If the heartbeat has not increased for more than T_fail seconds, the member is considered failed</li><li>And after T_cleanup seconds, it will delete the member from the list</li></ul><p>Typically T_cleanup is the same as T_fail.</p><p>Without T_cleanup, one entry might be updated with a new local time after it’s been deleted, if it’s not deleted from the received list.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/576/1*7ug03rfaPqGvb6oFowwcFg.png" /></figure><p>Bandwidth allowed: how many rows can be sent in one gossip.</p><p>If bandwidth allowed per node is only O(1), then only some of the rows are sent, so it takes O(N log(N)) time to propagate all the list.</p><h4>## 2.4: Which is the best failure detector?</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/705/1*ZSH1eU7xy4MCHvxtIujyxA.png" /></figure><p>PM(T): Probability of mistake in time T</p><p>L: Load per member</p><p>N*L: Network Message Load</p><p><strong>Load of all-to-all heartbeating;</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/580/1*UI9uw4RXK9Bdev0N7luXtA.png" /></figure><p><strong>Load of gossip based approach;</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/778/1*dtmGgOzX0OSeFC1fOFxDQA.png" /></figure><p><strong>What’s the optimal load?</strong></p><p>In theory, the worst case load L* (per member) as a function of T, PM(T), N and p_ml is at least;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/162/1*UV7b499JS_fnyWKqmOu8mw.png" /></figure><p>p_ml: Independent Message Loss probability (applied to all messages independently of other messages)</p><p>Notice that L* is independent of N. (scale free)</p><p>→So both all-to-all and gossip-based are sub-optimal.</p><p>Why? Because both approaches do not distinguish failure detection and dissemination.</p><p>Key:</p><ul><li>Separate the two components</li><li>Use a non heartbeat-based Failure Detection Component</li></ul><h4>## 2.5: Another Probabilistic Failure Detector</h4><p>SWIM: Scalable Weakly-consistent Infection-style Membership protocol</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/759/1*zPuQqMzRejmWc3XGvYDD6Q.png" /></figure><ul><li>pi sends a ping to pj</li><li>if pi received a ping back from pj, then do nothing else, otherwise;</li><li>sends a ping to pj indirectly by through K randomly selected processes</li><li>if pi receives at least one acknowledgements from pj by the end of the protocol period, then do nothing</li><li>if pi does not receive direct ack or any indirect ack from pj, then pj is marked as failure</li></ul><p>SWIM: <strong>both first detection time and process load are constant</strong> for fixed false positive rate and message loss rate.</p><p>Heatbeating: <strong>at least one of first detection time and process load increases with O(N)</strong> for fixed false positive rate and message loss rate.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/473/1*fRrHyUBzSUem7VyPpkzprQ.png" /></figure><p><strong>False Positive Rate (Accuracy);</strong></p><ul><li>PM(T) is exponential in -K, also depends on p_ml (probability of message loss) and p_f (probability of failure)</li></ul><p><strong>Load;</strong></p><p>see paper</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/407/1*pVrnIHEF2J36rG7s8rXnjQ.png" /></figure><p><strong>Detection time;</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/458/1*oavU-GQFjRw0yyy1lSY6VA.png" /></figure><p><strong>Completeness;</strong></p><ul><li>Eventually</li><li>can be made worst case O(N) protocol periods by using round-robin pinging (after each traversal permute the round-robin list)</li></ul><h4>## 2.6: Dissemination and suspicion</h4><p>How to disseminate failures detected by SWIM?</p><ul><li>Multicast (hardware/IP): unreliable, multiple simultaneous multicasts</li><li>Point-to-point (TCP/UDP): expensive</li><li><strong>Infection-style dissemination (the “I” of SWIM)</strong>: piggyback on Failure Detector messages (zero extra messages!)</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/751/1*JkB7OELbOEm6Q-4XAibSxA.png" /></figure><p>Piggyback some of the recently detected updates on top of ping, ack and indirect ping messages.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/654/1*5HSiDTMSYBgPJ8eHsYlyIA.png" /></figure><p><strong>Suspicion mechanism</strong></p><ul><li>false detections due to perturbed processes or packet losses (eg. from congestion)</li><li>indirect pinging may not solve the problem (eg. correlated message losses near pinged host)</li></ul><p>Key: <strong>Suspect</strong> a process before <strong>declaring</strong> it as failed in the group.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/775/1*H730hPb99En595P-MTO2mA.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/440/1*6uYL6Gc7jSSzQjFy2v9mvw.png" /></figure><h3># 2019/03/23 Week 2 Lesson 3: Grids</h3><h4>## 3.1: Grid Applications</h4><p>Running highly parallel computation without a supercomputer, with scheduling, across multiple sites.</p><h4>## 3.2: Grid Infrastructure</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/565/1*72eVtNjfjYRIrMXT1aHorw.png" /></figure><p>HTCondor: High throughput computing system</p><ul><li>run on workstations</li><li>when a workstation is free, ask the central server (or Globus) for tasks</li><li>once the workstation is user-interrupted, stop the task</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/540/1*ynbUCeIABbJjm6mlb7R4Ow.png" /></figure><p>Globus toolkit is an open-source software developed by Globus Alliance which involves universities, national US research labs and some companies.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/485/1*Qg0rCksVQYGzHszwFyHC4w.png" /></figure><h3># 2019/03/30 Week 3 P2P Systems</h3><h4>## 1: P2P System Introduction</h4><p>Why study peer to peer systems?</p><p>P2P is the first distributed systems that seriously focused on scalability with respect to number of nodes.</p><h4>## 2: Napster</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/460/1*oZha3GldAEJenZBkJSOEHA.png" /></figure><p>Servers store only the metadata: tuple of &lt;filename, ip_address, portnum&gt;</p><p>Search:</p><ul><li>send keyword to a server</li><li>all servers search their lists (<strong>ternary tree</strong> algorithm; each server has up to 3 children)</li><li>return a list of hosts &lt;ip_address, portnum&gt;</li><li>client pings each host in the list to find transfer rates</li><li>client fetches file from best host</li></ul><p>Joining a P2P system:</p><ul><li>send an http request to well-known url for that P2P service</li><li>message routed to introducer, a well known server that keeps track of some recently joined nodes in p2p system</li><li>introducer initializes new peers’ neighbor table</li></ul><p>Problems</p><ul><li>centralized server overloaded with search queries (SPoF)</li><li>no security</li></ul><h4>## 3: Gnutella</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/462/1*KLi7CYPzX96NRxWIXcR7GA.png" /></figure><p>completely P2P</p><p>every peer has “peer pointers” to some neighbors</p><p>5 main message types</p><ul><li>Query: search</li><li>QueryHits: response to query</li><li>Ping: to probe network for other peers</li><li>Pong: reply to ping, contains address of another peer</li><li>Push: used to initiate file transfer</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/684/1*W4GsW81HAG3Ps76dRd3UIQ.png" /></figure><p>Decrement TTL each time message is passed, so that the message doesn’t keep circulating around forever.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/466/1*5lDhKjq0ALVJAox_n_FygQ.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/500/1*Op5xBO_dBhfKs_3PfnjZNw.png" /></figure><p>How to search?</p><ul><li>Search local files</li><li>Send message to its immediate neighboring peers</li><li>When a neighboring peer receives the query, it sends out the message to all its neighboring peers except for the one that has sent the message</li><li>Each peer sends a message only once, that is, it stores recently sent queries and if it sees it again, the message is not forwarded</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/617/1*SHEEwaiJEWmRsptCxZCFBQ.png" /></figure><p>QueryHit messages are reverse-routed to the searcher.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/536/1*5kgW4Z8k0wvSVn-d8UZvMA.png" /></figure><p>First, requesting peer (bottom left) tries to set up an http connection to the responding peer (yellow). If it fails, it assumes that it’s behind a firewall and routs a Push message through the reverse QueryHit path. The responder then generates an HTTP connection to the requester.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/379/1*73ZdVfl0ywCwzGMWm524sg.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/457/1*kCtokZuoCMeyzgJuz-wZVA.png" /></figure><p>Problems of Gnutella:</p><ul><li>Ping/Pong constituted 50% of traffic: Multiplex ping/pongs</li><li>Repeated searches with same keywords: Cache Query &amp; QueryHits</li><li>Modem-connected hosts do not have enough bandwidth for passing Gnutella traffic: use a central server to act as proxy</li><li>Large number of freeloaders (70% only download, never upload)</li><li>Flooding cause excessive traffic</li></ul><h4>## 4: FastTrack and BitTorrent</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/522/1*UkTX_FSLcvxFMF0WAFr1UQ.png" /></figure><p>FastTrack is hybrid between Gnutella and Napster. It takes advantage of “healthier” participants in the system (<strong>supernodes</strong>).</p><p>Proprietary protocol (Kazaa, KazaaLite, Grokster) but some details available.</p><p>Peers are selected to be supernodes based on their contributions in the past. (reputation scheme; based on the number of uploads, etc.)</p><p>Instead of flooding a Query, one peer can send it to a nearby supernode.</p><p>Incentive to be a supernode: a lot of searches become local searches, so it’s fast.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/530/1*GIS9symc0sbGnc6DWdy_Cw.png" /></figure><p>BitTorrent has special incentive design.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/476/1*2_X8xzlVWcLCorogPpuppA.png" /></figure><h4>## 5: Chord</h4><p>DHT: Distributed Hash Table</p><ul><li>Requirements: Insert, lookup and delete objects with keys</li><li>Performance concerns: load balancing, fault-tolerance, efficiency of lookups and inserts, locality</li></ul><p>Intelligent choice of neighbors to reduce latency and message cost of routing.</p><p>Consistent Hashing:</p><ul><li>SHA-1 (ip_address, port) → 160 bit string</li><li>Truncated to m bits</li><li>Called peer id (number between 0 and 2^m-1)</li><li>Not unique but id conflicts very unlikely</li><li>Can then map peers to one of 2^m logical points on a circle</li></ul><p><strong>Two kinds of peer pointers</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/544/1*UROFkfLH0ADCfh3YBtXmRQ.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/622/1*V8y90n2icdmzpyT5YqdEVw.png" /></figure><p>Finger table: List of nodes accessible (known to exist) by a node.</p><p>Filenames also mapped using same consistent hash function, ie. first peer with id greater than its hash key (mod 2^m).</p><p>With K keys and N peers, each peer stores O(K/N) keys.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/744/1*lB1_AOhvCJQonkDkDhxi9Q.png" /></figure><p>Search algorithm:</p><ul><li>Suppose N80 wants to search for an entry for key “cnn.com/index.html” which hash the hash of K42.</li><li>It wants to find the first node with id greater than 42 (mod m)</li><li>The largest entry in the finger table of N80 below 42 is 16 (see the two slides above), so send a search query to N16.</li><li>N16 doesn’t have K42, so it forwards the search query to the next entry (the largest finger table entry of N16, but still to the left of N80), which is N32 (16+2⁵=32 and 16+2⁶=48, so N32 doesn’t know the existence of N45).</li><li>N32 still doesn’t have K42, so forwards the query to N45 according to the second line of the algorithm (“if none exist, send query to successor(n)”).</li><li>N45 matches and has K42 entry, so it return the response directly to N80</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/553/1*whENGtCHZnQEpjaaHCkPnA.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/449/1*21z8aq8Fq9nZbUrEJhgVqg.png" /></figure><h4>## 6: Failures in Chord</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/522/1*8iIAV84BxC9s6iOlLf_IiQ.png" /></figure><p>What happens when N32 has failed in the above case?</p><p>N16 doesn’t even know the existence of N45, so the query never reaches N45.</p><p>Solution: each node maintain the list of <strong>r successors</strong> instead of just one</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/519/1*7KktYvlcDLmpDE07hSAPVQ.png" /></figure><p>(w.h.p = with high probability)</p><p><strong>What if the peer that’s storing the file failed?</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/549/1*BqJovbQv9GqwBjiz2SXHMQ.png" /></figure><p>Store copies of the file to the successor and the predecessor of the node.</p><p>It’s also good for load balancing.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/511/1*M8YXb_Lu9BaSaDLpAAMpRQ.png" /></figure><p>N40 may need to copy some files/keys (id between 32 and 40) from N45, ie. file transfer occurs between the successor of the newly joined node and the newly joined node.</p><p>A new peer affects O(log(N)) other finger entries in the system, on average, because of the symmetry of the system where each node points to O(log(N)) finger table entries and is pointed by O(log(N)) peers. So the number of messages per peer join = O(log(N)*log(N)).</p><p><strong>Stabilization Protocol:</strong></p><p>Concurrent peer joins, leaves, failures might cause loopiness of pointers and failure of lookups. Chord peers periodically run a stabilization algorithm that checks and updates pointers and keys.</p><p><strong>Churn:</strong></p><p>When nodes are constantly joining, leaving and failing, unnecessary file/key copying may occur. Stabilization algorithm may consume more bandwidth to keep up.</p><p><strong>Virtual Nodes:</strong></p><p>Treat each node as multiple virtual nodes→more load balanced set of segments.</p><h4>## 7: Pastry</h4><p>Pastry is another P2P system which is similar to chord.</p><p>Routing table based prefix matching.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/473/1*ZIjgNghFdsvJ8sonJkw-wg.png" /></figure><p>For each prefix, say 011*, among all potential neighbors with a matching prefix, the neighbor with the shortest round-trip-time is selected.</p><h4>## 8: Kelips</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/524/1*Bcj4ixtn7v18-Ilo_gUA3A.png" /></figure><p>A node selects the closest peer from a foreign affinity group.</p><p>Files are stored in its original nodes (uploaders).</p><p>All peers in an affinity group store file pointers with filename hash (mod k), ie. same information is replicate through every node in an affinity group.</p><h3># 2019/04/06 Week 4 Lesson 1: Key-value stores</h3><h4>## 1.1: Why Key-Value/NOSQL?</h4><p>Today’s workloads</p><ul><li>Data: Large and unstructured</li><li>Lots of random reads and writes</li><li>Sometimes write-heavy</li><li>Foreign keys rarely needed</li><li>Joins infrequent</li></ul><p>Needs</p><ul><li>Speed</li><li>Avoid SPoF</li><li>Low TCO (total cost of operation)</li><li>Fewer system administrators</li><li>Incremental Scalability</li><li>Scale out, not up</li></ul><p>NoSQL = Not only SQL</p><p>KVS</p><ul><li>Necessary API: get(key) and put(key, value)</li><li>Tables: Like RDBMS tables, but columns may be missing, or unstructured</li><li>Not always have joins or foreign keys</li><li>Can have index tables, just like RDBMSs</li></ul><p>Column-oriented storage</p><ul><li>NoSQL systems typically store a column together (or a group of columns), indexed by the key</li><li>Range searches within a column are fast (no need to fetch the entire database)</li></ul><h4>## 1.2: Cassandra</h4><p>Ring-based Distributed Hash Table</p><ul><li>One ring per DC</li><li>No finger table (routing table), but when a coordinator receives a query, forwards to an appropriate replica (“Partitioner”)</li></ul><p>Two replication strategies</p><p><strong>SimpleStrategy</strong> uses the Partitioner, of which there are two kinds</p><ul><li>RandomPartitioner: Chord-like hash partitioning. Values are stored close to the hash key node.</li><li>ByteOrderPartitioner: Assign ranges of keys to servers: easier for range queries. Easier for range queries. Instead of using the hash of the keys, use keys itself (eg. timestamp)</li></ul><p><strong>NetworkTopologyStrategy</strong>: for multi-DC deployments</p><p>Two or three replicas per DC, per DC</p><ul><li>First replica placed according to Partitioner</li><li>Then go clockwise around ring until you hit a different rack (for rack tolerance)</li></ul><p><strong>Snitches</strong>: mechanism to map IPs to racks and DCs. Configured in cassandra.yml</p><ul><li>SimpleSnitch: Unaware of Topology (Rack-unaware), for running on VMs</li><li>RackInferring: Assumes topology of network by octet of server’s IP address. 101.102.103.104 = x.&lt;DC octet&gt;.&lt;rack octet&gt;.&lt;node octet&gt; (first is ignored)</li><li>PropertyFileSnitch: use config file</li><li>EC2Snitch: region = DC, availability zone = rack</li></ul><p>Writes:</p><ul><li>Need to be lock-free for heavy workloads. Preferably no disk access at all for the write in the critical write path.</li><li>Client sends a write request to a coordinator node in Cassandra cluster. Coordinator uses Partitioner to send query to all replica nodes responsible for key.</li><li>When X replicas respond, coordinator returns an acknowledgement to the client. (will talk about the X later)</li><li>Always writable: <strong>Hinted Handoff mechanism</strong> (if one or all replica is down, writes to other replicas AND writes locally until they are up)</li><li>One ring per datacenter. Per-DC coordinator elected (via Zookeeper)to coordinate with other DCs.</li></ul><p>When a replica receives a write request:</p><ol><li>Saves commit log for failure recovery</li><li>Change <strong>memtables</strong> (in-memory KVS)</li><li>Flush to disk at later time (when memtable is full or old) as <strong>SSTable</strong> (Sorted String Table) for the key/value and index/position. <br>Bloom filter is used.<br>When a memtable is flushed, a new SSTable is created. The same key may be written in older SSTables. Those SSTables are merged (compacted) periodically.</li></ol><p>Deletes:</p><ul><li>Add a tombstone to the log and eventually delete at compaction</li></ul><p>Reads:</p><ul><li>Coordinator sends read requests to X replicas. (will talk about the X later)</li><li>When X replicas respond, coordinator returns the latest-timestamped value from among those X.</li><li>Coordinator also fetches value from other replicas, then initiate a <strong>read repair</strong> if any two values are different.</li><li>A row may be split across multiple SSTables. So reads are slower than writes (but still fast)</li></ul><p>Membership:</p><ul><li>Any server in cluster cloud be the coordinator, so every server maintains the list of all servers.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/671/1*WqZWbDF53fD0Ndohaax2QQ.png" /></figure><p>Suspicion Mechanism:</p><ul><li>Set timeout based on underlying network and failure behavior, to improve accuracy.</li><li><strong>Accrual detector</strong>: Failure Detector outputs a value (PHI; Φ) representing suspicion.</li><li>Apps set an appropriate threshold.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/485/1*1vxnk6FOWjQD36pRIsno5g.png" /></figure><p>If the inter-arrival time for gossip messages from a particular server have been long in the past, then it waits slightly longer for the next heartbeat before marking the server as having failed.</p><p>CDF: Cumulative Distribution</p><p>Performance comparison with MySQL (50 GB data):</p><ul><li>MySQL: Writes 300 ms / Reads 350 ms avg</li><li>Cassandra: Writes 0.12 ms / Reads 15 ms avg</li></ul><h4>## 1.3: The Mystery of X — The Cap Theorem</h4><p>CAP Theorem: In a distributed system, you can satisfy at most 2 out of the 3 guarantees:</p><ol><li><strong>Consistency</strong>: all nodes see same data at any time, or reads return latest written value by any client</li><li><strong>Availability</strong>: the system allows operations all the time, and operations return quickly</li><li><strong>Partition-tolerance</strong>: the system continues to work in spite of network partitions (can happen across DCs when the Internet gets disconnected, or within a DC on a rack switch outage)</li></ol><p>In today’s cloud computing system, P is essential. So you have to choose between C and A.</p><ul><li>Cassandra: Availability and Eventual (weak) consistency</li><li>Traditional RDBMSs: Strong consistency over availability under a partition</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/622/1*lvui55QOrSwfB67ZvRRzww.png" /></figure><p>Eventual Consistency</p><ul><li>If all writes stop, then all replicas converge</li><li>May return stale value</li><li>Keeps converging (catching up) as long as there are writes</li></ul><p>RDBMS: <strong>ACID</strong> (<strong>A</strong>tomicity, <strong>C</strong>onsistency, <strong>I</strong>solation and <strong>D</strong>urability)</p><p>KVS like Cassandra: <strong>BASE</strong> (<strong>B</strong>asically <strong>A</strong>vailable <strong>S</strong>oft-state <strong>E</strong>ventual Consistency)</p><p><strong>Mystery of X</strong> (in Cassandra): Client may choose <strong>consistency level</strong> for each operation (read/write)</p><ul><li><strong>ANY</strong>: any server (may not be replica), fastest</li><li><strong>ALL</strong>: all replicas, ensures strong consistency but slowest</li><li><strong>ONE</strong>: at least one replica, faster than ALL but cannot tolerate a failure</li><li><strong>QUORUM</strong>: quorum across all replicas in all DCs</li><li><strong>LOCAL_QUORUM</strong>: quorum in coordinator’s DC</li><li><strong>EACH_QUORUM</strong>: quorum in every DC</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/578/1*lDlCiaIduUfeEvtgiHrg0A.png" /></figure><p>Reads in Quorum:</p><ul><li>Client specifies <strong>read consistency level</strong> <strong>R</strong> (≤ N = total number of replicas of that key)</li><li>Coordinator waits for R replicas to respond before sending results to client</li><li>In background, coordinator checks for consistency of remaining (N-R) replicas and initiates read repair if needed</li></ul><p>Writes in Quorum:</p><ul><li>Client specifies <strong>write consistency level W</strong> (≤ N)</li><li>Coordinator writes new value to W replicas and return.<br>Two flavors: 1. Wait until quorum is reached, 2. Just write and return (asynchronous)</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/494/1*Fc7DgNhZ6GuMs4wBEd8G7w.png" /></figure><h4>## 1.4: The Consistency Spectrum</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/734/1*v9y9VEJ4j6Av-meT8wcFGA.png" /></figure><p>Eventual consistency started from Amazon’s Dynamo, then LinkedIn’s Voldemort and Riak.</p><p>In recent years, requirements shifted towards more to strong consistency.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/674/1*ZZBkDf-Go8I43nRYL3wzwQ.png" /></figure><p>Commutative operation: such as +1</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/534/1*R3I_y3YgzQlcAX5FHO_zxQ.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/667/1*CdfzOufW__ynHWeBv513lQ.png" /></figure><p>Two major strong consistency models:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/531/1*B0M9JjQ5cqURz0gM0KnHXw.png" /></figure><h4>1.5: HBase</h4><p>Based on Google’s BigTable paper.</p><p>API: Get/Put (row), Scan (row range, filter), MultiPut</p><p>Prefers consistency over availability</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/657/1*xyoZrcDWIdVctIjXqR2kuA.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/564/1*lIZJTbPfg9Skk1icZGEqSg.png" /></figure><p>HBase maintains strong consistency by HLog</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/614/1*j9bguFthdunuAMyupOK5VA.png" /></figure><p>Log replay:</p><ul><li>Add edits to the MemStore from stale logs</li><li>After recovery from failure, or upon bootup</li><li>Use timestamp to find out where the database is w.r.t the logs)</li></ul><p>Replication:</p><ul><li>If an HBase is operated on multiple DCs, one is “Master” and others are “Slaves”</li><li>Master cluster synchronously sends HLogs over to slave clusters</li><li>Coordination among clusters in via Zookeeper</li><li>Zookeeper can be used like a file system to store control information</li></ul><h3># 2019/04/07 Week 4 Lesson 2: Time and Ordering</h3><h4>## 2.1: Introduction and Basics</h4><p>Synchronizing clocks is challenging because servers follow an asynchronous system model. (message delays, processing delays)</p><p>Definitions:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/598/1*49gE0yqHfCRfvyPizL1x6g.png" /></figure><ul><li>Clock <strong>Skew</strong>: Relative difference in clock <strong>values</strong> of two processes</li><li>Clock <strong>Drift</strong>: Relative difference in clock <strong>frequencies (rates)</strong> of two processes</li></ul><p>How often to synchronize?</p><ul><li>(Absolute) Maximum Drift Rate (MDR) of a clock is drift relative to UTC</li><li>max drift rate between two clocks with similar MDR is 2 * MDR</li><li>M: maximum acceptable skew</li><li>synchronize every M / (2 * MDR) time units (since time = distance / speed)</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/778/1*6k64ombp4kh96Czr3XU-bg.png" /></figure><h4>## 2.2: Cristian’s Algorithm</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/750/1*uCiePXTNeTaVkA9uBsQe6w.png" /></figure><p>Suppose we know;</p><ul><li>Minimum P→S latency: min1</li><li>Minimum S→P latency: min2</li></ul><p>The actual time at P when it receives response is between <strong>[t+min2, t+RTT-min1]</strong>.</p><ul><li>Lower bound (t+min2): when the message from S to P took exactly min2 time</li><li>Upper bound (t+RTT-min1): when the message from P to S took exactly min1 time</li></ul><p>P sets its time to half way through this interval: t + (RTT+min2-min1)/2</p><p>Then the error is bounded! At most (RTT+min2-min1)/2</p><h4>## 2.3: NTP</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/662/1*DytiY5MwcgSxpgNMXu_Ptg.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/905/1*22T4zgTWGrmtqZZyc29ujw.png" /></figure><p>Set offset o = (tr1-tr2+ts2-ts1)/2</p><p>What’s the error?</p><p>Suppose real offset is o_real</p><ul><li>Child is ahead of parent by o_real</li><li>Parent is ahead of child by -o_real</li></ul><p>One-way latency</p><ul><li>L1: latency of Message 1</li><li>L2: latency of Message 2</li></ul><p>Then</p><ul><li>tr1 = ts1 + L1 + o_real</li><li>tr2 = tr2 + L2 - o_real</li></ul><p>Subtract second equation from the first</p><p>o_real = (tr1-tr2+ts2-ts1)/2+(L2-L1)/2 = o+(L2-L1)/2</p><p>|o_real-o| &lt; |(L2-L1)/2)| &lt; (L2+L1)/2</p><p>Thus, the error is bounded by the round-trip-time (L2+L1).</p><h4>## 2.4: Lamport Timestamps</h4><p>Almost all cloud computing systems use some form of logical (Lamport) ordering of events.</p><p>Causality:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/645/1*tmc5h5ZqRLo1tyw0xfx75g.png" /></figure><p>Goal: Assign logical timestamp to each event</p><ul><li>Each process uses a local counter (clock) which is an integer (initially zero)</li><li>A process increments its counter when an event (a <strong>send</strong> or an <strong>instruction</strong>) happens at it. The counter value is the timestamp of the event.</li><li>A send event carries its timestamp</li><li>Timestamp of a receive event is <strong>max(local counter, timestamp of send)+1</strong>, which then updates the clock of receiver</li></ul><p><strong>Concurrent</strong> events: set of events that causality cannot be determined</p><p>Lamport timestamps are not guaranteed to be ordered or unequal for concurrent events.</p><h4>## 3.5: Vector Clocks</h4><p>Vector clocks (vector timestamps): each process maintains N clocks, where N is the number of processes it communicates, and call the whole vector a timestamp.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/558/1*OVjl4ZL4RXNC2WDiwXDXyA.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/783/1*bmE_fMct14oG4D8eWDcTJA.png" /></figure><p>Each message has sender’s timestamp (vector), and the receiver updates each of the clocks as such.</p><p>Causality: two events are causally related if and only if every element in a timestamp is strictly less than or equal to that of another event</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/470/1*zN_nvq28I5v_JpMtxzP9jg.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/543/1*Gt5Cpcj6lPtc7IukltvqCg.png" /></figure><h3># 2019/04/13</h3><h3># Week 5 Lesson 1: Snapshots</h3><h4>## 1.1: What is Global Snapshot?</h4><p>Use case of Global Snapshot: Checkpointing, Garbage collection, Deadlock detection</p><p>Instantaneous state of each process, Instantaneous state of communication channel</p><p>Time synchronization always has error, but it’s fine as long as causality is kept</p><h4>## 1.2: Global Snapshot Algorithm</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/632/1*freu6UTcUgo_hbasEneHTw.png" /></figure><p>Problem: Record a global snapshot (state for each process and for each channel)</p><ul><li>N processes in the system</li><li>Two uni-directional channels between each pair</li><li>Communication channels are FIFO-ordered</li><li>No failure</li><li>All messages arrive intact, and are not duplicated</li></ul><p>Requirements:</p><ul><li>Snapshot should not interfere with normal application actions</li><li>Each process is able to record its own state</li><li>Global state is collected in a distributed manner</li><li>Any process may initiate the snapshot</li></ul><p>Chandy-Lamport Global Snapshot Algorithm:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/748/1*HnuRvl-Le7-axTGjgCc10Q.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/774/1*Jz3jFiUqpXSwdCL6BYdzGQ.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/535/1*APyCSnm1z9hPrSbD1Xh27A.png" /></figure><h4>## 1.3: Consistent Cuts</h4><p>Cut = time frontier at each process and at each channel</p><ul><li>In the cut: events happening before the cut</li><li>Out of the cut: events happening after the cut</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/765/1*O4JmaFa-ORF00GCGzovNvA.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/854/1*dnwrRX92K9kpSlXPsLKR1Q.png" /></figure><p>Chandy-Lamport snapshot ensures consistent cut.</p><h4>## 1.4: Safety and Liveness</h4><p>Liveness = guarantee that something good will happen</p><p>Safety = guarantee that something bad will never happen</p><h3># Week 5 Lesson 2: Multicast</h3><h4>## 2.1: Multicast Ordering</h4><ul><li>Multicast: message sent to a group of processes</li><li>Broadcast: message sent to all processes (anywhere)</li><li>Unicast: message sent from one sender to one receiver</li></ul><p><strong>FIFO Ordering</strong>: Multicast from each sender are received in the order they are sent.</p><p><strong>Causal Ordering</strong>: All causally related multicasts must be received in the causality-obeying order. Causal ordering implies FIFO ordering.</p><p>Think of a distributed SNS. If X sends a message and Y sends a response to it. In this case <strong>causal ordering</strong> must be satisfied for everyone to correctly see the causality (FIFO ordering is not enough).</p><p><strong>Total Ordering (Atomic Broadcast)</strong>: All receivers receive all multicasts in the same order. May need to delay delivery of some messages, even a sender’s own message.</p><h4>## 2.2: Implementing Multicast Ordering 1</h4><p>FIFO ordering multicast algorithm:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/497/1*YpH3DzmXGcAjug2GytDgtw.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/511/1*y_VszeDRLCviRjCAgxWzrw.png" /></figure><ul><li>In a system with 3 processes, P1, P2, and P3.</li><li>Initially P1’s sequence vector = [0,0,0]</li><li>When P1 sends a message, it becomes [1,0,0] and the message carries the sequence number 1.</li><li>When P2 receives it, P2’s sequence vector from becomes [0,0,0] to [1,0,0].</li><li>If P2 receives the second multicast of P1 before the first, then the second message is buffered until the first message is received. Receiver’s sequence numbers are always incremented one by one. [0,0,0]→[1,0,0]→[2,0,0]</li></ul><p>Total ordering algorithm: <strong>Sequencer-based Approach</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/656/1*0dQlJlwtdCVECLQv-a6Tlg.png" /></figure><h4>## 2.3: Implementing Multicast Ordering 2</h4><p>Causal ordering multicast algorithm:</p><p>Same data structure as FIFO ordering.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/540/1*eVY1kLa0LHEsLMCQAFEcXg.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/863/1*vA4g_5Kgpqy-E2Mc3W6x0A.png" /></figure><h4>## 2.4: Reliable Multicast</h4><p>What happens to multicast when processes fail?</p><p>Reliable Multicast: All correct (non-faulty) processes needs to receive the same set of multicasts as all other correct processes.</p><p>Reliable multicast is orthogonal to ordering.</p><p>Sending one by one does not satisfy reliability, because the sender might fail during the loop.</p><p>How to fix?</p><p>Receivers also sends the sender’s message to all processes in the group.</p><p>Not the most efficient multicast protocol, but reliable.</p><h4>## 2.5: Virtual Synchrony</h4><p>Attempts to preserve multicast ordering and reliability in spite of failures.</p><p>Combines a membership protocol with a multicast protocol.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/840/1*mQBTzBwwPEZTEeH0JHQY9Q.png" /></figure><p>Virtual synchrony (VSync) multicast ensures that:</p><ol><li>The set of multicasts delivered in a given view is the same set at all correct processes that were in the view. <strong>What happens in a view stays in that view.</strong></li><li>The sender of the multicast message also belongs to that view.</li><li>If a process Pi does not deliver a multicast M in view V while other processes in the view V delivered M in V, then Pi will be forcibly removed from the next view delivered after V at the other processes.</li></ol><h3># Week 5 Lesson 3: Paxos</h3><h4>## 3.1: The Consensus Problem</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/532/1*lpvpl_nNhb1N4p3Dgt5q6w.png" /></figure><p>Reliable Multicast, Membership/Failure Detection, Leader Election and Mutual Exclusion all related to the <strong>Consensus</strong> problem.</p><p>The formal problem statement:</p><ul><li>N processes</li></ul><p>Each process p has</p><ul><li>input variable xp: initial either 0 or 1</li><li>output variable yp: initially b (can be changed only once)</li></ul><p>Consensus problem: design a protocol so that at the end either</p><ol><li>All processes set their output variables to 0, or</li><li>All processes set their output variables to 1</li></ol><p>There might be other constraints</p><ul><li>Validity = if everyone proposes same value, then that’s what’s decided</li><li>Integrity = decided value must have been proposed by some process</li><li>Non-triviality = there is at least one initial system state that leads to each of all-0’s or all-1’s outcomes</li></ul><p>Many problems in distributed systems are equivalent to consensus!</p><p>So consensus is a very important problem, and solving it would be really useful.</p><p><strong>Synchronous &amp; Asynchronous distributed system models</strong></p><p>Synchronous:</p><ul><li>Each message is received within bounded time</li><li>Drift of each process’ local clock has a known bound</li><li>Each step in a process takes lb &lt; time &lt; ub (each process has a min and max speeds at which it executes instructions)</li></ul><p>Asynchronous:</p><ul><li>No bounds on process execution</li><li>The drift rate of a clock is arbitrary</li><li>No bounds on message transmission delays</li></ul><p>In the synchronous system model, consensus is solvable. On the other hand, in the asynchronous system model, consensus is impossible to solve. (FLP proof)</p><p>Subsequently, safe or probabilistic solutions have become quite popular.</p><h4>## 3.2: Consensus in Synchronous systems</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/564/1*ql1_Zb0GrXzEgrcq_2JbkQ.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/849/1*CFQz7O_SeXWRXm_4LLZp0A.png" /></figure><ul><li>initially pi’s value set is empty, then pi adds its own contribution at r=1</li><li>at each round, pi multicasts new values since the previous round</li><li>and add each received values to its value set</li><li>at the end, the decision (output) variable is the minimum value</li></ul><h4>## 3.3: Paxos, Simply</h4><p>Consensus is impossible to solve in asynchronous system (FLP proof), because it is impossible to distinguish a failed process from one that is just very very (very) slow.</p><p>Paxos algorithm is:</p><ul><li>Most popular “consensus-solving” algorithm</li><li>Does not solve consensus problem</li><li>But provides <strong>safety</strong> and <strong>eventual liveness</strong></li><li><strong>Safety</strong>: Consensus is not violated</li><li><strong>Eventual Liveness</strong>: If things go well sometimes in the future (messages, failures, etc.), there is a good chance consensus will be reached. But not guaranteed.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/849/1*8WG4lunL_c8Xwho0JfRuow.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/857/1*WN5pzQJaPH0zXPKB-1Aa5A.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/872/1*Hjw0fJIsCiosJq42SVtI2w.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/864/1*kmoZiL9lynTMwOG4dUUH8g.png" /></figure><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=538df331ff41" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[「過去20年のトレンドを目を細めて見てると次の10年がなんとなくわかる」というテーマで講演を依頼しています]]></title>
            <link>https://medium.com/@taka.atsushi/%E9%81%8E%E5%8E%BB20%E5%B9%B4%E3%81%AE%E3%83%88%E3%83%AC%E3%83%B3%E3%83%89%E3%82%92%E7%9B%AE%E3%82%92%E7%B4%B0%E3%82%81%E3%81%A6%E8%A6%8B%E3%81%A6%E3%82%8B%E3%81%A8%E6%AC%A1%E3%81%AE10%E5%B9%B4%E3%81%8C%E3%81%AA%E3%82%93%E3%81%A8%E3%81%AA%E3%81%8F%E3%82%8F%E3%81%8B%E3%82%8B-%E3%81%A8%E3%81%84%E3%81%86%E3%83%86%E3%83%BC%E3%83%9E%E3%81%A7%E8%AC%9B%E6%BC%94%E3%82%92%E4%BE%9D%E9%A0%BC%E3%81%97%E3%81%A6%E3%81%84%E3%81%BE%E3%81%99-a8cc5d2e354e?source=rss-b64b37102e90------2</link>
            <guid isPermaLink="false">https://medium.com/p/a8cc5d2e354e</guid>
            <dc:creator><![CDATA[Atsushi Takayama]]></dc:creator>
            <pubDate>Sat, 02 Mar 2019 16:18:37 GMT</pubDate>
            <atom:updated>2019-03-07T07:05:59.104Z</atom:updated>
            <content:encoded><![CDATA[<p>下のようなお話をピクシブ株式会社で講演して、メンバーとカジュアルにディスカッションしていただける方を探しています。</p><ul><li><a href="https://www.sbbit.jp/article/cont1/34390">総務省の未来予測、2030年以降の情報通信技術はどうなっているのか</a></li><li><a href="https://diamond.jp/articles/-/12025">岡田斗司夫×堀江貴文が語りつくす！（第1回）世界は&quot;お金&quot;から&quot;評価&quot;の時代へ</a></li></ul><h3>依頼内容</h3><p>「過去20年のトレンドを<strong>目を細めて</strong>見てると次の10年が<strong>なんとなく</strong>わかる」というテーマで、講演者さんの視点からお話をしていただきます。</p><p>例えば「情報通信技術」とか「評価経済社会」というふうにある程度対象を絞ってもらうことを考えています。</p><p>過去10年〜20年ぐらいのトレンドをかいつまんで紹介していただき、さらに今後の10年で起こりそうなことを話してください。</p><p>「現在」の話にフォーカスしすぎることなく、過去と未来を俯瞰してください。</p><p>発表内容は他の場所で自由に使いまわしていただいて構いません。</p><p>参加者は（基本的に）弊社メンバーのみで、10〜30人程度を想定しています。</p><h3>目的</h3><p>目的は、弊社メンバーの一人一人が自分の頭でこのテーマについて考えるようになることです。</p><p>（ですので、「予想の正しさ」はあまり重要視していません）</p><p>さらには、日本全体でたくさんの人が10年後の世界を予想するようになれば、もっと良い社会になると思っています。</p><h3>時間と報酬</h3><p>平日（できれば金曜）の19時ぐらいから質疑応答多めで60分ぐらい+懇親会と考えています。</p><p>報酬は5万円ほどで考えていますが、相談可能です。</p><h3>お断り</h3><p>弊社メンバーからの紹介を優先させていただきます。</p><p>ご興味のある方はTwitterで<a href="https://twitter.com/edvakf">@edvakf</a>にDMください。</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*C2BwIty-UNJVzreGb3ljgA.jpeg" /></figure><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=a8cc5d2e354e" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[「速さが価値の仕事」と「正確さが価値の仕事」]]></title>
            <link>https://medium.com/@taka.atsushi/%E9%80%9F%E3%81%95%E3%81%8C%E4%BE%A1%E5%80%A4%E3%81%AE%E4%BB%95%E4%BA%8B-%E3%81%A8-%E6%AD%A3%E7%A2%BA%E3%81%95%E3%81%8C%E4%BE%A1%E5%80%A4%E3%81%AE%E4%BB%95%E4%BA%8B-81234510feac?source=rss-b64b37102e90------2</link>
            <guid isPermaLink="false">https://medium.com/p/81234510feac</guid>
            <dc:creator><![CDATA[Atsushi Takayama]]></dc:creator>
            <pubDate>Wed, 27 Feb 2019 16:14:37 GMT</pubDate>
            <atom:updated>2019-02-27T17:03:02.482Z</atom:updated>
            <content:encoded><![CDATA[<p>「仕事はスピードがすべて」みたいな考え方を見て、思うところがあったので書いてみました。</p><h4>結論から</h4><ul><li>「速さ」のためには「正確さ」も必要</li><li>速さだけが重要な仕事は機械化されていくはず</li><li>「正確さ」を磨いていこう</li></ul><h3>スタートアップの成功の要因の8割は市場選び</h3><p>という考え方を聞いたことがあるでしょうか？</p><p>どれだけ速く物を作っても、市場選びの時点で間違ってたら、残念ながら成功には結びつかないのですよね。</p><p>逆に市場選びさえ良ければ、他のことはまあなんとかなるみたいです。</p><h3>「手の速い優秀なエンジニア」vs「残念な設計」</h3><p>Supership取締役CTOの山崎さん曰く、</p><blockquote><em>手の速い優秀なエンジニアをせっかく集めても、設計が残念だと設計が残念なシステムが高速に実装されるだけなのよね。当たり前ですが。<br></em><a href="https://twitter.com/yamaz/status/1090294549744738304"><em>https://twitter.com/yamaz/status/1090294549744738304</em></a></blockquote><p>設計の正確さってとても大事、というお話です。</p><h3>「速さ」を支える「正確さ」</h3><p>スピードを上げられるための設計というものがあります。</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*2c8NYHPYeLnLMLMS9_PUag.jpeg" /></figure><p>図の左側の「正確さが価値」の部分は「スタートアップの成功の要因の8割は市場選び」みたいなやつです。</p><p>図の下側の「上手く設計しないと並列化できない」の部分についても、正確さが価値な部分です。</p><ul><li><strong>仮説検証をどう並列化するか？</strong>（ユーザーインタビューする人、データマイニングする人、ABテストを回す人、みたいな）</li><li><strong>並列化できるシステム境界をどう作るか？</strong>（適切にシステム分解されていれば、それぞれのシステムで考えることが減ってスピードが出せる）</li><li><strong>並列化できる仕事とできない仕事をどう分解するか？</strong>（例えばABテストの仕組みを作るのは並列化しにくいが、その上で動くABテストの一つ一つは並列化しやすい）</li></ul><p>などなど。「設計」（プログラミングに限らず業務設計や組織設計やビジネス設計も）が正確であれば、結果的に速さに繋がることっていっぱいあるのですよね。</p><h3>「速さ」←→「正確さ」という軸</h3><p>とにかく高速にPDCAすることに価値のある領域と、より正確さが求められる領域というのがあります。</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*4i7cNMiBB8vDBXHmpGjqQQ.jpeg" /></figure><p>この3つの軸以外にも</p><ul><li>UIデザイン→UXデザイン</li><li>アプリケーション開発→プロダクトマネジメント</li></ul><p>みたいなのもあると思います。</p><p>「とにかく高速にPDCA」した結果の課題解決をよりスピーディーにするには、UX方面やプロダクトマネジメント方面の正確さ（仮説の正しさ）がやっぱり重要になってくるのです。</p><h3>正確さに確信を持っていればスピードが出せる</h3><p>より長期的かつ本質的な判断基準の正確さに磨きをかけていけば、日々の一つ一つの判断は一瞬で下せるようになっていきます。</p><p>「スタートアップの成功の要因の8割は市場選び」の例で言えば、適切な市場、ビジネスモデル、パートナー、UX、等の自信を磨いていくと「こういう相手とは組まない」とか「こういうUXは提供しない」などの判断がスピーディーになります。</p><p>「正確さ」は「速さ」に繋がっています。</p><h3>「速さが価値」の仕事は、どんどん機械化されていく</h3><p>仕事とは、突き詰めていくと「判断基準の正確さを磨いていくこと」が本質的なことで、それを元に一つ一つの判断をしていることは作業みたいなものと言えるはずです。</p><p>プログラミングでいえば、頭の中で設計を組み立てているときが本質的な仕事で、ググったり実装に落とし込むところは既に作業と言えるはずですし、実際にそのような作業をどんどん減らす方向にプログラミング言語やフレームワークは進化してきました。</p><p>サービス開発でいえば、「細かい機能追加をたくさんやるよりも、機能を絞ってレコメンドを頑張ったほうが効率が良い」という時代です。</p><p>機械学習の大御所であるAndrew Ng先生曰く、「普通の人が1秒以内でやっていることはほとんど自動化可能で、多くの仕事は1秒以内のタスクの連続で構成されている」だそうです。</p><p><a href="https://youtu.be/V3gVGvoCg58?t=298">https://youtu.be/V3gVGvoCg58?t=298</a></p><p>そんな現代においては、人間が注力すべきなのはむしろ「正確さにしか価値がないこと」であるといえるかもしれません。</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=81234510feac" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Coursera: Cluster Analysis in Data Mining]]></title>
            <link>https://medium.com/@taka.atsushi/coursera-cluster-analysis-in-data-mining-7d1bf4784711?source=rss-b64b37102e90------2</link>
            <guid isPermaLink="false">https://medium.com/p/7d1bf4784711</guid>
            <category><![CDATA[data-science]]></category>
            <dc:creator><![CDATA[Atsushi Takayama]]></dc:creator>
            <pubDate>Sun, 17 Feb 2019 14:56:00 GMT</pubDate>
            <atom:updated>2019-03-10T17:01:52.952Z</atom:updated>
            <content:encoded><![CDATA[<p><a href="https://www.coursera.org/learn/cluster-analysis">Cluster Analysis in Data Mining | Coursera</a></p><h3># 2019/02/17</h3><h4>## 1.1: What is Cluster Analysis</h4><p>Cluster: a set of data objects which are similar (or related) to one another within the same group, and dissimilar (or unrelated) to the objects in other groups.</p><p>Cluster analysis, clustering, data segmentation: partition points into a set of groups which are as similar as possible</p><p>Cluster analysis is unsupervised learning</p><h4>## 1.2: Applications of Cluster Analysis</h4><ul><li>A key intermediate step for other data mining tasks (summarize data for classification, pattern discovery, etc., or detect outliers)</li><li>Data summarization, compression and reduction (vector quantization)</li><li>Collaborative filtering, recommendation systems, or customer segmentation</li><li>Dynamic trend detection (clustering stream data)</li><li>Multimedia data analysis, biological data analysis and social network analysis</li></ul><h4>## 1.3: Requirements and Challenges</h4><ul><li>Partitioning criteria (single level vs hierarchical)</li><li>Separation of clusters (exclusive vs non-exclusive (one document may belong to more than one class))</li><li>Similarity measure (distance-based vs connectivity-based)</li><li>Clustering space (full space vs subspaces)</li><li>Quality</li><li>Scalability</li><li>Constraint-based clustering</li><li>Interpretability and usability</li></ul><h4>## 1.4: A Multi-Dimensional Categorization</h4><ul><li>Technique-Centered (distance-based, density-based, grid-based, probabilistic model, leveraging dimensionality reduction methods)</li><li>Data Type-Centered (numerical data, categorical data, text data, multimedia data, time-series data, sequences, stream data, network data, uncertain data)</li><li>Additional Insight-Centered (visual insights, semi-supervised, ensemble-based, validation-based)</li></ul><h4>## 1.5: An Overview of Typical Clustering Methodologies</h4><p>Distance-based methods</p><ul><li>Partitioning algorithms: K-Means, K-Medians, K-Medoids</li><li>Hierarchical algorithms: Agglomerative (bottom-up) vs divisive methods (top-down)</li></ul><p>Density-based and grid-based methods</p><ul><li>Density-based:</li><li>Grid-based:</li></ul><p>Probabilistic and generative models</p><ul><li>Assume a specific form of the generative model</li><li>Model parameters are estimated with the Expectation-Maximization (EM) algorithm</li><li>Then estimate the generative probability of the underlying data points</li></ul><p>High-dimensional clustering</p><ul><li>Subspace clustering: bottom-up, top-down, correlation-based methods vs δ-cluster methods</li><li>Dimensionality reduction (cluster columns; or cluster columns and rows together (co-clustering))</li><li>Probabilistic latent semantic indexing (PLSI) then LDA<br>Topic modeling of text data; a cluster (topic) is associated with a set of words (dimensions) and a set of documents (rows) simultaneously</li><li>Non-negative matrix factorization (NMF)</li><li>Spectral clustering</li></ul><h4>## 1.6: An Overview of Clustering Different Types of Data</h4><ul><li>Numerical data</li><li>Categorical data</li><li>Text data</li><li>Multimedia data</li><li>Time-series data</li><li>Sequence data</li><li>Stream data</li><li>Graphs and homogeneous networks</li><li>Heterogeneous networks</li><li>Uncertain data</li><li>Big data</li></ul><h4>## 1.7: An Overview of User Insights and Clustering</h4><ul><li>Visual insights</li><li>Semi-supervised insights: passing user’s insights or intention to system</li><li>Multi-view and ensemble-based insights: multiple clustering results can be ensembled to provide a more robust solution</li><li>Validation-based insights: evaluation of the quality of clusters generated</li></ul><h4>## 2.1: Basic Concepts: Measuring Similarity between Objects</h4><p>Good clustering: <strong>high intra-class similarity</strong> &amp; <strong>low inter-class similarity</strong></p><p>Many ways to define similarity or quality of clustering.</p><h4>## 2.2: Distance on Numeric Data Minkowski Distance</h4><p>Data matrix &amp; dissimilarity (distance) matrix</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/228/1*faWGbBTo-lNT-2jXAE1OiA.png" /></figure><p>Distance functions are usually different for real, boolean, categorical, ordinal, ratio, and vector variables.</p><p>Weights can be associated with different variables based on applications and data semantics.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/732/1*PrygQx2P1mtW0iOPiOvuiw.png" /></figure><p>Special cases:</p><ul><li>Manhattan distance: p=1 (L_1 norm) <br>eg. Hamming distance: number of different bits between two binary vectors</li><li>Eucledean distance: p=2 (L_2 norm)</li><li>“Supremum” distance: p→∞ (L_max norm, L_∞ norm)<br>max distance between any component (attribute) of the vectors</li></ul><h4>## 2.3: Proximity Measure for Symmetric vs Asymmetric Binary Variables</h4><p>Two binary data i and j</p><ul><li>q: number of times where i and j are both 1</li><li>t: number of times where i and j are both 0</li><li>s, r: number of times where one of i and j is 1, and the other is 0</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/744/1*DssZM4Jobtoihb-SyrYBQQ.png" /></figure><h4>## 2.4: Distance between Categorical Attributes Ordinal Attributes and Mixed Types</h4><p>Proximity measure for categorical attributes</p><p><strong>Method 1</strong>: Simple matching: d(i, j) = (p-m) / p</p><p>m: # of matches, p: total # of variables</p><p><strong>Method 2</strong>: Use a large number of binary attributes (treat each nominal state as a binary attribute)</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/703/1*1Nk9qCdLaDP5CqZ1-gUyiQ.png" /></figure><h4>## 2.5: Proximity Measure between Two Vectors Cosine Similarity</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/706/1*0kse_ZeuhqMqk8z9pThHPg.png" /></figure><h4>## 2.6: Correlation Measures between Two variables Covariance and Correlation Coefficient</h4><p>Mean, standard deviation, variance, sample variance, covariance, sample covariance and correlation.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/735/1*TgXK6TbPIXHfDV_OR_vt2A.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/730/1*BjrAwoEZnRrUBcnbSsNh3w.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/720/1*rgPByJAEjcB7WzG-jGfq9Q.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/742/1*mMgdBLNOfH4dFi_Kjzah1w.png" /></figure><h3># 2019/02/24</h3><h4>## 3.1: Partitioning-Based Clustering Methods</h4><p>Partitioning method: Discovering the groupings in the data by optimizing a specific objective function and iteratively improving the quality of partitions</p><p>K-partitioning method: partition n objects into K clusters by so that an objective function is optimized</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/459/1*p1s3cqbRrnEfjru6Fbjijg.png" /></figure><p>c_k is the centroid or medoid of cluster k</p><p>Heuristic methods: K-means, K-medians, K-medoids, etc.</p><h4>## 3.2: K-Means Clustering Method</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/720/1*2mfKZ_H0F9K4jgKDPm1SUw.png" /></figure><p>Efficiency: O(tKn) where n: # of objects, K: # of cluster, and t: # of iterations</p><p>Often falls in a local minimum → initialization is important</p><p>Need to specify K: there are ways to determine the “best” K, but in practice, a range of K is tested</p><p>Sensitive to noisy data and outliers: validation using K-medians, K-medoids, etc.</p><p>Applying K-means for categorical data? → K-modes</p><p>Non-convex shaped clusters: density-based clustering, kernel K-means, etc.</p><h4>## 3.3: Initialization of K-Means Clustering</h4><p>Original proposal (MacQueen ’67): Select k seeds randomly</p><p>K-Means++:</p><ul><li>The first centroid is selected at random</li><li>The next centroid selected is the one that is farthest from the currently selected (according to a weighted probability score)</li><li>The selection continues until k centroids are obtained</li></ul><h4>## 3.4: The K-Medoids Clustering Method</h4><p>K-Means is sensitive to outliers</p><p>K-Medoids: Instead of taking the mean value of the object in a cluster as a reference point, representative objects (medoids; the most centrally located object in a cluster) are used</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/657/1*UjaZJnHDY1HEyE9pwGDdnQ.png" /></figure><p>PAM (Partitioning Around Medoids; Kaufmann &amp; Rousseeuw 1987)</p><ul><li>Starts from an initial set of medoids, and</li><li>Iteratively replaces one of the medoids by one of the non-medoids if it improved the total sum of the square errors (SSE) of the resulting clustering</li><li>PAM works effectively for small data sets but does not scale well for large data sets (due to the computational complexity)</li><li>Computational complexity: O(K(n-K)²)</li></ul><p>CLARA (Kaufmann &amp; Rousseeuw 1990): PAM on samples; O(Ks²+K(n-K)), s is the sample size</p><p>CLARANS (Ng &amp; Han 1994): Randomized re-sampling, ensuring efficiency + quality</p><h4>## 3.5: The K-Medians and K-Modes Clustering Methods</h4><p>Median (the central point) mathematically tends to minimize the sum of L_1-norm</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/710/1*kQLtpFWd8DzFAontp9cyNg.png" /></figure><p>K-Modes: Clustering Categorical Data</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/692/1*AEWghdk5iVXPUK6AZqRXbA.png" /></figure><h4>## 3.6: Kernel K-Means Clustering</h4><p>Project data onto a high-dimensional kernel space, and then perform K-Means clustering</p><p>Computational complexity is higher than K-Means (Need to compute and store n*n kernel matrix generated from the kernel function on the original data)</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/692/1*OlBdmYU1xAr6ze-uw-TQ8w.png" /></figure><h4>## Programming Assignment: Implementing the K-means Clustering Algorithm</h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/92b9f04097a46fba99a159723cbe3010/href">https://medium.com/media/92b9f04097a46fba99a159723cbe3010/href</a></iframe><h4>## 4.1: Hierarchical Clustering Methods</h4><p>Dendrogram of hierarchical clusters</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/419/1*oHn38ZLAMflSZFhm1zKQxg.png" /></figure><p>Agglomerative: bottom-up</p><p>Divisive: top-down</p><h4>## 4.2: Agglomerative Clustering Algorithms</h4><p>AGNES (Agglomerative Nesting)</p><p>Continuously merge nodes that have the least dissimilarity (use single-link method and dissimilarity matrix)</p><p>Variations</p><ul><li>Single link (nearest neighbor): similarity of two clusters = similarity between their most similar (nearest neighbor) members</li><li>Complete link (diameter): similarity of two clusters = similarity of their most dissimilar members</li><li>Average link (group average): similarity of two clusters = average of similarities of all pairs in the clusters</li><li>Centroid link (centroid similarity): similarity of two clusters = distance between the centroids of the clusters</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/750/1*tYM1qZ7JPogINWNNWn1z2w.png" /></figure><h4>## 4.3: Divisive Clustering Algorithms</h4><p>DIANA (Divisive Analysis)</p><p>More efficient when compared with agglomerative clustering</p><p>Challenges</p><ul><li>Choosing which cluster to split</li><li>Determining how to split</li><li>Handling the noise</li></ul><h4>## 4.4: Extensions to Hierarchical Clustering</h4><p>Weaknesses of hierarchical clustering methods</p><ul><li>Can never undo what was done previously</li><li>Do not scale well (at least O(n²)</li></ul><p>Other hierarchical clustering algorithms</p><ul><li>BIRCH (1996): Use CF-tree and incrementally adjust the quality of sub-clusters</li><li>CURE (1998): Represent a cluster using a set of well-scattered representative points</li><li>CHAMELEON (1999): Use graph partitioning methods on the K-nearest neighbor graph of the data</li></ul><h4>## 4.5: BIRCH: A Micro-Clustering-Based Approach</h4><p>BIRCH: Balanced Iterative Reducing and Clustering Using Hierarchies</p><p>Incrementally construct a CF (Clustering Feature) tree, a hierarchical data structure for multiphase clustering</p><ul><li>Phase 1: Scan DB to build an initial in-memory CF tree (a multi-level compression of the data that tries to preserve the inherent clustering structure of the data)</li><li>Phase 2: Use an arbitrary clustering algorithm to cluster the leaf nodes of the CF tree</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/748/1*lpeerNUtlG3j05rw6Kr-uw.png" /></figure><p>Diameter: Average pairwise distance within a cluster (square root of average mean squared distance between all pairs of points in the cluster)</p><p>BIRCH is a scalable and flexible clustering method → Impact to many other clustering methods</p><ul><li>Low-level micro-clustering: exploring CP-feature and BIRCH tree structure &amp; preserving the inherent clustering structure of the data</li><li>Higher-level macro-clustering: provide sufficient flexibility for integration with other cluster methods</li></ul><p>Concerns</p><ul><li>Sensitive to insertion order of data points</li><li>Due to the fixed size of leaf nodes, clusters may not be so natural</li><li>Clusters tend to be spherical given the radius and diameter measures</li></ul><h4>## 4.6: CURE: Clustering Using Well-Scattered Representatives</h4><p>Represent a cluster using a set of well-scattered representative points.</p><p>Cluster distance: Minimum distance between the representative points chosen</p><p>Shrinking factor α: The points are shrunk towards the centroid by a factor α</p><h4>## 4.7: CHAMELEON: Graph Partitioning on the KNN Graph of the Data</h4><p>Two clusters are merged only if the interconnectivity and closeness (proximity) between two clusters are high <strong>relative to</strong> the internal interconnectivity of the clusters and closeness of items within the clusters.</p><p>A graph-based, two-phase algorithm</p><ol><li>Use a graph-partitioning algorithm: Cluster objects into a large number of relatively small sub-clusters (graphlets)</li><li>Use an agglomerative hierarchical clustering algorithm: Find the genuine clusters by repeatedly combining these sub-clusters</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/653/1*xMI3k9RkpjlATtfycgdwyQ.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/720/1*W-Vx8m1vjk41jqmrmC0gqg.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/741/1*hN5biWdX7TqmhgS67B23jA.png" /></figure><h4>## 4.8: Probabilistic Hierarchical Clustering</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/691/1*pAiGhTkBzOm_GXgTMrpQuA.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/744/1*5F-BiWboYh1AcgXd275gvQ.png" /></figure><p>Quality of clustering is defined as the probability of that clustering to occur.</p><p>Then the distance between clusters can be expressed probabilistically.</p><h3>## 2019/03/02</h3><h4>## 5.1: Density-Based and Grid-Based Clustering Methods</h4><p>Density-Based Clustering:</p><ul><li>Discover clusters of arbitrary shape</li><li>Handle noise</li><li>One scan (only examine the local region to justify density)</li><li>Need density parameters as termination condition</li></ul><h4>## 5.2: DBSCAN: A Density-Based Clustering Algorithm</h4><p>DBSCAN: <strong>D</strong>ensity-<strong>B</strong>ased <strong>S</strong>patial <strong>C</strong>lustering of <strong>A</strong>pplications with <strong>N</strong>oise</p><p>A cluster is defined as a maximal set of density-connected points</p><ul><li>Eps (epsilon): Maximum radius of the neighborhood</li><li>MinPts: Minimum number of points in the eps-neighborhood of a point</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/363/1*oX_37Uh_jzarKrFGMoURXw.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/764/1*j98jdyRGOGzQ3ry7Udj_LQ.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/742/1*C7qfERypKTMpoOR9kJyj-Q.png" /></figure><p>Computational complexity:</p><ul><li>O(nlogn) if a spatial index is used</li><li>O(n²) otherwise</li></ul><p>DBSCAN is sensitive to the setting of parameters.</p><h4>## 5.3: OPTICS: Ordering Points To Identify Clustering Structure</h4><p>OPTICS is much less sensitive to parameter settings than the DBSCAN.</p><p>Insight: <strong>a high-density cluster is a part of a low-density cluster </strong>→ find high-density clusters first</p><p>Define two concepts: core distance &amp; reachability distance</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/745/1*0KmNHXq9pSxQvbvsODEnnA.png" /></figure><p>core object = core point (see the DBSCAN slide)</p><h4>## 5.4: Grid-Based Clustering Methods</h4><p>Features and challenges of a typical grid-based algorithm</p><ul><li>Efficiency and scalability: # of cells &lt;&lt; # of data points</li><li>Uniformity: Uniform, hard to handle highly irregular data distributions</li><li>Locality: Limited by predefined cell sizes, borders, and density threshold</li><li>Curse of dimensionality: Hard to cluster high-dimensional data</li></ul><h4>## 5.5: STING: A Statistical Information Grid Approach</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/737/1*zKSylI58u5-Oste0ADks_A.png" /></figure><p>When a region query is given, starting from the 1st layer, calculate the likelihood that a cell is relevant to the query at some confidence level using the statistical information of the cell, then proceed to the next layer.</p><p>Advantages:</p><ul><li>Query independent, easy to parallelize, incremental update</li><li>Efficiency: O(K) and K &lt;&lt; N (K: # of cells at the bottom layer, N: # of data points)</li></ul><p>Disadvantages: may lose accuracy because of its probabilistic nature</p><h4>## 5.6: CLIQUE: Grid-Based Subspace Clustering</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/754/1*X8ToUDgatKdY1kUSABBPgg.png" /></figure><p>Strength</p><ul><li>Automatically finds subspaces of the highest dimensionality as long as high density clusters exist in those subspaces</li><li>Insensitive to the order of records in input and does not presume some canonical data distribution</li><li>Scales linearly with the size of input and has good scalability as the number of dimensions in the data increases</li></ul><p>Weaknesses</p><ul><li>As in all grid-based clustering approaches, the quality of the results crucially depends on the appropriate choice of the number and width of the partitions and grid cells</li></ul><h3># 2019/03/09</h3><h4>## 6.1: Methods for Clustering Validation</h4><ul><li>Clustering evaluation: goodness</li><li>Clustering stability: sensitivity to parameters</li><li>Clustering tendency: suitability</li></ul><h4>## 6.2: Clustering Evaluation Measuring Clustering Quality</h4><ul><li>External measures: supervised (compare with prior or expert-specified knowledge, or the ground truth)</li><li>Internal measures: unsupervised (how well the clusters are separated and how compact the clusters are)</li><li>Relative measures: directly compare different clusterings</li></ul><h4>## 6.3: Constraint-Based Clustering</h4><p>External measures</p><p>Q(C, T): the quality of a clustering C compared to the ground truth T</p><ul><li>Cluster homogeneity</li><li>Cluster completeness</li><li>Rag bag (“misc” or “other”) better than alien: putting alien objects in a pure cluster is penalized</li><li>Small cluster preservation</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/647/1*s6Iqh7YYi_ShiHwJYtBGZw.png" /></figure><h4>## 6.4: External Measures 1: Matching-Based Measures</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/724/1*Ie_5zcGDw1mi3MfVoXl2SA.png" /></figure><p>purity_i = <strong>maximum</strong> # of points from one (ground truth) partition</p><p>eg. in the green table, C_1 contains 20 points from T_2 and 30 points from C_1, therefore purity_1 = 30/50 (rather than 20/50).</p><p>This seems good, but in the orange table, both C_1 and C_2 have the maximum # of points from the same ground truth partition T_2.</p><p>Maximum matching: C_1 and C_2 can’t match T_2 simultaneously, so match = 0.65 (C_1-T_3, C_2-T_2) rather than 0.6 (C_1-T_2, C_2-T_3).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/684/1*gA2WNS617iz1GsWWnQKqNA.png" /></figure><h4>## 6.5: External Measure 2: Entropy-Based Measures</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/687/1*FXZkXP8pwikzaaXmT7dXgA.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/690/1*7Al0CsPAnp5VAz5MtNnFug.png" /></figure><h4>## 6.6: External Measure 3: Pairwise Measures</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/721/1*9e6ju83dWXuP5GVu6CVxVA.png" /></figure><p>FN: two points have the same partition label, but clustered in different clusters</p><p>FP: two points have different partition labels, but clustered in the same cluster</p><p>To calculate TP, FN, FP and TN, we have to consider the total number of <strong>pairs</strong> of points.</p><p>r: # of clusters</p><p>k: # of ground truth partitions</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/696/1*NYiFdl0wxkkLLasxqPBLZA.png" /></figure><h4>## 6.7: Internal Measures for Clustering Validation</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/666/1*9_LcJno4_EBFQfOI59lJHw.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/720/1*_-CNEpuY17Id4jCxDnbNSA.png" /></figure><h4>## 6.8: Relative Measures</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/695/1*MQnA89X0qEOZ-J-Q7Iw4xw.png" /></figure><h4>## 6.9: Cluster Stability</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/671/1*q_bRPRwy__p7RggDi44qFg.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/690/1*heAPX4Ad1LB5VImYQgA5JQ.png" /></figure><h4>## 6.10: Clustering Tendency</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/687/1*qgyFgy2DeWwRSEJR2g1n0Q.png" /></figure><h4>## Programming Assignment</h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/6c30ee2fcfb1dac44a92a353962d2e7f/href">https://medium.com/media/6c30ee2fcfb1dac44a92a353962d2e7f/href</a></iframe><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7d1bf4784711" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[「良いエンジニア」を言語化してみました]]></title>
            <link>https://medium.com/@taka.atsushi/%E8%89%AF%E3%81%84%E3%82%A8%E3%83%B3%E3%82%B8%E3%83%8B%E3%82%A2-%E3%82%92%E8%A8%80%E8%AA%9E%E5%8C%96%E3%81%97%E3%81%A6%E3%81%BF%E3%81%BE%E3%81%97%E3%81%9F-b59ebe839b0f?source=rss-b64b37102e90------2</link>
            <guid isPermaLink="false">https://medium.com/p/b59ebe839b0f</guid>
            <dc:creator><![CDATA[Atsushi Takayama]]></dc:creator>
            <pubDate>Thu, 31 Jan 2019 10:00:24 GMT</pubDate>
            <atom:updated>2019-01-31T10:07:15.947Z</atom:updated>
            <content:encoded><![CDATA[<p>「<a href="https://voyagegroup.connpass.com/event/111412/">VOYAGE GROUP エンジニアの公開ガチ評価会</a>」に参加して、最近考えていた「良いエンジニア」像がかなり良い感じだと思うようになりました。</p><p>「ガチ評価会」自体の内容は<a href="https://shinkufencer.hateblo.jp/entry/2019/01/30/235537">他の方のブログ</a>に譲るとして、「ガチ評価会」で聞けなかった部分、つまり「普段だったら『ビジネス的側面からの技術投資判断』とかも聞くんだけど」と言っていたところが、まさに聞きたいところだったのでニヤッとしました。聞けなくて残念♪</p><h4>妥協ない挑戦</h4><p>元々ピクシブの技術力評価においては、「最近やった<strong>妥協ない挑戦</strong>は何ですか？」というのをキーワードにやってました。</p><p>解決すべき課題に対して、どういう背景があって、どういう事前調査をして、どういう実装をして、どう考察するか、というところまでをきちんと考えて仕事することに成長があるんだよ、というメッセージ性です。</p><p>そんなこと言っても普段は妥協ばっかりですって？いえいえ、相反する選択肢の中で、何を考えて「現状ベスト」を選んだかも<strong>妥協ない挑戦</strong>と考えています。</p><p>ただ、「何に対して妥協ない挑戦をすればいいのか？」という疑問の声が多かったので、次のような言語化をしてみました。</p><h4>4つの挑戦</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/960/1*VQIcWW_Q0BhR1hdPJcb3kg.png" /><figcaption>この図の説明は<a href="https://medium.com/@taka.atsushi/c356949fe361">こちら</a></figcaption></figure><h4>①チームの課題を最短経路で解決できる</h4><p>毎週仮説検証できるチームを作ることには、とてつもない価値があります。</p><p>チームをコンパクトに保てる力（複数の環境を使いこなせるとか）や、最短経路で課題解決できる判断力や、「顧客が本当に必要だったもの」を作ることができる力や、将来に渡って課題解決のスピードを保てる力などが求められます。</p><p><a href="https://medium.com/@taka.atsushi/%E3%83%94%E3%82%B62%E6%9E%9A%E3%83%AB%E3%83%BC%E3%83%AB%E3%81%AF%E6%89%8B%E6%9C%AD8%E6%9E%9A%E3%82%92%E6%8F%83%E3%81%88%E3%82%8B%E3%82%B2%E3%83%BC%E3%83%A0-f76df8c1463f">ピザ2枚ルールは手札8枚を揃えるゲーム</a></p><h4>②チームの手作業をフレームワーク化して減らし続けられる</h4><p>世の中のテクノロジーは、人間の手作業を減らす方向に進んでいます。資本主義最高ですね。</p><p>そういう「フレームワーク」をうまく使ってチームの仕事の効率を上げて、チームが本質的な課題解決に注力できるようにすることには大きな価値があります。</p><p>品質やセキュリティ等を「意識しなくても」高められるように環境整備していくのも、フレームワーク化の一部です。</p><p>（ここでいうフレームワークとは、ライブラリ、ツール、ミドルウェア、SaaS等、幅広い意味で使っています）</p><p><a href="https://medium.com/@taka.atsushi/%E6%95%A2%E3%81%88%E3%81%A6%E5%88%B6%E7%B4%84%E3%82%92%E4%B8%8E%E3%81%88%E3%81%9F%E3%81%BB%E3%81%86%E3%81%8C%E3%82%B9%E3%83%94%E3%83%BC%E3%83%89%E3%81%8C%E5%87%BA%E3%81%9B%E3%82%8B-81672da00c47">敢えて制約を与えたほうがスピードが出せる</a></p><h4>③まだフレームワークが整っていない分野を切り開く突破力がある</h4><p>まだ会社にはノウハウが少ないけど、世の中的には「めっちゃ頑張れば手が届く」ところまで来ている技術を、すぐに自分の物にして動くものを作っちゃう力です。</p><p>こういう人のおかげで会社のオプションが広がり、「この分野を攻めよう」というときに真っ先に声がかかることになるでしょう。</p><p><a href="https://medium.com/@taka.atsushi/%E5%A4%A7%E4%BC%81%E6%A5%AD%E3%81%8C%E3%82%B9%E3%82%BF%E3%83%BC%E3%83%88%E3%82%A2%E3%83%83%E3%83%97%E3%81%A8%E5%8B%9D%E8%B2%A0%E3%81%99%E3%82%8B%E3%81%B9%E3%81%8D%E3%81%A7%E3%81%AF%E3%81%AA%E3%81%84-260243e1ffae">大企業がスタートアップと勝負するべきではない</a></p><h4>④技術、組織、ビジネス等の状況から長期的視野でバランスの良い判断ができる</h4><p>ビジネスの視点で技術の判断をするとか、技術の視点で組織の判断をするとか、社内外の状況を長期的に把握して設計に落とし込めるような力です。この役割を務められれば、どんなスタートアップの創業CTOにもなれるでしょう。</p><p>ちなみにこれはCTOとしての自分がやってる仕事です。</p><p><a href="https://medium.com/@taka.atsushi/%E3%81%AA%E3%81%9C-%E3%82%A8%E3%83%B3%E3%82%B8%E3%83%8B%E3%82%A2%E3%83%AA%E3%83%B3%E3%82%B0%E7%B5%84%E7%B9%94-%E3%81%AF-%E3%82%A8%E3%83%B3%E3%82%B8%E3%83%8B%E3%82%A2%E3%81%AE%E7%B5%84%E7%B9%94-%E3%81%A0%E3%81%91%E3%82%92%E8%80%83%E3%81%88%E3%81%A6%E3%81%AF%E3%81%84%E3%81%91%E3%81%AA%E3%81%84%E3%81%8B-c356949fe361">なぜ「エンジニアリング組織」は「エンジニアの組織」だけを考えてはいけないか</a></p><h4>最も大事なこと</h4><p>以上4つのうち2つぐらいで価値発揮することを目指してくれるといいかなと思います。</p><p>しかし、テクノロジーはどんどん進化し続けています。今日ある仕事は、3年後にはフレームワーク化されて無くなってる可能性もあります。</p><p>現状に満足せず常に役割を変化させ続けることができるエンジニアが「良いエンジニア」なのは間違いありません。</p><p>やっぱり<strong>妥協ない挑戦</strong>に戻ってきちゃいましたね。</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b59ebe839b0f" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[前提条件を正しく知れば、取れる選択肢はおのずと限られる]]></title>
            <link>https://medium.com/@taka.atsushi/%E5%89%8D%E6%8F%90%E6%9D%A1%E4%BB%B6%E3%82%92%E6%AD%A3%E3%81%97%E3%81%8F%E7%9F%A5%E3%82%8C%E3%81%B0-%E5%8F%96%E3%82%8C%E3%82%8B%E9%81%B8%E6%8A%9E%E8%82%A2%E3%81%AF%E3%81%8A%E3%81%AE%E3%81%9A%E3%81%A8%E9%99%90%E3%82%89%E3%82%8C%E3%82%8B-98b9d35aa70b?source=rss-b64b37102e90------2</link>
            <guid isPermaLink="false">https://medium.com/p/98b9d35aa70b</guid>
            <dc:creator><![CDATA[Atsushi Takayama]]></dc:creator>
            <pubDate>Tue, 29 Jan 2019 16:01:22 GMT</pubDate>
            <atom:updated>2019-01-30T17:38:43.185Z</atom:updated>
            <content:encoded><![CDATA[<p>いくら議論しても平行線で全然噛み合わないときは、もしかしたらお互いの前提条件がずれているからなのかもしれません。まずは落ち着いて前提条件を列挙するところから始めてみてはいかがでしょうか？</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*JU7-Ksjiq4PaSbnS1-A6gw.jpeg" /><figcaption><a href="https://unsplash.com/photos/3V8xo5Gbusk">https://unsplash.com/photos/3V8xo5Gbusk</a></figcaption></figure><p>何か将来の方針を考える時、人は知らず知らずのうちに自分で前提条件を定義しちゃっていることがあります。自分と相手の前提条件が揃っていないと、堂々巡りに陥ってしまいます。</p><p>ビジネスにおいては、もちろん選択肢が無限にあるなんてことはありえませんね。予算、メンバー、自社のブランド、既存システム、採用計画、パートナー企業、法律などなど。前提条件は実は大量にあるものなのです。</p><p>他にもあります。人は身近なことを考えるのは得意ですが、遠い将来のことを考えるのは苦手です。世の中の長期トレンド、その中で自社はどのポジションを取っていくか、会社の将来のプロダクトビジョンなど、現在だけでなく将来のほうからの前提条件を置いてみるのも大事です。</p><p>長期トレンドというのは恐ろしいものです。地理的な面では少子化や都市への人口集中のトレンドなど。テクノロジー面では、一貫して人間がやる仕事を効率化していく<strong>資本主義的に合理的な方向</strong>に世の中は向かっています。</p><p>長期トレンドにはGoogleや中国でさえも逆らえません。</p><p>このようにして、現在の前提条件や未来の前提条件を並べてみると、取れる選択肢は実はそんなに多くないということに気付き、お互いに納得する妥当な選択に落ち着くのです。</p><h4>合わせて読みたい</h4><ul><li><a href="https://medium.com/@taka.atsushi/%E8%87%AA%E8%BB%A2%E8%BB%8A%E7%BD%AE%E3%81%8D%E5%A0%B4%E3%81%AE%E8%AD%B0%E8%AB%96-%E3%82%92%E9%81%BF%E3%81%91%E3%82%8B%E3%81%9F%E3%82%81%E3%81%AB%E6%84%8F%E8%AD%98%E3%81%97%E3%81%A6%E3%81%84%E3%82%8B%E3%81%93%E3%81%A8-996d78492ef1">「自転車置き場の議論」を避けるために意識していること</a></li><li><a href="https://medium.com/@taka.atsushi/%E6%95%A2%E3%81%88%E3%81%A6%E5%88%B6%E7%B4%84%E3%82%92%E4%B8%8E%E3%81%88%E3%81%9F%E3%81%BB%E3%81%86%E3%81%8C%E3%82%B9%E3%83%94%E3%83%BC%E3%83%89%E3%81%8C%E5%87%BA%E3%81%9B%E3%82%8B-81672da00c47">敢えて制約を与えたほうがスピードが出せる</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=98b9d35aa70b" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[「自転車置き場の議論」を避けるために意識していること]]></title>
            <link>https://medium.com/@taka.atsushi/%E8%87%AA%E8%BB%A2%E8%BB%8A%E7%BD%AE%E3%81%8D%E5%A0%B4%E3%81%AE%E8%AD%B0%E8%AB%96-%E3%82%92%E9%81%BF%E3%81%91%E3%82%8B%E3%81%9F%E3%82%81%E3%81%AB%E6%84%8F%E8%AD%98%E3%81%97%E3%81%A6%E3%81%84%E3%82%8B%E3%81%93%E3%81%A8-996d78492ef1?source=rss-b64b37102e90------2</link>
            <guid isPermaLink="false">https://medium.com/p/996d78492ef1</guid>
            <dc:creator><![CDATA[Atsushi Takayama]]></dc:creator>
            <pubDate>Mon, 28 Jan 2019 18:17:58 GMT</pubDate>
            <atom:updated>2019-01-29T16:06:54.301Z</atom:updated>
            <content:encoded><![CDATA[<p>CTOというのは会社全体のシステムを設計するお仕事なのですが、そんな大きな設計にバグがあったりすると、会社の未来を数年単位で苦しめるような、大損害になってしまいます。</p><p>そんな大きな話が、<strong>自転車置き場の議論</strong>に陥ったせいで十分に議論されないまま決まってしまったりしたらと思うと、心底ゾッとします。</p><blockquote><strong>自転車置き場の議論（bikeshedding）</strong>：例えば原発の開発計画について議論するべき場で、自転車置き場の素材をどうするかのような「議論しやすいけれど本質的ではないこと」に多くの時間を費やしてしまうこと</blockquote><p>本質的ではない議論に時間が費やされ、本質的な課題は解決されないまま「じゃあ続きは来週で」なんてことになってしまうフラストレーションは、誰しも経験があると思います。</p><h4>意識していること</h4><p>そんなわけで意識しているのが、次の図です。</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*VzpgMY_4ujEg49N-cMFMeA.png" /><figcaption><a href="https://www.liquidweb.com/kb/what-is-a-progressive-jpeg/">https://www.liquidweb.com/kb/what-is-a-progressive-jpeg/</a></figcaption></figure><p>時間は有限です。左側からスタートしても、絶対に右側までは到達しません。</p><ul><li>上：<strong>目につくものからいきなり詳細な話をしてしまう</strong>ものの、本質的なことに到達するまでに時間オーバーになる</li><li>下：<strong>ぼんやりでも良いので全体像から徐々に形を描いていって</strong>、細部は決められなくても気にしない</li></ul><p>冒頭の設計の例においては、10年後絶対に起こっているであろう未来を列挙した後に、それを元に3年先はまあこんな感じだよねって話をして、だいたい合意が取れればOKとします。</p><p>そこさえ握っておけば、あとの細部はチームに任せてしまっても、まあなんとかなるもんです。</p><h4>応用例</h4><p>考えてみると、この図を意識したほうが良いことって、けっこういっぱいありますね。</p><p><strong>マネジメント</strong></p><ul><li>上：やたら細かい指示を出す割にどこに向かってるか不明</li><li>下：大きな方向性を示して細部は任せる</li></ul><p><strong>セキュリティ</strong></p><ul><li>上：目についたところを片っ端から潰していくが、いつまで経っても肝心なところは防げない</li><li>下：全体に効くことから徐々にやっていく</li></ul><p><strong>チューニング</strong></p><ul><li>上：片っ端から（略）</li><li>下：全体像を把握</li></ul><p>他にも色々あると思います。ぜひこの画像を会議室の壁に貼っておきたいですね。</p><h4>合わせて読みたい</h4><ul><li><a href="https://medium.com/@taka.atsushi/%E6%95%A2%E3%81%88%E3%81%A6%E5%88%B6%E7%B4%84%E3%82%92%E4%B8%8E%E3%81%88%E3%81%9F%E3%81%BB%E3%81%86%E3%81%8C%E3%82%B9%E3%83%94%E3%83%BC%E3%83%89%E3%81%8C%E5%87%BA%E3%81%9B%E3%82%8B-81672da00c47">敢えて制約を与えたほうがスピードが出せる</a></li><li><a href="https://medium.com/@taka.atsushi/%E5%89%8D%E6%8F%90%E6%9D%A1%E4%BB%B6%E3%82%92%E6%AD%A3%E3%81%97%E3%81%8F%E7%9F%A5%E3%82%8C%E3%81%B0-%E5%8F%96%E3%82%8C%E3%82%8B%E9%81%B8%E6%8A%9E%E8%82%A2%E3%81%AF%E3%81%8A%E3%81%AE%E3%81%9A%E3%81%A8%E9%99%90%E3%82%89%E3%82%8C%E3%82%8B-98b9d35aa70b">前提条件を正しく知れば、取れる選択肢はおのずと限られる</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=996d78492ef1" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>