[Dev Tip] Redis new data structure: the HyperLogLog

Generally speaking, I love randomized algorithms, but there is one I love particularly since even after you understand how it works, it still remains magical from a programmer point of view. It accomplishes something that is almost illogical given how little it asks for in terms of time or space. This algorithm is called HyperLogLog, and today it is introduced as a new data structure for Redis.

Counting unique things

Usually counting unique things, for example the number of unique IPs that connected today to your web site, or the number of unique searches that your users performed, requires to remember all the unique elements encountered so far, in order to match the next element with the set of already seen elements, and increment a counter only if the new element was never seen before.

This requires an amount of memory proportional to the cardinality (number of items) in the set we are counting, which is, often absolutely prohibitive.

There is a class of algorithms that use randomization in order to provide an approximation of the number of unique elements in a set using just a constant, and small, amount of memory. The best of such algorithms currently known is called HyperLogLog, and is due to Philippe Flajolet.

HyperLogLog is remarkable as it provides a very good approximation of the cardinality of a set even using a very small amount of memory. In the Redis implementation it only uses 12kbytes per key to count with a standard error of 0.81%, and there is no limit to the number of items you can count, unless you approach 2^64 items (which seems quite unlikely).

The algorithm is documented in the original paper [1], and its practical implementation and variants were covered in depth by a 2013 paper from Google [2].

[1] http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf
[2] http://static.googleusercontent.com/media/research.google.com/en//pubs/archive/40671.pdf

How it works?

There are plenty of wonderful resources to learn more about HyperLogLog, such as [3].

[3] http://blog.aggregateknowledge.com/2012/10/25/sketch-of-the-day-hyperloglog-cornerstone-of-a-big-data-infrastructure/

Here I’ll cover only the basic idea using a very clever example found at [3]. Imagine you tell me you spent your day flipping a coin, counting how many times you encountered a non interrupted run of heads. If you tell me that the maximum run was of 3 heads, I can imagine that you did not really flipped the coin a lot of times. If instead your longest run was 13, you probably spent a lot of time flipping the coin.

However if you get lucky and the first time you get 10 heads, an event that is unlikely but possible, and then stop flipping your coin, I’ll provide you a very wrong approximation of the time you spent flipping the coin. So I may ask you to repeat the experiment, but this time using 10 coins, and 10 different piece of papers, one per coin, where you record the longest run of heads. This time since I can observe more data, my estimation will be better.

Long story short this is what HyperLogLog does: it hashes every new element you observe. Part of the hash is used to index a register (the coin+paper pair, in our previous example. Basically we are splitting the original set into m subsets). The other part of the hash is used to count the longest run of leading zeroes in the hash (our run of heads). The probability of a run of N+1 zeroes is half the probability of a run of length N, so observing the value of the different registers, that are set to the maximum run of zeroes observed so far for a given subset, HyperLogLog is able to provide a very good approximated cardinality.

The Redis implementation

The standard error of HyperLogLog is 1.04/sqrt(m), where “m” is the number of registers used.
Redis uses 16384 registers, so the standard error is 0.81%.

Since the hash function used in the Redis implementation has a 64 bit output, and we use 14 bits of the hash output in order to address our 16k registers, we are left with 50 bits, so the longest run of zeroes we can encounter will fit a 6 bit register. This is why a Redis HyperLogLog value only uses 12k bytes for 16k registers.

Because of the use of a 64 bit output function, which is one of the modifications of the algorithm that Google presented in [2], there are no practical limits to the cardinality of the sets we can count. Moreover it is worth to note that the error for very small cardinalities tend to be very small. The following graph shows a run of the algorithm against two different large sets. The cardinality of the set is shown in the x axis, while the relative error (in percentage) in the y axis.

The red and green lines are two different runs with two totally unrelated sets. It shows how the error is consistent as the cardinality increases. However for much smaller cardinalities, you can enjoy a much smaller error:

The green line shows the error of a single run up to cardinality 100, while the red line is the maximum error found in 100 runs. Up to a cardinality of a few hundreds the algorithm is very likely to make a very small error or to provide the exact answer. This is very valuable when the computed value is shown to an user that can visually match if the answer is correct.

The source code of the Redis implementation is available at Github:



From the point of view of Redis an HyperLogLog is just a string, that happens to be exactly 12k + 8 bytes in length
(12296 bytes to be precise). All the HyperLogLog commands will happily run if called with a String value exactly of this size, or will report an error. However all the calls are safe whatever is stored in the string: you can store garbage and still ask for an estimation of the cardinality. In no case this will make the server crash.

Also everything in the representation is endian neutral and is not affected by the processor word size, so a 32 bit big endian processor can read the HLL of a 64 bit little endian processor.

The fact that HyperLogLogs are strings avoided the introduction of an actual type at RDB level. This allows the work to be back ported into Redis 2.8 in the next days, so you’ll be able to use HyperLogLogs ASAP. Moreover the format is automatically serialized, and can be retrieved and restored easily.

The API is constituted of three new commands:

PFADD var element element … element
PFMERGE dst src src src … src

The commands prefix is “PF” in honor of Philippe Flajolet [4].

[4] http://en.wikipedia.org/wiki/Philippe_Flajolet

PFADD adds elements to the HLL stored at “var”. If the variable does not exist, an empty HLL is automatically created as it happens always with Redis API calls. The command is variadic, so allows for very aggressive pipelining and mass insertion.

The command returns 1 if the underlying HyperLogLog was modified, otherwise 0 is returned.
This is interesting for the user since as we add elements the probability of an element actually modifying some register decreases. The fact that the API is able to provide hints about the fact that a new cardinality is available allows for programs that continuously add elements and retrieve the approximated cardinality only when a new one is available.

PFCOUNT returns the estimated cardinality, which is zero if the key does not exist.

Finallly PFMERGE can merge N different HLL values into one. The resulting HLL will report an estimated cardinality that is the cardinality of the union of the different sets that we counted with the different HLL values.
This seems magical but works because HLL while randomized is fully deterministic, so PFMERGE just takes, for every register, the maximum value available across the N HLL values. A given element hashes to the same register with the same run of zeroes always, so the merge performed in this way will only add the count of the elements that are not common to the different HLLs.

As you can see HyperLogLog is fully parallelizable, since it is possible to split a set into N subsets counted independently to later merge the values and obtain the total cardinality approximation. The fact that HLLs in Redis are just strings helps to move HLL values across instances.

First make it correct, then make it fast

Redis HHLs are composed of 16k registers packed into 6 bit integers. This creates several performance issues that must be solved in order to provide an API of commands that can be called without thinking too much.

One problem is that accessing to registers require accessing multiple bytes, shifting, and masking in order to retrieve the correct 6 bit value. This is not a big problem for PFADD that only touches a register for every element, but PFCOUNT needs to perform a computation using all the 16k registers, so if there are non trivial constant times to access every single register, the command risks to be slow. Moreover, while accessing the registers, we need to compute the sum of pow(2,-register) which involves floating point math.

One may feel the temptation of using full bytes instead of 6 bit integers in order to speedup the computation, however this would be a shame since every HLL would use 16k instead of 12k that is a non trivial difference, so this route was discarded at the beginning. The command was optimized for a speedup of about 3 times compared to the initial implementation by doing the following changes:

* For m=16k which is the Redis default (the implementation is more generic and could theoretically work with different values) the implementation selects a fast-path with unrolled loops accessing 16 register at every time. The registers are accessed using fixed offsets / shifts / masks (via some pointer that is incremented 12 bytes at the next iteration).
* The floating point computation was modified in order to allow for multiple operations to be performed in parallel when possible. This was just a matter of adding parens. Floating point math is not commutative, but in this case there was no loss of precision.
* The pow(2,-register) term was precomputed in a lookup table.

With the 3x speedup provided by the above changes the command was able to perform about 60k calls per second in a fast hardware. However this is still far from the hundreds thousands calls possible with commands that are, from the user point of view, conceptually similar, like SCARD.

Instead of optimizing the computation of the approximated cardinality further, there was a simpler solution. Basically the output of the algorithm only changes if some register changes. However as already observed above, most of the PFADD calls don’t result in any register changed. This basically means that it is possible to cache the last output and recompute it only if some register changes.

So our data structure has an additional tail of 8 bytes representing a 64bit unsigned integer in little endian format. If the most significant bit is set, then the precomputed value is stale and requires to be recomputed, otherwise PFCOUNT can use it as it is. PFADD just turns on the “invalid cache” bit when some register is modified.

After this change even trying to add elements at maximum speed using a pipeline of 32 elements with 50 simultaneous clients, PFCOUNT was able to perform as well as any other O(1) command with very small constant times.

Bias correction using polynomial regression

The HLL algorithm, in order to be practical, must work equally well in any cardinality range. Unfortunately the raw estimation performed by the algorithm is not very good for cardinalities less than m*2.5 (around 40000 elements for m=16384) since in this range the algorithm outputs biased or even results with larger errors depending on the exact range.

The original HLL paper [1] suggests switching to Linear Counting [5] when the raw cardinality estimated by the first part of the HLL algorithm is less than m*2.5.

[5] http://dblab.kaist.ac.kr/Publication/pdf/ACM90_TODS_v15n2.pdf

Linear counting is a different cardinality estimator that uses a simple concept. We have a bitmap of N bits. Every time a new element must be counted, it is hashed, and the hash is used in order to index a random bit inside the bitmap, that is turned to 1. The number of unset bits in the bitmap gives an idea of how many elements we added so far using the following formula:

    cardinality = m*log(m/ez);

Where ‘ez’ is the number of zero bits and m is the total number of bits in the bitmap.

Linear counting does not work well for large cardinalities compared to HyperLogLog, but works very well for small cardinalities. Since the HLL registers as a side effect also work as a linear counting bitmap, counting the number of zero registers it is possible to apply linear counting for the range where HLL does not perform well. Note that this is possible because when we update the registers, we don’t really use the longest run of zeroes, but the longest run of zeroes plus one. This means that if an element is added and it is addressing a register that was never addressed, the register will turn from 0 to a different value (at least 1).

The problem with linear counting is that as the cardinality gets bigger, its output error gets larger, so we need to switch to HLL ASAP. However when we switch at 2.5m, HLL is still biased. In the following image the same cardinality was tested with 1000 different sets, and the error of each run is reported as a point:

The blu line is the average of the error. As you can see before a cardinality of 40k, where linear counting is used, the more we go towards greater cardinalities, the more the points “beam” gets larger (bigger errors). When we switch to HLL raw estimate the error is smaller, but there is a bias: the algorithm overestimates the cardinality in the range 40k-80k.

Google engineers studied this problem extensively [2] in order to correct the bias. Their solution was to create an empirical table of cardinality values and the corresponding biases. Their modified algorithm uses the table and interpolation in order to get the bias in a given range, and correct accordingly.

I used a different approach: you can see that the bias is not random but looks like a very smooth curve, so I calculated a few cardinality-bias samples and performed polynomial regression in order to find a polynomial approximating the curve.

Currently I’m using a four order polynomial to correct in the range 40960-72000, and the following is the result after the bias correction:

While there is still some bias at the switching point between the two algorithms, the result is quite satisfying compared to the vanilla HLL algorithm, however it is probably possible to use a curve that fits better the bias curve. I had no time to investigate this further.

It is worth to note that during my investigations I found that, when no bias correction is used, and at least for m=16384, the best value to switch from linear counting to raw HLL estimate is actually near 3 and not 2.5 as mentioned in [1], since a value of 3 both improves bias and error. Values larger than 3 will improve the bias (a value of 4 completely corrects it) but will have bad effects on the error.

The original HLL algorithm also corrects for values towards 2^32 [1][2] since once we approach very large values collisions in the hash function starts to be an issue. We don’t need such correction since we use a 64 bit hash function and 6 bits counters, which is one of the modifications proposed by Google engineers [2] and adopted by the Redis implementation.

Future work

Intuitively it seems like it is possible to improve the error of the algorithm output when linear counting is used by exploiting the additional informations we have. In the standard linear counting algorithm the registers are just 1 bit wide, so we have only two informations: if an element so far hashed to this bit or not. Still the HLL algorithm as proposed initially [1] and as modified at Google [2], when reverting to linear counting still only use the number of zero registers as the input of the algorithm. It is possible that also using the information stored in the registers could improve the output.

For example in standard linear counting, assuming we have 10 bits, I may add 5 elements that all happen to address the same bit. This is an odd case that the algorithm has no way to correct, and the estimation provided will likely be smaller than the actual cardinality. However in the linear counting algorithm used by HLL in a similar situation we may found that the value at the only register set is an hint about multiple elements colliding there, allowing a correction of the output.


HyperLogLog is an amazing data structure. My hope is that the Redis implementation, that will be available in a stable release in a matter of days (Redis 2.8.9 will include it), will provide this tool in a ready to use form to many programmers.

The HN post is here: https://news.ycombinator.com/item?id=7506774

[Discovery] Hành trình đi tìm nguồn gốc tên gọi các châu lục trên thế giới

Bạn có bao giờ tự hỏi tại sao bố mẹ lại đặt cái tên như thế cho mình hay không? Có thể do đó là một cái tên hay và ý nghĩa, tuy nhiên cũng có thể đằng sau có một nguyên nhân và nguồn gốc nào đó khác. Có lẽ tất cả mọi sự việc đều có nguyên nhân của nó, ngay cả cái tên “Trái đất” hay tên gọi của các châu lục hiện nay.

Châu Phi (Africa)

Có rất nhiều giả thuyết khác nhau về nguồn gốc tên gọi của châu Phi. Sau khi người La Mã đánh bại đế chế Carthage (hiện nay là Tunisia tại Bắc Phi) và kết thúc cuộc Chiến tranh Punic lần III, họ đã đặt tên cho vùng đất mới chiếm được này là Africa.

Giả thuyết phổ biến nhất được biến đến đó là vùng đất này được đặt tên theo một bộ tộc bản địa ở đây, người Afri. Mà “Africa” hay biến thể sau đó “Africus” có nghĩa là “vùng đất của người Afri”.

Một giả thuyết khác thuyết phục hơn bắt nguồn từ tiếng Phoenician (Phoenician là nền văn minh cổ đại đã phát minh ra bảng chữ cái alphabet). Từ “afar” trong tiếng Phoenician, có nghĩa là cát bụi, được ghép với hậu tố “-ica” trong tiếng Latin, dùng để chỉ vùng đất. Nó tạo thành cái tên “vùng đất của cát bụi”, do phía Bắc châu Phi là những vùng sa mạc rộng lớn, cũng là nơi người La Mã đánh chiếm và tuyên bố đây là vùng đất của họ.

Sau này, những người châu Âu đã tiếp tục khám phá xuống phía Nam châu Phi và phát hiện ra một lục địa rất rộng lớn. Tuy nhiên cái tên Africa vẫn được giữ nguyên và trở thành tên gọi của châu lục này.

Châu Nam Cực (Antarctica)

Cái tên Antarctica xuất phát từ tiếng Hy Lạp “antarktike”, có nghĩa là “đối diện phương Bắc”, và như chúng ta biết châu Nam Cực nằm ở cực Nam của Trái đất. John George Bartholomew là một chuyên gia vẽ bản đồ người Scotland, được cho là người đầu tiên đã sử dụng cái tên Antarctica để gọi châu lục này.

Cái tên này cũng đã từng được sử dụng bởi những người Pháp trước đó, tuy nhiên được đặt cho một vùng đất khác. Năm 1500, những người Pháp đã đặt tên một thuộc địa của mình ở Brazil, nằm phía dưới đường xích đạo, là Nam cực theo tiếng Pháp là “Antartique”.

Châu Á (Asia)

Bắt nguồn từ tiếng Hy Lạp cổ đại “Ἀσία”, do nhà sử học nổi tiếng Herodotus đặt ra vào khoảng năm 440 trước Công nguyên. Tuy nhiên cái tên cổ này có thể đã được sử dụng từ rất lâu trước đó, dùng để chỉ tên của một vùng đất thuộc bờ phía Đông biển Aegean, sau này được gọi là cao nguyên Anatolia (thuộc một phần của Thổ Nhĩ Kỳ hiện nay).

Theo một giả thuyết khá phổ biến khác thì cái tên theo tiếng Hy Lạp cổ “Ἀσία” này có nguồn gốc từ tiếng Phoenician là “Asu”, có nghĩa là “hướng Đông”. Và từ “Asu” trong tiếng Akkad (ngôn ngữ cổ của nền văn minh Lưỡng Hà) lại có nghĩa là “hướng lên, mọc lên”. Trong khi đó châu Á được biết đến như nền văn minh phương Đông và là vùng đất Mặt Trời mọc.

Châu Đại Dương (Australia)

Tên gọi Australia hiện nay có nguồn gốc từ cái tên “Terra Australis” trong tiếng Hy Lạp, có nghĩa là “vùng đất chưa được biết đến ở phía Nam. Tuy nhiên thời đó sự tồn tại của lục địa này mới chỉ là các tin đồn đại, bởi người La Mã chưa có những công nghệ hàng hải để khám phá ra châu lục này, cũng như chưa có các bằng chứng chứng minh sự tồn tại của nó.

Mãi đến khi người châu Âu tìm ra được vùng đất mới này ở phía Nam, cái tên lưu truyền trước đó “Terra Australis” tiếp tục được sử dụng để đặt tên cho vùng đất mới này. Sau đó cái tên này được các nhà thám hiểm châu Âu rút ngắn và gọi thành “Australia”. Cái tên Australia được sử dụng không chính thức trong rất nhiều năm, và mãi tới tận năm 1824 nó mới trở thành tên gọi chính thức của lục địa này.

Châu Âu (Europe)

Tên gọi của châu Âu có rất nhiều nguồn gốc khác nhau mà cho tới tận bây giờ các nhà sử học vẫn chưa thể xác định chính xác đâu mới là nguồn gốc chính. Có giả thuyết cho rằng nó bắt nguồn từ tiếng Phoenician “ereb” có nghĩa là “phía Tây”, so với châu Á là hướng Đông.

Cũng có ý kiến cho rằng Europe bắt nguồn từ tiếng Hy Lạp. Kết hợp giữa hai từ “eurys” có nghĩa là “rộng” và “ops” có nghĩa là “khuôn mặt”, vật chúng ta có Europe nghĩa là “khuôn mặt rộng”.

Theo các dữ liệu sử sách trước đó thì cái tên này cũng chưa từng được sử dụng cho một địa danh nào khác, điều đó cũng khiến các nhà sử học rất khó xác định nguồn gốc của nó.

Châu Mỹ (America)

Nguồn gốc của cái tên Americas thực sự rất thú vị, vì như chúng ta biết người tìm ra châu Mỹ là Columbus, nhưng nó lại được đặt tên theo tên của nhà thám hiểm Amerigo Vespucci.

Giống như Columbus, Vespucci cũng đã đi tới Thế giới mới (chỉ châu Mỹ) vào năm 1499 vào quay lại đó lần nữa vào năm 1502. Tuy nhiên điểm khác biệt là Vespucci biết chính xác đây là châu Mỹ và đã ghi chép rất tỷ mỷ trong nhật ký của mình, ông còn đặt tên châu lục này là New World. Trong khi đó Columbus vẫn nghĩ rằng mình đã tìm ra một đường đi mới tới châu Á mà không hề biết rằng mình đã phát hiện ra một châu lục mới.

Năm 1507, một người vẽ bản đồ ở Đức có tên là Martin Waldseemüller đã bắt tay vào vẽ bản đồ thế giới. Trước khi vẽ bản đồ, Martin Waldseemüller đã đọc rất kỹ cuốn sách của Vespucci. Mọi quốc gia đều được đặt tên theo giống cái, do vậy Martin Waldseemüller đã “nữ hóa” tên của Amerigo thành America. Tấm bản đồ này sau đó được lưu truyền ra toàn châu Âu và Columbus đành ngậm ngùi không thấy có tên mình trên bản đồ do ông không tin rằng mình đã tìm ra được một châu lục mới.

Tham khảo: todayifoundout

[Discovery] Orion – Tàu vũ trụ hứa hẹn đưa con người lên sao Hỏa đã thực hiện thành công thử nghiệm đầu tiên


Tàu vũ trụ thế hệ mới Orion của NASA đã thực hiện thành công chuyến bay thử không người lái đầu tiên và hạ cánh an toàn xuống Thái Bình Dương. Đây là con tàu không gian thế hệ mới được thiết kế để chở con người thực hiện những chuyến hành trình xa hơn trong vũ trụ. Sự kiện lần đầu tiên thử nghiệm thành công tàu Orion đánh dấu một bước ngoặt quan trọng trong sứ mạng tìm cách đưa con người lên sao Hỏa và các hành tinh khác trong tương lai.

Toàn cảnh sự kiện phóng tàu Orion

Orion là tàu không gian dạng con nhộng được thiết kế để thực hiện những chuyến đi dài trong vũ trụ. Hồi 7:05 theo giờ địa phương ngày 5/12 mới đây (tương đương với 19:05 theo giờ Việt Nam), Orion đã chính thức được phóng lên tại căn cứ không quân Mũi Canaveral, bang Florida bởi tên lửa đẩy Delta IV Heavy. Tiếp theo đó, Orion đã 2 vòng quanh Trái Đất ở độ cao 5800 km, cao nhất đối với 1 phương tiện chế tạo bởi con người chế tạo từ trước đến nay kể từ sau chương trình Apollo hồi năm 1972. Cuối cùng Orion đã hướng về Trái Đất với vận tốc 20.000 dặm/h (8940 m/s) và chịu nhiệt độ 2200 độ C trước khi bung dù và hạ cánh xuống vùng biển ngoài khơi bán đảo Baja Mexico, Thái Bình Dương.

orion-launch-streak-spectators.Tên lửa đẩy Delta IV Heavy đã mang theo tàu vũ trụ Orion và được phóng lên từ căn cứ không quân Mũi Canaveral, bang Florida.

Từ những năm 1970, NASA đã bắt đầu phát triển tàu không gian Orion nhằm đưa con người lên Mặt Trăng và trong các thập kỷ sau đó, nó sẽ được hoàn thiện để đưa con người tới những hành tinh khác mà cụ thể là sao Hỏa vào năm 2030. Orion được phát triển bởi hãng Lockheed Martin theo đơn đặt hàng của NASA và được đặt tên theo chòm sao lớn nhất trên bầu trời đêm. Giám đốc chương trình Orion Mark Geyer chia sẻ: “Thật tuyệt vời. Bạn có những ý tưởng mà bạn muốn làm, bạn lập nên 1 nhóm để cùng thực hiện và giờ đây, mọi thứ đã hoạt động như dự định của bạn. Chúng tôi vẫn còn một chặng đường dài phía trước với sứ mạng này nhưng ngay khi khởi đầu, mọi thứ đã thật suông sẻ.”

Video mô phỏng hoạt động trên quỹ đạo của tàu Orion

Orion là thế hệ tàu vũ trụ được trang bị các công nghệ tối tân nhất hiện nay của NASA và đây cũng là lần đầu tiên, nhiều công nghệ mới được thử nghiệm. Orion mang theo công nghệ truyền dữ liệu mạng với tốc độ nhanh gấp 1000 lần so với hệ thống trên trạm không gian quốc tế ISS hiện nay. Đồng thời, một hệ thống launch-abort cũng được trang bị để tăng độ an toàn cho phi hành đoàn 4 người trong quá trình phóng. Sau lần thử thành công đầu tiên, theo kế hoạch Orion sẽ được bay thử lần thứ 2 vào năm 2018 tại độ cao 700.000 km trên quỹ đạo của Mặt Trăng.

Tham khảo Bloomberg, Space

[Infographic] Vì sao ngồi và đứng lâu không tốt cho sức khoẻ

Hiện nay, nhiều nghiên cứu đã chỉ ra rằng việc ngồi hay đứng một tư thế trong thời gian dài sẽ làm tăng nguy cơ mắc bệnh cho con người. Bản thân việc đứng hay ngồi đều không có hại, chỉ khi chúng ta ngồi lâu hay đứng lâu mới tác động xấu đến sức khoẻ. Vậy những tác động đó là gì và làm sao để khắc phục được những nguy cơ gây bệnh này? Hãy cùng tìm hiểu qua Infographic dưới đây.

[Submit] vi sao ngoi va dung lau khong tot cho suc khoe.

[Discovery] Thuốc lá khiến lượng nhiễm sắc thể Y trong DNA của nam giới suy giảm


Một nghiên cứu vừa được công bố trên tạp chí Nature đã chỉ ra rằng nam giới nghiện thuốc có tỷ lệ mắc độ biến tế bào dẫn đến mất các nhiễm sắc thể Y trong máu của họ. Nói cách khác, thuốc lá chẳng những khiến tuổi thọ của bạn ngắn đi mà còn khiến nam giới mất đi nhiễm sắc thể Y – “nhiễm sắc thể chuẩn men của đàn ông”

Đồng tác giả của nghiên cứu, Lars Forsberg, nhà di truyền học tại Đại học Uppsala cho biết: “Nam giới hút thuốc sẽ có nguy cơ mất các nhiễm sắc thể Y cao hơn so với người bình thường. Đây là một dạng đột biến phổ biến nhất ở con người và nó có liên quan trực tiếp tới các bệnh ung thư.” Trước đây, các nhà nghiên cứu vẫn chưa hiểu rõ mối liên hệ trực tiếp giữa thuốc lá với các căn bệnh ung thư mà đặc biệt là ung thư phổi. Do đó, phát hiện trên đây vẫn còn khá sơ khai nhưng giờ đây, chúng ta đã biết rõ ràng rằng những người đàn ông nghiện thuốc có tần suất mất nhiễm sắc thể Y tăng cao.

Ở khía cạnh sinh học, chúng ta đã biết động vật có vú thường sỡ hữu cặp nhiễm sắc thể quy định giới tính là X và Y, chứa nhiều gen rất quan trọng. Hầu hết đàn ông đều có nhiễm sắc thể X và Y trong khi phụ nữ thì có 2 nhiễm sắc thể X, trừ một số ít ngoại lệ. Trong nghiên cứu, người ta đã kêu gọi 6000 tình nguyện viên là nam giới có độ tuổi trên 48, chia thành 3 nhóm nghiên cứu độc lập và phân tích DNA trong tế bào máu của họ. Kết quả cho thấy những người nghiện thuốc của tỷ lệ mất nhiễm sắc thể Y cao hơn so với người không hút.

Theo các nhà nghiên cứu, mức độ mất nhiễm sắc thể Y còn phụ thuộc vào người nam đó nghiện nặng hay không. Điều đó có nghĩa là càng hút nhiều thì tỷ lệ mất Y càng cao. Đồng thời, việc mất nhiễm sắc thể Y trong quá trình phân bào chỉ xảy đến đối với những người đang hút thuốc. Khi khảo sát những người đã ngừng hút, các nhà nghiên cứu không thấy sự khác biệt giữa DNA của họ đối với người bình thường. Một cách lạc quan, có thể giả thuyết rằng hiệu ứng mất nhiễm sắc thể Y có thể đảo ngược và nếu ngừng hút, bạn sẽ bình thường trở lại. Tuy nhiên, vẫn có một giả thuyết kém lạc quan hơn là có thể, vì một lý do nào đó những người ngừng hút, và trước đó đã bị mất nhiễm sắc thể Y, lại chết sớm hơn những người còn lại trong nghiên cứu. Nếu trường hợp này xảy ra thì có thể hiệu ứng đảo ngược này không xảy ra.

Daniel Bellot, nhà di truyền học tại MIT tỏ ra hết sức ngạc nhiên và hấp dẫn trước kết quả nghiên cứu trên dù không trực tiếp tham gia nghiên cứu. Ông cho biết, trước đây mối liên hệ giữa thuốc lá và ung thư thường được quy cho các loại chất trong khói thuốc, vốn làm tổn hại DNA và gây lỗi trong quá trình sao chép. Ngoài ra, việc mất nhiễm sắc thể Y cũng thường được biểu hiện trong giai đoạn cuối của bệnh ung thư. Tuy nhiên, kết hợp các hiểu biết trước đây với nghiên cứu mới, Bellot cho biết: “Trước đây chúng ta đã biết thuốc lá gây ra lỗi trong quá trình phân bào và dẫn tới ung thư. Giờ đây, chúng ta biết thêm một cơ chế gây ung thư thứ 2 là thuốc lá gây ra thừa hoặc thiếu nhiễm sắc thể. Và điều này còn đáng sợ hơn khi mà hàng nghìn gen sẽ bị ảnh hưởng cùng lúc.”

Robert Nenezra, nhà tế sinh học tế bào tại Trung tâm nghiên cứu ung thư Memorial Sloan Kettering cho biết “Đây là một nghiên cứu quan trọng”. Tuy nhiên, ông cho rằng cần phải có thêm nhiều nghiên cứu nữa để có thể làm rõ mối liên hệ giữa việc mất nhiễm sắc thể Y với các căn bệnh nam khoa. Dưới góc độ chẩn đoán, cần phải xác định chính xác việc mất nhiễm sắc thể Y xảy ra vào lúc trước hay sau khi bị ung thư. Nếu xác định được là việc mất Y xảy ra trước thì nó sẽ được dùng như một biểu hiện để xác định sớm bệnh ung thư ở những người hút thuốc.

Giáo sư Forsberg cũng dự định sẽ tiếp tục phát triển nghiên cứu trong tương lai nhằm xác định chính xác việc mất nhiễm sắc thể Y sẽ xảy ra ở loại tế bào nào và trong giai đoạn nào. Một khi làm được điều đó, các nhà nghiên cứu còn phải giải thích được tại sao các nhiễm sắc thể Y lại làm tăng tỷ lệ ung thứ và giảm tuổi thọ. Tuy nhiên, kết quả ban đầu của nghiên cứu đã làm những người đàn ông nghiện thuốc suy nghĩ lại về thói quen xấu của họ. Forsberg cho biết: “Nếu bạn muốn được khỏe mạnh và còn sống, hãy bỏ hút thuốc ngay trong hôm nay.”

Trả lời về việc mất nhiễm sắc thể Y có thể khiến đàn ông mất đi “bản lĩnh” hay không, giáo sư Forsberg cho biết: “Việc mất nhiễm sắc thể Y trong máu không phải là tác nhân khiến đàn ông mất đi khả năng sinh sản. Nó sẽ không gây ra điều đó.”

Tham khảo: Science

[Discovery] Những công nghệ có khả năng thay thế mật khẩu

Thay_the_pass_word.Mật khẩu đang đến giai đoạn khủng hoảng. Hầu hết mọi người đều chọn mật khẩu quá dễ đoán khiến tài khoản cá nhân bị xâm chiếm hay đánh cấp thông tin. Trong khi đó, mật khẩu tốt thì lại khó nhớ nên khiến chủ nhân vất vả không kém. Ngay cả Fernando Corbató, người phát minh ra mật khẩu máy tính, cũng nghĩ rằng thứ mà ông tạo ra là một cơn ác mộng kinh khủng. Giờ là lúc thích hợp để bắt đầu “giết” mật khẩu và thay thế bằng những công nghệ khác tiện lợi hơn, an toàn hơn. Có nhiều cách người ta có thể tăng tính an ninh trong không gian số, từ những thiết bị đeo lên người có thể lắng nghe nhịp tim cho đến những sản phẩm quét mống mắt y như phim viễn tưởng.

Thiết bị đeo được

Thiết bị đeo được (wearable) hiện đang là một xu hướng mới, mọi người đều nói về nó. Hiện nay là năm 2014 và bạn có thể mang cả một chiếc máy tính mạnh mẽ trên cổ tay mình dưới dạng một chiếc đồng hồ thông minh. Đồng hồ Android Wear là một ví dụ rõ ràng nhất cho việc này. Sang này sau đến lượt Apple tung ra sản phẩm đeo được của mình, và chính vì sự tăng trưởng nhanh chóng của thị trường này mà nhiều công ty bảo mật đã nghĩ đến việc sử dụng wearable như một giải pháp thay thế password. Họ muốn dùng chiếc đồng hồ, hay các vòng tay theo dõi sức khỏe, như là một mã định danh của chính bạn.

Một trong số những thiết kế dạng này đó là Everykey. Mặc dù chưa tồn tại trên thị trường nhưng sản phẩm này sẽ cho phép bạn mở khóa mọi thứ, từ tài khoản Facebook cho đến cánh cửa nhà. Dự án này từng gây quỹ trên trang KickStarter và nhà phát triển cho biết họ “tận dụng cơ chế mã hóa theo chuẩn quân đội” nhằm chứa mật khẩu cho thiết bị của bạn ngay trên chính thiết bị đó, còn password để đăng nhập vào các trang web thì lưu trên máy chủ. Khi cần đăng nhập thì vòng tay sẽ gửi dữ liệu được mã hóa thông qua Bluetooth để cho phép người dùng truy cập.


Google mới đây cũng triển khai ý tưởng sử dụng thiết bị đeo được để bỏ qua công đoạn nhập mật khẩu vào màn hình khóa của điện thoại, tablet Android 5.0. Khi được thiết lập và ghép đôi với một thiết bị Bluetooth an toàn nào đó, có thể là tai nghe, smartwatch hay bất kì thứ gì khác, máy sẽ tự động vô hiệu hóa tạm thời cơ chế khóa. Ý của Google đó là nếu bạn đang ở gần chiếc smartphone của mình thì tại sao lại phải mất công khóa máy làm gì? Chỉ khi nào bạn đi ra xa (hoặc điện thoại bị lấy cắp, bị để quên), lúc đó kết nối Bluetooth bị ngắt thì thiết bị của bạn mới cần phải được bảo vệ.

Việc bỏ qua bước nhập password nghe có vẻ khá tuyệt, vừa an toàn lại vừa tiện lợi nữa. Nhưng nếu bạn đang ngủ thì sao? Chiếc smartphone, tablet của bạn vẫn nằm trong tầm kết nối Bluetooth, và bất kì ai cũng có thể đến cầm chiếc máy của bạn lên nghịch hay xem trộm thông tin trong khi bạn vẫn đang ngủ ngon lành. Tương tự, chiếc vòng Everykey cũng có thể được kích hoạt khi bị mất, nhưng nếu bạn đang ngủ hoặc không để ý thì…


Một giải pháp cho vấn đề này đến từ một công ty khởi nghiệp của Canado. Họ sử dụng các cảm biến để đo lượng điện phát ra khi cơ thể hoạt động, từ đó nhận biết được khi nào người dùng ngủ để đổi sang chế độ bảo mật khác với khi bạn thức. Điếu đó giúp mang wearable tiến gần hơn đến danh hiệu “kẻ tiêu diệt password”.

Cảm biến vân tay

Khi Apple giới thiệu Touch ID vào năm 2013, nó đã gây ra một “làn sóng” tích hợp cảm biến vân tay lên thiết bị di động. Mặc dù iPhone 5s không phải là chiếc smartphone đầu tiên có cảm biến dạng này nhưng chính nhờ tính dễ dùng của nó mà người ta đánh giá cao việc triển khai Touch ID. Hóa ra một công nghệ đã xuất hiện từ rất lâu vẫn có thể thay thế cho password một cách hiệu quả trong bối cảnh ngành mobile đang loay hoay trong việc đơn giản hóa trải nghiệm người dùng.

Giờ đây bạn có thể vào ngay màn hình chính mà không cần nhập từng kí tự mật khẩu (chỉ việc để tay lên cảm biến là xong), mua app cũng không cần nhập mật khẩu như trước (vì đã có vân tay). Đến năm 2014 Apple lại mở cảm biến vân tay ra cho các ứng dụng bên thứ ba xài, từ đó mở rộng tiềm năng của Touch ID ra rất rộng và nó có thể khởi động cả một lĩnh vực kinh doanh bảo mật mới.

Apple_TouchID. ​Nhưng cảm biến vân tay không phải là không có điểm yếu. Đồng ý rằng việc giả vân tay thì khó hơn việc dụ cho người dùng “khai” ra password nhưng điều đáng nói là vân tay của bạn lại có ở khắp mọi nơi. Trên bàn, trên ghế, trên ly, tách, chén dĩa, trên xe… MỌI NƠI! Việc loại bỏ nguy cơ bị lấy dấu vân tay là rất khó bởi không lẽ lúc nào đi ra đường cũng phải mang găn tay hay sao? Tất nhiên có nhiều yếu tố khác quyết định đến sự thành công trong vừa đánh lừa đầu đọc vân tay, nhưng việc vân tay dễ bị lộ cũng đã tương đối nguy hiểm rồi. Đó là chưa kể đến việc ngón tay bị ướt thì độ chính xác giảm đi. Nếu công ty bạn có xài đầu đọc vân tay để điểm danh và mở đóng cửa thì bạn sẽ biết được những khi quét mà máy không nhận thì bực bội đến dường nào.

Ngay cả Touch ID cũng có những vấn để của riêng mình. Lúc mới ra mắt, nhiều người gặp khó khăn khi chưa làm quen với cảm biến này. Kế tiếp, một hội có tên Chaos Computer Club đã có thể vượt qua Touch ID bằng tấm ảnh chụp dấu vân tay của người dùng để lại trên một tấm kính. Nhiều hacker cũng từng trình diễn việc đánh lừa Touch ID bằng nhiều biện pháp khác nhau, trong đó có cả việc tạo ra một bản mẫu vân tay từ chất liệu dẻo.

Thế nhưng, việc nói cảm biến tay không mang lại những lợi ích so với password thì cũng không đúng. Thứ mà cảm biến vân tay nói chung và Touch ID đem đến cho người dùng chính là sự tiện lợi. Chỉ việc chậm hoặc quét ngón tay một cái là xong, bạn đã có quyền truy cập máy rồi. Mọi thứ chỉ diễn ra trong 1, 2 giây ngắn ngủi thay vì cả chục giây nhập password. Bạn cũng chẳng cần nhớ tài khoản nào thì có mật khẩu nào. Cũng chính vì lý do này mà rất nhiều công ty PC mới tích hợp đầu đọc vân tay lên laptop của họ đấy thôi. Như lời IBM nói khi chiếc laptop có cảm biến vân tay đầu tiên của hãng ra mắt thì “thứ từng được xem là chỉ có trong phim khoa học viễn tưởng giờ đã hiện diện cho mọi doanh nghiệp, lớn và nhỏ, trong một mẫu laptop dùng thường ngày”.


Giống như thiết bị đeo được, cảm biến vân tay vẫn hi sinh ít nhiều tính bảo mật để có được sự tiện lợi. Có thể nó tiện hơn, thậm chí là an toàn hơn password, nhưng chỉ nhiêu đó thôi thì e là vẫn không đủ.

Nhận dạng khuôn mặt

Nếu như vân tay cảm biến vân tay đã trở nên tốt hơn trong những năm gần đây thì công nghệ nhận dạng gương mặt còn đi được một bước dài hơn. Ý tưởng sử dụng máy tính để nhận dạng gương mặt đã có từ những năm 1960 rồi, nhưng trong thời gian gần đây kĩ thuật này đã đạt đến một đỉnh cao mới với độ chính xác được tăng cao, tốc độ nhanh hơn và thuật toán cũng tốt hơn. Laptop có trang bị tính năng mở khóa bằng gương mặt chẳng phải là mới, Android cũng đã có chức năng tương tự từ 3 năm trước. Facebook thậm chí còn phát triển một công cụ nhận dạng khuôn mặt dùng trong nội bộ nhằm “đánh giá hiệu năng ở cấp độ con người”. Nghe thật là tuyệt.

​Chưa hết, Facebook còn sử dụng việc nhận dạng khuôn mặt để tự động tag bạn vào hình ảnh sau khi upload lên mạng xã hội này. Đã bao lần bạn hết sức ngạc nhiên vì Facebook có thể đánh tag chính xác rất nhiều người có mặt trong ảnh mà bạn không cần phải làm gì cả? Ngoài ra, nhiều trạm xăng cũng dùng công nghệ này để quảng cáo, và sử dụng bởi cảnh sát để bắt tội phạm. Hệ thống của FBI với tên gọi Next Generation Identification (NGI, thế hệ định dạng kế tiếp) có thể tạo ra một cơ sở dữ liệu lên đến 52 triệu gương mặt và giúp lực lượng hành pháp giải quyết nhiều vấn đề. Hệ thống này cũng ngốn đến 1 tỉ USD để xây dựng.

Vậy nên, nếu FBI sử dụng nhận dạng gương mặt thì chắc hẳn nó đủ an toàn để thay thế cho mật khẩu nhỉ? Thật ra là không. Cũng như mọi công nghệ khác, việc nhận dạng gương mặt cũng còn tùy thuộc nhiều vào chất lượng của phần mềm. Chỉ một camera độ phân giải cao không thì vẫn chưa thấm vào đâu, quan trọng là phải có phần mềm tốt để xử lý và nhận dạng, kết hợp với đó còn là một cơ sở dữ liệu được bảo mật cao nhưng vẫn phải đảm bảo thời gian truy xuất ngắn.

Nhan_dien_guong_mat. ​Facebook có viết một giải thuận để xác định xem hai tấm ảnh chụp hai gương mặt có phải xuất phát cùng một người hay không, và độ chính xác của nó hiện đang là 97,25% (của con người là 97,5%). Nhưng không phải tính năng nhận dạng gương mặt nào cũng chính xác đến thế. Hệ thống của FBI chấp nhận sai số cao hơn, lên tới 20% (họ đang cố gắng cải tiến nó để tăng độ chính xác lên thành 85% trong tương lai). Hay nói cách khác, độ tin cậy của hệ thống nhận biết gương mặt vẫn còn ở khoảng cách rất xa so với việc sử dụng vân tay để xác định danh tính của một cá nhân.

Quét mống mắt

Đây cũng là một công nghệ thú vị có khả năng thay thế mật khẩu, và nghe cũng khá giống các bộ phim viễn tưởng. Bạn chỉ việc đưa mắt của mình lại gần camera, máy sẽ quét một cái và mở khóa cho bạn. Hoặc để mở cửa, bạn chỉ cần đưa mắt lại gần bộ quét là xong, không phải nhập một loạt mã như nhiều công ty hiện đang sử dụng. Những công nghệ đủ tốt thậm chí còn chẳng yêu cầu bạn phải dí mắt vào một cái máy quét nào cả.

cau-tao-mat-56e98. ​Cơ chế của máy quét mống mắt như sau: máy sẽ sử dụng camera với một lượng hồng ngoại vừa đủ để ghi lại cấu trúc của mống mắt (thường gọi là “tròng đen của mắt”, là phần làm cho mắt có màu nâu hay màu xanh tùy theo chủng tộc. Mống mắt có thể co giãn để cho đồng tử điều chỉnh lượng ánh sáng thích hợp để vào mắt. Mống mắt không phải là võng mạc, và mỗi người sẽ có cấu trúc riêng không ai lẫn với ai, cũng như vân tay vậy.). Cấu trúc này sau đó sẽ được phân tích bằng các thuật toán toán học và thống kê để chuyển đổi thành một lượng dữ liệu số nào đó.


Kế tiếp, một bộ nguồn riêng sẽ thực hiện việc so sánh bằng cách đối chiếu dữ liệu nói trên với những mẫu cấu trúc đã lưu sẵn trong cơ sở dữ liệu. Tốc độ đối chiếu có thể đạt đến cả trăm nghìn hoặc thậm chí là cả triệu mẫu trong một giây với một CPU đơn nhân. Nếu dữ liệu quét khớp với một cấu trúc mống mắt của ai đó thì hệ thống sẽ trả về thông tin định danh của họ. Hiện nay hệ thống mống mắt đã được áp dụng nhiều nơi với mục đích hải quan, đóng mở cửa công ty, phòng thí nghiệm. Độ chính xác của việc quét mống mắt là rất ấn tượng, và nó có thể được kết hợp một giải pháp định danh khác như nhận dạng gương mặt để tăng tính bảo mật.

Một lợi thế chính của công nghệ này, bên cạnh tốc độ và độ chính xác cao, đó là việc mống mắt là thứ mà người ta luôn “mang” theo bên người. Chúng cũng luôn được bảo vệ bởi các cơ chế sinh học nhưng vẫn dễ dàng phơi bày ra bên ngoài để quét. Nếu bạn đeo vòng đeo tay thì vẫn có khả năng bạn bỏ quên nó ở nhà, vân tay thì có thể bị lưu lại khắp mọi nơi, nhận dạng khuôn mặt thì kém chính xác ở thời điểm hiện tại và vẫn dễ bị làm giả hơn so với cấu trúc mống mắt.

Các thiết bị quét mống mắt hiện nay cũng đang dần trở nên rẻ hơn. Có một thiết bị đang bán trên thị trường hiện nay mang tên Myris. Sản phẩm giá 280$ này nhìn như một con chuột máy tính, tuy nhiên khi bạn lật nó lên thì mặt dưới máy có các camera và cảm biến để quét. Việc bạn nhìn vào Myris cũng giống như nhìn vào một tấm gương, và mọi chuyện chỉ có thế thôi, không có gì phức tạp.

Myris kết nối với máy tính bằng cổng USB và nó sẽ phục vụ cho việc đăng nhập các ứng dụng hay website mà bạn chỉ định. Từ tài khoản ngân hàng, tài khoản Facebook cho đến các trang web công ty, hầu như mọi thứ đều có thể được xài với Myris. Song song đó, dữ liệu sinh học của người dùng sẽ được mã hóa tối đa và lưu trên chính thiết bị này nên không lo ngại việc hacker có thể trộm nó từ xa.

Thực chất thì Myris cũng cần dựa vào password, có điều những password đó sẽ được liên kết với mống mắt của bạn để bỏ qua công đoạn nhập liệu truyền thống. Nhưng hãy nghĩ đến tương lai xa hơn, khi mà các trang web, các dịch vụ trên mạng đã bắt đầu sử dụng mống mắt để đăng nhập thì lúc đó những thiết bị như Myris sẽ phát huy hết tác dụng.


Và mọi chuyện không chỉ dừng lại ở việc Myris là một thiết bị rời bên ngoài. Hồi tháng 11 năm nay Myris đã bắt tay với Wistron NeWeb Corporation (WNC), một nhà sản xuất máy tính Đài Loan chịu trách nhiệm gia công PC cho Acer, HP, để tích hợp công nghệ quét mống mắt lên laptop. Sớm nhất là vào năm sau chúng ta sẽ thấy các cảm biến cần thiết được tích hợp thẳng vào máy tính. Khi đó, thay vì phải cầm Myris lên mỗi khi cần đăng nhập, giờ đây bạn chỉ việc liếc qua webcam một cái là xong.

Có vẻ như tương lai của cơ chế quét mống mắt trong việc thay thế password là cực kì tươi sáng. Tuy nhiên, mọi thứ không chỉ phụ thuộc vào công nghệ. Nó còn phụ thuộc vào cách quảng bá của các hãng phần cứng, phần mềm, cách triển khai của các trang web, ứng dụng và phần mềm, cách người tiêu dùng tiếp nhận nó sau một thời gian dài đã quá quen thuộc với mật khẩu dạng kí tự truyền thống. Biết đâu vân tay lại trở thành ông vua, hay kĩ thuật nhận dạng khuôn mặt sẽ giết chết mật khẩu thì sao? Chúng ta hãy cùng chờ xem.

Tham khảo: Gizmodo, M2Sys, Mashable

[Infographic] Mark Zuckerberg đã khởi nghiệp như thế nào – Cuộc đời nhà sáng lập Facebook

Cựu sinh viên Đại học Havard – Mark Zuckerberg đã tự mình làm nên một đế chế và trở thành tỷ phú trẻ nhất hiện nay trên thế giới. Khởi nghiệp thành công với mạng xã hội Facebook, Mark Zuckerberg là một trong những tên tuổi có ảnh hưởng nhất trên mạng trực tuyến và kết nối xã hội. Hãy cùng tìm hiểu về cuộc đời và sự nghiệp của anh qua Infographic dưới đây.

[Submit] Mark Zuckerberg da khoi nghiep nhu the nao.